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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ СОРТИРОВ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), во втором блоке

COOS СОЭЕТСНИХ

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

РЕСПУБЛИН

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

К АВТОРСКОМ У СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3738210/24-24 (22) 04.05.84 (46) 23. 11.85. Бюл. Р 43 (72) A.È. Захаров, В.Н. Кустов, И.В. Кнасницкий и В.В. Красавцев (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 1012239, кл. G,06 F 7/06, 1983.

Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.! .Наука, 1982, с. 11. (54)(57) УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ

СОРТИРОВКИ КОДОВ, содержащее два блока сортировки, каждый из которых содержит и/2 регистров и и /4 узлов

":сравнения, где n — число сортируемых кодов, причем выходы регистров первого блока сортировки подключе.ны к первым группам входов соответствующих узлов сравнения первого и второго блоков сортировки, о т л и ч а ю щ е е с я тем, что, с, целью расширения области применения.путем обеспечения возможности .сортировки произвольной последовательности кодов, в него введены первый и второй элементы НЕ, в каждый блок. сортировки введены первая и вторая группы из и /2 подгрупп элементов И переписи, группа из и /2 подгрупп элементов ИЛИ переписи,,й/4 узлов коммутации, каждый из которых содержит четыре группы элементов И и две группы элементов ИЛИ, во второй блок сортировки введены

fl./4 дополнительных узлов коммутации, каждый из которых содержит две группы элементов И по в /4 подгрупп элементов И в каждой и груп„„ЯО„„! 193660- А

1511 4 С 06 F 7/Об пу элементов ИЛИ из q/4 подгрупп элементов ИЛИ, причем входы, сортируемых чисел устройства соединены с информационными входами соответ" ствующих подгрупп элементов И переписи первых групп первого и второго блоков сортировки, в каждом блоке сортировки выходы элементов

И переписи 1-й подгруппы первой группы, где 1 = 1,2,..., p/2, соединены с первыми входами элементов ИЛИ i-й подгруппы, выходы которых соединены с информационными входами элементов И переписи 1-й подгруппы второй группы, выходы которых соединены с входами (-го регистра, . управляющие входы элементов И переписи первой и второй групп обоих блоков сортировки соединены с входами соответственно записи и переписи

1 устройства, в каждом блоке сортировки выходы узлов сравнения под.ключены к информационным входам элементов И соответствен1ло первой, второй, третьей и четвертой групп соответствующего узла коммутации, в котором выходы элементов И первой и четвертой групп соеди.нены соответственно с первыми входами элементов ИЛИ первой группы, а выходы элементов И второй и третьей групп подключены соответственно к первым и вторым входам .эле" ментов ИЛИ второй группы, в каждом блоке сортировки выходы элементов ИЛИ первой и второй групп j-ro . узла коммутации, где . 1 = 1,2,..., р/4, соединены с вторыми входами элементов ИЛИ соответственно K-й и (К+1)-й подгрупп, где К= 1,3,5, (и /2-1) во втором блоке

1193660

20 сортировки выходы К-го и (V,+1)-го регистров соединень1 с соответствующими информационными входами элементов И соответственно 1-й и (1+1)-й подгрупп первой и второй групп j-го дополнительного узла коммутации, в котором выходы элементов И 1 -й подгруппы второй группы соединены с первыми входами элементов ИЛИ 1-й подгруппы, выходы элементов И j-й подгруппы первой группы )-ro дополнительного узла коммутации соединены с вторыми входами элементов ИЛИ (n /4+1-1)-й подгруппы () +1)-ro дополнительного узла коммутации,,выходы подгрупп элементов ИЛП дополнительных узлов коммутации второго блока сортировИзобретение относится к цифровои вичислительной технике, в частности к устройствам сортировки кодов, и может быть использовано для быстрого упорядочения масси-. воп данных, представленных двоичными кодами, Цель изобретения — расширение области применения путем обеспечения возможности сортировки произ" вольной последовательности кодов, г которая за конечное количество шагов сводится к бимонотонной последовательности, и повышение быстродействи;, устройства.

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

Устройство .содержит первый блок 1 сортировки, второй блок 2 сортировки, регистр 3, схему 4 сравнения, элемент И 5, элемент

