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

сортировки выходы к-го и (k+1)-ro регистров-соединень4 с соответствую щими информационными входами элементов И соответственно j-й и (j + 1)-ft подгруп а первой и второй групп j-ro дополнительного узла коммутации, в котором выходы элементов И j-й подгруппы второй груп пы соединены с первыми входами элементов 11Ш j-й подгруппы, выходы элементов И j-й подгруппы первой группы -j-ro дополнительного узла коммутации соединены с вторыми входами элементов ИЛИ (n/4+i-j) подгруппы (j+1)-ro дополнительного узла ко№-1утации, выходы .подгрупп элементов ИЛИ дополнительных узлов ко 4мутации второго блока сортиров0Krf подключены к вторым группам вхо дов узлов сравнения соответственно .первою и второго блоков сортировки, вход перекоммутации устройства соединен с управляющими входами элементов И всех подгрупп вторых групп дополнительных узлов коммутации и через элемент НЕ - с управляющими входами элементов И всех подгрупп первых групп дополнительных узлов коммутации, вход съема результатов сортировки устройства подключен к управляющим входам элементов И первых и третьих групп узлов коммутации и через элемент НЕ. - к управляющим входам .элеме 1тов И вторых и четвертых групп узлов коммутации.

УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ СОРТИРОВ1Ш КОДОВ, содержащее два блока сортировки, каждый из которых содержит ti/2 регистров и п/4 узлов .сравнения, где п- число сортируемых кодов, причем выходы регистров первого блока сортировки подключены к первым группам входов соот- ветствующих узлов сравнения первого и второго блоков сортировки, отличающееся тем, что, с. целью расширения области примедгения путем обеспечения возможности сортировки произвольной последовательности кодов, в него введены первьй и второй элементы HEj в каждый блок сортировки введены первая и вторая группы из п/2 подгрупп элементов И переписи, группа из п/2 подгрупп элементов ИЛИ переписи, .Л/4 узлов коммутации, калда ый из которых содержит четыре группы элементов И и две группы элементов ИЛИ, в.о второй блок сортировки введены fV/4 дополнительных узлов коммутации, каждый из которых содержит две группы элементов И по п/4 подгрупп элементов И в каждой и группу элементов ИЛИ из п/4 подгрупп элементов ИЛИ, Причем входы.сортируемых чисел устройства соединены с информационными входами соответствующих подгрупп элементов И переписи первых групп первого и второго блоков сортировки, в каждом блоке сортировки выходы элементов : И переписи i-й подгруппы первой группь1, где i 1,2,..., , соединены с первыми входами элементов ИЛИ i-й подгруппы, выходы которых соединены с информационными входами элементов И переписи i-й подгруппы второй группы, выходы которых соединены с входами {-го регистра, управляющие входы элементов И пере(/} писи первой и второй групп обоих блоков сортировки соединены с входами соответственно записи и переписи устройства, в каждом блоке сортиров§ ки выходы узлов сравнения подключены к информационньм входам элементов И соответственно первой, СО второй, третьей и четвертой групп со соответствующего узла коммутации, О) в котором выходы элементов И первой и четвертой групп соедиОд нены соответственно с первыми входами элементов ИЛИ первой группы, а выходы элементов И второй и третьей групп подключены соответственно к первым и вторым входам элементов ИЛИ второй группы, в каждом блоке сортировки выходы элементов ИЛИ первой и второй групп f-ro узла коммутации, где - j 1,2,..., ti/4, соединены с вторыьш входами элементов ИЛИ соответственно К-й и (К+1)-й подгрупп, где ,3,5, ...,(п/2-1), во втором блоке

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

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

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

Устройство содержит первый блок 1 сортировки, второй блок 2 сортировки, регистр 3, схему 4 сравнения, элемент И 5, элемент ШИ1 6, элемент И 7, узел.8 коммутации, элемент И 9, элемент И 10, элемент ИЛИ 11, дополнительный узел 12 коммутации, элемент И 13, -элемент И 14, элемент ИЛИ 15, элемент ИЕ 16, элемент НЕ 17, входы 18 сортируемых чисел устройства, вход 19 заимей, вход 20 переписи, вход 21 нерекоммутации, вход 22 съема результатов сортировки.

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

