Топологии характерные для МВС

Диаметр коммуникационной сети (D)- называется максимальное расстояние между двумя произвольными узлами этой сети. Его надо минимизировать чтобы ускорить работу по пересылке данных между узлами. D<=5!!! Иначе не эффективно.

Сеть с топологий типа «двумерная решетка» (D=2(sqrt(M*N)-1)) может быть достаточно просто реализована и, вместе с тем, эффективно использована при реализации многих численных алгоритмов (например, при интегрировании систем дифференциальных уравнений в частных производных). Из сети с топологией типа «двумерная решетка» может быть получена сеть с топологией сети типа «тор». Для этого достаточно соединить между собой граничные процессоры по «горизонтали» и по «вертикали».

В полносвязной сети (типа "клика") между любой парой процессоров существует непосредственная связь. Полносвязная сеть обеспечивает минимальные время обмена данными между любыми двумя процессорами системы, однако сложно реализуема и имеет высокую стоимость при большом количестве процессоров. Диаметр сети с топологией типа "клика" D=1.

Диаметр сети с топологией типа "бинарное дерево" D=log2(N).

Утолщенное дерево (рис) — топология компьютерной сети, изобретенная Charles E. Leiserson из MIT, является дешевой и эффективной для суперкомпьютеров. (самая эффективная!!!). В отличие от классической топологии дерево, в которой все связи между узлами одинаковы, связи в утолщенном дереве становятся более широкими (толстыми, производительными по пропускной способности) с каждым уровнем по мере приближения к корню дерева. Часто используют удвоение пропускной способности на каждом уровне. Сети с топологией fat tree являются предпочтительными для построения кластерных межсоединений на основе технологии Infiniband.

Сеть с топологией типа "звезда" эффективна, например, при организации централизованных схем параллельных вычислений. Диаметр сети с топологий типа «звезда» D=2.

Диаметр сети с топологией типа "гиперкуб" D=log2N N=2^ p где p – количество измерений гиперкуба. В сети с топологий «гиперкуб» диаметр сети медленно растет с ростом числа процессоров в системе. Заметим, что в p-мерном гиперкубе каждый процессор непосредственно связан ровно с p соседями.

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

Определение. Два процессора непосредственно связаны друг с другом, если двоичное представление их номеров имеет только одну различающуюся позицию;

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

Примеры использования:

On the Tianhe-2, they are using their TH Express-2 interconnect network, which taps a fat tree topology with 13 switches, each with 576 ports at the top level. (Top500 #1)

SuperMUCThe: interconnect is a non-blocking InfiniBand Network with Fat Tree topology. (Top EU)

Другие примеры: Hypercube (SGI Origin2000), 2D torus (Cray X1), 3D torus (Cray T3E and XT3, IBM Blue Gene/L), Crossbar (NEC Earth Simulator),топология двухмерного тора МВС-1000.

Дата добавления: 2015-01-03