Устройство коммутации и сортировки Советский патент 1989 года по МПК G06F7/06 

laiy

СП

о

СЛ

о

00

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

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

На фиг.1 представлена схема устройства на фиг.2 - схема блока коммутации,- на фиг,3 - настройка блока коммутации соответственно на соеди- .нительные функции проходные каналы и Поворот каналов ; на фиг,4 - пример настройки блоков коммутации устройства

Устройство содержит (п -п)/2 блоков 1 коммутации, первую и вторую группы по -п информационных входов- выходов 2 и 3 устройства о Казвдый блок 1 коммутации содержит с первого по четвертый информационные входы-выходы 4-7, компаратор 8, триг- гер 9, первьй и второй магистральные коммутаторы 10 и 11, управляющий вход 12,

Компаратор 8 может быть реализован на микросхемах цифрового компаратора К 564 Ш 2, который обладает свойством наращиваемости по числу разрядов. При этом выход Больше или равно компараторов 8 следует соединить с выходом элемента ИЛИ, входы которого соединены с выходами Больше и Равно цифрового компаратора К564ИП2,. выполняющего сравнение старших разрядов.

Магистральные коммутаторы 10 и 11 могут быть реализованы на БИС 583хЛ1, которые позволяют организовать коммутацию четырех двунаправленных магистралей требуемой разрядности. При этом если на управляющий вход СО магистрального коммутатора 10 или 11 подается уровень логического нуля, то на управляющие входы для магистрали L2 БИС 583хЛ1 необходимо подать двоичный код (0101), что приводит к коммутации магистралей L2 и L3. Если на вход СО магистрального коммутатора 10 или 11 подается уровень логической единицы, то на управляющие

е; Q

с

0

5

входы для магистрали L1 БИС 583хЛ1 необходимо подать двоичн()ГЙ код (1001), что приводит к коммутации магистра-ч лей L1 и L3.

Назначение каждого блока 1 (i,j) коммутации состоит в сортировке двух чисел А и В, поданных на входы-выходы 4 и 5, т,е, в выделении максимального из двух чисел на входе-выходе 6 и минимального на входе-выходе 7, а также в запоминании по результату произведенной сортировки соединительной функции блока 1 В зависимости от соотношения чисел А и В блок автоматически настраивается на одну из двух возможных соединительных функций: проходные каналы (фиг.За) либо Поворот каналов слева вниз и сверху направо (фиг.Зб), которую блок 1 запоминает с помощью триггера 9.

Все числа, поступающие в устройство; представлены т-разрядным дво- и чным кодом, что соответствует разрядности информационных каналов устройства.

Алгоритм работы устройства елеа

дующий о

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

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

ход 2 устройства подается пузырек - тояние. При этом на управляющий вход номер входа-выхода 3, с которым необходимо организовать связь. Поскольку в этом случае выполняется сортиСО МК Ю подается уровень логической 1 вень логического

, а на вход СО МК 11 - . Это приводит к

Tot-iy, что к магистрали L3 в МК 10 подключается магистраль L1, а в МК 11 магистраль L2. В результате выполненной коммутации магистралей число А поступает на вход-выход 6, а число В на вход-выход 7. Тем самым данный блок 1 вьтолняет операцию сортировки пары чисел А,В и одновременно настраивается на соединительную функровка массива чисел от 1 до п, то кажда 1й пузырек всплывает на предназначенном ему входе-выходе 3 устройства. При этом происходит автоматическая настройка и запоминание требуемых каналов связи, которые и образуют новый рисунок соединений. В целом, устройство может быть исползовано в двух основных сортировка данных и коммутирующая сеть.

Устройство работает следуклцим образом.

В режиме сортировки данных на входы-выходы 2 ,...,2„ устройства подаются тп-разрядные двоичные коды элементов исходного массива. При поступлении единичного сигнала на вход 12 в каждом блоке 1 устройства компаратором 8 производится сравнени чисел А и В, поступивших соответственно на входы 5 и А, и занесение результата сравнения в триггер 9.Если в данном блоке имеет место случай Л В, то с выхода Меньше компаратора 8 поступает единичный сигнал на информационный вход триггера 9, а с выхода Больше или равно - нулево сигнал на вход установки в ноль триггера 9, что приводит к установке последнего в единичное состояние.

При этом на управляющий вход СО магистрального коммутатора (МК) 10 подается уровень логического О, а на вход СО МК 11 - уровень логической 1 Это приводит к тому, что к магистрали L3 в МК 10 подключается магистраль L2, а в МК 11 - магистраль L1. В результате выполненно коммутации магистралей число А поступает на вход-выход 7 блока 1, а число В - на вход-выход 6. Тем самым данный блок 1 вьтолняет опера- цмо сортировки пары чисел (А,В) и одновременно настраивается на соединительную функцию Проходные каналы (фиг.За).

