Устройство для сортировки чисел Советский патент 1990 года по МПК G06F7/08 

СП 00

4

СО

со

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

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

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

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

сортировки

5

,где m - количество чисел сортируемого массива), каждый из которых содержит п приемных регистров 10, коммутатор 11, п регистров 12 результата, узел 13 сортировки и коммутатор 14.

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

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

35

40

45

Для каждого j-ro блока 9 сорти-v ровки (,,..,k) на J-M выходе блока 6 постоянной памяти формируется 4-разрядное управляющее слово, два старших разряда которого управляют коммутатором 1 1 ,. а два младщих - коммутатором 14. В зависимости от значе- ния информации на управляющих входах коммутаторов 11 и 14, они устанавливаются в положение, когда па их иы- ход поступает информация или с первых входов (информация на управляющих входах 00), или с вторых входов (информация на управляющих входах 0,1), или с третьих входов (информация на управляющих входах 10), или с четвертых входов (информация на управляющих входах 11), только для коммутаторов 11 .

Управляющая информация для коммутатора 11 блока 91 сортировки в блоке 6 постоянной памяти записана следующим образом: 00 - в ячейке по адресу 2J-1; 01 - в ячейках по адре50

0

5

0

5

0

5

40

45

50

сам с О по J-2 и с 2j по 2k-1 кроме блока 10 - в ячейках по адресам с j по 2(J-1), кроме 9( ; 11 - в ячейке по адресу j-1.

Управляющая информация для коммутатора 14 j-ro блока 9J сортировки в блоке постоянной памяти записана следующим образом: 00 - в ячейках по адресам с j по 2 (j-t), кроме блока 01 - в ячейках по адресам с О по (j - 1) и с 2J по (2k-l); 10 - в ячейке по адресу 2j-1.

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

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

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

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

мутатор 7 на передачу информации с второго входа; коммутаторы II и 14. блока 9 на передачу информации соответственно с нервого и третьего входов; коммутатор 1 1 блока 9 на передачу информации с четвертого входа; коммутаторы 1 блоков 9,,.,,9к и коммутаторы 1А блоков 92.,...,9 «-i на передачу информации с вторых входов. По переднему фронту второго тактового импульса происходит запись информации в регистры 10 и 12 в блоках 9,...,9 1 и увеличение содержимого счетчика 4 на единицу.

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

В первом блоке 9 сортировк-и п первых просортированных чисел с выходов регистров 12 и п вторых просортированных чисел с выходов регистров 10 поступают на входы узла 13 сортировки, где они сортируются и -поступают на выходы в порядке убывания, т.е. наибольшее число на пер- вом выходе, следующее по величине число на втором и т.д., наименьшее по величине на 2п выходе. С второй ячейки узла в постоянной памяти считывается третье управляющее слово, которое устанавливает: коммутатор 7 на передачу информации с третьего входа; коммутаторы 11 и 14 блока 9 на передачу информации соответственно с третьего и первого входов; коммутаторы 1 1 блоков 9, , 9 4, , . . , 9 к и коммутаторы 14 блоков 9,,9j,...,9 K.I а передачу информации с вторых вхоов.

По переднему фронту третьего так-i ового импульса происходит запись нформации в регистры 10 и 12 в локах 9 ,. . . , 9 |(; и увеличение содеримого счетчика 4 на единицу.

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

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

7493 6

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

Формула изобретения

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

п количество чисел сортируе20

30

35

мого массива, п - количество информационных входов устройства), причем 15 каждый блок сортировки содержит приемный регистр, регистр результатов и ком-i мутатор, синхровходы всех регистров всех блоков сортировки объединены и являются тактовым входом устройства,в каждом блоке сортировки выходы разрядов регистра результата соединены .с входами цервой группы коммутатора,выходы коммутатора (i-1 )-г:о блока сортировки (,...,k) соедине а 1 с информацион- 25 ными входами регистра i-ro блока сортировки, отличающееся тем, что, с целью повышения быстродействия, в него введены входной.узел сортировки, счетчик, блок памяти, выходной коммутатор, в (1-1)-й блок сортировки введены узел сортировки и второй коммутатор, в k-й блок сортировки введен узел сортировки, причем информационные входы чисел устройства соединены с выходами чисел входного узла сортировки, выходы чисел которого соединены с информационными входами приемного регистра первого блока сортировки, во всех блоках сор- 40 тировки выходы разрядов приемного регистра соединены с входами первых групп узла сортировки и второго коммутатора, выходы которого соединены с информационными входами регистра ре- 45 зультата, выходы разрядов которого соединены с входами второй группы узла сортировки, в (i-lj-x блоках сортировки выходы первой и второй групп узла сортировки соединены соответственно с входами второй и третьей групп первого и второго коммутаторов, выходы первой группы узла сортировки j-ro блока сортировки (j l,...,k) соединены с входами j-й 5 -группы выходного коммутатора, входы (k+l)-й группы которого соединены с. выходами разрядов регистры результата k-ro блока сортировки, в k-м блоке сортировки выходы Первой группы

0

15874938

узла сортировки соединены с входамиединен с тактовьм входом устройства,

второй группы второго коммутатора,а выходы разрядов соединены с вховходы второй группы узла сортировкидами блока памяти, j-й выход котосоединены с входами третьей и четвер-рого соединен с управляющими входатой групп второго коммутатора и сми первого и второго коммутаторов

входами четвертых групп коммутаторовj-ro блока сравнения, (k+|)-ft выход

(i-l)-x блоков сортировки, вход на-блока памяти соединен с управляющим

чальной установки устройства соеди-входом выходного комму татора, вынен с входом начальной установкиjg ход которого является выходом устсчетчика, счетный вход которого со-ройства.

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