Теория и практика параллельных вычислений
Методы логического представления топологии коммуникационной среды
Как показало рассмотрение основных коммуникационных операций в подразделе 3.1, ряд алгоритмов передачи данных допускает более простое изложение при использовании вполне определенных топологий сети межпроцессорных соединений. Кроме того, многие методы коммуникации могут быть получены при помощи того или иного логического представления исследуемой топологии. Как результат, важным моментом при организации параллельных вычислений является возможность логического представления разнообразных топологий на основе конкретных (физических) межпроцессорных структур.
Способы логического представления (отображения) топологий характеризуются следующими тремя основными характеристиками:
- уплотнение дуг (congestion), выражаемое как максимальное количество дуг логической топологии, которые отображаются в одну линию передачи физической топологии;
- удлинение дуг (dilation), определяемое как путь максимальной длины физической топологии, на который отображается дуга логической топологии;
- увеличение вершин (expansion), вычисляемое как отношение количества вершин в логической и физической топологиях.
Для рассматриваемых в рамках пособия топологий ограничимся изложением вопросов отображения топологий кольца и решетки на гиперкуб. Предлагаемые ниже подходы для логического представления топологий характеризуются единичными показателями уплотнения и удлинения дуг.
