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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 19) (И) ш СОбГ 7/О ПИ АНИ РЕТЕНИ е(прототип)Р 41 И. Г. .8) видет Р 7/О оц льство СС 1976,ство СССР 8, 1981т 7/ и групОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ВТОРСНОМУ СВИДЕТЕЛЬСТВ(И - количество сортируемых чисел),каждая из которых включает схемусравнения, коммутатор и регистр, выходы разрядов которого соединены спервыми группами входов коммутатораи схемы сравнения, выход которогоподключен к управляющему входу коммутатора, информационные входы первойгруппы устройства соединены с установленными входами регистра первойячейки анализа, выходы коммутатора(11-2), соединены с установочнымивходами регистра ( +1)-й ячейки анализа, о т л и ч а ю щ е е с я тем,что, с целью повышения быстродействия, в каждую ячейку анализа введены (П) регистров, в-ю ячейку анализакоммутаторов, а в е -ю ячейку анализа, где 1 = 2,3.(11-1), введены (1-1) схем сравнения,причем информационные входы К-" пы устроиства, где= 2,3 р,пр подключены к установочным входам 1-го регистра первой ячейки анализа в 3-й ячейке анализа, где с = 1,2 (п), выходы разрядов регистров с второго по (1 +1)-й подключены к первой группе входов соответствующего коммутатора, выходы коммутаторов со второго по (+1)-й и регистров с И+2)- го по й-й -й ячейки анализа соединены с установочными входами соответствующих регистров ( +1)-й ячейки анализа, выходы коммутаторов (а 1-1)-й ячейки анализа являются выходами устройства, в 1 -й ячейке анализа выходы разрядов (0+ 1)-го регистраР соединены с вторыми группами входов коммутаторов с первого по-й и схем сравнения с первой по -ю, выходы которых соединены с управляющими входами коммутаторов соответственно с второго ло (1+1)-й, в первой ячейке анализа выходы разрядов первого регистра подключены к первой группе входов второго коммутатора, в каждой ) в .й ячейке анализа выходы разрядов регистров с первого по (1-1)-й соединены с третьей группой входов коммутаторов соответственно со второго по-й, вторые управляющие входы которых соединены с выходами схем сравнения соответственно со второй по-ю, а выходы разрядов-го регистра подключены к второй группе ф входов ( +1)-го коммутатора.3030 2 1 112Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени.В задачах, связанных с обработкой данных.сейсморазведки, гидроакустики при распознавании образов необходимо . производить сортировку данных, При О :чем часто сортировку необходимо производить в реальном масштабе времени, т.е. с той же частотой, с которой поступают данные.Известно устройство для сортировки В б -разрядных чисел, содержащее6 регистров, И схем сравнения, схемы сравнения, элементы И и запрета, коммутатор, переключатели Я .Недостатком устройства является наличие механических элементов, снижающих его надежность.Наиболее близким по технической сущности к предлагаемому является УстРойстВО Для сортиРОВки чисеЛу СО 25 держащее е ячеек, где й - количество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр результата, причем выходы регистра результата соединены с второй группой информа 35 ционных входов элемента сравнения и первой группой информационных входов коммутатора, установочные входы при" емного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединены с установочными входами регистра ре " зультата и с второй группой информационных входов коммутатора, а выходЫ коммутатора являются выходами ячейки,45 входы установки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью50 регистра результата соединены с входом тактовых сигналов устройства,выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом устройства, группы информационных входов каждой ячейки,кроме первой, соединены с группойвыходов предыдущей ячейки, а группайнформационных входов первой ячейкиявляется группой информационных входов устройства 23 . Недостатком известного устройства является низкое быстродействие.Цель изобретения - повышение быстродействия.Поставленная цель достигается тем, что в устройстве для сортировки чисел, содержащем (И"1) ячеек анализа (,П - количество сортируемых чисел), каждая из которых включает схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с первыми группами входов коммутатора . и схемы сравнения, выход которого подключен к управляющему входу коммутатора, информационные вход первой группы устройства соединены с установленными входами регистра первой ячейки анализа, выходы коммута 1 тора-й ячейки анализа, где 11,2(И),. соединены с установочными входами регистра (1+1)-й ячейки анализа, в каждую ячейку анализа введены (И) .регистров,1вв ,ю ячейку анализа 1 коммутаторов в-ю ячейку анализа, где= 2,3 (И) введены -1) схем сравнения, причем информационные входы 1 -й группы устройства, где 1 = 2,3 .р, подключены к установочным входам 1-го регистра первой ячейки анализа в 1-ой ячейке анализа, где1,2(И), выходы разрядов регистров с второго по (Г)"й подключены к первой группе входов соответствующего коммутатора, выходы коммутаторов с второго по ( +1)-й и регистров с (3 +2)-го по И -й 1 -й ячейки анализа соединены с установочными входами соответствующих регистров с(1+1)-й ячейки анализа, выходы коъюмутаторов (11-1)-й ячейки анализа являются выходами устройства, в 1 -й ячейке анализа выходы разрядов (1:+1)-го регистра соединены с вторыми группами входов коммутаторов с первого по 1-й и схем сравнения с первой по"ю, выходы которых соединены с управляющими входами коммутаторов соответственно с второго по-й, в первой ячейке анализа выходы разрядов первого регистра, подключены к первой группе входов второго коммутатора, в030 срв ом ф 3 1123 каждой-ой ячейке выходы регистров с первого по (1-1)-й соединены с третьей группой входов коммутаторовс второго по-й, вторые управляющие входы которых соединены с выходами схем сравнения соответственно с второй по .-ю, а выходы разрядов 1 в . го регистра подключены к второй группе входов (1 +1)-го коммутатора.На чертеже представлена функцио р нальная схема предлагаемого устроиства.Устройство содержит П -1 ячеек 1, 1,, 1анализа ( п - количество чисед в груйпе), каждая из которых 15 содержит и регистров 2 ,22схем сравнения 31,33 и +1 коммутаторов 4 4 4+ ф ком мутаторы 4 и 4, в каждой ячейке 1 анализа двухходовые, а остальные трехвходовые.Устройство работает следующим образом.По каждому импульсу происходит запись новой группы сортируемых чиселр 5 с входов устройства в первую ячейку анализа 1; и информации с выходов предыдущих ячеек 1; в последующие 1 . В каждой ячейке 1 анализа происходит сравнение содержимого регист.ра 2;, с содержимым регистров 212,. Результат сравнения (1 - если содержимое регистра 2;, меньше содержимого соответствующего регистра 2 1,2, или 0 - если содержимое35 регистра 2 больше или равно содержимому соответствующего регистра 212) со схем сравнения 33; поступает на управляющие входы соответствующих коммутаторов 41 4 4;, , Сигнал логической "1" на управляющем входе коммутаторов 41 и 4; устанавливает их в положение, когда на их выход поступает информация с первых входов, а при сигнале логического "0" на управляющем входе этих коммутаторов на выход поступает информация с вторых входов, В зависимости от значения сигналов на управляющих входах трехвход,. ных коммутаторов на их выход поступает информация с первых (на первом и втором управляющем входе сигналы логического "0"), вторых (на первом управляющем входе сигнал логической " 1", на втором логического "0") или третьих (на первом и втором управляющем входе сигналы логической "1") входов.В каждой ячейке 1 анализа происходит определение места положения числа, записанного в регистре 2 по отношению к просортированным числам, записанным в регистрах 212. На выходах коммутаторов 4 4 1 каждой ячейки 1 анализа получаем группу из+1 просортированных, чисел (большее число на выходе коммутатора 4;, меньшее на выходе коммутатора 41 ). Просортированные числа получаем на выходе ячейки 1анализа, после прохождения их через все ячейки анализй,111 фф -1Устройство работает на конвейерному принципу. Каждая ячейка 1 анализа устройства является отдель-ной ступенью конвейера, Наличие в каждой ячейке регистров 22 11 позволяет совместить во времени обработку информации во всех ячейках анализа. Поэтому быстродействие устройства определяется временем прохождения информации через ячейку 1 фанализа, т.е. тактом конвейера, и не зависит от количества сортируемых чисел.Данное время определяется форму- лой где Сг - время записи в регистр;й - время сравнения чисел насхеме сравнения;й в . время задержки информациина коммутаторе.По сравнению с известным в предлагаемом устройстве, время сортиров- .ки в котором составляет 2 ш тактов, быстродействие значительно повышено.