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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее П групп блоков сравнения двух чисел по И блоков в группе и сумматоры, причем каждьп -и вход сортируемых чисел, где i 1,2, ...,гг, соединен с первыми входами f5лoкoв сравнения, i -и группы и с вторыми входами t -х блоков сравнение j -х групп блоков сравнения, где j 1, 2, ...,П, отличающееся тем, что, с целью повышения быстродействия, в него введено 11 групп Коммутаторов , причем выходы блоков сравнения J -и группы соединены с входами 4 -го сумматора, выход которого соединен с управляющими входами l -х коммутаторов J -X групп, информационные входы которых подключены к i -м вхо- . дам устройства, а выходы - к -м выходам устройства.jg

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

3щ> 0 06 F 7/06

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬП ИЙ (21) 3495522/18-24 (22) 30.09.82 (46) 07.01.84 ° Бюл. Р 1 (72) И.A. Янушевский (53} 681.322(088.8) (56) 1. Авторское свидетельство СССР

9424141, кл. G 06 F 7/06, 1971.

2. Братальский Е.A. Крупский A.A

Способы упорядочения массива с помощью ассоциативного устройства.Вопросы радиоэлектроники, сер. ЭВТ, 1973, вып. 7, с. 90-93 (прототип). (54)(57) УСТРОЙСТВО,ЦЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее и трупп блоков сравнения двух чисел по И блоков в каждой группе и сумматоры, причем

„„SU„„ A каждый -и вход сортируемых чисел, где = 1,2, ..., n соединен с первыми входами блоков сравнения

-и группы и с вторыми входами s --x блоков сравненич ) -х групп блоков сравнения, где = 1, 2, ..., 0 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введено И групп коммутаторов, причем выходы блоков сравнения

-й группы соединены с входами -го сумматора, выход которого соединен с управляющими входами -х коммутаторов j -х групп, информационные входы которых подключены к 4 -м входам устройства, а выходы - к s -M выходам устройства.

1065854

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

Известно устройство для сортировки информации, содержащее матрицу ячеек, каждая иэ которых состоит из триггера с входными схемами И, ин-, вертора, схем И или ИЛИ (1) .

Недостатком данного устройства являются большие аппаратурные затраты.

Наиболее близким по технической сущности к предлагаемому является 15 устройство для сортировки чисел, содержащее накопитель, блок модификации, блок сравнения, индикаторы опроса, блок сумматоров и регистр признаков опроса, входы которого со- 2О единены с выходными цепями чтения накопителя, а выходи — с входами блоков сравнения, другие абды которых соединены с выходами соответствующих ячеек накопителя, à выходы с входами индикаторов опроса, выходы которых соединены с входами соответствующих сумматоров (2) .

Недостатком известного устройства является невысокое быстродействие.

Цель изобретения — повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для сортиров ки чисел, содержащее и групп блоков сравнения двух чисел по и блоков в каждой группе и сумматоры, причем каждый 1 -й вход сортируемых чисел, где = 1, 2, ..., и, соединен с первыми входами блоков сравнения 4О ! -й группы и с вторыми входами 1 -х блоков сравнения 1 -х групп блоков сравнения, где ) = 1, 2, введено и групп коммутаторов, причем выходи блоков сравнения,4 -й группы соедийены с входами < -го сумматора, выход кОторого соединен с управляющими входами 3 -х-коммутаторов -х групп„ информационные входы которых подключены к Ф -м входам устройства, а выходы — к tl -м выходам устройства.

На чертеже показана схема устройства.

Устройство для сортировки чисел содержит входы 1, 1, ..., 1 блоки 21 -2 сравнения двух чисел, сумматоры 3„, 3, ..., Зп, коммутаторы 4 „ -4 „ и выходы 5„, 5,, 5(Устройство работает следующим образом,.

В момент с на входы 1, 1

1 „ поступают соответственйо чйсла (), x (t), ..., x (t). Скорость поступления массивов чисел определяет 65 ся величиной такта 4 с . Через интервал времени 4tcpz на выходе блока сравнения двух чисел 2„.; формируется двоичный признак сравйения Ь, в соответствии с выражением

1, если Е 0

= 1v, egn(Л)=

А, если 2 с 0

Затем все двоичные признаки сравнения, сформированные на выходах

< -й строки матрицы (7j ), поступают на входы сумматора 3j, на выходе которого с задержкой Ь(.с и формируется управляющий сигнал р< т.е

П 1(+4 (.Ср + 4 сул = X,, (4 ср,1,"4 (2)

Поскольку предполагается, что все входные числа попарйо неравны, т.е. X, y X, если только 1 ф то последовательное применение преобразований (1) и (2) к входному набору чисел не изменяет отношения строгого линейного порядка. Таким образом, из условия Х; < Х следует, что p„„ < p>, причем Pi (4,g „, n); < g q,g . Следовательно, о указывает номер позиции для чйсла Х„ в линейно упорядоненном по возрастанию массиве чисел

Коммутаторы 4 . выполняют сор\ тировку чисел х, B соответствии с их номерами позиций: коммутатор 4„, пропускает число к на выход 5 в том и только в том случае, если

p;= s.

Таким образом, на выходах 5 (, 5

5ц будет сформирована упорядо ченная по возрастанию последователь ность чисел Х (), к q(z) ..., Х к(„1 с общей задержкой вычисления 4с

=-4 ср + 4 (сцл + 4t ко i где 4 ющ задержка вычисления в коьмутаторе.

Необходимо отметить, что при ис- пользовании в устройстве и -канальной линии задержки йа время 41ср, +

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

1065854 с м - ь срз ЧЬ" (3) Задержка сигнала в коммутаторе приближенно равна задержке сравнения двух чисел, т.е..йком = < cp (4) С учетом (3) и (4) оценим сверху общую задержку вычисления в предлагаемом устройстве 1 и Й Фас Cogт 44р = (5 )

ate (a ® и}.

В качестве базового объекта взят параллельный процессор, реализующий алгоритм сортировки методом подсчета за время фФ,е = h4cp.y n Pop>hi

Так как операция сравнения двух чисел может быть представлена как последовательное применение операции вычитания и логической операции И (ИЛИ), то справедливо неравенст во Ь1ср > g4 >, где 41р задержка вычисления разности (суммы) двух чисел. Тогда задержка суммирования чисел удовлетворяет условию

Преимуществом предлагаемого устройства по сравнению с базовым объектом является большой уровень технологичности при изготовлении, так как базовый объект обладает менее регулярной вычислительной структурой: в предлагаемом устройстве используются регулярные матричные и векторные структуры, а в базовом значительную часть вычислительных ресурсов занимает нерегулярное коммутационное и "обвязочное" оборудование. Кроме того, в предлагаемом устройстве возможно использование управляющих сигналов на выходе сум15 маторов в качестве самостоятельных ,выходных сигналов устройства для указания позиций чисел в формируемом массиве чисел, упорядоченных по возрастанию, в тех системах, где

2О не требуется расстановка самих чисел в указанные позиции. Так как в устройстве применена конвейерная обработка, то скорость поступления входных наборов чисел может достигать величины порядка 100 Ирц, а время задержки вычислений 10 c. Экономический эдфект при внедрении 1000 предлагаемых устройств составит

5 мхщ. руб, 10 65854

Составитель Е. Иванова

Редактор В. Петрам Техред N, Тепер Корректор Л. Патай

Чакаэ 11046/49 Тираж 706 Подписное

БНИИПИ Государственного комитета СССР по делам иэобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4