Неполнодоступные коммутаторы.

 

Полнодоступные коммутаторы разных видов: разделенные, неразделенные, с ветвлением сигналов – при n входах требуют не менее C*n*log(n) коммутационных элементов. При большом количестве коммутируемых вычислительных устройств (и, следовательно, входов коммутатора) полнодоступные коммутаторы требуют больших аппаратных затрат на реализацию. Действительно, на каждое вычислительное устройство при полнодоступной коммутации приходится C*log(n) коммутационных элементов, что с некоторого момента может оказаться дороже самого вычислительного устройства. Поэтому при большом количестве входов используется неполнодоступная коммутация, а при относительно небольшом количестве коммутируемых входов – полнодоступная. 

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

       Неполнодоступную коммутацию можно рассматривать как промежуточную коммуникационную среду между полнодоступными коммутаторами и коммуникационными сетями. Действительно, коммуникационные сети не позволяют реализовывать непосредственно любые задания на коммутацию – и в этом смысле они не являются полнодоступными. С другой стороны, у каждого процессорного элемента для его связей с другими процессорными элементами через сеть есть специальная коммуникационная часть, которую можно рассматривать как коммутационный элемент. Совокупность таких коммутационных элементов всех процессорных элементов образует некоторый неполнодоступный коммутатор (элементы которого распределены по процессорным элементам системы).

 

 

Коммутационные графы и задачи их построения.

 

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

 

       Определение. Ориентированный граф называется коммутационным, если он содержит n выделенных висячих вершин, называемых входами, n других висячих вершин, называемых выходами, для любой подстановки s длины n в данном графе существует множество из n не имеющих общих дуг путей, соединяющих i-ый вход с выходом s_i для всех i=1, 2, …, n соответственно.

 

       Теперь можно рассматривать задачи теории графов:

· проверить, является ли тот или иной граф коммутационным или нет,

· найти коммутационный граф с наименьшим количеством вершин, у которого все вершины, кроме входов и выходов, имеют k входящих дуг и k выходящих,

· найти планарный коммутационный граф с наименьшим количеством вершин, у которого все вершины, кроме входов и выходов, имеют k входящих дуг и k выходящих,

· …

 

Требование неблокируемости тоже может быть сформулировано на языке теории графов.

 

Определение. Ориентированный коммутационный граф называется неблокирующим, если для любой подстановки s длины n для любого множества путей, соединяющих соответствующие этой подстановке входы и выходы, и для любой пары выделенных входов s, r найдутся такие два пути, соединяющие вход s с выходом s_r и вход r с выходом s_s, что попарно не имеют общих дуг следующие n путей: s -> s_r, r -> s_s, i -> s_i, i=1, 2, …, n, i ≠ s, i ≠ r.

 

Иными словами, неблокируемость означает, что можно изменить соединение для любой пары входов и выходов, не меняя других соединений. Из этого вытекает, что для любого подмножества входов и соответствующих им выходов можно изменить соединения, не меняя других соединений.

Аналогично может быть определен коммутационный граф, соответствующий неразделенному коммутатору.

 

       Определение. Неориентированный граф называется коммутационным, если он содержит n выделенных висячих вершин, называемых входами, и для любого разбиения множества входов на пары существует множество из n/2 не имеющих общих ребер путей, соединяющих входы этих пар.

 

 

***

В разделе «Коммутаторы» рассмотрены задачи построения коммутаторов большой размерности из более мелких коммутаторов такого же типа. Такие задачи носят теоретико-графовый характер. Рассмотрены полнодоступные коммутационные схемы, количество элементов которых приближается к нижним оценкам. Нижние оценки количества элементов рассматриваемых полнодоступных коммутаторов равны или пропорциональны величине n*log(n). Приводятся примеры схем, близких к этим оценкам. Иногда часть сложных коммутационных элементов можно заменить более простыми (с меньшим количеством состояний). Но количество таких элементов все равно пропорционально n*log(n). 

Оптимальные неблокирующие полнодоступные разделенные коммутаторы (схемы Клоза) описаны в [ 15 ].

       Неполнодоступные коммутаторы – это устройства, обобщающие коммуникационные сети и полнодоступные коммутаторы. Неполнодоступные коммутаторы мало исследованы. Здесь интересна проблема: определение такого неполнодоступного коммутатора, который оптимален по затратам, но достаточен для решения задач, для которых строится вычислительная система.

 

 

Задачи к разделу «Коммутаторы».

                       

1. Существует ли полнодоступный разделенный коммутатор с 8 входами и 8 выходами, состоящий из 16 элементов, имеющих по 2 входа и 2 выхода?

 

2. Нарисовать и настроить матричный разделенный коммутатор с 8 входами и 8 выходами, состоящий из коммутационных элементов, имеющих по 2 входа и 2 выхода. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

       1 2 3 4 5 6 7 8

       8 4 6 2 5 3 1 7

 

3. Нарисовать и настроить треугольный разделенный коммутатор с 8 входами и 8 выходами, состоящий из коммутационных элементов, имеющих по 2 входа и 2 выхода. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

       1 2 3 4 5 6 7 8

       8 4 6 2 5 3 1 7

 

4. Нарисовать и настроить полнодоступный трехкаскадный разделенный коммутатор с 9 входами и 9 выходами, состоящий из коммутационных элементов, имеющих по 3 входа и 3 выхода. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

       1 2 3 4 5 6 7 8 9

       8 4 6 2 5 3 1 7 9

 

5. Нарисовать и настроить полнодоступный трехкаскадный разделенный коммутатор с 12 входами и 12 выходами, у которого первый и третий каскады состоят из коммутационных элементов, имеющих по 4 входа и 4 выхода, а коммутационные элементы центрального каскада имеют по 3 входа и 3 выхода. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

        1 2 3 4 5 6  7 8 9 10 11 12

       10 3 5 1 7 12 8 9 4 2 11 6

 

6. Нарисовать и настроить полнодоступный треугольный неразделенный коммутатор с 12 (6 по вертикали и 6 по горизонтали) входами. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

         1 2 3 4 5 6 7 8 9 10 11 12

       10 3 2 9 7 12 5 11 4 1  8 6

 

7. Нарисовать и настроить полнодоступный логарифмический двухкаскадный неразделенный коммутатор с 12 входами, у которого первый состоит из коммутационных элементов, имеющих по 8 входов, а коммутационные элементы второго каскада имеют по 6 входов. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

       1 2 3 4 5 6 7 8 9 10 11 12

       10 3 2 9 7 12 5 11 4 1 8 6

 

8. Нарисовать и настроить полнодоступный логарифмический двухкаскадный неразделенный коммутатор с 12 входами, у которого первый состоит из коммутационных элементов, имеющих по 8 входов, а коммутационные элементы второго каскада имеют по 6 входов. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

       1 2 3 4 5 6 7 8 9 10 11 12

       10 3 2 9 7 12 5 11 4 1 8 6

 

9. Нарисовать и настроить полнодоступный логарифмический двухкаскадный неразделенный коммутатор с 16 входами, у которого первый состоит из 4, а второй из 2 коммутационных элементов, имеющих по 8 входов. Соединить в этом коммутаторе входы и выходы в соответствии с подстановкой 

       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

        11 8 9 7 15 12 4 2 3 16 1 6 14 13 5 10

 

 

РАЗМЕЩЕНИЯ И ПЕРЕРАЗМЕЩЕНИЯ ДАННЫХ В ПАРАЛЛЕЛЬНОЙ ПАМЯТИ

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: