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

сд

СО ГчЭ

ES

со

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

k-й частью массива из n-чисел, последующая обработка чисел требуется для получения полностью просортиро- ванного массива из п чисел. Увеличение быстродействия достигается за счет распараллеливания процесса сортировки чисел, по сравнению с прототипом быстродействие повышено в m раз. 2 ил.

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

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

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

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

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

Каждый узел 10; сравнения состоит из элемента И 11, регистра 12, m схем 13 сравнения, m элементов ИЛИ 14, m элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15, счетчика-дешифратора 16, 2т-входового коммутатора 17,

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

Перед началом сортировки импульсом положительной полярности на входе 1 начальной установки триггер 6К. устанавливается в О. В первом такте работы числа первого сортируемого массива с входов 2 поступают на входы блока 4 сортировки. На выходе блока 4 сортировки получают m просортированных чисел в порядке убывания (наибольшее число находится на первом, следующее на втором и т.д., наименьшее на т-м выходе).

По переднему фронту первого тактового импульса в регистры 5 5fc,..., 5m записывается информация с выходов блока 4 сортировки, а в триггер Ь - нуль. За время тактового импульса сигнал 1 с инверсного выхода триггера 6К, проходя через элемент И 7, успевает установить 0 триггеры 64, 6е,..., 6 в 1.

Во втором такте 1 с выходов триггеров 60 6iЈ,..., 6К поступает на первые входы элементов ИЛИ 14,

5 14г,... , 14т во всех узлах 104,Ю4,..., JO,,-, сравнения. В каждом i-м узле 10, сравнения 1 с выходов элементов ИЛИ 144, 14ft,.. о, 14т поступает на входы счетчика-дешифратора 16, на

0 котором подсчитывается количество единиц и формируется сигнал 1 на выходе Информация с выхода первого элемента ИЛИ 14 разрешает(1) или запрещает(О)прохождение так, товых импульсов через элемент И 11 . на синхровход регистра 12. Состояние выходов счетчика-дешифратора 16 узла 10; сравнения определяет номер узла 10 сравнения, в который

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

5 16 узла 10, сравнения имеется сигнал 1, информация с выхода регистра 12 переписывается в (1+1)-й узел сравнения, на втором выходе - в (1+2)-й узел сравнения и т0д0 На

Q первые и вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15V, 1 За,..., 15„, узлов 10, 10$,,.., Юп, сравнения поступает 1, которая устанавливает на выходах О. На первые и вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15„, 15g,..., 15щ первого узла 10 сравнения поступают соответственно О и 1, которые устанавливают на выходах сигнал 1.

Коммутаторы 17 в узлах 10, 1 Ое ,..., 10 т- 4 сравнения сигналом 1 с выходов элемента ИСКЛЮЧАЮЩЕЕ , ИЛИ 15.4, 15.,,..., 15т первого Узла 10 сравнения устанавливаются в положения, когда на их вход поступает информация соответственно с второго, третьего, ..., m-го входов. Коммутаторы 17 узлов 10т, Ют,... сравнения сигналом 1 с т-х выходов счетчиков-дешифраторов 16 соответственно узлов , 10,,..., 10„-г« сравнения устанавливаются в положение, когда на их выходы поступает информация с 2т-го входа. С входов 2 на входы блока 4 сортировки поступают вторые m чисел первого сортируемого маесива„

По переднему фронту второго тактового импульса происходит запись вторых m просортированных чисел из выходов блока 4 сортировки в регистры 5, 5г,... 5т, запись информации с выходов регистров 5«, 5,...t5tn в регистры 12 соответственно узлов 10f, 10с,..., Ют сравнения, перезапись информации с выходов регистра 12 узла 10; сравнения в регистр- 12 узла 10,.,т сравнения, запись нуля с инверсного выхода триггера 6 ц в триггер 6.