KI1I 6 элемент И 7, узел 8 коммутации, элемент И 9, элемент И 10, элемент ИЛИ 11, дополнительный узел 12 коммутации, элемент И 13, .элемент И 14, элемент ИЛИ 15, элемент НЕ 16, элемент НЕ 17, входы 18 .сортируемых чисел устройства, вход

19 записи, вход 20 переписи, вход

21 перекоммутации, вход 22 съема результатов сортировки. кИ подключены к вторым группам входов узлов сравнения соответственно ,первого и второго блоков сортировки, вход перекоммутации устройства соединен с управляющими входами .элементов И всех подгрупп вторых групп дополнительных узлов коммутации и через элемент НŠ— с управляющими входами элементов И всех подгрупп первых групп дополнительных узлов коммутации, вход съема результатов сортировки устройства подключен к управляющим входам элементов И первых и третьих групп узлов коммутации и через элемент НŠ— к управляющим входам элементов И вторых и четвертых групп узлов коммутации.

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

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

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

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

1193660

2 2 8 8 8 8 8 2 1 1 1 1 1 1 Блок 1 сорти7 1 2 2 1 5 7 7 2 5 4 8 3 2 ровки

5 7 5 4 7 4 6 5 6 2 5 4 5 3

4 6 1 2 3 1 5 4 7 8 6 7 8 4

Содержимое регистров

1 8 7 6. 5 7 4 1 5 4 2 3 2

6 5 4 5 4 6 3 6 8 6 3 5 4

8 4 6 3 6 3 2 8 4 3. 7 2 6

Блок 2

6 сортировки

3 3 3 1 2 2 1 3 3 7 8 6 7 8

Во втором блоке 2 сортировки сиг-налы с выходов регистров 3 посту-. пают на входы второй .группы узлов

12 коммутации. Единичный сигнал, подаваемый на вход 21 устройства, поступает на вторые входы группы элементов И 10, на первые входы которых поступают сигналы с входа узлов 12 коммутацш . С выходов группы элементов И t0 сигналы поступают на первые входы элементов ИЛИ 11, с выходов которых сигналы поступают . на вторые входы схем 4 сравнения.

Единичный сигнал, подаваемый на вход 22 устройства, поступает на вторые входы третьих групп элементов И 13, на первые входы которых поступают, сигналы с выходов схем 4 сравнения. Сигналы с выходов третьих групп элементов И 13 поступают на вторые входы вторых элементов

ИЛИ 15, с выхода которых они поступают на вторые входы первых элементов ИЛИ, с выхода которых

3 они поступают на первые входы вторых групп .элементов И 7, подготавливая запись в регистры 3 новых значений кодов в следующем такте работы устройства t . В таблице nput ведены примеры сортировки произ. вольной последовательности кодов

:чисел в диапазоне 1-8, которые могут быть представлены двоичными кодами, записываемыми в регистры 3.

Для каждого из тактов t;,i = 0,6

1 приведены исходные расположения ко дов по регистрам 3 устройства.

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

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

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

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

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

Динамика изменения содержимого регистров 3 устройства по рабочим тактам представлена таблицей.

ВНИИПИ Заказ 7315/51 Тираж 709 Подписное

Филиал ППП "Патент", r.Óæãoðîä, ул.Прое лная, 4

Для изменения режима функционирования устройства с целью упорядочения кодов по убыванию необходимо снять единичный сигнал с входа 22 устройства, вследствие чего входы и выходы первых групп. схем 8 коммутации будут перекоммутированы в обратном порядке, с помощью единичного сигнала, поступающего с выхода элемента НЕ 17,.

Заметим также, что на такте t последовательность кодов, записанных в регистрах 3, всегда являет1193660 ф ся бимонотонной. После такта t3 функционирование устройства происходит аналогично функционированию известного устройства, т.е. происходит упорядочение бимонотонной . последовательности кодов.

Таким образом, в результате выполнения тактов to — t произвольная последовательность кодов, поступаю10 щая на входы 18 устройства, будет упорядочена по возрастанию или по убыванию в зависимости от значения входного сигнала на входе 22 устройства.