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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее (ц-)) ячеек анализа (И - количество сортируемых чисел), каждая из которых включает схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с первыми группами входов коммутатора и схемы сравнения, выход которого подключен к управляющему входу коммутатора , информационные входы первой группы устройства соединены с установленными входами регистра первой ячейки анализа, выходы коммутатора 4-й ячейки анализа, где - 1,2,..., (п-2), соединены с установочными входами регистра (/+1)-й ячейки анализа , отличающееся тем, что, с целью повьпиения быстродействия , в каждую ячейку анализа введены (П-1) регистров, -а -ю ячейку анализа i коммутаторов, а в J -ю:ячейку анализа, где j 2,3,..., (tt-1), введены (j-1) схем сравнения, причем информационные входы k-й группы устройства, где k - 2,3,...,ii, подключены к установочным входам k-го регистра первой ячейки анализа в К-и ячейке анализа, где с 1,2,..., (П-1), выходы разрядов регистров с второго по

СОЮЭ СОВЕТСКИХ

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

РЕСПУБЛИК

09) (И) 3(5D С 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H ABTOPCH0MY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3643654/24-24 (22) 22.09.83 (46) 07.11.84. Бюл. Р 41 (72) А.А. Мельник и И.Г. Цмоць (53) 681.325.66(088.8) (56) 1. Авторское свидетельство СССР

ll 637810, кл. G 06 F 7/08, 1976.

2. Авторское свидетельство СССР

11« 1007099, кл. G 06 F 7/08, 1981 (прототип) ° (54)(57) УСТРОЙСТВО ДЛ 1 СОРТИРОВКИ

ЧИСЕЛ, содержащее (rl-1) ячеек анализа (l1 — количество сортируемых чисел), каждая из которых включает схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с первыми группами входов коммутатора и схемы сравнения, выход которого подключен к управляющему входу коммутатора, информационные входы первой группы устройства соединены с установленными входами регистра первой ячейки анализа, выходы коммутатора

«-й ячейки анализа, где = 1,2, ° (n -2), соединены с установочными входами регистра (i +1)-й ячейки анализа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в каждую ячейку анализа введены (g-1) регистров, в « -ю ячейкУ анализа « коммутаторов, а в 1 -ю. ячейку анализа, где 1 = 2,3,..., («1-1), введены ()-1) схем сравнения, причем информационные входы k-й группы устройства, где k = "-,Ç,...,n, подключены к установочным входам 1«--го регистра первой ячейки анализа в

8-й ячейке анализа, где = 1,2,..., (п-1), выходы разрядов регистров с второго по (0 +1)-й подключены к первой группе входов соответствующего коммутатора, выходы коммутаторов со второго по (i+1)-й и регистров с (0+2)го по й-й «-й ячейки анализа соединены с установочными входами соответствующих регистров (« +1)-й ячейки анализа, выходы коммутаторов («1-1)-й ячейки анализа являются выходами устройства, в 3 --A ячейке анализа выходы разрядов (8+ 1)-ro регистра соединены с вторыми группами входов коммутаторов с первого по 0 -й и схем сравнения с первой по«: -ю, выходы которых соединены с управляющими входами коммутаторов соответственно с второго ло (1+1)-й, в первой ячейке анализа выходы разрядов первого регистра подключены к первой группе входов второго коммутатора, в каждой

j †-..й " ячейке анализа выходы разрядов регистров с первого по (1-1)-й соединены с третьей группой входов коммутаторов соответственно со второго по « -й, вторые управляющие входы которых соединены с выходами схем сравнения соответственно со второй по « -ю, а выходы разрядов j -го регистра подключены к второй группе входов (1+1)-го коммутатора.

3030 2

1 112

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

В задачах, связанных с обработкой данных.сейсморазведки, гидроакустики при распознавании образов необходимо . производить сортировку данных. При- 10 счем часто сортировку необходимо производить в реальном масштабе времени, т.е. с той же частотой, с которой поступают данные.

Известно устройство для сортировки И||1 -разрядных чисел, содержащее

6 регистров, И схем сравнения, схемы сравнения, элементы И и запрета, коммутатор, переключатели i)1).

Недостатком устройства является наличие механических элементов, снижающих его надежность.

Наиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел со 25 держащее и| ячеек, где и| — количество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр результата, причем выходы регистра результата соединены с второй группой информа35 ционных входов элемента сравнения и первой группой информационных входов коммутатора, установочные входы при" емного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединены с установочными входами регистра ре зультата и с второй группой информационных входов коммутатора, а выходЫ коммутатора являются выходами ячейки, 45 входы установки приемного регистра и регистра результата .в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью

50 регистра результата соединены с входом тактовых сигналов устройства, I выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим .вхо-- 55 дом коммутатора, управляющий вход элемента сравнения соединен с управляю-. щим входом устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предыдущей ячейки, а группа йнформационных входов первой ячейки является группой информационных входов устройства f23 .

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

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

