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

1.1.2. Архитектура Connection Machine 2 по Скилликорну.Классификация В. Хендлера.Хендлер предложил использовать три критерия, которые представляютразличные уровни процесса выполнения машинных команд.Первый уровень выполнения программы соответствует работе устройствауправления (УУ), которое производит выборку и дешифрацию команд программыи однозначно идентифицирует процессор.Второй уровень выполнения машинных команд. На этом уровне командапоступает в арифметико-логическое устройство (АЛУ), где производится еёвыполнение.33Третий уровень соответствует обработке битовой информации, для этогоэлементарные логические схемы (ЭЛС) процессора делятся на группы,обрабатывающие по одному двоичному разряду. Число групп соответствуетдлине машинного слова (рисунок 1.1.3).Рис.

1.1.3. Схема классификации В. ХендлераАрхитектура описывается с помощью трёх переменных k, d и w,идентифицирующихкаждыйуровень,т.е.длянекоторойпараллельнойархитектуры С описание в классификации будет выглядеть следующим образом:t(C) = (k, d, w).В качестве примера рассмотрим некоторую архитектуру Z состоящую из 5ВУ (процессоров), т.е. 5 УУ, которые производят выборку инструкций. КаждоеУУ имеет в своём распоряжении одно АЛУ. И каждое АЛУ работает с 64-хразрядным словом, т.е. состоит из 64 ЭЛС, обрабатывающих биты.

Нижеприведено её описание в классификации Хендлера:t(Z) = (5, 1, 64).ДалееХендлеррасширяетклассификациювведениемописанияконвейеризации. Предположим, что в вышеописанной архитектуре С, на34последнем уровне присутствует конвейер из w’ ступеней, тогда еслифункциональное устройство обрабатывает w-разрядные слова на каждой из w’ступенейконвейера,топараллелизмданногоуровняхарактеризуетсяпроизведением w x w’. По аналогии для первых двух уровней конвейеризацияописывается при помощи выражений k×k' и d×d'.

