Устройство коммутации и сортировки
Изобретение относится к области вычислительной техники и может быть использовано при построении мультипроцессорных вычислительных систем, параллельных и ассоциативных процессоров управляющих систем, средств систем поиска информации и распознавания образов. Цель изобретения - расширение функциональных возможностей за счет выполнения операций сортировки, поиска максимума и минимума и повышение быстродействия за счет параллельной настройки каналов. Цель достигается тем, что устройство содержит матрицу из (N<SP POS="POST">2</SP>-N)/2 блоков 1 коммутации, A - я строка которой содержит (N-A) блоков 1 коммутации (A =1,...,N-1, N-размер обрабатываемого массива данных), B-й столбец треугольной матрицы блоков коммутации (B =1,...,N-1) содержит B блоков 1 коммутации. 4 ил.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК
ОПИСАНИЕ ИЗОБРЕТЕНИЯ Н А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ ПРИ ГННТ СССР (21) 4399882/24-24 (22) 29 ° 03.88 (46) 07.11.89,Вюл. В 41 (71) Таганрогский радиотехнический институт им.В.Д.Калмыкова (72) В.Н.Решетняк, В.П.Карелин и В.Ф.Гузик (53) 681.325(088 ° 8) (56) Авторское свидетельство СССР У 1102038, кл. Н 03 К 17/04, 1983. Фет Я.И. Параллельные процессоры для управляющих систем. M. Энергоиздат, 1981 с. 126-128. (54) УСТРОЙСТВО КОМИУТА1ЦП1 И СОРТИРОВКИ (57) Изобретение относится к области вычислительной техники и может быть использовано при построении мульти„SU 1520508 A 1 2 процессорных вычислительных систем, параллельных и ассоциативных процессоров управляющих систем, средств систем поиска информации и распознавания.образов ° Цель изобретения — рас ширение функциональных возможностей за счет выполнения операций сортировки, поиска максимума и минимума и повышение быстродействия за счет параллельной настройки каналов. Цель достигается тем, что устройство содержит матрицу из (n -n) /2 блот ков 1 коммутации, а-я строка которой содержит и-а блоков 1 коммутации а = I,...,n-1, п — размер обрабатываемого массива данных), b-й столбец треугольной матрицы блоков коммутации (b=I,...,n-I) содержит Ь блоков 1 коммутации. 4 ил.! 520508 Изобретение относится к вычислительной технике и может быть использовано для построения мультипроцессорных вычислительных систем, параллельных и ассоциативных процессоров управляющих систем, средств систем поиска информации и распознавания образов, Цель изобретения — расширение функциональных возможностей устройства за счет выполнения операций сортировки, поиска максимума и минимума и повышение его быстродействия за счет параллельной настройки каналов. На фиг.1 представлена схема устройства; на фиг.2 — схема блока коммутации на фиг.Ç вЂ” настройка блока коммутации соответственно на соеди,нительные функции "проходные каналы" и "Поворот каналов"; на фиг.4 — пример настройки блоков коммутации устройства. Устройство содержит (и -и)/2 бло l ков 1 коммутации, первую и вторую группы по и информационньг»г входоввыходов 2 и 3 устройства. Каждый блок 1 коммутации содержит с первого по четвертыи информационные входы выходы 4 7, компаратор 8, триггер 9, первый и второй магистральные коммутаторы 10 и 11, управляющий ВХОД 12. Компаратор 8 может быть реализован на микросхемах цифрового компаратора К 564 ИП 2, который обладает свойством наращиваемости по числу разрядов. При этом выход »Больше или равно" компараторов 8 следует соединить с выходом элемента ИЛИ, входы которого соединены с вьгходами "Больше" и "Равно" цифрового компаратора К564ИП2, выполняющего сравнение старших разрядов. Магистральные коммутаторы 10 и 11 могут быть реализованы на БИС 583хЛ1, которые позволяют организовать коммутацию четырех двунаправленных магистралей требуемой разрядности. При этом, если на управляющий вход СО магистрального коммутатора 10 или ii подает50 ся уровень логического нуля, то на управляющие входы для магистрали L2 БИС 583хЛ1 необходимо подать двоичный код (0101), что приводит к ком" мутации магистралей 1.2 и 1.3. Если на вход СО магистрального коммутатора 10 или 11 подается уровень логической единицы, то на управляющие входы для магистрали L! БИС 583хЛ1 необходимо подать двоичный код (100!), что приводит к коммутации магистра--» лей L1 и LÇ. Наз»»ачен»»е каждого блока 1 (i, j) коммутации состоит в сортировке двух чисел А и В, поданньгх на входы †выходы 4 и 5, т,е, в выделении максимального из двух чисел на входе-выходе б и минимального на входе-выходе 7, а также в запоминании по результату произведенной сортировки соединительной функции блока 1. В зависимости от соотношения чисел А и В блок автоматически настраивается на одну иэ двух возможных соединительных функций: проходные каналь» (фиг. За) либо Поворот каналов слева вниз и сверху направо" (фиг.36), которую блок 1 запоминает с помощью триггера 9. Все числа, поступающие в устройство, представлены m-разрядным двоичным кодом, что соответствует разрядности информационных каналов устройCTBG, Алгоритм работы устройства следующий. В основу работы устройства положен процесс упорядочивания массива элементов методом пузь»рька .При этом в каждой строке матрицы устройства вьгполняется перестановка поступивших на ее входь»-выходы 2 чисел путем попарнсй сортировки чисел, поступивших на входы-выходы каждого блока 1 строки матрицы, Целью такой перестановки является выделение в каждой строке максимального из поступивших чисел р тî сî,пузырька K0TopblA "всплывает" на первом входе-вь»ходе последнего блока 1 в каждой строке. Таким образом (II-1) строк матрицы обеспечивают формирование на входахвыходах 3 устройства упорядоченной по возрастанию последовательности из и эпементов исходного массива чисел. Тем самым выполняется операция сортировки исходного массива. При этом на первом входе-выходе 3 устройства выделяется минимальный элемент массива, а на и-и входе-выходе 3 — максимальный элемент массива. Для настройки устройства на новьп» рисунок соединений используется процесс пузырьковой сортировки входноI o массива элементов. Входы-выходы 2 и 3 устройства нумеруются двоичными числа»п» от 1 до и. На кажць»й вход-вы1520508 ход 2 устройства подается "пузырек"номер входа-выхода 3, с которым необходимо организовать связь. Поскольку в этом случае выполняется сорти5 ровка массива чисел от 1 до п, то каждый "пузырек" всплывает" на предназначенном ему входе-выходе 3 уст- ройства. При этом происходит автоматическая настройка и запоминание 10 требуемых каналов связи, которые и образуют новый рисунок соединений. В целом, устройство может быть использовано в двух основных pe ax: сортировка данных и коммутирующая сеть. 15 Устройство работает следующим образом. В режиме сортировки данных на входы-выходы 2,,...,2 „ устройства подаются m-разрядные двоичные коды 20 элементов исходного массива. При поступлении единичного сигнала на вход 12 в каждом блоке 1 устройства компаратором 8 производится сравнение чисел А и В, поступивших соответ- 25 ственно на входы 5 и 4, и занесение результата сравнения в триггер 9.Если в данном блоке имеет место случай Л (В, то с выхода "Иеньше" компаратора 8 поступает единичный сигнал 30 на информационный вход триггера 9, а с выхода "Больше или равно" — нулевой сигнал на вход установки в ноль триггера 9, что приводит к установке последнего в единичное состояние. При этом на управляющий вход СО магистрального коммутатора (МК) 10 подается уровень логического "0", а на вход СО МК 11 — уровень логической 1 Это привОдит к тому» что 40 к магистрали LÇ в MK 10 подключается магистраль L2, а в МК 11 — магистраль L1. В результате выполненной коммутации магистралей число А поступает на вход-выход 7 блока 1, 45 а число В - на вход-выход 6. Тем самым данный блок 1 выполняет операцию сортировки пары чисел (A,В) и одновременно настраивается на соединительную функцию "Проходные каналы" (фиг.За}. Если в данном блоке имеет место случай А 7, В, то с выхода "Меньше" компаратора 8 поступает нулевой сигнал íà вход установки в единицу триг- 55 гера 9, а с выхода "Больше или равно" — единичный сигнал на вход установки в ноль триггера 9, что приводит к установке последнего в нулевое состояние. При этом на управляющий вход СО ИК 10 подается уровень логической 11", а на вход СО MK 11 — уровень логического "0" ° Это приводит к тому, что к магистрали L3 в МК 10 подключается магистраль L1, а в МК 11магистраль L2. В результате выполненной коммутации магистралей число А поступает на вход-выход 6, а число В— на вход-выход 7. Тем самым данный блок 1 выполняет операцию сортировки пары чисел AS и одновременно настраивается на соединительную функцию "Поворот каналов слева вниз и сверху направо" (фиг.3б}. При этом триггер 9 запоминает результат сравнения чисел А и В, поступивших на входы-выходы данного блока, и своими выходами управляет состоянием магистральных коммутаторов 10 и 11, обеспечивая этим настройку блока на соответствующую соединительную функцию. Результаты произведенной сортировки передаются на соседние блоки 1, матрицы, расположенные справа и внизу, в которых происходят аналогичные процессы. При этом большее из чисел А и В всегда передается с входа-выхода 6 данного блока 1 на вход-выход 4 правого соседнего блока 1, а меньшее — с входа-выхода 7 данного блока 1 на входвыход 5 нижнего соседнего блока 1 (или на вход-выход 4 для первого блока 1 в строке). Таким образом, про-. цедура перестановки чисел, поступивших на входы-выходы каждой строки матрицы, завершается выделением максимального из них на входе-выходе 6; последнего блока строки и передачей всех остальных чисел (меньших выделенного числа} на входы-выходы нижней соседней строки. В результате описанного процесса . на входах-выходах 3,,...,3 „ устройства формируется упорядоченная по возрастанию последовательность элементов исходного массива. При этом на входе-выходе 3 выделяется минималь1 ный элемент, а на входе-выходе 3 „— максимальный элемент исходного массива. Процесс "пузырьковой" сортировки протекает асинхронно и распространяется по блокам 1 устройства в виде "волны" из блока 1,, Завершается ! описанный процесс после срабатывания блока 1„, „ „, что потребует времени и ., где 7- время срабатывания 1520508 отдельного блока 1. При поступлении .нулевого сигнала на вход 12 результат сортировки исходного массива фиксируется на входах-выходах 3 устройства. В режиме коммутирующей сети для настройки устройства на новый рису.нок соединений на каждый вход-выход 2 устройства необходимо подать двоичный код номера 1 входа-выхода 3, с которым необходимо организовать связь.. Таким образом, на входы-выходы 2 устройства подается неупорядоченный мас сив чисел от 1 до и, Нри этом при по- 1 даче единичного сигнала на вход 12 устройство работает так же, как и в режиме сортировки данных. В результате произведенной "пузырьковой" сортировки каждое из входных чисел ) появляется на входе-выходе 3 устройj ства. Тем самым прокладываются требуемые каналы связи между входами" выходами устройства, которые и определяют новый рисунок соединений. На фиг.4 показан пример настройки коммутирующей сети на рисунок соединеиий, в котором входы-выходы 2 „ ...,2 z соединены соответственно с входами-выходами 34y ° ° ° 3 j ° Лля такой настройки 30 на входы-выходы 2 1, ° ° .,2 необходимо подать соответственно двоичные коды чисел 4, 3, 5, 1 2. При поступлении нулевого сигнала на вход 12 фиксируется новый настроенный рисунок соединений входов-выходов 2 и 3 .устройств. ио настроенным каналам связи возможна долговременная передача данных в обоих направлениях, что обеснечивают в каждом блоке магистральные коммутаторы 10 и При этом данные, поступающие на входы-выходы устройства, не подвергаются "пузырьковой сортировке, так как на: входе 12 присутствует нулевой логический уровень, который, поступая в каждом блоке 1 на вход синхронизации триггера 9, фиксирует его состояние на настроенную соединительную функцию, которая и сохраняется без изменений в каждом блоке на весь 50 период коммутации данных по настроенным каналам связи. Формула изобретения 1 устройство коммутации и сортиров- 5э ;ки, содержащее треугольную матрицу из (тР-п)/2 блоков коммутации, а-я I 1 строка которой содержит (n-a) блоков коммутации (где а-l,...,n-l,n — размер обрабатываемого массива данных), Ъ-й столбец треугольной матрицы (где Ь-1...,,n-l), содержит Ь блоков коммутации, при этом первый информационный вход-выход блока коммутации а-й строки к-го столбца треугольной матрицы (где к-а,...,п-2) подключен к второму информационному входу-выходу блока коммутации а-й строки (к+1)-го столбца треугольной матрицы, первый информационный входвыход блока коммутации а-й строки (и-1)-го столбца треугольной матрицы подключен к а-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации а-й строки à-ro столбца треугольной матрицы подключен к второму информационному входу-BbIxo» ду блока коммутации (а+1)-й строки (а+1)-го столбца треугольной матрицы, третий информационный вход-выход блока коммутации (n-1)-й строки (n-1)-го столбца треугольной матрицы подключен к и-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации Ь-го столбца с-й строки (где с-l,...,Ь-i) треугольной матрицы подключен к четвертому информационному входу-выходу блока коммутации Ь-го столбца (с+1)-й строки треугольной матрицы, второй информационный вход-выход блока коммутации первой строки первого столбца треугольной матрицы подключен к первому информационному входу-выходу второй группы устройства, четвертый информационный вход-выход блока коммутации первой строки Ь-го столбца треугольной мат-. рицы подключен к (Ь+1)-му информационному входу-выходу второй группы устройства, причем каждый блок коммутации треугольной матрицы содержит триггер, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет выполнения операций сортировки, поиска максимума и минимума и увеличения быстродействия устройства за счет параллельной настройки каналов, вход признака настройки устройства подключен к управляющим входам блоков коммутации матрицы, причем калдый блок коммутации треугольной матрицы содержит компаратор, первый и второй магистральные коммутаторы, при этом 1 520508 10 в каждом блоке коммутации треугольной матрицы первый информационный вход-выход блока коммутации подключен к первому информационному входу5 выходу первого магистрального коммутатора, второй информационньп входвыход блока коммутации подключен к первому входу компаратора, к второму информационному входу-выходу первого 10 магистрального коммутатора и к первому информационному входу-выходу второго магистрального коммутатора, третий информационньпЪ вход-выход блока коммутации подключен к второму ин- 15 формационному входу-выходу второго магистрального коммутатора, четвертый информационньпЪ вход-выход блока коммутации подключен к второму входу компаратора и к третьим информационным входам-выходам первого и второго магистральных коммутаторов, управляющий вход блока коммутации подключен к входу синхронизации триггера, инверсный и прямой выходы которого под" ключены соответственно к управляющим входам первого и второго магистральных коммутаторов, первый и второй выходы компаратора подключены соответственно к входам установки в "1 и в "0" триггера.! 520508 «Д е Фиа > й) () (>) Составитель А.Смирнов Техред А.Кравчук Корректор И-пожо Редактор В.Данко Заказ 6758/49 Тираж б68 Подписное ВНИИПИ Государственного комитета пб изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101
