Классификация систем параллельной обработки

Процесс решения задачи можно представить как воздействие определенной последовательности команд программы (потока команд) на соответствующую последовательность данных (поток данных), вызываемых этой последовательностью команд. Различные способы организации параллельной обработки информации можно представить как способы организации одновременного воздействия одного или нескольких потоков команд на один или несколько потоков данных.

Для такой классификации оказывается полезным ввести понятие множественности потоков команд и данных. Под множественным потоком команд или данных будем понимать наличие в системе нескольких последовательностей команд, находящихся в стадии реализации, или нескольких последовательностей данных, подвергающихся обработке командами.

Исходя из возможности существования одиночных и множественных потоков все системы могут быть разбиты на четыре больших класса.

1. Системы с одиночным потоком команд и одиночным потоком данных (ОКОД).

2. Системы с множественным потоком команд и одиночным потоком данных (МКОД).

3. Системы с одиночным потоком команд и множественным потоком данных (ОКМД).

4. Системы с множественным потоком команд и множественным потоком данных (МКМД).

Рис. 1. Системы ОКОД (а), МКОД (б, в), ОКМД (г), МКМД (д)

Д— данные; К— команды; Р— результаты

Возможные способы реализации параллельной обработки информации хорошо укладывается в представленную классификацию, и каждому классу систем присущи вполне определенные способы.

Системы класса ОКОД. Системы этого класса—обычные однопроцессорные ЭВМ (рис. 1, а), включающие в себя запоминающее устройство (ЗУ) для команд и данных (оно чаще всего бывает общим) и один процессор, содержащий арифметико-логическое устройство (АЛУ) и устройство управления (УУ). В современных системах этого класса наиболее широко используется первый путь организации параллельной обработки — совмещение во времени различных этапов решения разных задач, при котором в системе одновременно работают различные устройства: ввода, вывода и собственно обработки информации.

Введение большого числа параллельно работающих периферийных устройств позволяет существенно сократить время на ввод информации в оперативное запоминающее устройство (ОЗУ), уменьшая общее время решения задачи, и до некоторой степени сгладить разрыв между скоростями работы центральных (процессор и ОЗУ) и периферийных устройств. Значительный эффект в производительности однопроцессорной системы дает разделение ОЗУ на несколько модулей, функционально самостоятельных, что позволяет им работать независимо друг от друга. Производительность увеличивается за счет уменьшения простоев устройств из-за так называемых конфликтов при обращении к ОЗУ.

При параллельной работе многих устройств ввода—вывода и процессора неизбежны ситуации, когда нескольким устройствам требуется обращение к ОЗУ для записи или чтения информации. Такая ситуация и называется конфликтной. Естественно, разрешить этот конфликт можно только путем введения системы приоритетов, которая устанавливает определенную очередность удовлетворения запросов в ОЗУ. При этом неизбежны очереди, а следовательно, и простои устройств. При наличии нескольких модулей ОЗУ с независимым управлением есть определенная вероятность того, что различные устройства будут обращаться к различным модулям, а следовательно, очередь к ОЗУ разделится на несколько меньших очередей и время ожидания (т. е. простой устройства) в очереди будет уменьшено. Кроме совмещения во времени различных этапов обработки информации в системах класса ОКОД существенное увеличение производительности достигается за счет введения конвейера команд.

По существу конвейер команд — это также совмещение во времени работы нескольких различных блоков, выполняющих отдельные части общей операции. Если совмещение во времени работы различных устройств можно назвать «макросовмещением», то конвейер является как бы «микросовмещением». При организации конвейера команд часто применяются также способы увеличения производительности, базирующиеся на использовании многомодульных ОЗУ. Во-первых, если программы и данные размещать в разных модулях памяти, то это позволит совмещать во времени выборку команды и операнда, что при выполнении ОЗУ в виде одного функционального устройства было бы невозможно. Во-вторых, используется тот факт, что команды и данные обычно при обработке выбираются из некоторой последовательности ячеек памяти с последовательно возрастающими адресами. Если организовать ОЗУ таким образом, что все четные адреса будут принадлежать одному модулю ОЗУ, а все нечетные — другому, и сдвинуть начало цикла работы этих двух модулей на 1/2 цикла, то при выполнении программы среднее время обращения к ОЗУ существенно уменьшается (в пределе в 2 раза). Этот принцип может быть распространен и на большее число модулей ОЗУ с независимым управлением. При N модулях ОЗУ среднее время обращения к ОЗУ оказывается равным 1/N-й цикла ОЗУ. Такая память называется памятью с чередованием адресов или расслоением обращений.

В системах класса ОКОД возможна реализация и еще одного способа увеличения производительности — конвейер арифметических и логических операций, который вполне вписывается в этот класс систем, так как поток команд остается один: просто команды разбиваются на некоторое число микроопераций, образуя таким образом несколько потоков микрокоманд. По этой причине системы с конвейером арифметических и логических операций скорее относятся к следующему классу - МКОД.

Системы класса МКОД. Структуру систем этого класса можно представить в виде схемы, изображенной на рис. 1, б: несколько потоков команд воздействуют на единственный поток данных. Однако не существует такого класса задач, в которых одна и та же последовательность данных подвергалась бы обработке по нескольким разным программам. По этой причине в чистом виде такая схема до сих пор не реализована.