В такте t подаются сигналы на входы 18 устройства, связанные с первыми входами первой группы элементов И 5,,на вторые входы которых поступает, единичный сигнал с вхО-

да 19 устройства. Каждый вход 18 устройства представляет собой группу шин, на которые подаются сигналы, соответствующие сортируемым двоичным кодам. С выхода первых групп элементов И 5 сигналы поступают на первые входы первой группы элементов ИЛИ 6, с выхода которых они передаются на первые входы вторых групп И 7, на вторые входы которых

подаются единичные сигналы с входа 20 устройства. С выхода второй группы элементов И 7 сигналы передаются в регистры 3. После записи сигнала в регистры 3 единичньш сигнал

с входа 20 устройства снимается. С выхода регистров 3 первого блока 1 сортировки сигналы поступают на первые входы схем 4 сравнения устройства. Схемы 4 сравнения выполняют сравнение двух кодов и выдачу меньшего из них на первый выход, а большего - на второй.

31

Во втором блоке 2 сортировки сигналы с выходов регистров 3 поступают на входы второй группы узлрв 12 коммутации. Единичный сигнал, подаваемый на вход 21 устройства, поступает на вторые входы группы элементов И 10, на первые входы которых поступают сигналы с входа узлов 12 коммутации. С выходов группы элементов И 10 сигналы поступают на первые входы элементов ИЛИ 11, с выходов которых сигналы поступают на вторые входы схем 4 сравнения. Единичный сигнал, подаваемый на вход 22 устройства, поступает на вторые входы третьих групп элементов И 13, на первые входы которых поступают .сигналы с выходов схем .4 сравнения. Сигналы с выходов третьих групп элементов И 13 поступают на вторые входы вторых элементов ИЛИ 15, с выхода которых они поступают на вторые входы первых элементов ШШ, с выхода которых они Поступают на первые входы вторых групп .элементов И 7, подготавливая запись в регистры 3 новых значений кодов вследующем такте работы устройства t . В таблице приведены примеры сортировки произвольной последовательности кодов чисел в диапазоне 1-8, которые могут быть представлены двоичными кодами, записываемыми в регист ры 3. ля из тактов t- i 0,6 риведены исходные расположения коов по регистрам 3 устройства.

193660

В такте Ц подается очередной

управляющий сигнал на вход 20 устройства, который после записи в регистры 3 нового содержимого

снимается. Заметим, что единичные сигналы на входах 21 и 22 устрой-ства не снимались. Далее устройство функционирует точно таким же обра.зом, что и в такте t,

В такте t подается очередной единичный сигнал на вход 20 устрой- ства и функционирование устройства продолжается аналогично такту t. В такте Ц подается очередной

единичный сигнал на вход 20 устройства и одновременно снимается единичный сигнал с входа 21 устройства, изменяя тем самым логику работы устройства, так как с выхода элемента НЕ 16 единичный сигнал открывает пятые группы элементов И 9. В результате этого сигналы,.поступающие на входы вторых узлов 12 коммутации, переключаются с помощью

.элементов И 9 в обратном порядке на вторые входы третьих групп элементов ИЛИ 11.

В тактах t устройство функционирует аналогично такту t, с той разницей, что вновь подается едшшчньш сигнал на вход 21 устрой ства, т.е. логика работы устройства восстанавливается.

Динамика изменения содержимого регистров 3 устройства по рабочим тактам представлена таблицей. Для изменения режима функционирования устройства с целью упорядо чения кодов по убыванию необходимо снять единичный сигнал с входа 22 устройства, вследствие чего входы выходы первых групп- схем 8 коммутации будут перекоммутированы в обратном порядке, с помощью единич иого сигнала, поступающего с выхода элемента НЕ 17.. Заметим также, что на такте Ц последовательность кодов, записанных в регистрах 3, всегда являет606ся бимонотонной. После такта ta функционирование устройства происходит аналогично функционированию известного устройства, т.е. происходит упорядочение бимонотонной последовательности кодов. Таким образом, в результате вьшолнения тактов t - t произвольная последовательность кодов,поступаю.щая на входы 18 устройства, будет упорядочена по возрастанию или по убыванию в зависимости от значения входного сигнала на входе 22 устройства.