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

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройст вах обработки информации, предназначенных для сортировки массивов данны в реальном масштабе времени. В задачах, связанных с обработкой данных сейсморазведки, гидроакустики при распознавании образов необходимо производить сортировку данных. Причем часто сортировку необходимо производить в реальном масштабе времени, т.е. с той же частотой, с которой noctynaroT данные. Известно устройствоДЛЯ сортировки mП -разрядных чисел, содержащее rt регистров, П схем сравнения, схемы сравнения, элементы И и запрета, коммутатор, переключатели . Недостатком устройства является наличие механических элементов, снижающих его надежность. Наиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел, содержащее гп ячеек, где W - количество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемен та сравнения, каждая ячейка содержит коммутатор и регистр результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационных входов коммутатора, установочные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединен с установочными входами регистра ре-р зультата и с второй группой информационных входов коммутатора, а выходы коммутатора являются выходами ячейки входы установки приемного регистра и регистра результата -в исходное состояние соединены с входом установки устройства в исходное состояние, вхо управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход эл мента сравнения соединен с управляющим входом ycTpoi cTsa, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предьщущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства 2. Недостатком известного устройства является низкое быстродействие. Цель изобретения - повьшение быстродействия . i Поставленная цель достигается тем, что в устройстве для сортировки чисел, содержащем (rt-l) ячеек анализа (И - количество сортируемых чисел), кiaждaя из которых включает схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с первыми группами входов коммутатора и схемы сравнения, выход которого подключен к управляющему входу коммутатора, информационные входы первой группы устройства соединены с установленными входами регистра первой ячейки анализа, выходы коммутатора А -и ячейки анализа, где i 1,2,...,(П-2),. соединены с установочными входами регистра (1+1)-й ячейки анализа, в каждую ячейку анализа введены (11-1) регистров, в 4 гю ячейку анализа i коммутаторов BJ -ю ячейку анализа, гдеj 2,3,..., (И-1) введены (J-1) схем сравнения, причем информационные входы k-и группы устройства, где k 2,3,...,и, подключены к установочным входам k-ro регистра первой ячейки анализа в Е-ой ячейке анализа, где 1,2(n-l), выходы разрядов регистров с второго по (Р-1)-й подключены к первой группе входов соответствующего коммутатора,выходы коммутаторов с второго по (+1)-й и регистров с (5+2)-го по и-и 1-й ячейки анализа соединены с установочными входами соответствующих регистров (+1)-й ячейки анализа, выходы ко тутаторов (11-1)-й ячейки анализа являются выходами устройства, в -и ячейке анализа выходы разрядов (+1)-го регистра соединены с вторыми группами входов коммутаторов с первого по Р-й и схем сравнения с первой по t -ю, выходы которых соединены с управляющими входами коммутаторов соответственно с второго по j -и, в первой ячейке анализа выходы разрядов первого регистра .-подключены к первой группе входов второго коммутатора, в каждой -ой ячейке выходы регистров с первого по (}-1)-й соединены с третьей группой входов коммутаторов с второго по j -и, вторые управляющие входы которых соединены с выходами схем -сравнения соответственно с второй по }.-ю, а выходы разрядовj -го регистра подключены к второй группе входов (j+1)-ro коммутатора. На чертеже представлена функциональная схема предлагаемого устройства. Устройство содержит ц -1 ячеек If , 1л ,..., 1(.1 анализа (О - количеств чисел в группе), каждая из которых содержит ц регистров 2 . ,2,... ,2, схем сравнения 3(,32,...,3 и 1+ 1 коммутаторо-в ком мутаторы 4 и 4, в каждой ячейке 1- анализа двухходовые, а остальные трехвходовые. Устройство работает следующим образом. По каждому импульсу происходит запись новой группы сортируемых чисе с входов устройства в первую ячейку анализа 1 и информации с выходов предьщущих ячеек 1j в последующие . В каждой ячейке 1 анализа происходит сравнение содержимого регист ра содержимым регистров 2,..., Результат сравнения (1 - если содержимое регистра 2 меньше содержимого соответствующего регистра 2,..., 2,, или О - если содержимое регистра больше или равно содержимому соответствующего регистра 2,..., 2;) со схем сравнения 3г ,... поступает на управляюпще входы соответствующих коммутаторов 4,... 4 . Сигнал логической 1 на управляющем входе коммутаторов 4;j и 4- , устанавливает их в положение, когда на их выход поступает информация с первых входов, а при сигнале логического О на управляющем входе этих коммутаторов на выход поступает информация с вторых входов. В зависимости от значения сигна лов на управляющих входах трехвход. ных коммутаторов на их выход поступает информация с первых (на первом и втором управляющем входе сигналы логического О), вторых (на первом управляющем входе сигнал логической 1, на втором логического О) или третьих (на первом и втором управляющем входе сигналы логической 1) входов. В каждой ячейке-1 анализа происходит определение места положения числа, записанного в регистре по отношению к просортированным числам, записанным в регистрах 2j,...,2. На выходах коммутаторов 4,...,4 каждой ячейки 1 анализа получаем группу из +1 просортированных ,чисел (большее число на выходе коммутатора , меньшее на выходе коммутатора , ). Просортированные числа получаем на выходе ячейки 1i. анализа, после прохождения их через все ячейки анализ ,1. ,..., 1« i Устройство работает на Конвейерному принципу. Каждая ячейка 1 анализа устройства является отдель- ной ступенью конвейера. Наличие в каждой ячейке регистров 2,... ,2 позволяет совместить во времени обработку информации во всех ячейках анализа. Поэтому быстродействие устройства определяется временем прохождения информации через ячейку 1/ анализа, т.е. тактом конвейера, и не зависит от количества сортируемых чисел. Данное время определяется формулой -ср в -ifOM где tpr :- время записи в регистр; tj,.- - время сравнения чисел на схеме сравнения;, время задержки информации на коммутаторе. По сравнению с известный в предлагаемом устройстве, время сортировки в котором составляет 2 ш тактов, быстродействие значительно повышено.

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

«4

.

i

i

.i

fij

.«. . S3

-