Коммутатор

 

Изобретение относится к цифровой вычислительной технике, предназначено для логической обработки массивов / г 2 Лз 77« /75 фиг., информации и является усовершенствов анием изобретения по а.с. № 1120313. Цель изобретения - расширение функциональных возможностей коммутатора за счет выполнения операции формирования единичного вектора. Коммутатор содержит две треугольные матрицы 2, 3, группу элементов ИЛИ 4, группу элементов НЕ 5, ячейки 6 со входа- MI-I 7, 9, 11, 13, 15 и выходами 8, 10, 12, 14, 16. Ячейка коммутатора содержит элементы НЕ, элементы И, элементы ИЛИ. Коммутатор работает в режимах сжатия, расширения, сплетения , перегруппировки и формирования единичного вектора. 2 ил. С S

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51) 4 0 06 F 7/ОО ф *, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ " Q Ф(,) у р

4 /

17г )7) 17(17 (/)на . 1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (61) 1120313 (21) 4032407/24-24 (22) 03.03.86 (46) 30,05.87. Бюл. ¹ 20 (71) Ленинградский электротехнический институт им. В ° И. Ульянова (Ленина) (72) Т, В ° Волченская и В. С. Князьков (53) 681.3(088.8) (56) Авторское свидетельство СССР № 1120313, кл, G 06 F 7/00, 1983 ° (54) КОММУТАТОР (57) Изобретение относится к цифровой вычислительной технике, предназначено для логической обработки массивов информации и является усовершенствованием изобретения по а.с. № 1120313.

Цель изобретения — расширение функциональных возможностей коммутатора за счет выполнения операции формирования единичного вектора. Коммутатор содержит две треугольные матрицы 2, 3, группу элементов ИЛИ 4, группу элементов HE 5, ячейки 6 со входами 7, 9, 11, 13, 15 и выходами 8, 10, 12, 14, 16. Ячейка коммутатора содержит элементы HF., элементы И, элементы ИЛИ. Коммутатор работает в режимах сжатия, расширения, сплетения, перегруппировки и формирования единичного вектора. 2 ил, 1 1314332 2

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

Операция вычисления связности между элементами является одной из основных при решении задач проектирования (компоновка элементов, размешение элементов, трассировка связей), программирования (выделение областей памяти ЭВМ в зависимости от связности данных), а также при решении задач на графах (поиск максимально связанных подмножеств, разбиение на подграфы, вычисление характеристик связности граФа) и др.

На фиг, 1 приведена схема предлагаемого коммутатора; на фиг. 2 — схема ячейки.

Коммутатор 1 (фиг. 1) содеРжит треугольные матрицы 2 и 3, группу элементов ИЛИ 4, группу элементов

HI. 5, ячейки 6 с вторым горизонтальным входом 7 и выходом 8, первым горизонтальным входом 9 и выходом IO, третьим горизонтальным входом Il u выходом 12, первым вертикальным входом 13 и выходом 14, вторым вертикальным входом 15 и выходом 16, выхо

I7 коммутатора, причем в первой треугольной матрице 2, первый 13 и второй 15 вертикальные входы ячейки 6 с координатами (i, j) соединены соответственно с первым 14 и вторым 16 вертикальными выходами ячейки с коор динатами (i 1, j), второй 7, первый

9 горизонтальные входы ячейки с координатами (i, j) соединены соответственно с вторым 8, первым 10 гори— зонтальными входами ячейки с координатами (i, j — 1). Во второй треугольной матрице 3, первый 16 и второй 17 вертикальные входы ячейки 6 с координатами (1с, 1) соединены соответственна с первым 15 и вторым 13 вертикальными выходами ячейки 6 с координатами (k-1, 1), второй 7, первый

9 горизонтальные входы ячейки с координатами (k, 1) соединены соответственно с вторым 8, первым IO горизонтальными входами ячейки с коорf5

50 динатами (К, l-l), (K, i = 1-N; j — 1 1; 1 = 1-К), причем третий горизонтальный вход ll каждой ячейки 6 соединен с вторым входом второго элемента И 21 данной ячейки 6 и ее третьим 12 горизонтальным выходом. Третий ll горизонтальный выход ячейки 6 с координатами (i, j) в первой треугольной матрице 2 соединен с третьим горизонтальным выходом 12 ячейки 6 с координатами (1, 1-1), третий горизонтальный вход 11 ячейки 6 с координатами (К, 1) во второй треугольной матрице 3 соединен с третьим горизонтальным выходом 12 ячейки 6 с координатами (К, 1-1), второй 8 горизонтальный выход последней ячейки 1-й строки первой треугольной матрицы 2 соединен с вторым горизонтальным входом 7 первой ячейки (N-К-1)-й строки второй треугольной матрицы 3, третий горизонтальный выход 12 последней ячейки i-й строки первой треугольной матрицы 2 соединен с тре" тьим горизонтальным входом 9 первой ячейки (N-К)-й строки второй треугольной матрицы 3, третий горизонтальный выход последней ячейки последней строки первой треугольной матрицы 2 соединен с третьим горизонтальным входом 11 первой ячейки последней строки второй треугольной матрицы 3, второй вертикальный выход 16 j-й ячейки последней строки первой треугольной матрицы 2 и второй вертикальный выход 16 (N-1+1)-й ячейки последней строки второй треугольной матрицы 3 подключены соответственно к первому и второму входам

j-ro элемента группы ИЛИ 4, выход которого является выходом 17 коммутатора, первый горизонтальный вход 9 первой ячейки k-й строки второй треугольной матрицы 3 подключен к выходу k-ro элемента группы НЕ 5, вход которого соединен с первым горизонтальным входом 9 первой ячейки (N-K+

1)-й строки первой треугольной матрицы 2.

Ячейка коммутатора (фиг. 2) содержит элементы НЕ 18 и 19, элементы

И 20-22, элементы ИЛИ 23 и 24, элемент И 25, Коммутатор работает следующим образом.

Режим сжатия. Сжатием произвольного вектора f называется операция

x» z/f, где я — управляющий логичес1314332 кий (двоичный) вектор, размерность которого совпадает с размерностью вектора f, Результат операции — вектор х, который содержит те компоненты Й; исходного вектора, которые соответствуют z, = 1. Размерность вектора х совпадает с количеством единиц вектора z.

В треугольной матрице 2 на входы

13 и 15 ячеек 6 с координатами (i 10

j) (1 = j) подаются соответственно константы "1", "0", а на входы 13 и

15 ячеек 6 с координатами (K, 1) (К = 1) треугольной матрицы 3 подаются константы "0". На входы 11 яче- 15 ек 6 крайнего левого столбца треугольной матрицы 2 подаются константы "1", на горизонтальные входы 9 ячеек 6 крайнего левого столбца треугольной матрицы 2 — логические уров 20 ни, соответствующие коду управляющего логического вектора z Входными каналами коммутатора 1 при выполнении операции сжатия являются горизонтальные входы 7 ячеек 6 крайнего левого столбца треугольной матрицы 2> а выходными каналами — верти— кальные выходы 16 ячеек 6 последней строки треугольной матрицы 2.

В крайнем левом столбце ячеек 6 треугольной матрицы 2 нулевой логический уровень образует на вертикальном выходе 14 ячейки 6, на горизонтальный вход 9 которой подан логический уровень. Начиная с указанной ячейки, нулевой логический уровень образуется на вертикальных выходах

14 всех расположенных ниже ячеек 6 рассматриваемого столбца. Таким об- 40 разом, только в единственной ячейке 6 крайне о левого столбца треугольной матрицы 2 имеет место одновременное наличие единичных логических уровней на входах 13 и 9, в ре- 45 зультате чего именно в этой ячейке осуществляется подключение горизонтального входа 7 к вертикальному выходу 16, т,е, реализуется соединительная функция "Разветвление вниз, Следовательно, на выход 16 последней ячейки 6 крайнего левого столбца треугольной матрицы 2 направляются сигналы того горизонтального входного канала 7, которому соответствует первая сверху единица управляющего логического вектора z. На горизонтальном выходе 10 ячейки 6, в которой произошло разветвление, образуется нулевой логический уровень. В результате на горизонтальные входы

9 ячеек 6 смежного правого столбца треугольной матрицы 2 подается копия исходного управляющего логического вектора за исключением его первой единицы. Соединение последующих входных каналов 7 коммутатора 1 с выходными каналами 16 в треугольной матрице 2 осуществляется аналогично „

Таким образом, на выходы 16 нижней границы треугольной матрицы 2 в первом, втором и так далее столбцах направляются сигналы тех входных каналов 7, которым соответствует первая, вторая и так далее единицы исходного кода управляющего логического вектора z, что соответствует операции сжатия °

Очевидно, что треугольная матрица 3 коммутатора 1 не принимает участия в выполнении операции сжатия, Режим формирования единичного вектора. Формированием единичного вектора называется операция x z/f, где z — управляющий логический вектор, размерность которого совпада— ет с размерностью вектора f. Результат операция — вектор х, который содержит только единичные компоненты

f, исходного вектора, которые соответствуют поразрядно z, = 1. Размерность вектора х равна количеству единиц в результирующем векторе при операции пересечения векторов f u z поразрядно, В треугольной матрице 2 на входы

13 и 15 ячеек 6 с координатами (i, j) (i=j) подаются соответственно константы "1" и "0", а на входы 13 и 15 ячеек 6 с координатами (К, 1) (K=1) треугольной матрицы 3 подаются константы "0" ° На входы 11 ячеек

6 крайнего левого столбца треугольной матрицы 2 подаются константы

11 t1

0, на горизонтальные входы 9 ячеек 6 крайнего левого столбца треугольной матрицы 2 — логические уровни, соответствуюшие коду управляющего логического вектора z. Входными каналами коммутатора 1 при выполнении операции формирования единичного вектора являются горизонтальные входы 7 ячеек 6 крайнего левого столбца треугольной матрицы 2, а выходными каналами — вертикальные выходы 16 ячеек 6 последней строки треугольной матрицы 2, l3l4332 гично, 40

В крайнем левом столбце ячеек 6" треугольной матрицы 2 нулевой логический уровень. образуется на вертикальном выходе 14 той ячейки 6, на горизонтальные входы 9 и 7 которой подан единичный логический уровень.

Начиная с указанной ячейки, нулевой логический уровень образуется на вертикальных выходах 14 всех расположенных ниже ячеек 6 рассматриваемого столбца, Таким образом, только в единственной ячейке 6 крайнего левого столбца треугольной матрицы 2 имеет место одновременное наличие единичных логических уровней на входах 13, 9 и 7, Следовательно, на выход 16 последней ячейки 6 крайнего левого столбца треугольной матрицы 2 направляются сигналы того горизонтального входного канала 7, которому соответствует первая сверху единица управляющего логического вектора z разрядно совпадающая с единицей входного вектора f ° На горизонтальном выходе 10 ячейки 6, в которой прои-. зошло разветвление, образуется нулевой логический уровень. В результате на горизонтальные входы 9 ячеек 6 смежного правого столбца треугольной матрицы 2 подается копия исходного управляющего логического вектора, за исключением первой единицы, поразрядно совпавшей с единицей вектора f, Соединение последующих входных каналов 7 коммутатора 1 с выходными каналами 16 в треугольной матрице 2 осуществляется аналоОчевидно, что треугольная матрица 3 коммутатора 1 не принимает участия в выполнении операции формирования единичного вектора, Режим расширения. Расширением произвольного вектора называется операция х — z/f, размерность z не меньше размерности вектора f Результат операции — вектор х, в котором компоненты исходного вектора занимают позиции, соответствующие единицам вектора z. Размерность вектора совпадает с размерностью вектора z, В матрице 2 на горизонтальные входы 11 ячеек 6 крайнего левого столбца подаются константы "1", причем на граничные вертикальные входы 15 ячеек 6 с координатами (i, j) (i = j ) в матрице 2 и на граничные вертикаль5

35 ные входы 13 и 15 ячеек 6 с координатами (k, 1) (k = 1) в матрице 3 подаются константы "0", а на граничные вертикальные входы 13 ячеек 6 с координатами (i, j) (i = j) матрицы 2— логические уровни, соответствующие коду управляющего (расширяющего) логического вектора.

Входными каналами коммутатора 1 при выполнении операции расширения также являются горизонтальные входы

7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами— вертикальные выходы 16 ячеек 6 последней строки треугольной матрицы 2.

При этом i-й компоненте произвольного вектора соответствует горизонтальный вход 7 первой ячейки И-(т1) строки матрицы 2, где ш — размерность произвольного вектора, На (N-m) верхние горизонтальные входы

7 ячеек 6 крайнего левого столбца матрицы 2 подаются константы "0", на нижние горизонтальные m-входы 9 ячеек 6 крайнего левого столбца матрицы 2 — константы "1", а на (Nm) горизонтальные входы 9 — константы "0!Ó °

В тех столбцах треугольной матрицы 2, где управляющий вектор имеет нули, не может быть ячеек 6, в которых произошло бы разветвление вниз и, следовательно, на выходных каналах !6 последних ячеек 6 этих столбцов сохраняются нулевые логические уровни, Столбцы треугольной матрицы 2, которым соответствуют единицы управляющего вектора z ведут себя следующим образом.

В соответствии с управляющим вектором единичные логические уровни поданы на граничные вертикальные входы 13 ячеек 6 3, и так далее столбцов треугольной матрицы 2, тогда поскольку на все нижние горизонтальные входы 9 ячеек 6 крайнего левого столбца поданы константы "1", ситуация одновременного наличия единичных логических уровней на входах

13 N-(m-1) -й ячейке

6 j, -ro столбца, Следовательно, сигналы N †(m-1) — го и так далее входных каналов 7 направлены на вертикальные выходы 16 последних ячеек 6 j -го и ! так далее столбцов матрицы 2, что соответствует операции расширения.

1314332

1О

55

В выполнении данной операции треугольная матрица 3 не принимает участия, Режим сплетения, Сплетением называется операция х(Е, z ф, которая по двум производным векторам f u g логическому вектору г строит вектор такой, что компонента х, принимает значение очередной компоненты f, если z; = О, либо очередной компоненты g, если z„ = 1. Размерность вектора х совпадает с размерностью z и равна сумме размерностей f u g.

При выполнении операции сплетения треугольная матрица 2 работает в режиме расширения вектора g управляющим вектором z а треугольная матрица 3 — в режиме расширения вектора управляющим вектором z при этом в матрице 2 верхние m строки не принимают участия в операции расширения, так как на горизонтальные входы 9 этих строк поданы константы "0", а в матрице 3 — нижние m строки, так как на горизонтальные входы 9 этих строк поданы константы "0". Сигналы, образующие на вертикальных выходах

16 ячеек 6 последней строки матрицы

2 и матрицы 3, одновременно поступают на элементы группы ИЛИ 4, Входными каналами коммутатора 1 при выполнении операции сплетения являются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами — выходы

17 элементов группы ИЛИ 4, Режим перегруппировки, Перегруппировкой произвольного вектора f называется операция x f h z где z логический вектор, размерность кото— рого равна размерности вектора f, Результат операции — произвольный вектор х, который в качестве и первых компонент х содержит те компоJ кенты f„ исходного вектора f кото рые соответствуют г„ =Х(Т j и), а в качестве m следующих компонент х и+ (— те компоненты f; исходного вектора f, которые соответствуют

z,=0 (I f с m), где пи m — соответственно количество единиц и нулей в логическом векторе z, Размерность вектора х совпадает с размерностью z и равна сумме n+m, При выполнении операции перегруппировки матрица 2 р аботает в режиме сжатия вектора f логическим вектором

z, а матрица 3 — в режиме сжатия этого же вектора логическим вектором z, Результирующий вектор второй операции сжатия сцепляется справа с результирующим вектором первой операции сжатия и таким образом, получается результирующий вектор операции перегруппировки °

На горизонтальные входы 9 ячеек 6 крайнего левого столбца матрицы 2 подаются логические уровни, соответствующие коду управляющего логического вектора z, Входными каналами коммутатора 1 при выполнении операции перегруппировки являются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами — выходы 17 элементов группы ИЛИ 4. На горизонтальные входы 9 ячеек 6 крайнего правого столбца матрицы 3 с элементов группы НЕ подаются логические уровни, соответствующие коду вектора z °

Наличие горизонтального входа 11 в каждой ячейке 6 коммутатора 1 позволяет выделять в полных треугольных матрицах 2 и 3 треугольные подматрицы меньших размеров и организовать одновременную и независимую работу подматриц, что значительно расширяет функциональные возможности коммутатора.

Рассмотрим, каким образом с помощью горизонтальных входов ll производится выделение треугольных подматриц в треугольной матрице 2 коммутатора 1.

Пусть на горизонтальный вход ll

i-й ячейки 6 крайнего левого столбца треугольной матрицы 2 подан нулевой логический уровень, а на все другие горизонтальные входы 11 ячеек 6 этого столбца — единичные логические уровни, В этом случае в треугольной матрице 2 выделяются две независимые треугольные подматрицы. Логический вектор, имеющий g нулей,,выделяет в треугольной матрице (д+1) независимых подматриц.

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

Формула и з о б р е т е н и я

Составитель О. Березикова

Техред М.Ходанич Корректор И. Шулла

Редактор 10. Середа

Заказ 2214/49 Тираж 673 Подписное

ВНИИПИ Г осударственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., ц. 4/5

Производственно-полиграфическое прецприятие, r, Ужгород, ул. Проектная, 4

9 ной матрицы 2, соответствует идентичная смежная с ней по диагонали треугольная подматрица из треугольной матрицы 3, т.е ° образуется пара идентичных треугольных подматриц, одна из которых расположена в треугольной матрице 2, а другая — в треугольной матрице 3, Все пары выделенных треугольных подматриц могут работать одновременно и работа лю- 10 бой пары не зависит от работы других пар, что позволяет в каждой из пар треугольных подматриц организовать свой режим работы,. причем работать эти пары будут одновременно, выпол- 15 няя различные операции сплетения и перегруппировки, Размеры пар треугольных подматриц можно оперативно изменять, меняя код логического вектора ° 20

Свойства коммутатора выполнять операции перегруппировки одновременно во всех определенным образом выКоммутатор по авт. св. 11 - 1120313, отличающийся тем, что, с целью расширения функциональных возможностей за счет выполнения операции формирования единичного вектора, в каждую ячейку введены четвертый элемент И и второй элемент ИЛИ, причем второй и третий горизонтальные входы каждой ячейки соединен с первым и вторым входами второго элемента ИЛИ, выход которого соединен с первым входом четвертого элемента

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