Если в данном блоке имеет место случай А 7/ В, то с выхода Меньше компаратора 8 поступает нулевой сигтояние. При этом на управляющий вход

СО МК Ю подается уровень логической 1 вень логического

, а на вход СО МК 11 - . Это приводит к

0

Tot-iy, что к магистрали L3 в МК 10 подключается магистраль L1, а в МК 11- магистраль L2. В результате выполненной коммутации магистралей число А поступает на вход-выход 6, а число В- на вход-выход 7. Тем самым данный блок 1 вьтолняет операцию сортировки пары чисел А,В и одновременно настраивается на соединительную функ5 цию Поворот каналов слева вниз и сверху направо (фиг,36).

При этом триггер 9 запомина:ет результат сравнения чисел А и В, поступивших на входы-выходы данного

0 блока, и своими выход 4И управляет состоянием магистральных коммутаторов 10 и 11, обеспечивая этим настройку блока на соответствующую соединительную функцию. Результаты

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

Q передается с входа-выхода 6 данного блока 1 на вход- выход 4 правого соседнего блока 1, а меньшее - с входа-выхода 7 данного блока 1 на вход- выход 5 нижнего соседнего блока 1 (или на вход-выход А для первого блока 1 в строке). Таким образом, про- , цедура перестановки чисел, поступивших на входы-выходы каждой строки матрицы, завершается выделением максимального из них на входе-выходе 6 ; последнего блока строки и передачей всех остальных чисел (меньших выделенного числа) на входы-выходы нижней соседней строки.

В результате описанного процесса на входах-выходах 3,,...,3 устройства формируется упорядоченная по возрастание последовательность элементов исходного массива. При этом на

Q входе-выходе 3 выделяется минималь- Hbrii элемент, а на входе-выходе 3 - максимальный элемент исходного массива. Процесс пузырьковой сортировки протекает асинхронно и распространя5

0

5

Изобретение относится к области вычислительной техники и может быть использовано при построении мультипроцессорных вычислительных систем, параллельных и ассоциативных процессоров управляющих систем, средств систем поиска информации и распознавания образов. Цель изобретения - расширение функциональных возможностей за счет выполнения операций сортировки, поиска максимума и минимума и повышение быстродействия за счет параллельной настройки каналов. Цель достигается тем, что устройство содержит матрицу из (N²-N)/2 блоков 1 коммутации, A - я строка которой содержит (N-A) блоков 1 коммутации (A =1,...,N-1, N-размер обрабатываемого массива данных), B-й столбец треугольной матрицы блоков коммутации (B =1,...,N-1) содержит B блоков 1 коммутации. 4 ил.

нал на вход установки в единицу триг- -г ется по блока м 1 устройства в виде

о «р - ,„.4 ,,„ к„ 1 о -

гера 9, а с выхода Больше или равно - единичный сигнал на вход установки в ноль триггера 9, что приводит к установке последнего в нулевое сосволны из блока 1 , , . Завершается описанный процесс после срабатывани

блока 1 ни п С

h-1, rv-1

где

что потребует време- время срабатывания

/л .

,„.4 ,,„ к„ 1 о -

волны из блока 1 , , . Завершается , описанный процесс после срабатывания

1 С

h-1, rv-1

где

что потребует време- время срабатывания

/л .

отдельного блока 1. При поступлении нулевого сигнала на вход 12 резуль- :тат сортировки исходного массива фиксируется на входах-выходах 3 устройства,

В режиме коммутирующей сети для настройки устройства на новый рисунок соединений на к аждый вход-выход 2

устройства необходимо подать двоичный , к второму информационному

код номера j входа-йыхода 3, с которым необходимо организовать связь. Таким образом, на входЬ1-выходы 2 устройства подается неупорядоченный мас- сив чисел от 1 до п. При этом при даче единичного сигнала на вход 12 устройство работает так же, как и в режиме сортировки данных, В результате произведенной пузырьковой сорвходу-выходу блока коммутации а-й строки (к+1)-го столбца треугольной матрицы, первый информационный вход- выход блока коммутации а-й строки (п-1)-го столбца треугольной матрицы подключен к а-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации а-й строки а-го столбца треугольной матрицы подключе к второму информационному входу-выхо ду блока коммутации (а+1)-й строки (а+1)-го столбца треугольной матрицы fpeтий информационный вход-выход бло ка коммутации (п-1)-й строки (n-l)-r столбца треугольной матрицы подключен к п-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации Ь-го столбца с-й строки (где c-t,.,.,Ь-1) треугольной матрицы подключен к четвертому информационному входу-выходу блока коммутации Ь-го столбца Сс- -О-й строки треуголь ной матрицы, второй информационный вход-выход блока коммутации первой строки первого столбца треугольной матрицы подключен к первому информационному входу-выходу второй группы устройства, четвертый информационный вход-выход блока коммутации первой строки Ь-го столбца треугольной матрицы подключен к (Ь+1)-му информационному входу-выходу второй группы

