Диссертация (Разработка моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети на основе эволюционного подхода), страница 5

Класс SISD – Single Instruction, Single Data (ОКОД – Одиночный потокКоманд, Одиночный поток Данных).26Архитектуры, принадлежащие к данному классу, выполняют один потокинструкций над одним потоком данных – это обычные машины, классическоготипа, исполняющие последовательные программы. Параллелизм в данном классеможет быть реализован с применением конвейеризации.Конвейеризация предполагает разбиение процесса выполнения операциина несколько этапов, например, этап выборки инструкции, этап дешифрации, этапвыборки данных и этап вычисления. При таком подходе после выполнениявыборки инструкции начинается её дешифрация и одновременно с выполнениемпроцесса дешифрации, начинается выборка следующей инструкции и т.д.Несмотря на одновременное выполнение нескольких команд, данный подход ненарушает последовательности их выполнения и соответствия классификации [2].2.

Класс MISD – Multiple Instruction, Single Data (МКОД – Множественныйпоток Команд, Одиночный поток Данных).Архитектуры, принадлежащие к данному классу, на сегодняшний день неимеют конкретных реализаций. Данный класс включён для поддержания полнотыклассификации.Ностоитотметить,чтонекоторыенаучно-техническиелитературные источники относят к данному классу архитектуры конвейерноготипа.3. Класс SIMD – Single Instruction, Multiple Data (ОКМД – Одиночныйпоток Команд, Множественный поток Данных).Архитектуры, которые относятся к данному классу, выполняют однуинструкцию над разными потоками данных. К данному типу архитектуры могутотноситься, например, конвейерные и матричные процессоры. В качествепримера можно привести такие параллельные системы, как ILLIAC IV и Сгау-1.4.

Класс MIMD – Multiple Instruction, Multiple Data (МКМД –Множественный поток Команд, Множественный поток Данных).Данный класс представляют параллельные архитектуры обрабатывающиеразные потоки инструкций над разными потоками данных, т.е. выполняющиеразные участки программы одновременно, при условии, что к программномуалгоритму применимо распараллеливание [2].27С точки зрения классификации Флинна РСОД принадлежат к классуMIMD, т.к. каждый узел выполняет свою часть программы.Различныевидыархитектурмногопроцессорныхсистем,требуютразличных подходов к построению алгоритмов и разработке, выполняющихся наних параллельных программ. Подходы и алгоритмы, применяемые при разработкепрограмм, сильно привязаны к архитектуре многопроцессорной системы, именяются от системы к системе.Абстрагируясь от архитектурных нюансов построения и взяв за основугипотетических представителей, идеально соответствующих классификации,предлагаемой Флинном, можно привести пример, демонстрирующий различияпри разработке программного обеспечения для разных классов.В качествепримера можно привести задачу умножения матриц размерности NxM и MxN вSIMD и MIMD-архитектурах.При решении данной задачи алгоритм для класса SIMD, в общем виде,может быть следующим.

В каждое вычислительное устройство, число которыхможет достигать N, подаются векторы данных, представляющих строки первойматрицы и столбцы второй, либо в зависимости от величины M некоторые ихучастки.Послеосуществлениязагрузкиэлементоввекторовнаднимипараллельно выполняется одну скалярная операция. В этом случае произойдёт Mопераций умножения и на выходе получится M массивов данных, после чего надэтими массивами выполняется N-1 операция сложения.Рассмотрим алгоритм выполнения аналогичной задачи для класса MIMD.Для данного класса характерна декомпозиция исходной задачи на атомарныепроцедуры, которые распределяются между ВУ и обмениваются между собойданными.Пример реализации такого алгоритма приведен в работе [25].

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

В соответствии с введенным расширением, классMIMD подразделяется на: параллельные архитектуры, основанные на слабосвязанных ВУ, т.е. сраспределённой памятью; параллельные архитектуры с сильно-связанными узлами, т.е. с общейпамятью.Вернувшись к рассмотрению классификации Флинна можно заметить, чтопо сравнению с другими классами представители класса MIMD болееуниверсальны в своём применении.КлассификацияMIMD-архитектурныхподходовбылапредложенаангличанином Роджером Хокни.

