Новосибирский государственный университетФакультет информационных технологий |
А.М.Федотов |
Решетка (mesh) - топология, в которой граф линий связи образует прямоугольную сетку (обычно двух- или трехмерную). Подобная топология может быть достаточно просто реализована и, кроме того, эффективно использована при параллельном выполнении многих численных алгоритмов (например, при реализации методов анализа математических моделей, описываемых дифференциальными уравнениями в частных производных).
Поскольку значительная часть научно-
технических задач связана с обработкой
массивов, вполне естественным
представляется стремление учесть эту
специфику в топологии ВС,
ориентированных на подобные задачи.
Такие топологии относят к
решетчатым, а их конфигурация определяется видом и размерностью массива.
Простейшими примерами для одномерных массивов могут служить цепочка и кольцо. Для двумерных
массивов данных наиболее подходит
топология плоской прямоугольной матрицы
узлов, каждый из которых соединен с
ближайшим соседом. Такая сеть
размерности n×n (n
= √N) имеет следующие
характеристики: D =
2(n-1); d = 2 для угловых
узлов, d = 2 для краевых узлов и
d = 4 для остальных узлов;
I = 2(N-n);
В = n.
Возможны и иные
формы плоской двухмерной решетчатой
топологии.
Двухмерные решетчатые
топологии встречаются в ВС класса SIMD и транспьютерных ВС. Они были использованы в системах Intel Paragon и Intel Touchstone Delta.
Если провести операцию свертывания (wraparound) плоской матрицы, соединив
информационными трактами одноименные
узлы левого и правого столбцов или
одноименные узлы верхней и нижней строк
плоской матрицы, так чтобы столбцы
(строки) образовывали кольцо, то из
плоской конструкции получается топологию типа цилиндра. В топологии цилиндра каждый ряд (или столбец) матрицы представляет собой кольцо. Если
одновременно произвести свертывание
плоской матрицы в обоих направлениях,
получается тороидальная топология сети.
Двухмерный тор на базе решетки
n×n обладает следующими
параметрами: D =
2min[n/2]; d = 4; I = 2N; B = 2n. Сеть с топологией тора используется в системах AP3000 компании Fujitsu.
Помимо свертывания к плоской решетке может быть применена операция скручивания (twisting). Суть этой операции состоит в том, что все узлы объединяются в разомкнутую или замкнутую спираль, то есть узлы, расположенные с противоположных краев плоской решетки, соединяются с некоторым сдвигом. Это приводит к топологиям витого цилиндра и витого тора. Если горизонтальные петли объединены в виде спирали, образуется так называемая сеть
типа ILLIАС. Подобная конфигурация сети
соответствует хордальной сети четвертого порядка и характеризуется следующими значениями: D = n-1; d = 4; I = 2N; B = 2n. Если же столбцы узлов также объединены в виде спирали, получается топология витого тора.
Следует упомянуть и трехмерные сети. Один из вариантов, реализованный в архитектуре суперЭВМ Cray T3D, представляет собой трехмерный тор, образованный объединением процессоров в кольца по трем координатам: х, у и z.
Примерами ВС, где реализованы различные варианты
решетчатых топологий, могут служить:
ILLIAC IV, МРР, DAP, CM-2, Paragon и др.
Основная:
Ключевые термины (головные): Статическая топология; Размер сети; Число связей; Диаметр сети; Степень узла; Пропускная способность сети; Задержка сети; Связность сети; Ширина бисекции сети; Полоса бисекции сети;
Федотов Анатолий Михайлович |
НГУ ФИТ НГУ ИВТ СО РАН |