Коммутатор Советский патент 1987 года по МПК G06F7/00 

113

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

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

Длина сформированного единичного вектора может служить оценкой связности.

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

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

Коммутатор 1 (фиг. 1) содержит треугольные матрицы 2 и 3, группу элементов ИЛИ А, группу элементов НЕ 5, ячейки 6 с вторым горизонтальным входом 7 и выходом 8, первым горизонтальным входом 9 и выходом 10, третьим горизонтальным входом 11 и выходом 12, первым вертикальным входом 13 и выходом 14, вторым вертикальным входом 15 и выходом 16, выхо 17 коммутатора, причем в первой треугольной матрице 2, первый 13 и второй 15 Вертикальные входы ячейки 6 с координатами (а, j) соединены соответственно с первым 14 и вторым 16 вертикальными выходами ячейки с координатами (i-I, j), второй 7, первый 9 горизонтальные входы ячейки с координатами (i, j) соединены соответственно с вторым 8, первым 10 горизонтальными входами ячейки с координатами (i, j-I). Во второй треугольной матрице 3, первый 16 и второй 17 вертикальные входы ячейки 6 с координатами (k, 1) соединены соответственно с первым 15 и вторым 13 вертикальными выходами ячейки 6 с координатами (k-l, 1), второй 7, первый 9 горизонтальные входы ячейки с координатами (k, 1) соединены соответственно с вторым 8, первым 10 гори- зонтальн111ми входами ячейки с коор

2-

динатами (К, 1-1), (К, i 1-N; j l-i; 1 1-К), причем третий горизонтальный вход 11 кйждой ячейки 6 соединен с вторым входом второго элемента И 21 данной ячейки 6 и ее третьим 12 горизонтальным выходом. Третий 1I горизонтальный выход ячейки 6 с координатами (i, j) в первой треугольной матрице 2 соединен с третьим

горизонтальным выходом 12 ячейки 6 с координатами (i, j-1), третий горизонтальный вход I1 ячейки 6 с координатами (К, 1) во второй треугольной матрице 3 соединен с третьим горизонтальным выходом 12 ячейки 6 с координатами (К, 1-1), второй 8 горизонтальный выход последней ячейки i-й строки первой треугольной матрицы 2 соединен с вторым горизонтальным

входом 7 первой ячейки (К-К-1)-й

строки второй треугольной матрицы 3, третий горизонтальный выход 12 последней ячейки строки первой треугольной матрицы 2 соединен с третьим горизонтгшьным входом 9 первой ячейки (М-К)-й строки второй треугольной матрицы 3, третий горизонтальный выход последней ячейки последней строки первой треугольной матрицы 2 соединен с третьим горизонтальным входом 11 первой ячейки последней строки второй треугольной матрицы 3, второй вертикальный выход 16 j-й ячейки последней строки

первой треугольной матрицы 2 и второй вертикальный выход 16 (М-1+1)-й ячейки последней строки второй треугольной матрицы 3 подключены соответственно к первому и второму входам

элемента группы ИЛИ 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. Где Z - управляющий логичес313

кий (двоичный) вектор, размерность которого совпадает с размерностью вектора f. Результат операции - вектор X, который содержит те компоненты f- исходного вектора, которые соответствуют z; 1. Размерность вектора X совпадает с количеством единиц вектора z,

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

13и 15 ячеек 6 с координатами (i, j) (i j) подаются соответственно константы 1, О, а на входы 13 и

15 ячеек 6 с координатами (К, 1)

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

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

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

5

0

5

3324

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

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

Очевидно, что треугольная матрица 3 коммутатора 1 не принимает участия в выполнении операции сжатия.

Режим формирования единичного вектора. Формированием единичного вектора называется операция , где z - управляющий логический вектор, размерность которого совпадает с размерностью вектора f. Результат операция - вектор х, который содержит только единичные компоненты f; исходного вектора, которые соответствуют поразрядно Z| 1. Размерность Вектора х равна количеству единиц в результирующем векторе при операции пересечения векторов f и z поразрядно.

В треугольной матрице 2 на входы 13 и 15 ячеек 6 с координатами (i, j) () подаются соответственно константы 1 и О, а на входы 13 и 15 ячеек 6 с координатами (К, 1) () треугольной матрицы 3 подаются константы О. На входы 11 ячеек 6 крайнего левого столбца треугольной матрицы 2 подаются константы О, на горизонтальные входы 9 ячеек 6 крайнего левого столбца треугольной матрицы 2 - логические уровни, соответствующие коду управляющего логического вектора z. Входными каналами коммутатора 1 при выполнении операции формирования единичного вектора являются горизонтальные входы 7 ячеек 6 крайнего левого столбца треугольной матрицы 2, а выходными каналами - вертикальные выходы 16 ячеек 6 последней строки треугольной матрицы 2.

