Устройство для сортировки чисел Советский патент 1984 года по МПК G06F7/06 

:л

30

::л

4

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

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

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

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

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

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

Поставленная цель достигается

тем, что в устройство для соотиоов|Ки чисел, содержащее п групп блоков сравнения двух чисел по п блокЬв в каждой группе и сумматоры, причем каждый 1 -и вход сортируемых чисел, где V 1, 2, ..., п , соединен с п ервыми входами блоков сравнения 1-й группы и с вторыми входами i блоков сравнения j -х групп блоков сравнения, где j 1,2, ...,t} , введено п групп коммутаторов, причем выходы блоков сравнения , -и группы.соедийены с входами -го суматора, выход которого.соединен с управляющими входами i -х-коммутаторов /1 -X групп, информацкюнные входы которых подключены к -м входам устройства, а выходы - к j -м выходам устройства.

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

Устройство для сортировки чисел содержит входы 1, Ig, ..., 1„ , блоки 2;| 2 сравнения двух чисел, сумматоры 3, 3g, ..., Зп , коммутаторы 4 -4 „„ и выходы 5, 5, ...

SH

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

В момент t на входы 1, 1 , ., 1п постуцают соответственно числа X, 11) , xj (t) , . . 4 , х, (t). Скорость поступления массивов чисел определяеся величиной такта uf . Через интервал времени bicp2 выходе блока сравнения двух чисел формируется двоичный признак сравнения в соответствии с выражением

..(. 6tcp,sgntxi(t)-X3(t) (1)

1, если 2 О

, 1,П , () О, если 2 О

Затем все двоичные признаки сравнения , сформированные на выходах -и строки матрицы (2Ц ), поступают на входы сумматора 3, на выходе которого с задержкой ulctjM формируется управляющий сигнал р , т.е

рд-t li t срз- ut е.ъ; 1 bt ,; .ч;

(2

Поскольку предполагается, что все входные числа попарно неравны, т.е. xi Xj , если только 5 j , то последовательное применение преобразований (1) и (2) к входному набору чисел не изменяет отношения строгого линейного порядка. Таким образом, из условия X; XJ следует, что р pj, причем р ,/5. с {4,,,.. - t,n . Следовательно, р указывает номер позиции для числа Х в линейно упорядоненном по возрастанию массиве чисел

Коммутаторы л

--. . выполняют сорровку чисел тировку чисел в соответствии с

их номерами позиций: коммутатор пропускает число Xj на выход 5( в том и только в том случае, если

р; |.

Таким образом, на выходах 5-( , 5 ..., 5,, будет сформирована упоряло(Ченная по возрастанию последователь5 ность чисел «к(,Хк(г) , ..., X к{п)

с общей задержкой вычисления ut |

Л-Ьср7 + + t Ko(W f rfleetwjM-; задержка вычисления в когФ таторе.

Необходимо отметить, что при йспол1:,зовании в устройстве п -канальной линии задержки на время iicp + + й1су/й для входного набора чисел, обеспечивающей синхронное поступление на входы коммутаторов управляющих и информационных сигналов, величина такта ьЛ может быть уменьшэна от значения utcpj Aicyw Д значения ,определяемого максимальным временем переходного процесса в каждом из составляющих элементов устройства. Практически указанная величина такта равна времени переходного процесса в активном элементе схемы, например в вентиле для КМОП-схем, Так как операция сравнения двух чисел может быть представлена как последовательное применение операци вычитания и логической операции И (или), то справедливо неравенство л1ср, uiF где atр задержка вычисления разности (суммы) двух чисел. Тогда задержка сулячирования чисел удовлетворяет условию itcijm Задержка сигнала в коммутаторе приближенно равна задержке сравнения двух чисел, т.е. . btcp2 С учетом (3) и (4) оценим сверху общую задержку вычисления в предлагаемом устройстве lit tcь tcpЛ2 6pa (5) ,) в качестве базового объекта взя параллельный процессор, реализующи алгоритм сортировки методом подсче ta за вpeмяДtв «п . Преимуществом предлагаемогс устройства по сравнению с базовым объектом является большой уровень технологичности при изготовлении, так как базовый объект обладает менее регулярной вычислительной структурой: в предлагаемом устройстве используются регулярные матричные и векторные структуры, а в базовом значительную часть вычислительных ресурсов занимает нерегулярное коммутационное и обвязочное оборудование. Кроме того, в предлагаемом устройстве возможно использование управляющих сигналов на выходе сумматоров в качестве самостоятельных выходных сигналов устройства для указания позиций чисел в формируемом массиве чисел, упорядоченных по возрастанию, в тех системах, где не требуется расстановка самих чисел в указанные позиции. Так как в устройстве применена конвейерная обработка, то скорость поступления входных наборов чисел может достигать величины порядка 100 МГц, а время задержки вычислений 10 с. Экономический эффект при внедрении 1000 предлагаемых устройств составит 5 млн. руб

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