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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации. Устройство содержит M входных 5<SB POS="POST">1</SB>-5<SB POS="POST">M</SB> и выходной 8 регистры, K - триггеров 6<SB POS="POST">1</SB>-6<SB POS="POST">K</SB> где K=N/M, N - количество сортируемых чисел в массиве, M - количество информационных входов устройства, N-1 узлов сравнения 10<SB POS="POST">1</SB>-10<SB POS="POST">N-1</SB>. Каждый узел сравнения содержит элемент И, регистр, M схем сравнения, M элементов ИЛИ, M ЭЛЕМЕНТОВ ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик-дешифратор и 2M-входовый коммутатор. Блок сортировки предназначен для сортировки за один такт M чисел, что является K-й частью массива из N чисел, последующая обработка чисел требуется для получения полностью просортированного массива из N чисел. Увеличение быстродействия достигается за счет распараллеливания процесса сортировки чисел, по сравнению с прототипом быстродействие повышено в M раз. 2 ил.

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

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

РЕСПУБЛИК аю св с59 4 С 06 F 7 06

g,(nggr

И .:. -: .::,".«ИИМ

Б,;ь,i iQ :. E>A

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

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

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

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

ПРИ ГКНТ СССР

1 (21) 4369257/24-24 (22) 25.01.88 (46) 30,12.89. Бюл. У 48 .(72) А.А.Мельник и И.Г.Цмоль (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

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

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

В 1185326, кл. G 06 F 7/06, 1985.

2 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВ1И. «П1СЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации.

Устройство содержит ш входных 5 -5щ и выходной 8 регистры, 1 триггеров и

6 -6» где k = —, n — количество

»э

111

1532913

20 сортируемых чисел в массиве, m — - количество информационных входов устройства, и-1 узлов сравнения 10»10„ . Каждый узел сравнения содержит регистр, m схем сравнения, элемент И, m элементов ИЛИ, ш элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик-дешифратор и 2m-входовый коммутатор. Блок сор, тировки предназначен для сортировки за один такт m чисел, что является

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

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

На фиг. 1 представлена схема устройства; на фиг. 2 — схема узла сравнения.

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

Каждый узел 10; сравнения состоит из элемента И 11, регистра 12, ш схем 13 сравнения, m элементов

ИЛИ 14, m элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ 15, счетчика-дешифратора 16

2m-входового коммутатора 17.

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

Перед началом сортировки импульсом положительной полярности на входе 1,начальной установки триггер

6 .<, устанавливается в "0". В первом .такте работы числа первого сортируемого массива с входов 2 поступают на входы блока 4 сортировки.

На выходе блока 4 сортировки получают m просортированных чисел в порядке убывания (наибольшее число находится на первом, следующее на втором и т.д., наименьшее на m-м выходе).

По переднему фронту первого тактового импульса в регистры 5», 5,..., 5 записывается информация с выходов блока 4 сортировки, а в триггер 6», — нуль. За время такто25

k-й частью массива из п-чисел, последующая обработка чисел требуется для получения полностью просортированного массива из и чисел. Увеличение быстродействия достигается за счет распараллеливания процесса сортировки чисел, по сравнению с прототипом быстродействие повышено в m раз; 2 ил. ваго импульса сигнал "1" с инверсного выхода триггера б, проходя через элемент И 7, успевает установить триггеры 6, 6 ...., 6» в "1".

Во втором такте "1" с выходов триггеров б,, 6,..., 6 поступает на первые входы элементов ИЛИ 14, 14,...,14,„во всех узлах 10„10,...,, 10„ < сравнения. В каждом i-м узле .

10; сравнения "1" с выходов элементов ИЛИ 14», 14,..., 14 поступает на входы счетчика-дешифратора 16, на котором подсчитывается количество единиц и формируется сигнал "1" на выходе. Информация с выхода перво"

ro элемента ИЛИ 14< разрешает("1") или запрещает("0"1прохождение тактовых импульсов через элемент И 11 на синхровход регистра.12. Состояние выходов счетчика-дешифратора

16 узла 10; сравнения определяет номер узла 10 сравнения, в который число с выходов регистра 12 переписывается. При нулях на выходах счетчика-дешифратора 16 информация в регистре 12 не изменяется, Если на первом выходе счетчика-дешифратора

16 узла 10; сравнения имеется сигнал "1", информация с выхода регистра 12 переписывается в (i+1)-й узел сравнения, на втором выходе - в (i+2)-fi узел сравнения и т.д. На первые и вторые входы элементов ИСКЛОЧАЮЩЕЕ ИЛИ 15, 15<,...,15,„ узлов

10, 10 ...,,10, сравнения поступает "1", которая устанавливает на выходах "0". На первые и вторые входы элементов ИСКЛЮЧАК1ЦЕЕ ИЛИ 15, 15,..., 15щ первого узла 10 срав-. нения поступают соответственно "0" и "1", которые устанавливают на выходах сигнал "1".

153291

Коммутаторы 17 в узлах 10, 1

10п,...,10 1.< сравнения сигналом

"1" с выходов элемента ИСКЛЮЧАКЩЕЕ

ИЛИ 15п, 15з,..., 15 первого узла

1Оа сравнения устанавливаются в положения, когда на их вход поступает информация соответственно с второго, третьего, ..., ш-ro входов. Коммута-. торы 17 узлов 10, 10 *»,..., 10»» <. сравнения сигналом "1" с m-x выходов счетчиков-дешифраторов 16 соответственно узлов 10, 10,..., 10< сравнения устанавливаются в положение, когда на их выходы поступает информация с 2m-ro входа. С входов 2 на входы блока 4 сортировки поступают вторые m чисел первого сортируемого массива.

По переднему фронту второго так- 2О тового импульса происходит запись вторых ш просортированных чисел из выходов блока 4 сортировки в регистры 5, 5,..., 5, запись информации с выходов регистров 5<, 5,...,5,»1

I в регистры 12 соответственно узлов

10» 10q 10,сравнения, перезапись информации с выходов регистра .

12 узла 10; сравнения в регистр 12 узла 10;„„ сравнения, запись нуля с 3О инверсного выхода триггера 6 в триггер 6».

В третьем такте "0" с выходов триггера б, поступает на первые вхо-. ды элемента ИЛИ 14< 14,. °,,14я1 узлов 10», 10 101»,сравнения и

35 разрешает прохождение информации через данные элементы с выходов схем

13», 13,..., 13„ сравнения. Информация с выходов входного регистра 5 поступает на первые входы схем 13. сравнения всех узлов 10 сравнения, где она сравнивается с содержимым регистров 12 ° При превышении содер.жимого регистра 5 над содержимым регистра 12 на выходе схемы 13 сравнения получают сигнал "1", а в других случаях — сигнал "0". В ysлах 10», 10п,...,10»1 сравнения результаты сравнения с выхода схемы

13 сравнения проходят через элемент ИЛИ 14 и поступают íà J-й вход счетчика-дешифратора 16, который подсчитывает количество чисел в регистрах 5», 5п,..., 5»,, больших, чем число с выхода регистра 12, и формирует на выходе, соответствующем данному числу, сигнал "1". В ys;ле 101 сравнения на входы элемента

3 6

ИСКЛЮЧАЮЩЕЕ ИЛИ 15 . поступает инфорi мация с выходов элементов ИЛИ 14. узлов 10 10; сравнения, которая устанавливает на выходе сигнал "0" (информация на первом и втором входах одинакова) или "1 (информация на первом и втором входах разная) ° .Информация с выхода элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 15> узла 10; сравнения поступает на j-й управляющий вход коммутатора 17 узла 101, cpasнения и разрешает("I") Hëè запрещает (0"} прохождение на выход коммутатора

17 информации с выхода регистра 5) .

По переднему фронту третьего тактового импульса происходит запись следующих ш просортируемых чисел из выходов блока 4 сортировки в регистры

5», 5,..., 5ш, запись нуля с выхода триггера 61 в триггер 6, запись информации с выходов коммутаторов 17 предыдущих узлов 10; сравнения в регистры 12 последующих узлов 10; „ сравнения.

По приходу следующих тактовых импульсов устройство работает аналогично.

По переднему фронту (k+1)-ro тактового импульса происходит запись первых ш чисел второго сортируемого массива в регистры 5>, 5,...,5„» запись информации с выходов коммутаторов 17 предыдущих узлов 10; сравнения в регистры 12 последующих узлов

10 +» сравнения, запись куля в триггер 6 .

За время (k+1)-го тактового импульса сигнал "1" с инверсного выхода триггера бп, проходя через элемент И7, успевает установить триггеры 64, бп... °,6 „ в единицу.

После (1+1)-rо тактового импульса числа первого массива сортируются в порядке убывания (наибольшее число находится в регистре 12 первого узла

10 сравнения, следующее число по величине в регистре 12 второго узла

10 сравнения и т.д., наименьшее в регистре 8).

По приходу следующих тактовых импульсов одновременно с сортировкой второго массива производится последовательный по m чисел вывод первого отсортированного массива и т.д.

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

Устройство для сортировки чисел, содержащее входной и выходной регист1532913

pbr, k-триггеров, где k —; n - коm личество сортируемых чисел в массиве; m — - количество информационных входов устройства, (n-1) узлов сравнения, элемент И, выход которого соединен с входом установки в "1" 1-го триггера. (1 = 1 2,... k) прямой вы— гход р-го триггера (р = 1,2,...,k"1) соединен с информационным входом (p+1)-го триггера, вход начальной установки устройства соединен с входом установки в "О" (k-1)-ro тригге1 а, инверсный выход k-го триггера оединен с информационным входом ервого триггера и с первым входом элемента И, каждый узел сравнения содержит регистр, схему сравнения, | элемент И и элемент ИЛИ, причем так- 20 новый вход устройства соединен с ходами синхронизации первого входного и выходного регистров, с тактовыми входами всех триггеров, с первыми входами элементов И каждого уз-. 25

Ла сравнения, в котором выход элеМента И соединен с входом синхронизации регистра, выход которого сое 1инен с первым входом схемы сравне ия, второй вход которой соединен с 3О

ыходом входного регистра и информаионным входом регистра первого уза сравнения, второй вход элемента соединен с выходом элемента ИЛИ, ервый вход которого соединен с выодом схемы сравнения, о т л и ч а—

g ш е е с я тем, что, с целью повыения быстродействия, в него введены

m-1) входных регистров, блок сортиовки, а в кажцый уэел сравнения вве- 4О ены (m-1) схем сравнения, (m-1) лементов ИЛИ, ш элементов ИСКХПОЧАЮфЕЕ ИЛИ, счетчик-дешифратор и 2шЭходовьп коммутатор, причем информационные входы устройства соединены

С входами блока сортировки, выходы которого соединены с входами соответствующих входньж регистров, и

Выходы второго., третьего, m-го выходного регистров соответственно соединены с первыми входами второй, третьей, m-й схем сравнения, в каждом узле сравнения с первого по (n-1)-й прямой выход 1-го триггера (1 1, 2,...,k) соединен с первыми входами элементов ИЛИ в ((1-1)ш+1)-м, ((1 l)m+2), ((1-1)m+m) узлах сравнения, выход коммутатора (n-1)-го узла сравнения соединен с информационныи входом выходного регистра, выход которого соединен с ш-м вьжодои устройства, в каждом i-м узле сравнения (i 1,2,...,n-l) выход регистра соединен с вторым входом 2,3...

m-Й схем сравнения, выходы которых соединены с вторыми входами соответствующих элементов ИЛИ, выход

j-го: элемента ИЛИ (= 1,2...m) соединен с первыми входами J-ro элемента ИСКЛЮЧАММЦЕЕ ИЛИ, -м входом счетчика-дешифратора и первым входом J-го элемента ИСКЛЮЧАКЗЦЕЕ ИЛИ (х + 1)-го узла сравнения, g-й информационный вход коммутатора соединен с выходом g-го входного регистра, -Й управляющий вход коммутатора соединен с выходом J-.ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (i + 2 - g )-го узла сравнения, (m+g )-й информационный вход коммутатора соединен с вьжодом регистра (i + 1-$)-ro узла сравнения, (m+j)-Й управляющий вход коммутатора соединен с -и выходом счетчика-дешифратора (i+1-))-ro узла сравнения, выход комиутатота

i-го узла сравнения соединен с входом регистра (i+1.)-ro узла сравнения, в (J-1)-м узле c,pàâíeíèÿ управляющие и информационные входы ком" мутатора с (m+J)-ro по 2ш-й соединены с вторыми входаии элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ первого узла сравнения и с входом логического нуля устройства, выходы регистров (n-ш+

+1), (n-ш+2)...(n-l)-ro узлов сравнения соединены соответственно с первым, вторым ... (m-1)-м выходаии устройства.

1532913

Составитель В. Иванова

ТехредЛ.Олийнык КорреКтор-Т.Палий

Редактор Л. Пчолинская

Заказ 8100/53 Тираж 668 Подписное

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

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

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