0

5

0

5

0

5

513

В крайнем левом столбце ячеек 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 на горизонтальные тзхо ды 1 1 ячеек 6 крайнего левого столбца подаются константы 1, причем на граничные вертикальные входы 15 ячеек 6 с координатами (i, j) (i j) в матрице 2 и на граничные вертикаль3326

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

Входными каналами коммутатора 1

to при выполнении операции расширения также являются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами - вертикальные выходы 16 ячеек 6 пос -5 ледней строки треугольной матрицы 2, При этом i-й компоненте произвольного вектора соответствует горизонтальный вход 7 первой ячейки N-(m- i) строки матрицы 2, где га - раз0 мерность произвольного вектора. На (N-m) верхние горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2 подаются константы О, на нижние горизонтальные т-входы 9

25 ячеек 6 крайнего левого столбца

матрицы 2 - константы 1, а на (N- т) горизонтальные входы 9 - константы О.

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

Столбцы треугольной матрицы 2, которым соответствуют единицы управ- 40 ляющего вектора z, ведут себя следующим образом.

В соответствии с управляющим вектором единичные логические уровни

45 поданы на граничные вертикальные входы 13 ячеек 6 j, и так далее столбцов треугольной матрицы 2, тогда поскольку на все нижние горизонтальные входы 9 ячеек 6 крайнего вого столбца поданы константы 1, ситуация одновременного наличия единичных логических уровней на входах 13 и 9 возникает в N-(m-l) -и ячейке 6 j -го столбца. Следовательно, сиг налы N-(m-l)-ro и так далее входных каналов 7 направлены на вертикальные выходы 16 последних ячеек 6 j,-го и так далее столбцов матрицы 2, что соответствует операции расширения.

71

В выполнении данной операции треугольная матрица 3 не принимает участия .

Режим сплетения. Сплетением называется операция х--/f, z, g, котора по двум производным векторам f и g логическому вектору z строит вектор такой, что компонента х; принимает значение очередной компоненты f, если z; 0, либо очередной компоненты g, если z;) 1, Размерность вектора X совпадает с размерностью z и равна сумме размерностей f и g,

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

16ячеек 6 последней строки матрицы 2 и матрицы 3, одновременно поступают на элементы группы ИЛИ 4,

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

17элементов группы ИЛИ 4.

Режим перегруппировки. Перегруппировкой произвольного вектора f называется операция х---f Дг, где z - логический вектор, размерность которого равна размерности вектора f, Результат операции - произвольный вектор X, который в качестве п первых компонент X: содержит те компоненты f; исходного вектора , кото7 рые соответствуют (I j п), а в качестве m следующих компонент X п+ - те компоненты f; исходного вектора f, которые соответствуют (I т), где пи m - соответственно количество единиц и нулей в. логическом векторе z. Размерность вектора х совпадает с размерностью z и равна сумме n+m,

При выполнении операции перегруппировки матрица 2 работает в режиме сжатия вектора f логическим вектором Z, а матрица 3 - в режиме сжатия

8

этого же вектора логическим векти- ром z .

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

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

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

ячеек 6 крайнего правого столбца матрицы 3 с .элементов группы НЕ подаются логические уровни, соответствующие коду вектора z.

Наличие горизонтального входа 11

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

подматриц, что значительно расширяет функциональные возможности коммутатора.

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

Пусть на горизонтальный вход 11 i-й ячейки 6 крайнего левого столбда треугольной матрицы 2 подан нулевой логический уровень, а на все другие горизонтальные входы 1 ячеек 6 этого столбца - единичные логические уровни, В этом случае в треугольной

матрице 2 выделяются две независимые треугольные подматрицы. Логический вектор, имеющий g нулей, выделяет в треугольной матрице (§+1) независимых подматриц,

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

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

Свойства коммутатора выполнять операции перегруппировки одновременно во всех определеннЕ)1м образом Bt iРедактор Ю. Середа

фиг.г

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

332If

деляемых парах треугольных подматриц позволяет аппаратно реализовать процедуру сортировки (упорядочения) элементов массива.

5

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

Коммутатор по авт. св. № 1120313, отличающийся тем, что,

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

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

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

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