Данная классификация разделяет класс MIMDна конвейеры, системы с переключателем и сети (рисунок 1.1.1).Подконвейернымиподразумеваютсяархитектуры,вкоторыхвычислительное устройство выполняет поток инструкций в соответствии сконвейерными принципами и работает в режиме разделения времени дляотдельных потоков.Класс «Переключаемые», подразделяется на: MIMD-архитектуры, в которых существует возможность прямогосообщения между любыми ВУ, которая может быть реализуема с помощьюпереключателя. MIMD-архитектуры, в которых прямое сообщение между ВУ возможнотолько с пограничными соседними устройствами, а взаимодействие с остальнымиузлами происходит за счёт специальной системы маршрутизации, через узлыпосредники.29Рис.

1.1.1. Схема классификации Хокни.Далее MIMD-архитектуры с переключателем Роджер Хокни подразделяетна те, в которых вся память распределена среди процессоров как их локальнаяпамять (примером реализации таких архитектурных подходов могут послужитьсистемы PASM и PRINGLE). В данном варианте коммуникации междупроцессорами реализуются с помощью сложного устройства-переключателя.Данный тип машин называется MIMD-машины с распределенной памятью. Еслипамять является разделяемым ресурсом, который доступен всем процессорамчерез переключатель, то такие системы называются системами с общей памятью,представителями данного класса являются такие системы как CRAY X-MP, BBNButterfly и др.Ещё одним критерием классификации является тип переключателясистемы. Переключатели делятся на простые, многокаскадные и работающие наобщей шине.Т.к.

современные системы могут содержать как разделяемую память, так ираспределенную. Хокни вводит подкласс т.н. гибридных MIMD-систем спереключателем.30Класс Сети представляют РСОД, и дальнейшая их классификацияоснована исключительно на топологии. Такие топологии как:звезда;регулярные решетки различной размерности;гиперкубы;сети с иерархической структурой, такой, как деревья, пирамиды, кластеры;сети, изменяющие свою конфигурацию.РСОД, спроектированные на основе различных топологий, можновыделить в группу гибридных сетевых MIMD-архитектур.Такжеобъединяющихстоитразныеотметитьклассы.существованиегибридныхПримером даннойархитектур,разновидностиможетпослужить Connection Machine 2, который имеет топологию гиперкуба, все узлыкоторого являются кластерами полносвязанных процессоров.КлассификацияФенгаподразделяетпараллельныеархитектурывзависимости от параллельно обрабатываемых бит.В 1972 году Т.

Фенг представил новую систему классификации, в еёоснову Фенг положил два критерия: число бит n в машинном слове, которые обрабатываются параллельно привыполнении машинных инструкций; число одновременно обрабатываемых слов m.На основе данных значений все архитектуры характеризуются двумяпараметрами (n, m). Тогда n*m определяет параллельность архитектуры. Даннаяхарактеристика носит название максимальной степени параллелизма:P = m*n.(1.1.1)Значение P характеризует пиковую производительность. Несомненнымдостоинством классификации Фенга можно считать единый аспект, позволяющийпроизводить их сравнительный анализ любых архитектурных подходов, но31структуризацияРСОД,наосноведаннойклассификациивыглядитнецелесообразной.В 1989 году Д.

Скилликорн предложил новый метод классификации,расширяющийклассыФлинна.Скилликорнпредложилввестичетыреабстрактных понятия: IP – интерпретатор команд (может отсутствовать); DP – процессор данных; IM – Instruction Memory, DM — Data Memory — иерархия памяти; (запоминающее устройство, в котором хранятся данные и команды,пересылаемые между процессорами); Переключатели;Переключатели могут быть четырёх типов: переключатель «1-1» связывает два устройства; переключатель «n-n» связывает все устройства одного множестваустройств с соответствующими устройствами другого множества; переключатель«1-n»соединяетодноустройствосовсемиустройствами определённого множества; переключатель «n x n» обеспечивает связь любого устройства изодного множества с каждым устройством из другого множества.На основе вышеизложенных концепций Скилликорн вводит восемьхарактеристик:1. Количество процессоров команд IP.2. Число ЗУ команд IM.3.

Тип переключателя между IP и IM.4. Количество процессоров данных DP.5. Число ЗУ данных DM.6. Тип переключателя между DP и DM.7. Тип переключателя между IP и DP.8. Тип переключателя между DP и DP.32Каждаяархитектураописываетсяспомощьювышеописанныххарактеристик. Пример применения данной классификации приведён в [2]. ВработерассматриваетсяописаниеConnectionMachine2.Втерминахвышеописанных характеристик:(1, 1, 1 - 1, n, n, n - n, 1 - n, n х n).Схема архитектуры Connection Machine 2 приведена на рисунке 1.1.2.Рис.