Параллельные архитектуры

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

Слабо и сильно связанные машины

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

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

Взаимодействие процессоров

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

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

Полносвязная и линейная конфигурации сети

Рис. 9.1. Полносвязная и линейная конфигурации сети

Кольцевая конфигурация сети

Рис. 9.2. Кольцевая конфигурация сети

Решетчатая сеть

Рис. 9.3. Решетчатая сеть

Скажем, в линейной сети на рис. 9.1 сообщение из узла 1 в узел 5 должно пройти через три промежуточных узла, а в кольцевой сети на рис. 9.2

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

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

Принципы анализа параллельных алгоритмов

При работе с параллельными алгоритмами нас будут интересовать два новых понятия: коэффициент ускорения и стоимость. Коэффициент ускорения параллельного алгоритма показывает, насколько он работает быстрее оптимального последовательного алгоритма. Так оптимальный алгоритм сортировки требует 0(N log N) операций. У параллельного алгоритма сортировки со сложностью 0(N) коэффициент ускорения составил бы <9(log N).

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

Близким понятием является расщепляемость задачи. Если единственная возможность для нашего алгоритма параллельной сортировки состоит в том, что число процессоров должно равняться числу входных записей, то такой алгоритм становится бесполезным, как только число входных записей оказывается достаточно большим. Никаких похожих ограничений в алгоритме последовательной сортировки нет. По большей части нас будут интересовать такие алгоритмы параллельной сортировки, в которых число процессоров значительно меньше потенциального объема входных данных и это число не требует увеличения при росте длины входа.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >