Теория и практика параллельных вычислений

         

Выбор топологии сети


Топология сети передачи данных определяется структурой линий коммутации между процессорами вычислительной системы. В системе ПараЛаб обеспечивается поддержка следующих типовых топологий:

  • полный граф (completely-connected graph или clique) – система, в которой между любой парой процессоров существует прямая линия связи; как результат, данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров;
  • линейка (linear array или farm) – система, в которой каждый процессор имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);
  • кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки;
  • решетка (mesh) – система, в которой граф линий связи образует прямоугольную двумерную сетку; подобная топология может быть достаточно просто реализована и, кроме того, может эффективно использоваться при параллельном выполнении многих численных алгоритмов (например, при реализации методов блочного умножения матриц);
  • гиперкуб (hypercube) – данная топология представляет частный случай структуры N-мерной решетки, когда по каждой размерности сетки имеется только два процессора (т.е. гиперкуб содержит 2N

    процессоров при размерности N); данный вариант организации сети передачи данных достаточно широко распространен на практике и характеризуется следующим рядом отличительных признаков:

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



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий