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

 

Изобретение относится к вычислительной технике. Цель изобретения - уменьшение аппаратурных затрат. Устройство содержит информационные входы 1. 2, тактовый вход 3, вход 4 начальной установки, вход 5 задания количества сортируемых чисел , мультиплексоры 6-9, блок сравнения 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, блоки памяти (БП) 12, 13.17,18, регистры 14,15. 16, триггер 19, счетчики 20,21, элемент ИЛ И 22, элемент И 23, выходы 24, 25, 26. Числа поступают по входам 1 и 2 и записываются в БП 12 и 13. Затем из БП 12 и 13 происходит выборка двух чисел, сравнение их и запись по тем же адресам в БП 12 и 13, возможна их перестановка в зависимости от результата сравнения. Порядок выборки (адреса БП 12 и 13) задается алгоритмом, хранящимся в БП 17 и 18, выполненных в виде ПЗУ. 3 ил.

СОЮЗ СОВЕТСКИХ социАлистических

РЕСПУБЛИК (51)5 G 06 F 7/06 госудАРственное пАтентное

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ (21) 4786033/24 (22) 25.01.90 (46) 30.12.92. Бюл. N. 48 (71) Львовский научно-исследовательский радиотехнический институт (72) А.А,Мельник (56) Авторское свидетельство СССР

N 1123030, кл, G 06 F 7/06, t984.

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

N 1298737, кл, G 06 F 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Цель изобретения — уменьшение аппаратурных затрат. Устройство. Ж» 1784966 Al содер>кит информационные входы 1, 2, тактовый вход 3, вход 4 начальной установки, вход 5 задания количества сортируемых чисел, мультиплексоры 6-9, блок сравнения

10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, блоки памяти (БП) 12, 13, 17, 18, регистры 14, 15, 16, триггер 19, счетчики 20, 21, элемент ИЛ И

22, элемент И 23, выходы 24, 25, 26. Числа поступают по входам 1 и 2 и записываются в БП 12 и 13. Затем из БП 12 и 13 происходит выборка двух чисел, сравнение их и запись по тем >ке адресам в БП 12 и 13, возможна их перестановка в зависимости от результата сравнения. Порядок выборки (адреса БП

12 и 13) задается алгоритмом, хранящимся в БП 17 и 18, выполненных в виде ПЗУ. 3 ил.

1784966

3 . 4

Изобретение относится к вычислитель- соединен с входом триггера 19, первым ной технике и может быть использовано в входом схемы 22 ИЛИ и счетным входом, вычислительных системах для решения за- " счетчика 21, выходкоторого соединен с втодач сортировки чисел. .. ::, рым входом блока 18 постоянной памяти и

Цель изобретейия — уменьшение аппа- 5 вторым входом блока 17 пастояйной памяти, ратурных затрат.".:.:.. :-:: :::..- ::,:,:. " первый вход которого соедийен с выходом

На фиг. 1 йредставлена схема устройст- . регистра 16, вход xoxoporo соединен с вхова для сбфтировки чисел; на фиг. 2 — граф, ",дом5устройства, вход сбросэтриггера19и алгоритма сортировки; на фиг. 3 - блочная счетчика 21 соединяй с входом 4 устройства структура графа алгоритма сортировки .. 10 и вторым входом схемы 22 ИЛИ, информа- ..

Устройство для"бЪртЪровки чисел со- " ционный вход счетчика 20 соедийен с пер-: дер>кит . информационные входы 1,2, такта- вым выходом блока 17 постоянной памяти, вый вход 3 вход 4 начальной установки, второй ebixop, которого соединен c ïåðâûì

„вход5задайия количества,сортируемыхчи- входом схемы 23 И, второй:вход которой сел, двухвходовые мультиплексоры 6 — 9, 15 соединен с входом.3 устройства, схему 10 сравнения, схему 11 ИСКЛ.ЮЧАЮ-:: : Счетчик 20 служит для подсчета количЕLUEE ИЛИ, блоки 12, 13 оператйвной памя-, ства выполненных тактов на одном этапе ти, регистры 14 — 16, блоки 17, 18 постоянной алгоритма сортировкй и работает в режиме памяти,триггер19,счетчики20,21,схему22 вычитания. С ка>1кдым тактовым импуль-.

