Устройство для параллельной сортировки кодов

СОЮЗ СОЭЕТСНИХСОЦИАЛ ИСТИЧЕСНИХРЕСПУБЛИН 801193660 1504 006 Р 7ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯ(46) 23.11.85. Бюл. Р (72) А.И. Захаров, В. М,В. Кнасницкий и В.В (53) 681.325 (088.8) (56) Авторское свидет Р 1012239, кл. 6,06 ГАлгоритмы, математ печение и архитектура сорных вычислительных .Наука, 1982, с. 11. 1ев 43Н. Куст Краса ельство С 7/06, 19 3. ес ческо цесМ. огоп стем И Ввей.(54)(57) УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ КОДОВ, содержащее два блока сортировки, каждый из которых содержит О/2 регистров и и /4 узлов ":сравнения, где о - число сортируемых кодов, причем выходы регистров первого блока сортировки подключены к первым группам входов соответствующих узлов сравнения первого и второго блоков сортировки, о т л и ч а ю щ е е с я тем, что, с, целью расширения области приме,нения.путем обеспечения возможности .сортировки произвольной последовательности кодов, в него введены первый и второй элементы НЕ, в каждый блок. сортировки введены первая и вторая группы из й /2 подгрупп элементов И переписи, группа из и /2 подгрупп элементов ИЛИ переписи, ,й/4 узлов коммутации, каждый из которых содержит четыре группы элементов И и две группы элементов ИЛИ, .во второй блок сортировки введены 11./4 дополнительных узлов коммутации, каждый из которых содержит две группы элементов И по о /4 подгрупп элементов И в каждой и группу элементов ИЛИ из и/4 подгрупп элементов ИЛИ, причем входы, сортируемых чисел устройства соединены с информационными входами соответ" ствующих подгрупп элементов И переписи первых групп первого и второго блоков сортировки, в каждом блоке сортировки выходы элементов И переписи 1-й подгруппы первой группы, где 1 = 1,2 о/2, соединены с первыми входами элементов ИЛИ 1-й подгруппы, выходы которых соединены с информационными входами элементов И переписи 1-й подгруппы второй группы, выходы которых соединены с входами 1-го регистра, . управляющие входы элементов И переписи первой и второй групп обоих бло" ков сортировки соединены с входами соответственно записи и переписи устройства, в каждом блоке сортировки выходы узлов сравнения под.ключены к информационным входам элементов И соответственно первой, второй, третьей и четвертой групп соответствующего узла коммутации,в котором выходы элементов И первой и четвертой групп соеди.нены соответственно с первыми входами элементов ИЛИ первой группы, а выходы элементов И второй и третьей групп подключены соответственно к первым и вторым входам .эле" ментов ИЛИ второй группы, в каждом блоке сортировки выходы элементов ИЛИ первой и второй групп 1-го .узла коммутации, где 1= 1,2р/4, соединены с вторыми входами элементов ИЛИ соответственно К-йи (К+1)-й подгрупп, где К= 1,3,5,1193660 1 О 15 20 сортировки выходы К-го и +1)-горегистровсоединень 1 с соответствующими информационными входами элементов И соответственно 1-й и(1+1)-й подгрупп первой и второйгрупп 1-го дополнительного узлакоммутации, в котором выходы элементов И -й подгруппы второй группы соединены с первыми входамиэлементов ИЛИ 1-й подгруппы, выходы элементов И -й подгруппыпервой группы 1-го дополнительногоузла коммутации соединены с вторыми входами элементов ИЛИ (в /4+1-1)-йподгруппы (+1)-го дополнительногоузла коммутациивыходы подгруппэлементов ИЛП дополнительных узловкоммутации второго блока сортиров" Изобретение относится к цифровоивичислительной технике, в частности к устройствам сортировки кодов, и может быть использованодля быстрого упорядочения массивоп данных, представленных двоичными кодами,Цель изобретения - расширениеобласти применения путем обеспечения возможности сортировки произ"вольной последовательности кодов,которая за конечное количество шагов сводится к бимонотонной последовательности, и повышение быстродействи;, устройства.На чертеже показана структурная.схема устройства. Устройство содержит первый блок 1 сортировки, второй блок 2 сортировки, регистр 3, схему 4 сравнения, элемент И 5, элемент Ш 1 П 6, элемент И 7, узел 8 коммутации, элемент И 9, элемент И 10, элемент ИЛИ 11, дополнительный узел 12 коммутации, элемент И 13, ,элемент И 14, элемент ИЛИ 15, элемент НЕ 16, элемент НЕ 17, входы 18 .сортируемых чисел устройства, вход 19 записи, вход 20 переписи, вход 21 перекоммутации, вход 22 съема результатов сортировки. кИ подключены к вторым группам вхо-дов узлов сравнения соответственно,первого и второго блоков сортировки, вход перекоммутации устройства соединен с управляющими входами.элементов И всех подгрупп вторыхгрупп дополнительных узлов коммутации и через элемент НЕ - с управляющими входами элементов И всехподгрупп первых групп дополнительных узлов коммутации, вход съемарезультатов сортировки устройстваподключен к управляющим входамэлементов И первых и третьихгрупп узлов коммутации и через элемент НЕ - к управляющим входамэлементов И вторых и четвертых группузлов коммутации. Рассмотрим работу устройства в режиме сортировки ходов по возрастанию. Работа устройства выполняется за семь рабочих тактов.Б такте Со подаются сигналы на входы 18 устройства, связанные с первыми входами первой группы элементов И 5 на вторые входы которых поступает. единичный сигнал с входа 19 устройства, Каждый вход 18устройства представляет собой группу шин, на которые подаются сигналы, соответствующие сортируемым двоичным кодам. С выхода первых групп элементов И 5 сигналы поступают на первые входы первой группы .элементов ИЛИ 6, с выхода которых они передаются на первые входы вторых групп И 7, на вторые входы которых подаются единичные сигналы с входа 20 устройства. С выхода второй группы элементов И 7 сигналы передаются в регистры 3, После записи сигнала в регистры 3 единичный сигнал с входа 20 устройства снимается. Свыхода- регистров 3 первого блока 1сортировки сигналы поступают напервые входы схем 4 сравнения устройства. Схемы 4 сравнения выпол 30 няют сравнение двух кодов и выдачу меньшего из них на первый выход, а большего - на второй,ровк 3 1 8 6 7 3Во втором блоке 2 сортировки сиг" налы с выходов регистров 3 посту-. пают на входы второй .группы узлов 12 коммутации. Единичный сигнал, подаваемый на вход 21 устройства, поступает на вторые входы группы элементов И 10, на первые входы которых поступают сигналы с входа узлов 12 коммутацп, С выходов группы элементов И 10 сигналы поступают на первые входы элементов ИЛИ 11, с выходов которых сигналы поступают на вторые входы схем 4 сравнения. Единичный сигнал, подаваемый на вход 22 устройства, поступает на вторые входы третьих групп элементов И 13, на первые входы которых поступают, сигналы с выходов схем 4 сравнения. Сигналы с выходов третьих групп элементов И 13 поступают на вторые входы вторых элементов ИЛИ 15, с выхода которых они поступают на вторые входы первых элементов ИЛИ, с выхода которых они поступают на первые входы вторых групп, элементов И 7, подготавливая запись в регистры 3 новых значений кодов в следующем такте работы устройства С . В таблице приведены примеры сортировки произ. вольной последовательности кодов :чисел в .диапазоне 1-8, которые могут быть представлены двоичными кодами, записываемыми в регистры 3. Для каждого из тактов с;, = 0,61 приведены исходные расположения кодов по регистрам 3 устройства. В такте С подается очереднойуправляющий сигнал на вход 20 уст. ройства, который после записи врегистры 3 нового содержимогоснимается. Заметим, что единичные.сигналы на входах 21 и 22 устройства не снимались. Далее устройствофункционирует точно таким же образом, что и в такте С10 В тактеподается очереднойединичный сигнал на вход 20 устройства и функционирование устройства продолжается аналогично такту 1.В тактеподается очереднойединичный сигнал на вход 20 устройства и одновременно снимается единичный сигнал с входа 21 устройства,.изменяя тем самым логику работыустройства, так как с выхода эле-мента НЕ 16 единичный сигнал открываетпятыегруппы элементов И 9. В .-результате этого сигналы, поступающие на входы вторых узлов 12 коммутации, переключаются с помощью 25 .элементов И 9 в обратном порядке навторые входы третьих групп элементов ИЛИ 11. В тактах г. - й устройство функционирует аналогично такту Т, стой разницей, что вновь подаетсяединичный сигнал на вход 21 устройства, т.е. логика работы устройства восстанавливается.Динамика изменения содержимогорегистров 3 устройства по рабочим тактам представлена таблицей.ВНИИПИ Заказ 7315/51 Тираж одписное Филиал ППП "Патент", г,ужгород, ул,Проенгная, 4 3Для изменения режима функционирования устройства с целью упорядочения кодов по убыванию необходимо снять единичный сигнал с входа 22 устройства, вследствие чего входы и выходы первых групп схем 8 коммутации будут перекоммутированы в обратном порядке, с помощью единичного сигнала, поступающегос выхода элемента НЕ 17,. Заметим также, что на такте С последовательность кодов, записанных в регистрах 3, всегда являет 1193660 Ься бимонотонной. После такта 1 Зфункционирование устройства происходит аналогично функционированиюизвестного устройства, т,е. происходит упорядочение бимонотонной. последовательности кодов.Таким образом, в результате выполнения тактов- 1 произвольнаяпоследовательность кодов, поступаю 10 щая на входы 18 устройства, будетупорядочена по возрастанию или поубыванию в зависимости от значениявходного сигнала на входе 22 устройства.