Стр. 15 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
13
Типовые топологии представлены на рис. 1.2:
• полный граф (completely-connected graph or clique ) - система, в которой
между любой парой процессоров существует прямая линия связи; данная
топология обеспечивает минимальные затраты при передаче данных, одна-
ко является сложно реализуемой при большом количестве процессоров;
• линейка (linear array or farm) - система, в которой каждый процессор име-
ет линии связи только с двумя соседними (с предыдущим и последующим)
процессорам; такая схема является, с одной стороны, просто реализуемой, а
с другой - соответствует структуре передачи данных при решении многих
вычислительных задач (например, при организации конвейерных вычисле-
ний);
• кольцо (ring ) - данная топология получается из линейки процессоров
соединением первого и последнего процессоров линейки;
• звезда (star) - система, в которой все процессоры имеют линии связи с не-
которым управляющим процессором; данная топология является эффек-
тивной, например, при организации централизованных схем параллельных
вычислений;
• решетка (mesh) - система, в которой граф линий связи образует прямо-
угольную сетку (обычно двух- или трехмерную); подобная топология мо-
жет быть достаточно просто реализована и, кроме того, эффективно ис-
пользуема при параллельном выполнении многих численных алгоритмов
(например, при реализации методов анализа математических моделей, опи-
сываемых дифференциальными уравнениями в частных производных);
• гиперкуб (hypercube) - данная топология представляет частный случай
структуры решетки, когда по каждой размерности сетки имеется только два
процессора (т.е. гиперкуб содержит 2N процессоров при размерности N);
данный вариант организации сети передачи данных достаточно широко
распространен в практике и характеризуется следующим рядом отличи-
тельных признаков:
o два процессора имеют соединение, если двоичное представление их
номеров имеет только одну различающуюся позицию;
o в N-мерном гиперкубе каждый процессор связан ровно с N соседями;
o N-мерный гиперкуб может быть разделен на два (N – 1)-мерных
гиперкуба (всего возможно N различных таких разбиений);
o кратчайший путь между двумя любыми процессорами имеет длину,
совпадающую с количеством различающихся битовых значений