ИЛИ; схему 23 И, выходй24 — 26. :, 20 сом, поступающим по входу 3, из содержиВход 1 устройства соединен с первым: мого счетчика 20 вычитается единица. информационным : входОм мультиплексора .. Счетчик 21 служит для" подсчета количества

6, второй информационный вход которого . выполненйых этапов алгоритма сортйрьвки соединен с выходом 24 устройства и выхо-: и работает в"режиме сложения. Как только. дом регистра 14, вхад которого соединен q 25 содержимое счетчика 20 становится равным выходом блока 12 оперативной nàìëòè, ин:- ", нулю, чта говорит об окончании вьгполненйя формационный. вход которого соедйнен с " "этайа, сигнал с et o выхода поступает на счетныходом мультиплексора 8, первыи ин- " ный вход счетчика 21 и прибавляет к его формацйонный вход которого соедийей с — содер>кимому единицу. вйходом мультиплексора 6, вторым инфор- 30 В блоке 17 постоянной памяти зашито мационным входом мультиплексора 9 и вто- количество тактов вь полняемых на каждом рым входом схемы 10 сравнения; первый: из этапов алторитма сортировки в завйсивхад которой соединен с вторым инфарма-.. мости от количества N сортируемых чисел. ционным входам мультийлексора 8, первым, Адресом блока 17 служит содержимое региинформационным входом мультиплексора 35 стра 16. в котором храйится значение й, и

9 и выходам мультиплексора 7, первый ин- содержимое счетчика 21,:в. катарам указан формациоййый вход которого соединен c номер выполняемого этайа. Кроме того, в входом 2 устройства, а второй информаци- одном разряде блока 17 йостоянной памяти онный вход которого соединен с выходом хранится значение. управляемое схемой . устройства 25 и выходом регистра 15; вход 40 23 И, Если в Данном разряде записана которого соединен,с выходом блока 13 one-. единица, схема 23 И открыта и через нее ративйой памяти, информационный вход .проходят тактовые импульсы с входа 3 ускоторого соединен с выходом мультййлек- тройства. Если в данном разряде записан сора 9, управляющий вход которого соеди- ноль, схема 23 И закрыта. Это бйвает в нен с управляющим входом мультиплек- 45 случае, когда выполнилась последняя итесора 8 и выходом схемы 1.1 ИСКЛЮЧАЮ- рация для данного N и устройство завершиЩЕЕ ИЛИ, первый вход которой соединен. - ло сортировку чисел. По шине 26 данный с выходом схемы 10 сравнения, а второй сигнал поступает йэ выход устройства, со вход соедйнен с первым выходом блока 18 общая d готовнастй к сортировке следу ощепостоянной памяти, второй выход которого 50 ro:массива чисел. соединен с адресным входом блока 13 one- . В блоке 18 постоянной памяти запиративной памяти, вход зайиси/считьва-: саны адреса, по которым производится ния которогосоединенсвыходомсхемы23И, считывание и запись операндов в блоки счетным входом счетчика.20, синхровхода- . оперативйой памяти 12, 13 в каждом такте ми регистров 14, 15 л вйходом записи/счи- 55 на всех выполняемйх- этапах. Адресом блотывания блока 12 оперэтйвной памяти, ка l8 служит содержимое счетчиков 20 и 21. адресный вход которого соединен стретьйм Кроме того, в одном разряде блока 18 по-., выходом блока 18 постоянной памяти, пер- стоянной памяти записан сигнал, поступавый вход которого соединен с первым вьixo- ющий на схему 11 ИСКЛЮЧАЮЩЕЕ ИЛИ, дом счетчика 20, второй выход которого

1784966 которая управляет прохо>кдением информации через мультиплексоры 8, 9.

Алгоритм сортировки Бетчера, реализуемый устройством, ориентирован на сорти)>овку количества чисел N, кратного степени

