Устройство для сортировки чисел

ОЮЗ СОВЕТСНИХОЦИАЛИСТИЧЕСНРЕСПУБЛИН О 1 ЙЙЙВ 3(5 И 0 06 Г 7/ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПИЙОПИСАНИЕ ИЭОБРЕТЕНИИ АВТОРСКОМУ СВИДЕТЕЛЬГГВУ,А. Янушевский81.322(088.8)Авторское свид1, кл. 0 06 Р 7/Братальский Е,А.бы упорядочения массоциативного усы радиоэлектронивып. 7, с. 90-93(54)(57) УСТРОЙСТВО,ЦЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее й трупп блоков сравнения двух чисел по И блоков в каждой группе и сумматоры, причем каждьп 1 1 -и вход сортируемых чисел где= 1,2, , п, соединен с первыми входами блоков сравнения-и группы и с вторыми входами- блоков сравненич-х групп блоков сравнения, где= 1, 2,П о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введено И групп коммутаторов, причем выходы блоков сравнени-й группы соединены с входамисумматора, выход которого соединен с управляющими входами-х коммут торов 1 -х групп, информационные входы которых подключены к 4 -м вх дам устройства, а выходы - к-м выходам устройства.Изобретение относится к вычислительной технике и может быть использовано в ассоциативных процессорах,в системах распознавания образов,в устройствах управления базами данных.Известно устройство для сортировки инФормации, содержащее матрицуячеек, каждая иэ которых состоит изтриггера с входными схемами И, ин-,вертора, схем И или ИЛИ )1).Недостатком данного устройстваявляются большие аппаратурные затраты.Наиболее близким по техническойсущности к предлагаемому является 15устройство для сортировки чисел,содержащее накопитель, блок модиФикации, блок сравнения, индикаторыопроса, блок сумматоров и регистрпризнаков опроса, входы которого со Оединены с выходными цепями чтениянакопителя, а выходи - с входамиблоков сравнения, другие вхбды которых соединены с выходами соответствующих ячеек накопителя, а выходыс входами индикаторов опроса, выходы которых соединены с входами соответствующих сумматоров (2) .Недостатком известного устройства является невысокое быстродействие,Цель изобретения - повышениебыстродействия устройства.Поставленная цель достигаетсятем, что в устройство для соотиоовки чисел, содержащее и групп блоковсравнения двух чисел по и блокЬвв каждой группе и сумматоры, причемкаждый 1 -й вход сортируемыхчисел,где= 1, 2, , и, соединен спервыми входами блоков сравнения 4 О-й группы и с вторыми входами 1 -хблоков сравнения 1 -х групп блоковсравнения, где ) = 1, 2, , йвведено о групп коммутаторов, причем выходи блоков сравиения, -й 45группы соедийены с входами-го сумматора, выход кОторого соединен суправляющими входами 4 -х коммутаторов ) -х групп информационныевходы которых подключены к 1 -м входам устройства, а выходы - к 1 -мвыходам устройства,На чертеже показана схема устройства.Устройство для сортировки чиселсодержит входы 1), 116блоки 211 -2 сравнения двух чисел,сумматоры З Зфф Зпкоммутаторы 4 -4 и выходы 5, 55 пУстройство работает следующим образом,.В момент 1 на входы 11, 1,1постуцают соответственйо чйслах(1), х(с), , х,(с). Скоростьпоступления массивов чисел определяетб 5ся величиной такта ас, Через интервал времени Ь 1 ср на выходе блока сравнения двух чисел 2; Формируется двоичный признак сравйения , в соответствии с выражением (,О Ь 1 ) =К;И- ХЮ ( 1 )1, если Е ) О = 1,п, ф (г) =П, если й с ОЗатем все двоичные признаки срав. нения, сФормированные на выходах-й строки матрицы (2 ), поступают на входы сумматора 3, на выхо. де которого с задержкой ь 1 см Формируется управляющий сигнал (, т.е "1+ьср +ьсуд=ХЬср 1 4(2)Поскольку предполагается, что все входные числа попарйо неравны, т.е. Х,Х, если толькофто последовательное применение преобразований (1) и (2) к входному набору чисел не изменяет отношения строгого линейного порядка. Таким образом, из условия Х; с Хследует, чтос ), причем с,"А" д 3; , б 4,й . Следовательно, о; указывает номер позиции для чйсла Х в линейно упорядоиенном по возрастанию массиве чисел Коммутаторы 4 выполняют сор тировку чисел Х, в соответствии с их номерами позиций: коммутатор 4, пропускает число Х навыход 5 в том и только в том случае, если Таким образом, на выходах 5), 55 п будет сФормирована упорядо,ченная по возрастанию последовательность чисел Хк кк.Х к(п) с общей задержкой вычисления ьс =Мср + Ь 1 сцц +ком, где Йкомзадержка вычисления в коьмутаторе.Необходимо отметить, что при ис- пользовании в устройстве и -канальной линии задержки йа время 61 ср + + Ьсур для входного набора чисел, обеспечивающей синхронное поступление на входы коммутаторов управляющих и инФормаионвых сигналов, величина такта Ьс может быть уменьшена от значения ьср + Ь 1 сдр, до значения,Ьо ,определяемого максимальным временем переходного процесса в каждом из составляющих элементов устройства. Практически укаэанная величина такта равна времени переходного процесса в активном элементе схемы, например в вентиле для КИОЛ-схем.(3) Задержка сигнала в коммутаторе приближенно равна задержке сравнения двух чисел, т.е.(4) С учетом (3) и (4) оценим сверху .общую задержку вычисления в предлагаемом устройствеЬ й Ь Фас Вофй 46(= (5 )й,(,Го и)В качестве базового объекта взят параллельный процессор, реализующий алгоритм сортировки методом подсчета за время фФ,в = Ь сри Ео п Г Так как операция сравнения двух чисел может быть представлена как последовательное применение операции вычитания и логической операции И (ИЛИ), то справедливо неравенст войсргЬ 1 , где бар задержка вычисления разности (суммы) двух чисел. Тогда задержка суммирования чисел удовлетворяет условию Преимуществом предлагаемого устройства по сравнению с базовым объектом является большой уровень технологичности при изготовлении, таккак базовый объект обладает менеерегулярной вычислительной структурой: в предлагаемом устройстве используются регулярные матричные ивекторные структуры, а в базовомзначительную часть вычислительныхресурсов занимает нерегулярное коммутационное и "обвязочноеп оборудование. Кроме того, в предлагаемомустройстве возможно использованиеуправляющих сигналов на выходе сум маторов в качестве самостоятельных,выходных сигналов устройства дляуказания позиций чисел в Формируемом массиве чисел, упорядоченныхпо возрастанию, в тех системах, где 2 О не требуется расстановка самих чиселв указанные позиции. Так как в устройстве применена конвейерная обработка, то скорость поступления входных наборов чисел может достигатьвеличины порядка 100 ИГц, а времязадержки вычислений 10с. Экономический эАйект при внедрении 1000предлагаемых устройств составит5 мющ. руб,10 65854 Составитель Е. Ивановаетраш Техред М, Тепер Корректо Патай Редактор В илиал ППП "Патент", г. Ужгород, ул. Проектна Чакаэ 11046/49 БНИИПИ Р по дел 113035, Мо