Поставленная цель достигается тем, что в устройстве для сортировки чисел, содержащем (И"1) ячеек анализа (,П вЂ” количество сортируемых чисел), каждая из которых включает схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с первыми группами входов коммутатора . и схемы сравнения, выход которого подключен к управляющему входу коммутатора, информационные вход| первой группы устройства соединены с установленными входами регистра первой ячейки анализа, выходы коммутас тора | -й ячейки анализа, где 1

1,2, ° . °,(И-2), соединены с установочными входами регистра (i+1)-й ячейки анализа, в каждую ячейку анализа введены (n-1) .регистров, с в вЂ,ю ячейку анализа 1 коммутаторов в j -ю ячейку анализа, где j = 2,3,..., (И-1) введены ()-1) схем сравнения, причем информационные входы k -й группы устройства, где k = 2,3,...,tt, подключены к установочным входам

k-ro регистра первой ячейки анализа в 1-ой ячейке анализа, где

1,2,...,(И-1), выходы разрядов регистров с второго по (0-1)-й подключены к первой группе входов соответствующего коммутатора, выходы коммутаторов с второго по (+1)-й и регистров с (3 +2)-го по и -й 1 -й ячейки анализа соединены с установочными входами соответствующих регистров с (1+1)-й ячейки анализа, выходы коМмутаторов (tl-1)-й ячейки анализа являются выходами устройства, в |, -й ячейке анализа выходы разрядов (| .+1)-го регистра соединены с вторыми группами входов коммутаторов с первого по

f-й и схем сравнения с первой по -ю, выходы которых соединены с управляющими входами коммутаторов соответственно с второго по 1 -й, в первой ячейке анализа выходы разрядов первого регистра, подключены к первой группе входов второго коммутатора, в

030 срв ом

3 1123 каждой 1 -ой ячейке выходы регистров с первого по ()-1)-й соединены с третьей группой входов коммутаторов

Ф с второго по g -й, вторые управляющие входы которых соединены с выходами схем сравнения соответственно с второй по j.-ю, а выходы разрядов j †. го регистра подключены к второй группе входов (1 +1)-ro коммутатора.

На чертеже представлена функциональная схема предлагаемого устройства.

Устройство содержитtl --1 ячеек 1, 1,..., 1, 1 анализа (и — количество чисед в груйпе), каждая из которых содержит и регистров 2,2,...,2,, схем сравнения 3,3>,...,3„ и +1 коммутатороъ 4,4, ...,4 +у, коммутаторы 4 и 4„, в каждой ячейке

1 ° анализа двухходовые, а остальные

1 трехвходовые.

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

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

Результат сравнения (1 — если содержимое регистра 2;, меньше содержимого соответствующего регистра

2 1... °,2<,. или 0 — если содержимое

35 регистра 2„ больше или равно содержимому соответствующего регистра

21,...,2„ ) со схем сравнения 3,....,3; поступает на управляющие входы соответствующих коммутаторов 41,..., 4

4;,1 . Сигнал логической "1" на управляющем входе коммутаторов 41 и

4; устанавливает их в положение, когда на их выход поступает информация с первых входов, а при сигнале логического "0" на управляющем входе этих коммутаторов на выход поступает информация с вторых входов. В зависимости от значения сигналов на управляющих входах трехвход .. ных коммутаторов на их выход поступает информация с первых (на первом и втором управляющем входе сигналы логического "0"), вторых (на первом управляющем входе сигнал логической

" 1", на втором логического "0") или третьих (на первом и втором управляющем входе сигналы логической "1") входов.

В каждой ячейке 1 анализа происходит определение места положения числа, записанного в регистре 2 по отношению к просортированным числам, записанным в регистрах

2,...,2„. На выходах коммутаторов

4,...,4 „ каждой ячейки 1 анализа получаем группу из 1 +1 просортированных, чисел (большее число на выl ходе коммутатора 4;, меньшее на вы ходе коммутатора 4„ 1 ). Просортированные числа получаем на выходе ячейки 1» анализа, после прохождения их через все ячейки анализа .1,...,1

У ° ° ° Э

Устройство работает на конвейерному принципу. Каждая ячейка 1 анализа устройства является отдель- ной ступенью конвейера. Наличие в каждой ячейке регистров 24,...,2 11 позволяет совместить во времени обработку информации во всех ячейках анализа. Поэтому быстродействие устройства определяется временем прохождения информации через ячейку 1. ! анализа, т.е. тактом конвейера, и не зависит от количества сортируемых чисел.

Данное время определяется формулой где tpr — время записи в регистр;

t — время сравнения чисел на схеме сравнения;

t †. время задержки информации на коммутаторе.

По сравнению с известным в предлагаемом устройстве, время сортиров- .ки в котором составляет 2 m тактов, быстродействие значительно повышено.

° ° Ý

° ФФ

° Ф

° °

ВЕИИПИ Звхаэ 8141/40 Тираи 698 Подяисиое .Филиал ППП "Пвтеит", г. Узгород, ул.Проектная,4