2. Поэтому разрядность регистра 16 равна

l = 1ogz()og2 Ивах- 1), где Мтах максимальный размер сортируемого массива чйсел на устройстве. Разрядность счетчика 20 m =

=)092 Nmax - 1, разрядность счетчика 21 К

=)ogq()ogz йп х()о92) )и х+ 1)(, где )х(обозначает большое целое число Х.

Устройство для сортировки чисел работает следующим образом, На входе 5 задается код количества N сортируемых чисел;

f1o входу 4 поступает сигнал начальной установки, который устанавливает триггер

19 и счетчик 21 в состояние "0", в регистр 16 записывается код N, à s счетчик 20 из блока

17 значение количества тактов, выполняемых на первом этапе (данное значение равно N/2, так как на первом этапе произ-. водится запись. в процессор сортируемых чисел по двум каналам). Затем по входам 1, 2 в процессор поступают сортируемые чис ла, а по входу 3 таковые импульсы, поступающие через схему 23 И на си хровходы регистров 14, 15, счетный вход счетчика 20. и входы записи/считывания блоков 12, 13; оперативной памяти;

На первом эта пе осуществляется прием входной информации и выполнение первого этапа алгоритма сортировки Бетчера. блок-схема которого для N = 8 показана на фиг. 2. Сигнал "ноль" с выхода триггера 19 пропускает на выходы мультиплексоров 6, 7 данные с входов 1, 2. На первом такте первая пара чисел поступает на входы мультиплексоров 8, 9 и на входы схемы 10 сравнения. В зависимости от того, какое

; число больше — на входе 1 или на входе 2— схема 10 сравнения вырабатывает значение логического нуля или единицы; Сигнал с выхода схемы 10 сравнения проходит через схему 11 ИСКЛЮЧАЮЩЕЕ ИЛИ и поступает на управляющий вход мультиплексоров

8. 9. Через мультиплексор 9 проходит на вход блока 13 большое число, а через мультиплексор 8 проходит на вход блока 12 меньшее число. В этом случае на второй вход схемы 11 ИСКЛЮЧАЮЩЕЕ,ИЛИ поступает из блока 18 сигнал логического нуля, Если же из блока 18 постоянной памяти поступает сигнал логической единицы, то схема 11 ИСКЛЮЧАЮЩЕЕ ИЛИ инвертирует сигнал с выхода схемы 10 сравнения и на входы блоков 12, 13 поступают соответственно большее и меньшее числа.

Таким образом, на блоках 6-11 устройства выполняется базовая операция алго15

20 регистров 14, 15

35

40. содер>кимого счетчика 20 вычитается едини55

10

50 ритма сортировки Бетчера. По высокому потенциалу тактового импульса в блоки 12, 13 оперативной памяти по адресам, поступающим из блока 18 постоянной памяти записывается первая пара входных чисел, Задним фронтом первого тактового импульса из содержимого счетчика 20 вычитается единица.

Во втором такте аналогично производится запись в блоки 12, 13- оперативной памяти второй пары чисел, а. из содержимого счетчика 20 снова вычитается единица.

После приема последней N/2-й пары чисел содер>кимое с етчика 20 становится равным нулю, что говорит о завершении первого этапа. Сигнал с выхода счетчика 20, поступает на счетный вход счетчика 21, прибавляя к ето содержимому единь цу; проходит через схему 22 ИЛИ, записывая из блока 17 в счетчик ".2 количество тактов, выполняемых на втором этапе. а также устанавливает триггер 19 в состояние "1". Сигнал с выхода триггера 19 переключает мультиплексоры 6

7, пропуская на их выходы информацию C

На втором этапе низким потенциалом первого тактового импульса из блоков 12, 13 оперативной памяти. по адресам из блока

18 считывается первая пара чисел, которая положительным фронтом импульса записывается в регистры 14, 15.:На блоках 6-11 выполняется базовая операция алгоритма сортировки Бетчера, и высоким потенциалом импульса по тем же адресам в блоки 12, 13 оперативной памяти "записывается большее и меньшее числа, причем выбор блока оперативной памяти определяется структурой алгоритма сортировки. Задним фронтом первого тактового импульса из ца.

Во втором такте аналогично выполняется вторая базовая операция алгоритма сортировки, а из содержимого счетчика 20 снова вычитается единица. После выполнения последней..базовой операции второго этапа содержимое счетчика 20 становится равным нулю, что говорит о завершении второго этапа. Сигналом с выхода счетчика

20 производится прибавление к содержимому счетчика 21 единицы и запись через схему 22 ИЛИ s счетчик 20 количества тактов, выполняемых на третьем этапе.

Аналогично описанному выполняется третий, четвертый и последующие этапы. На последнем этапе производится выгрузка просортированных данных из блоков 12, 13 оперативной памяти через регистры 14, 15 на выходы 24, 25. После выгрузки последней пары чисел содержимое счетчика 20 стано1784966

15

30

55 вится равным нулю.и сигнал с его выхода прибавляет к содер>кимому счетчика 21 единицу, информация с выхода счетчика 21 поступает ча блок 17 постоянной памяти и с его выхода на схему 23 И поступает сигнал

"0", который закрывает ее и прекращается подача тактовых импульсов на соответствующие блоки устройства. На выход 26 поступает сигнал о завершении сортировки чи сел.

Граф алгоритма сортировки может быть представлен в блочном виде (фиг. 3) состоящим из трех блоков, что позволяет сформировать правило его построения, а также разработать программу расчета содержимого блока 18 постоянной памяти управляющего схемой 11 и формирующего адреса блоков 12, 13 оперативной памяти. Блоки А, В выполняют сортировку N/2 чисел, а блок

С вЂ” их слияние. Каждый из блоков А, В снова можно разбить на три блока такого >ке типа, только обрабатывающие в ..2 раза меньше чисел и т,д., аж до двухвходовых блоков (базовой операции). Каждый третий блок содержит Iog К-1 этапов. где К вЂ” количество входов блока, Содержимое разряда блока 18 постоянной памяти, управляющего схемой II. pacсчитывается следующим образом. Для первого этапа вычисления блоков С, входящих в блоки А, включая N-входовой, сигнал управления схемой II равен О, а для остальных этапов -1, Сигналы же управления схемой 1! при выполнении итерации блоков В зеркально симметричны соответствующим значениям для блоков А. На фиг, 2 в качестве примера над кружками базовых операций показаны значения сигналов управления схемой II для графа сортировки 8 чисел.

Содержимое двух последних выходов 40 блока -18 постоянной памяти, являющееся адресами блоков 12. 13 оперативной памяти, рассчитывается по следующему алгоритму: задать (произвольно, или исходя из удобства работы) начальчые адреса записи входных данных в блоки 12, 13 оперативной памяти; определить значение сигнала управле ния схемой!! для всех тактов работы устройства; нарисовать граф алгоритма сортировки для заданного примера массива; возле каждой базовой операции алгоритма на графе проставить значение сигнала управления схемой Il; задать на выходах графа алгоритма номер ячейки (адрес), куда записывается число;

6 проставить на обоих входах каждой базовой операции на графе алгоритма номер блока памяти и адрес, по.которому записывается число, При этом исходить из следующего: если возле данной базовой операции сигнал управления схемой II равен 0 — большее число записывается в блок 13 оперативной памяти, меньшее — в блок 12 оперативной памяти, по тем же адресам, по которым считывались оба числа. Если же сигнал управления схемой It равен 1, большее число записывается в блок 12, а меньшее — в блок 13.

На фиг, 2 показан пример формирования адоесов для N = 8. Здесь через А обозначен блок 12 оперативной памяти, через

 — блок 13 оперативной памяти. По адресам на выходах графа считываются выходные данные.

В таблице в качестве примера приведено потактное состояние устройства для следук>щих пэр входных чисел: 5, 8: 6, 3; I, 2;

4,7;

По сравнению с прототипом на предлагаемое устройство требуются существенно меньшие затраты оборудования. Так, если необходимо выполнить сортировку 1024 чисел, то на реализацию прототипа потребуется 116050 мультиплексоров и 58025 схем сравнения, тогда как для предлагаемого устройства при увеличении N увеличиваются только объемы оперативной и постоянной памяти. -.

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

Устройство для сортировки чисел, содержащее четыре мультиплексора и блок сравнения, причем информационные входы первой и второй групп устройства соединены с информационными входами первой группы соответственно первого и второго мультиплексоров, выходы которых соединены с информационными входами соответственно первой и второй групп третьего мультиплексора и блока сравнения. а также с информационными входами соответственно второй и первой групп четвертого мультиплексора, управляющие входы третьего и четвертого мультиплексоров объединены, отл ич а ю щеес ятем, что, C целью уменьшения аппаратурных затрат, оно содер>кит четыре блока памяти, три регистра, два счетчика, триггер, элемент. И, элемент ИЛИ и.элемент ИСКЛЮЧАЮЩЕЕ

ИЛИ, причем выходы третьего и четвертого мультиплексоров соединены с информациоНными входами соответственно первого и второго блоков памяти, выходы которых соединены с информационными входами соответственно первого и второго регистров, выходы разрядов которых являются информационными выходами соответственно

1784966:.

1:О

C. первой и второй групп устройства и: соеди-: разрядов которого соедийены с адресными нены с информацйонными,входами вторых, - входами первой группы четвертого блока групп соответственно йервого и второго, памяти, адреснь1е входы второй группы комультиплексороe, уйравляющие входы ко- ::: торого соединены с выходами разрядов втоторых подключены к выходу триггеравходы . 5 рого счетчика и адресными входами второй установки в нулевое и-единичное состоявшие группы третьего блока .памяти., выход кото- которого подключены соответствейно"к пер-".:;: .- рого являегся выходом okончания работы вому и второму входам элемента ИЛИ, вы -: ., устройства -и" соединен с первым входом ход которого соединен с входом установки элемента И; вьи од которого соединен со в нулевое состояние первого счетчика, вы- 10 счетным входом первого. ечетчика, входа- ход переполнения которого соединен с пер- " ми синхронизации первого и.второго реги вым входом элемента ИЛИ- и счетным ". стров и управляю@йми входами первого. и входом второго счетчика, вход установки в, второго блоков памяти, адресные входы нулевое состояние которого соединен с которых соедийены С выходами cîoòâåòñòвторым входом элемента ИЛИ и входом 15 венно первой и второй групп четвертого начальной установки устройства, входы . блока памяти; выход которого и выход задания количества сортируемых чисел ус- блока сравнейия соединенй соответствен- тройства соединены с информационными но с первым и вторым входами"элемента входами третьего регистра, выходы разря- ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого дов которого соединены с адресными вхо- 20 соединен с управляющим входом третьедами первой группы третьего блока памяти, . го мультиплексора. второй вход элеменвыходы которого соединены с информаци-: та И подключей к тактовому входуустройонными входами первого счетчика, выходы ства.. т

: Выходы

24, 25

Блок 13. Блох 12

Адрес блока 12

Такт

Адрес блока 13

Сигнал

Этап

О 1 уп рав. ления схемой

3

1

О

7,8 5,6-3,4

1,2

2

4

2

1

1

3

2

3

2

О

1

О

О

О

1

0

О

0

1

1

1 х х х х

О

3

3

3

О

3

1

3

2

О

1

5.

5

5

3.

3

3

3

1

1 \

1

1

1 х

6

6

6

4

4

5 х х

2

7

7

7

7 х х х

4

4

4

2

2

2

2

3

3

8

8

8

8

8

8

8

S

8

8 х

3

3

5

5

3

5

5

5

4

4 х х

1

1 i

1

3

3

2 х х х

7

2

2

4 .4

6

6

6

6

6

1784966

/ 1

Составитель A. Мельник

Техред M.ÌoðãåHTàë Корректор 0, Кравцова

Редактор

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

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

Ъ 113035, Москва, Ж-35, Раушская наб„4/5