тировки каждое из входных Т1исел j появляется на вкоде- выходе 3 j устройства. Тем самым прокладываются требуемые каналы связи между входашс- выходами устройства, которые и определяют Новый рисунок соединений. На фиг,4 показан пример настройки коммутирующей сети на рисунок соединений, в котором входы-выходы 2,,,.,,25 соединены соответственно с входами-выходами 3,... ,3 i. Для такой настройки

на входы-выходы 2 ,.,,,2 необходимо подать соответственно двоичные коды чисел 4, Э, 5, 1, 2.

При поступлении нулевого сигнала на вход 12 фиксируется новый настроенный рисунок соединений входов-вько- дов 2 и 3 устройств. 110 настроенным каналам связи возможна долговременная передача данных в обоих направлениях, что обеспечивают в кавдом блоке магистральные коммутаторы 10 и 11, При этом данные, поступающие на входы-выходы устройства, не подвергаютс пузырьковой сортировке, так как на входе 12 присутствует нулевой логи- ческий уровень, который, поступая , в каждом блоке 1 на вход синхронизации триггера 9, фиксирует его состояние на настроенную соединительную функцию, которая и сохраняется без изменений в каждом блоке на весь период коммутации данных по настроенньм каналам связи,

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

Устройство коммутации и сортиров- ки, содержащее треугольную матрицу Чиз ()/2 блоков коммутации, а-я строка которой содержит (п-а) блоков

коммутации (где а-1,...,п-1,п - размер обрабатываемого массива данных), Ь-й столбец треугольной матрицы (где Ь-1,...,п-1), содержит b блоков коммутации, при этом первый информационный вход-выход блока коммутации а-й строки к-го столбца треугольной матриць (где к-а,... ,п-2)

г

0

5

0

5

0

входу-выходу блока коммутации а-й строки (к+1)-го столбца треугольной матрицы, первый информационный вход- выход блока коммутации а-й строки (п-1)-го столбца треугольной матрицы подключен к а-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации а-й строки а-го столбца треугольной матрицы подключен к второму информационному входу-выходу блока коммутации (а+1)-й строки (а+1)-го столбца треугольной матрицы, fpeтий информационный вход-выход блока коммутации (п-1)-й строки (n-l)-ro столбца треугольной матрицы подключен к п-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации Ь-го столбца с-й строки (где c-t,.,.,Ь-1) треугольной матрицы подключен к четвертому информационному входу-выходу блока коммутации Ь-го столбца Сс- -О-й строки треугольной матрицы, второй информационный вход-выход блока коммутации первой строки первого столбца треугольной матрицы подключен к первому информационному входу-выходу второй группы устройства, четвертый информационный вход-выход блока коммутации первой строки Ь-го столбца треугольной мат. рицы подключен к (Ь+1)-му информационному входу-выходу второй группы

устройства, причем каждый блок ком- iyтaции треугольной матрицы содержит триггер, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет вьшолнения операций сортировки, поиска максимума и минимума и увеличения быстродействия устройства за счет параллельной настройки каналов, вход признака настройки устройства подключен к управляющим входам блоков коммутации матрицы, причем каждый блок кoм {yтaции треугольной матрищ содержит компаратор, первый и второй магистральные коммутаторы, при этом

в каждом блоке кo fyтaции треугольной матрицы первьп информационный вход-выход блока коммутации подключен к первому информационному входу- выходу первого магистрального коммутатора, второй информационньй вход- выход блока коммутации подключен к первому входу компаратора, к второму информационному входу-выходу первого магистрального коммутатора и к первому информационному входу-выходу второго магистрального коммутатора, третий информационньп вход-выход блока коммутации подключен к второму ин- формационному входу-выходу второго

магистрального коммутатора, четвертый информационньш вход-выход блока кo lмyтaции подключен к второму входу компаратора и к третьим информационным входам-выходам первого и второго магистральных коммутаторов, управляющий вход блока коммутации подключен к входу синхронизации триггера, инверсный и прямой выходы которого подключены соответственно к управляющим входам первого и второго магистральных коммутаторов, первый и второй

выходы компаратора подключены соответственно к входам установки в

1

и в О

триггера.

фиг.1

W

ггЛ

6 I /)

накс(А,Ь)А

Фиг.