На практике реализована другая схема обработки, представленная на рис. 1, в. Здесь один поток команд К разделяется устройством управления на несколько потоков микроопераций, каждая из которых реализуется специализированным, настроенным на выполнение именно данной микрооперации, устройством. Поток данных проходит последовательно через все (или часть) этих специализированных АЛУ. Именно такого класса системы принято называть конвейерными. Основу конвейерной обработки составляет раздельное выполнение некоторой операции в несколько этапов (за несколько ступеней) с передачей данных одного этапа следующему. Производительность при этом возрастает благодаря тому, что одновременно на различных ступенях конвейера выполняются несколько операций. Конвейеризация эффективна только тогда, когда загрузка конвейера близка к полной, а скорость подачи новых операндов соответствует максимальной производительности конвейера. Если происходит задержка, то параллельно будет выполняться меньше операций и суммарная производительность снизится. Векторные операции обеспечивают идеальную возможность полной загрузки вычислительного конвейера.

При выполнении векторной команды одна и та же операция применяется ко всем элементам вектора (или чаще всего к соответствующим элементам пары векторов). Для настройки конвейера на выполнение конкретной операции может потребоваться некоторое установочное время, однако затем операнды могут поступать в конвейер с максимальной скоростью, допускаемой возможностями памяти. При этом не возникает пауз ни в связи с выборкой новой команды, ни в связи с определением ветви вычислений при условном переходе. Таким образом, главный принцип вычислений на векторной машине состоит в выполнении некоторой элементарной операции или комбинации из нескольких элементарных операций, которые должны повторно применяться к некоторому блоку данных. Таким операциям в исходной программе соответствуют небольшие компактные циклы.

Разумеется, в системах МКОД с целью достижения высокой производительности используется не только конвейер операций. Обычно в таких системах используется и конвейер команд, и различные способы совмещения работы многих устройств. Однако при этом главным, определяющим признаком является наличие конвейера арифметических и логических операций. Заметим, также, что системы этого класса развивают максимальную производительность только при решении задач определенного типа, в которых существуют длинные последовательности (цепочки) однотипных операций над достаточно большой последовательностью данных, т. е. когда имеет место параллелизм объектов или данных.

Системы класса ОКМД. Системы этого класса также ориентированы на использование параллелизма объектов или данных для повышения производительности. Обобщенная структура представлена на рис. 1,г.

Общая схема, представленная на рис. 1, г, может реализоваться разными способами. Так, например, АЛУ может представлять собой достаточно сложное устройство, содержащее обрабатывающий процессор и оперативное ЗУ. В этом случае поток данных в каждый процессор поступает из собственного ЗУ. Управление и память команд реализуются отдельной ЭВМ, управляющей ансамблем процессоров. Память данных может иметь не только адресную выборку, но и ассоциативную, т. е. по содержимому памяти.

Машины типа SIMD состоят из большого числа идентичных процессорных элементов, имеющих собственную память. Все процессорные элементы в такой машине выполняют одну и ту же программу. Очевидно, что такая машина, составленная из большого числа процессоров, может обеспечить очень высокую производительность только на тех задачах, при решении которых все процессоры могут делать одну и ту же работу. Модель вычислений для машины SIMD очень похожа на модель вычислений для векторного процессора: одиночная операция выполняется над большим блоком данных.

В отличие от ограниченного конвейерного функционирования векторного процессора, матричный процессор (синоним для большинства SIMD-машин) может быть значительно более гибким. Обрабатывающие элементы таких процессоров - это универсальные программируемые ЭВМ, так что задача, решаемая параллельно, может быть достаточно сложной и содержать ветвления. Обычное проявление этой вычислительной модели в исходной программе примерно такое же, как и в случае векторных операций: циклы на элементах массива, в которых значения, вырабатываемые на одной итерации цикла, не используются на другой итерации цикла. Модели вычислений на векторных и матричных ЭВМ настолько схожи, что эти ЭВМ часто обсуждаются как эквивалентные.

В системах класса ОКМД могут использоваться для достижения высокой производительности и другие пути параллельной обработки, однако определяющим является одновременная обработка нескольких потоков несколькими процессорами.

Системы класса МКМД. Возможны два способа построения систем МКМД: в виде совокупности элементарных систем (рис. 1, а) и по схеме, приведенной на рис. 1, д. На первый взгляд разница незначительная: в варианте а для каждой последовательности команд и данных имеется собственное ЗУ, в варианте д все команды и все данные размещаются в общих ЗУ. Это различие приводит однако к двум сильно отличающимся по построению и организации вычислений типам вычислительных систем и комплексов: многомашинным (рис. 1, а) и многопроцессорным (рис. 1,д). В многомашинном варианте вся система как бы распадается на несколько независимых систем класса ОКОД, т. е. по существу самостоятельных ЭВМ со всеми особенностями, присущими им. При этом обычно существуют определенные связи между ЭВМ, объединяющие эти ЭВМ в систему. В многопроцессорном варианте система (комплекс) достаточно жестко связана общей памятью команд и данных и, хотя процессоры системы имеют достаточную самостоятельность, в системе организуется совместная их работа.

Многомашинные системы (комплексы) в наилучшей степени приспособлены для решения потока независимых задач. При этом объединение в систему нескольких ЭВМ существенно увеличивает производительность системы. Многопроцессорные системы (комплексы) являются достаточно универсальными и обеспечивают повышение производительности при использовании всех видов параллелизма, но, пожалуй, наибольший эффект достигается при задачах, характеризующихся параллелизмом независимых ветвей.

Из всех рассмотренных систем наиболее универсальными в отношении класса решаемых задач являются системы МКМД. Их программное обеспечение не ориентируется, как правило, на решение только определенного класса задач.