Устройство коммутации и сортировки

(50 4 С 06 Г 7/06 ПИСАНИЕ ИЭОБРЕТЕНИ 2 тем,оцесеский арелин льство С 7/04, 1 е проце СР 83 сор р М.8,Т 1 сится к ластибытььтико ГОСУДАРСТВЕННЫЙ НОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГННТ СССР Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение отноовычислительной техники и можетиспользовано при построении му процессорных вычислительных сис параллельных и ассоциативных пр соров управляющих систем, средств систем поиска ин 4 юрмации и распознавания.образовЦель изобретения - рас ширение Функциональных возможностей за счет выполнения операций сортировки, поиска максимума и минимума и повышение быстродействия за счет параллельной настройки каналов. Цель достигается тем, что устройство содержит матрицу из (и -и) /2 блоков 1 коммутации, а-я строка которой содержит и-а блоков 1 коммутации а = 1. ,п, п - размер обрабатываемого массива данных), Ь-й столбец треугольной матрицы блоков коммутации (Ь=1п) содержит Ь блов 1 коммутации, 4 ил,Изобретение относится к вычислительной технике и может быть использовано для построения мультипроцессорных вычислительных систем, параллельных и ассоциативных процессоровуправляющих систем, средств системпоиска информации и распознаванияобразов,Цель изобретения - расширениефункциональных возможностей устройства за счет выполнения операций сортировки, поиска максимума и минимумаи повышение его быстродействия засчет параллельной настройки каналов.На Фиг.1 представлена схема устройства; на Фиг,2 - схема блока коммутации на Фиг.З - настройка блокакоммутации соответственно на соеди,нительные Функции проходные каналы"и "Поворот каналов"; на Фиг.4 - пример настройки блоков коммутации устройства.Устройство содержит (и -и)/2 бло 2ков 1 коммутации, первую и вторуюгруппы по и информационньгг входоввыходов 2 и 3 устройства. Каждыйблок 1 коммутации содержит с первого по четвертыи информационные входы-выходы 4-7, компаратор 8, триггер 9, первый и второй магистральныекоммутаторы 10 и 11, управляющийВХОД 12,Компаратор 8 может быть реализованна микросхемах цифрового компаратораК 564 ИП 2, которьп обладает свойством наращиваемости по числу разрядов.При этом выход Больше или равно компараторов 8 следует соединить с выходом элемента ИЛИ, входы которогосоединены с выходами "Больше" и "Рав"но" цифрового компаратора К 564 ИП 2,выполняющего сравнение старших разрядов.Магистральные коммутаторы 10 и 11могут быть реализованы на БИС 583 хЛ 1,которые позволяют организовать коммутацию четырех двунаправленных магистралей требуемой разрядности. При этом,если на управляющий вход СО магистрального коммутатора 10 или 11 подает 50ся уровень логического нуля, то науправляющие входы для магистрали1,2 БИС 583 хЛ 1 необходимо подать двоичный код (0101), что приводит к ком"мутации магистралей 1.2 и 1,3. Еслина вход СО магистрального коммутатора 10 или 11 подается уровень логической единицы, то на управляющие входя для магистрали 1.,1 БИС 583 хЛ 1 необходимо подать двоичный код (100), что приводит к коммутации магистра-лей 1,1 и 1.3.Назачене каждого блока 1 (1,З) коммутации состоит в сортировке двух чисел А и В, поданных на входы в выходы 4 и 5, т,е,. в выделении максимального из двух чисел на входе-выходе б и минимального на входе-выходе 7, а также в запоминании по результату произведенной сортировки соединительной функции блока 1, В зависимости от соотношения чисел А и В блок автоматически настраивается на одну иэдвух возможных соединительных функций: "проходные канали" (фиг,За) либо Поворот каналов слева вниз и сверху направо" (фиг,Зб), которую блок 1запоминает с помощью триггера 9.Все числа, поступающие в устройство, представлены ш-разрядным двоичным кодом, что соответствует разрядности информационных каналов устройства,Алгоритм работы устройства следующииВ основу работы устройства положен процесс упорядочивания массиваэлементов методом пузырька.При этомв каждой строке матрицы устройствавьполняется перестановка поступивших на ее входь-выходы 2 чисел путемпоп рнсй сортировки чисел, поступивших на входы-выходы каждого блока 1строки матрицы, Целью такой перестановки является выделение в каждойстроке максимального из поступившихчисел, т,е, "пузырька", который"всплывает" на первом входе-выходепоследнего блокав каждой строке.Таким образом (и) строк матрицыобеспечивают Формирование на входахвыходах 3 устройства упорядоченнойпо возрастанию последовательности изи эпементов исходного массива чисел,Тем самым выполняется операция сортировки исходного массива. При этом напервом входе-выходе 3 устройства выделяется минимальный элемент массива, а на и-и входе-выходе 3 - максимальный элемент массива.гля настройки устройства на новьприсунок соединений используется процесс пузырьковой сортировки входного массива элементов. Входы-выходы2 и 3 устройства нумеруются двоичнымичислап от 1 до и, На кажцый вход-выход 2 устройства подается "пузырек"номер входа-выхода 3, с которым необходимо организовать связь, Поскольку в этом случае выполняется сорти 5ровка массива чисел от 1 до п, токаждый "пузырек" всплывает" на предназначенном ему входе-выходе 3 уст-ройства. При этом происходит автоматическая настройка и запоминание 10требуемых каналов связи, которые иобразуют новый рисунок соединений,В целом, устройство может быть использовано в двух основных режимах: сортировка данных и коммутирующая сеть. 15Устройство работает следующим образом.В режиме сортировки данных навходы-выходы 2.,2устройстваподаются ш-разрядные двоичные коды 20элементов исходного массива. При поступлении единичного сигнала навход 12 в каждом блоке 1 устройствакомпаратором 8 производится сравнениечисел А и В, поступивших соответственно на входы 5 и 4, и занесениерезультата сравнения в триггер 9.Если в данном блоке имеет место случай Л ( В, то с выхода "Меньше" компаратора 8 поступает единичный сигнал 30на информационный вход триггера 9, ас выхода "Больше или равно" - нулевойсигнал на вход установки в нольтриггера 9, что приводит к установке последнего в единичное состояние.35При этом на управляющий вход СОмагистрального коммутатора (МК) 10подается уровень логического "0",а на вход СО ИК 11 - уровень логической 1 е Это приводит к тому что 40к магистрали ЬЗ в МК 10 подключается магистраль Ь 2, а в МК 11 - магистраль Ь 1, В результате выполненнойкоммутации магистралей число А по"ступает на вход-выход 7 блока 1, 45а число В - на вход-выход 6. Тем самым данный блок 1 выполняет операцию сортировки пары чисел (А,В) иодновременно настраивается на соединительную функцию "Проходные каналы" (фиг.За),Если в данном блоке имеет местослучай А , В, то с выхода "Меньше"компаратора 8 поступает нулевой сигнал на вход установки в единицу триггера 9, а с выхода "Больше или равно" - единичный сигнал на вход установки в ноль триггера 9, что приводитк установке последнего в нулевое состояние, При этом на управляющий вход СО МК 10 подается уровень логической "1", а на вход СО МК 11 - уровень логического "0". Это приводит к тому, что к магистрали ЬЗ в МК 10 подключается магистраль Ь 1, а в МК 11- магистраль Ь 2. В результате выполненной коммутации магистралей число А поступает на вход-выход 6, а число В - на вход-выход 7, Тем самым данный блок 1 выполняет операцию сортировки пары чисел А,В и одновременно настраивается на соединительную функцию "Поворот каналов слева вниз и сверху направо" (фиг,3 б).При этом триггер 9 запоминает результат сравнения чисел А и В, поступивших на входы-выходы данного блока, и своими выходами управляет состоянием магистральных коммутаторов 10 и 11, обеспечивая этим настройку блока на соответствующую соединительную функцию. Результаты произведенной сортировки передаются на соседние блоки 1, матрицы, расположенные справа и внизу, в которых происходят аналогичные процессы. При этом большее из чисел А и В всегда передается с входа-выхода 6 данного блока 1 на вход-выход 4 правого соседнего блока 1, а меньшее - с входа-выхода 7 данного блока 1 на вход- выход 5 нижнего соседнего блока (или на вход-выход 4 для первого блока 1 в строке), Таким образом, процедура перестановки чисел, поступивших на входы-выходы каждой строки матрицы, завершается выделением максимального из них на входе-выходе 6, последнего блока строки и передачей всех остальных чисел (меньших выделенного числа) на входы-выходы нижней соседней строки.В результате описанного процесса на входах-выходах 3,3устройства Формируется упорядоченная по возрастанию последовательность элементов исходного массива. При этом на входе-выходе 3 выделяется минимальный элемент, а на входе-выходе 3- максимальный элемент исходного массива. Процесс "пузырьковой" сортировки протекает асинхронно и распространяется по блокам 1 устройства в виде "волны" из блока 1 Завершаетсяописанный процесс после срабатывания блока 1,, что потребует времени и Г, где 7- время срабатыванияотдельного блока 1. При поступлении .нулевого сигнала на вход 12 результат сортировки исходного массива фиксируется на входах-выходах 3 устройства.В режиме коммутирующей сети для настройки устройства на новый рису.нок соединений на каждый вход-выход 2 устройства необходимо подать двоичный код номера 1 входа-выхода 3, с которым необходимо организовать связь., Таким образом, на входы-выходы 2 устройства подается неупорядоченный массив чисел от 1 до и, Нри этом при по ф даче единичного сигнала на вход 12 устройство работает так же, как и в режиме сортировки данных. В результате произведенной "пузырьковой" сортировки каждое из входных чисел 1 появляется на входе-выходе 3 устрой 1 ства. Тем самым прокладываются требуемые каналы сызи между входами" выходами устройства, которые и определяют новый рисунок соединений. На 2 фиг.4 показан пример настройки коммутирующей сети на рисунок соединеиий, в котором входы-выходы 2,2соединены соответственно с входами-выхо" дами 33 . Для такой настройки на входы"выходы 2 12необходимо подать соответственно двоичные коды чисел 4, 3, 5, 1, 2.При поступлении нулевого сигнала на вход 12 фиксируется новый настроенный рисунок соединений входов-выходов 2 и 3 .устройств. ио настроенным каналам связи возможна долговременная передача данных в обоих направлениях, что обеснечивают в каждом блоке ма.гистральные коммутаторы 10 и При этом данные, поступающие на входы-выходы устройства, не.подвергаются "пузырьковойсортировке, так как на: входе 12 присутствует нулевой логи.ческий уровень, который, поступая в каждом блоке 1 на вход синхронизации триггера 9, фиксирует его состояние на настроенную соединительную функцию, которая и сохраняется без изменений в каждом блоке на весьО период коммутации данных по настроен" ным каналам связи.Формула изобретения устройство коммутации и сортиров-,ки, содержащее треугольную матрицуиз (п-п)/2 блоков коммутации, а-я1строка которой содержит (и-а) блоков коммутации (где ап,п - размер обрабатываемого массива данных), Ъ-й столбец треугольной матрицы (где Ьп), содержит Ь блоков коммутации, при этом первый информационный вход-выход блока коммутации а-й строки к-го столбца треугольной матрицы (где к-ап) подключен к второму информационному входу-выходу блока коммутации а-й строки (к+1)-го столбца треугольной матрицы, первый информационный вход- выход блока коммутации а-й строки (и)-го столбца треугольной матрицыподключен к а-му информационному входу-выходу первой группы устройства, третий информационный вход-выходблока коммутации а-й строки а-го столбца треугольной матрицы подключен к второму информационному входу-выходу блока коммутации (а+1)-й строки(а+1)-го столбца треугольной матрицы,третий информационный вход-выход блока коммутации (и)-й строки (и)-гостолбца треугольной матрицы подключен к п-му информационному входу-выходу первой группы устройства, третий информационный вход-выход блока коммутации Ь-го столбца с-й строки (где с. Ь) треугольной матрицы подключен к четвертому информационному входу-выходу блока коммутацииЬ-го столбца (с+1)-й строки треугольной матрицы, второй информационный вход-выход блока коммутации первой строки первого столбца треугольной матрицы подключен к первому информационному входу-выходу второй группыустройства, четвертый информационный вход-выход блока коммутации первой строки Ь-го столбца треугольной мат-. рицы подключен к (Ь+1)-му информационному входу-выходу второй группы устройства, причем каждый блок коммутации треугольной матрицы содержиттриггер, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет выполнения операций сортировки, поиска максимума и минимума и увеличения быстродействия устройства за счет параллельной настройки каналов, вход признака настройки устройства подключен к управляющим входам блоков коммутации матрицы, причем калдый блок коммутации треугольной матрицы содержит компаратор, первый и второй магистральные коммутаторы, при этомв каждом блоке коммутации треугольной матрицы первьо информационный вход-выход блока коммутации подключен к первому информационному входу 5 выходу первого магистрального коммутатора, второй информационньп вход- выход блока коммутации подключен к первому входу компаратора, к второму информационному входу-выходу первого 10 магистрального коммутатора и к первому информационному входу-выходу второго магистрального коммутатора, третий информационньп вход-выход блока коммутации подключен к второму ин формационному входу-выходу второго магистрального коммутатора, четвертый информационньп вход-выход блокакоммутации подключен к второму входукомпаратора и к третьим информационным входам-выходам первого и второгомагистральных коммутаторов, управляющий вход блока коммутации подключенк входу синхронизации триггера, инверсный и прямой выходы которого под"ключены соответственно к управляющимвходам первого и второго магистральных коммутаторов, первый и второйвыходы компаратора подключены соответственно к входам установки в "1"и в "0" триггера,Подписноетениям и открытиям пр скан наб., д. 4/5