Отсюда получим:t( С ) = (k×k',d×d',w×w'),где k – параллельные процессоры;k' - размер макроконвейера у каждого процессора;d – число АЛУ каждого процессора (АЛУ работают параллельно);d' – размер конвейера из устройств АЛУ;w – размер слова, обрабатываемого в АЛУ;w' - число ступеней в конвейере АЛУ.Например, выше рассмотренная архитектура Z имеет на последнем уровнеконвейер из 6 ступеней, тогда в описании к последнему уровню добавим x6,отсюда получим следующее:t(Z) = (5, 1, 64x6).Операция (x) может применяться не только для внутренних описаний, нотакже и для более сложных конструкций. Например, если три архитектуры Zобъединены по принципу конвейера в систему ZZZ, то описание по Хендлерубудет следующим:t(ZZZ) = (5, 1, 64x6)x(5, 1, 64x6)x(5, 1, 64x6).Для описания в сложных параллельно работающих конструкциях Хендлервводит операцию (+) , в том случае, если архитектура ZZZ3 включает трипараллельно работающих ZZZ, её описание выглядит следующим образом:35t(ZZZ3) = (5, 1, 64x6)x(5, 1, 64x6)x(5, 1, 64x6) + (5, 1, 64x6)x(5, 1, 64x6)x(5, 1, 64x6) + (5, 1, 64x6)x(5, 1, 64x6)x(5, 1, 64x6).Для компактности можно переписать описание следующим образом:t(ZZZ3) = [(5, 1, 64x6)x(5, 1, 64x6)x(5, 1, 64x6) + … + (5, 1, 64x6)x(5, 1,64x6)x(5, 1, 64x6)] {3 раз}.Последняя операция – альтернатива (V), предназначена для отображенияразличных режимов работы.

В качестве примера можно привести ВС C.mmp,которая может быть запрограммирована для функционирования в трех разныхрежимах:t(C.mmp) = (16, 1, 16) v (1 х 16, 1,16) v (1, 16, 16). конвейеризациюнаподобиетой,котораяприсутствуетвовсехсовременных персональных компьютерах и обеспечивает на этапе выборку идешифрацию команд; архитектурные возможности параллельного выполнения логических иарифметических операций; отдельные процессорыввода/вывода, работающие независимо ипараллельно с основными процессорами.Классификация В.

Хендлера основана на понятиях параллелизма иконвейеризации, но не включает описание системных коммуникаций, чтоусложняет её применение в области РСОД.Классификация Дункана.Р. Дункан предложил свой вариант классификации, исключив из неёпараллелизм, присутствующий на самом нижнем уровне.Также он предложил не рассматривать следующие типы параллелизма:36В основу своей классификации Дункан закладывает классификациюФлинна, расширив её следующим образом (рисунок 1.1.4).Рис.

1.1.4. Классификация Дункана.Дункан разделяет все множество архитектурных решений на группы, вкоторых процессоры работают синхронно и с независимо друг от другаработающими процессорами, либо архитектуры, в которых заложена та или инаямодификация идеи MIMD. Далее происходит детализация каждого из классов[32].Систолическиемассивами)архитектурыпредставляютсобой(ихчащемножествоназываютпроцессоров,систолическимиобъединенныхрегулярным образом (например, система WARP). Обращение к памяти можетосуществляться только через определенные процессоры на границе массива.Выборка операндов из памяти и передача данных по массиву осуществляется водном и том же темпе.

Направление передачи данных между процессорамификсировано. Каждый процессор за интервал времени выполняет небольшуюинвариантную последовательность действий.Гибридные MIMD/SIMD архитектуры, dataflow, reduction и wavefrontвычислительные системы осуществляют параллельную обработку информации на37основе асинхронного управления, как и MIMD системы. Но они выделены вотдельную группу, поскольку все имеют ряд специфических особенностей,которыми не обладают системы, традиционно относящиеся к MIMD.MIMD/SIMD - типично гибридная архитектура. Она предполагает, что вMIMD системе можно выделить группу процессоров, представляющую собойподсистему, работающую в режиме SIMD (PASM, Non-Von).

Такие системыотличаются относительной гибкостью, поскольку допускают реконфигурацию всоответствии с особенностями решаемой прикладной задачи.Остальные три вида архитектур используют нетрадиционные моделивычислений. Dataflow используют модель, в которой команда может выполнятьсясразу же, как только вычислены необходимые операнды. Таким образом,последовательность выполнения команд определяется зависимостью по данным,которая может быть выражена, например, в форме графа. Данный подходявляется актуальным в РСОД.Модель вычислений, применяемая в reduction машинах, иная и состоит вследующем: команда становится доступной для выполнения тогда и только тогда,когда результат ее работы требуется другой доступной для выполнения команде вкачестве операнда.Wavefront array архитектура объединяет в себе идею систолическойобработки данных и модель вычислений, используемой в dataflow. В даннойархитектуре процессоры объединяются в модули и фиксируются связи, покоторым процессоры могут взаимодействовать друг с другом.

Однако, впротивоположностьсинхроннойработесистолическихмассивов,даннаяархитектура использует асинхронный механизм связи с подтверждением(handshaking), из-за чего "фронт волны" вычислений может менять свою форму помере прохождения по всему множеству ВУ.При замене в данных моделях команд на атомарные процедуры можнозаметить сходство с технологией распараллеливания комплекса ИЗЗ в РСОД.38Как видно, из рассмотренных выше примеров архитектурные решения вобласти проведения параллельных вычислений настолько разнообразны, что дажевозникают проблемы с приведением их к единой классификации.1.2. Анализ топологий распределённых систем обработки данныхВажным компонентом РСОД являются коммуникационные связи междуузлами, которые предназначены для взаимодействия, а также синхронизации ивзаимоисключения параллельных процессов.

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

Топология данного типа привлекательна вплане сокращения временных затрат на передачу данных, однако имеетсущественный недостаток, а именно, сложность реализации при большом числеВУ (рисунок 1.2.1).39Рис. 1.2.1. Полносвязная топологияЛинейка – топология, в которой каждый узел имеет сообщение с двумясоседними,кромепервогоипоследнего.Такаясхемаорганизациикоммуникационной среды является просто реализуемой, а также на неё хорошоложатся алгоритмы задач, применяющих конвейерные вычисления (рисунок1.2.2).Рис. 1.2.2.

Линейная топологияКольцо – данная топология является одним из вариантов линейнойтопологии, в которой, первый и последний узел имеют соединение.Рис. 1.2.3. Топология кольцо40Звезда – топология, в которой один управляющий узел, с которымсоединены все остальные. Данная топология представляет эффективное решениепри организации соответствующих централизованных параллельных схемвычислений (рисунок 1.2.4).Рис. 1.2.4. Топология звездаРешетка – представление РСОД с данной топологией в виде графавыглядит как прямоугольная двух- или трехмерная сетка.

Данная топология имеетдостаточно простую реализацию и может эффективно применяться привыполнении многих параллельных численных алгоритмов (рисунок 1.2.5).Рис. 1.2.5. Топология решётка41Гиперкуб – топология, которая представляет один из вариантов решётки,когда по каждой размерности сетки имеется только два узла (т.е. гиперкубсодержит 2N узлов при размерности N) (рисунок 1.2.6).Рис.

1.2.6. Топология гиперкубТакая организация сети для передачи данных достаточно широкораспространена на практике и имеет ряд отличительных признаков: два узла соединены в том случае, если двоичные представленияидентификаторов различаются только в одной позиции (код Грея); в N-мерном гиперкубе каждый узел имеет связи с N соседними узлами; N-мерный гиперкуб может быть разбит на два N-1-мерных гиперкуба(всего возможно N таких разбиений); самый короткий путь между двумя любыми узлами имеет длину,которая совпадает с количеством отличающихся бит в двоичном представленииидентификаторов узлов (Хэмминга) [33].Решётка-тор–представляетмногомернуюрешётку,имеющуюциклические соединения между ВУ в нескольких измерениях (рисунок 1.2.7).42Рис. 1.2.7.

Топология решетка-торВсе сетевые топологии характеризуются следующими свойствами: диаметр – свойство, определяющее максимальное расстояние междудвумя узлами. Данная характеристика может отображать максимальное время,которое необходимо для осуществления передачи данных между узлами, т.к.время передачи обычно соответствует длине пути; связность – свойство, характеризующее существование различныхмаршрутов передачи данных; ширина бинарного деления – данное свойство, определяется какминимальное количество дуг, которое надо удалить для разделения сети передачиданных на две несвязные области одинакового размера; стоимость–характеристика,котораяопределяетобщеечислокоммуникационных линий в системе.Втаблице1.2.1приведеныхарактеристикипеременная p представляет число узлов в системе [33].основныхтопологий,43Таблица 1.2.1.

Характеристики основных топологийТопологияДиаметрШиринабисекцииСвязностьСтоимостьПолный графЗвездаПолное двоичноедеревоЛинейкаКольцоРешетка N=2Решетка-тор N=2Гиперкуб12p2/41p-11p(p-1)/2p-12log((p+1)/2)11p-1p-1Lp/2J2(Vp-1)2LVp/2Jlog p12Vp2Vpp/21224log pp-1P2(p-Vp)2p(p log p)/2Следует также отметить, что топологии, имеющие сложную реализацию,могут быть построены не на аппаратном уровне, а на основе специализированногопрограммного обеспечения, такие топологии называются виртуальными либопрограммно-реализуемыми.Такойподходприменяетсядляупрощенияразработки ПО.1.3.