В третьем такте О с выходов триггера 6( поступает на первые вхот ды элемента ИЛИ 1,4 , 14ц,,., 14гп уз- лов 10, Юд.,..., 10,у, сравнения и разрешает прохождение информации через данные элементы с выходов схем 13, 13&,..., 13т сравнения. Информация с выходов входного регистра 5;

1

поступает на первые входы схем 13 сравнения всех узлов 10 сравнения, где она сравнивается с содержимым регистров 12. При превышении содержимого регистра 5/ над содержимым регистра 12 на выходе схемы 13; сравнения получают сигнал 1, а в других случаях - сигнал О. В узлах 10, Юа,.. „, 10W сравнения результаты сравнения с выхода схемы 13j сравнения проходят через элемент ИЛИ 14 и поступают на J-й вход счетчика-дешифратора 16, который подсчитывает количество чисел в регистрах 5, 5Ј,.„, 5т, больших чем число с выхода регистра 12, и формирует на выходе, соответствующем данному числу, сигнал 1. В уз,ле 10j сравнения на входы элемента

5329136

ИСКЛЮЧАЮЩЕЕ ИЛИ 15 j поступает инфор

to

15

20

25

30

35

40

45

50

55

мация с выходов элементов ИЛИ 14: узлов , 10; сравнения, которая устанавливает на выходе сигнал О (информация на первом и втором входах одинакова) или 1 (информация на первом и втором входах разная). Информация с выхода элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 15j узла 10; сравнения поступает на j-й управляющий вход коммутатора 17 узла lQ( сравнения и разрешает(I)или запрещает (О) прохождение на выход коммутатора 17 информации с выхода регистра 5j .

По переднему фронту третьего тактового импульса происходит запись следующих m просортируемых чисел из выходов блока 4 сортировки в регистры 5 , 5,00., 5ffl, запись нуля с выхода триггера 6., в триггер 6g, запись информации с выходов коммутаторов 17 предыдущих узлов 10 , сравнения в регистры 12 последующих узлов 10j4| сравнения.

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

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

За время (k+l)-ro тактового импульса сигнал 1 с инверсного выхода триггера 6ц, проходя через элемент И7, успевает установить триггеры 6$, 6fi,...,6KB единицу.

После (k+l)-ro тактового импульса числа первого массива сортируются в порядке убывания (наибольшее число находится в регистре 12 первого узла 10( сравнения, следующее число по величине в регистре 12 второго узла 10g сравнения и т.д„, наименьшее в регистре 8).

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

Устройство для сортировки чисел, содержащее входной и выходной регистры, k-триггеров, где k « - ; n - количество сортируемых чисел в массиве; m - количество информационных входов устройства, (п-1) узлов сравнения, элемент И, выход которого соединен с входом установки в 1 1-го триггера (1 1,2}... k), прямой выход р-го триггера (р 1,2,,,.,k-l) соединен с информационным входом (р+1)-го триггера, вход начальной установки устройства соединен с входом установки в О (k-l)-ro триггера, инверсный выход k-ro триггера соединен с информационным входом первого триггера и с первым входом Элемента И, каждый узел сравнения qoflepacHT регистр, схему сравнения, элемент И и элемент ИЛИ, причем тактовый вход устройства соединен с Еходами синхронизации первого входного и выходного регистров, с такто- йыми входами всех триггеров, с первыми входами элементов И каждого уэ- jia сравнения, в котором выход эле- И соединен с входом синхрони- г|ации регистра, выход которого сое- Динен с первым входом схемы сравне- йия, второй вход которой соединен с ыыходом входного регистра и информационным входом регистра первого узла сравнения, второй вход элемента р соединен с выходом элемента ИЛИ, первый вход которого соединен с вы- годом схемы сравнения, отличающееся тем, что, с целью повышения быстродействия, в него введены (т-1) входных регистров, блок сортировки, а в каждый узел сравнения введены (т-1) схем сравнения, (т-1) Элементов ИЛИ, m элементов ИСКЛЮЧАЮ- rilEE ИЛИ, счетчик-дешифратор и 2т- йходовый коммутатор, причем информационные входы устройства соединены С входами блока сортировки, выходы которого соединены с входами соответствующих входных регистров,, и Выходы второго, третьего, m-го выходного регистров соответственно сое

0

5

0

5

0

5

динены с первыми входами второй, третьей, m-й схем сравнения, в каждом узле сравнения с первого по (п-1)-и прямой выход 1-го триггера (, 2,...,k) соединен с первыми входами элементов ИЛИ в((1-1)т+1)-м, ((1-1)т+2), ((l-l)tn-Hn) узлах сравнения, выход коммутатора (n-l)-ro узла сравнения соединен с информационным входом выходного регистра, выход которого соединен с m-м выходом устройства, в каждом i-м узле сравнения (i 1,2,...,п-1) выход регистра соединен с вторым входом 2,3... m-й схем сравнения, выходы которых соединены с вторыми входами соответствующих элементов ИЛИ, выход j-ro элемента ИЛИ (j l,2...m) соединен с первыми входами J-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, j-м входом счетчика-дешифратора и первым входом J-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (i + 1)-го узла сравнения, J-й информационный вход коммутатора соединен с выходом j-ro входного регистра, j-й управляющий вход коммутатора соединен с выходом j-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (i + 2 - j )-ro узла сравнения, (га+,})-й информационный вход коммутатора соединен с выходом регистра (i + l-j)-ro узла сравнения, (m+j)-ft управляющий вход коммутатора соединен с j-м выходом счетчика-дешифратора (i+l-j)-ro узла сравнения, выход коммутатота 1-го узла сравнения соединен с входом регистра (i-H)-ro узла сравнения, в (j-l)-M узле сравнения управляющие и информационные входы коммутатора с (m+j)-ro по 2го-й соединены с вторыми входами элементов ИСКЛЮЧАКЭДЕЕ ИЛИ первого узла срав- нения и с входом логического нуля устройства, выходы регистров (n-m+ + 1), (п-пН-2). ..(п-1 )-го узлов сравнения соединены соответственно с первым, вторым ..„ (т-1)-м выходами устройства.