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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени. Цель изобретения - повышение быстродействия. Устройство, имеющее вход 1 начальной установки, тактовый вход 2, N информационных входов 3, содержит узел 4 сортировки, счетчик 5, блок 6 памяти, коммутатор 7, K блоков 9 сортировки (K = M/N, где M - количество чисел сортируемого массива). Каждый блок 9 состоит из входного регистра 10, коммутатора 11, выходного регистра 12, узла 13 сортировки и коммутатора 14. Повышение быстродействия достигается за счет распараллеливания процесса сортировки. 1 ил.

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК (5))5 G 06 F 7/08

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР (2)) 4450384/24-24 (22) 27,06,88 (46) 23.08.90. Бюл. Р 31 (72) А.А, Мельник и И.Г. Цмоць (53) .681.325 (088,8) (56). Авторское свидетельство СССР

h . 1277090, кл . G 06 F 7/04, 1986.

Авторское свидетельство СССР

)1 - 1007099, кл, G 06 F 7/08, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов

„„SU„„1587493 A1

2 данных в реальном масштабе времени.

Цель изобретения — повышение быстродействия. Устройство, имеющее вход 1 начальной установки, тактовый вход 2, п информационных входов 3, содержит узел 4 сортировки, счетчик

5, блок 6 памяти, коммутатор 7, m блоков 9 сортировки (Ic = - где и количество чисел сортируемого масси-. ва) . Каждый блок 9 состоит иэ входного регистра 10 коммутатора. 11, выходного регистра 12, узла 13 сортировки и коммутатора 14. Повышение быстродействия достигается за счет распараллеливания процесса сортировки. 1 ил.

Ж 1587493

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

Цель изобретения — повышение быстродействйя.

На чертеже предстанлена функцио- lð нальная схема устройства для сортировки чисел.

Устройство содержит вход 1 начальной установки, вход 2 тактовых импульсов, п информационных входов 3, входной узел 4 сортировки, счетчик 5, блок 6 памяти, выходной коммутатор

7, выходы 8 устройства, k блоков 9

ITl сортировки (k = —,где m — количестп 20 во чисел сортируемого массива), кажР дый из которых содержит п приемных регистров 10, коммутатор 11, и реги ст. ров 12 результата, узел 13 сортиров— ки и коммутатор 14, 25

Устройство работает следующим образом.

Перед началом работы импульсом с входа 1 счетчик 5 устанавливается в нуль. Информация с выходов счетчи- 30 ка 5 поступает на адресные входы блока 6 памяти, в котором записана программа управления коммутатором 7 и коммутаторами ll и 14 в блоках 9,...

К

Для каждого j-го блока 9 сорти- ровки (j=l,. .,k) íà j-м выходе блока

6 постоянной памяти формируется 4-разрядное управляющее слово, два старших разряда которого управляют коммутатором ll а два младших — коммутатором 14. В зависимости от значения информации на управляющих входах коммутаторов 11 и 14, они устанавливаются в положение, когда на их выход поступает информация или с первых входов (информация на управляющих входах 00), или с вторых входов (информация на управляющих входах

0,1), или с третьих входов (информация на управляющих входах 10), или с четвертых входов (информация на управляющих входах 11), только для коммутаторов 11, Управляющая информация для коммутатора 11 j-го блока 9 „ сортировки н блоке 6 постоянной памяти записана следующим образом. 00 — в ячейке по адресу 2j-1; 01 — в ячейках по адресам с О по j 2 и с 2j по 2k-1 кроме блока 9<; 10 в ячейках по адресам с j по 2 (1-1), кроме 91, l l — в ячейке по адресу j — l

Управляющая информация для коммутатора 14 j-ro блока 9 сортировки

1 и блоке постоянной памяти записана следующим образом: 00 — в ячейках по адресам с j по 2 (j — 1), кроме блока 91; 01 — в ячейках по адресам с О по (j — 1) и с 2j по (2k-1); 10 в ячейке по адресу 2j-l.

С (k+1)-ro выхода блока бпамяти считывается управляющая информация для коммутатора 7, При поступлении на управляк щий вход коммутатора 7 информации, равной (1-1), где 1 = 1, 2,...,k + 1, на выход коммутатора поступает информация с 1-ых входов.

Управляющая информация для коммутатора 7 в блоке постоянной памяти записана следующим образом: в ячейке по адресу (3-1) записано число (j — 1); в ячейках по адресам с k по 2k-2 записано число k-1; в ячейке по адресу

2k-1 записано число k.

В первом такте п чисел первого сортируемого массива с входа 3 поступают .на входы узла 4 сортировки, где они сортируются и поступают на выход в порядке убывания, т,е. наибольшее число будет на первом выходе, следующее по величине число на втором выходе и т.д., наименьшее на п-ì выходе, С нулевой ячейки блока 6 постоянной памяти считывается первое управляющее слово, которое устанавливает: коммутатор 7 на передачу информации с первого входа; коммутатор

11 блока 9 на передачу информации с четвертого входа; коммутаторы 11 блоков 9,...,9 к и коммутаторы 14 блоблоков 9 .. .,9 к на передачу информации с второго входа.

По переднему фронту первого тактового импульса происходит запись информации в регистры 10 и 12 в блоках 9 . ..9 к и увеличение содержимого счетчика 4 на единицу. !

Во втором такте п следующих чисел первого сортируемого массива поступают на входы узла 4 сортировки, на выходе которого получаем просортированные числа в порядке убывания. С первой ячейки блока 6 постоянной памяти считывается второе управляющее слово, которое устананлинает: ком1587493

55 мутатор 7 на передачу информации с второго входа; коммутаторы ll и 14. блока 9„ на передачу информации соответственно с первого и третьего входов; коммутатор 11 блока 9 на передачу информации с четвертого входа, коммутаторы ll блоков 9»,...,9к и коммутаторы 14 блоков 9,...,9 к» на передачу информации с вторых входов. По переднему фронту второго тактового импульса происходит запись информации в регистры 10 и 12 в блоках 9»,...,9 », и увеличение содержимого счетчика 4 на единицу, В третьем такте и следующих чисел первого сортируемого массива поступают на входы узла 4 сортировки,где они сортируются в порядке убывания, В первом блоке 9» сортировки п первых просортированных чисел с выходов регистров 12 и п «торых просортированных чисел с выходов регистров 10 поступают на входы узла

13 сортировки, где они сортируются и .поступают на выходы в порядке убывания, т.е. наибольшее число на первом выходе, следующее по величине число на втором и т.д,, наименьшее по величине на 2п выходе. С второй ячейки узла в постояшюй памяти считывается третье управляющее слово, которое устанавливает: коммутатор 7 на передачу информации с третьего входа; коммутаторы 11 и 14 блска 9 < на передачу информации соответственно с третьего и первого входов; коммутаторы 11 блоков 9»,9 4,...,9 к и коммутаторы 14 блоков 9»,9, ° ..,9 к» на передачу информации с вторых входов i

По переднему фронту третьего так-в тового импульса происходит запись информации в регистры 10 и 12 в блоках 9»,. ° .,9 »» и увеличение содержимого счетчика 4 на единицу.

В следующих тактах устройство работает аналогично !

После 2k-rn тактового импульса счетчик 5 устанавливается в нуль, в регистрах 10 и 12 устройства размещены числа первого частично просортированного массива, причем на выход коммутатора 7 поступает и наибольших чисел первого массива. IIo приходу следующих тактовых импульсов одновременно с сортировкой и выводом результатов сортировки первого

45 массива производится ввод и сортировка второго массива и т.д. Числа, просортированные в порядке убывания, снимаются с выхода 8, Формула изобретения

Устройство для сортировки чисел, содержащее k блоков сортировки, где

m — (m — количество чисел сортируеи мого массива, n — количество информационных входов устройства), причем каждый блок сортировки содержит приемный регистр, регистр результатов и ком-, мутатор, синхровходы всех регистров всех блоков сортировки объединены и являются тактовым входом устройства,в каждом блоке сортировки выходы разрядов регистра результата соединены .с входами первой группы коммутатора,выходы коммутатора (i-I)-го блока сортировки (i=2.... k) соединены с информационныл»и входами регистра д-го блока сортировки, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия., в него введены входной. узел сортировки, счетчик, блок памяти, выходной коммутатор, в (i-1)-й блок сортировки введены узел сортировки и второй коммутатор, в k-й блок сортировки введен узел сортировки, причем информационные входы чисел устройства соединены с выходами чисел входного узла сортировки, выходы чисел которого соединены с информационными входами приемного регистра первого блока сортировки, во всех блоках сортировки выходы разрядов приемного регистра соединены с входами первых групп узла сортировки и второго коммутатора, выходы которого соединены с информационными входами регистра результата, выходы разрядов которого соединены с входами второй группЫ чэла сортировки, в (i-1)-х блоках сортировки выходы первой и второй групп узла сортировки соединены соответственно с входами второй и третьей групп первого и второго коммутаторов, выходы первой группы узла сор" тировки j-го блока сортировки (j

=l,...,k) соединены с входами j-й группы выходного коммутатора, входы (k+I)-й группы которого соединены с, выходами разрядов регистры результата k-го блока сортировки, в k-м блоке сортировки выходы первой группы

1587493

Составитель В. Козлов

Редактор Н. Яцола Техред H.яндык

Корректор M. Максимишинец

Заказ 2420 Тираж 563 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. /5

Производственно-издательский комбинат "Патент",. г.ужгород, ул. Гагарина,101 узла сортировки соединены с входами второй группы второго коммутатора, входы второй группы узла сортировки соединены с входами третьей и четвертой групп второго коммутатора и с входами четвертых групп коммутаторов (i-1)-х блоков сортировки, вход начальной установки устройства соединен с входом начальной установки 10 счетчика, счетный вход которого соединен с тактовым входом устройства, а выходы разрядов соединены с входами блока памяти, j-й выход которого соединен с управляющими входами первого и второго коммутаторов

j-го блока сравнения, (k+1)-й выход блока памяти соединен с управляющим входом выходного коммутатора выход которого является выходом устройства.