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

е

от

со

4;:

сл

ю

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

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

На чертеже приведена схема устройства.

Устройство содержит стековые блоки памяти (СБП) 1 и 2, операционные регистры 3-6, элемент 7 сравнения, дешифраторы 8 и 9, элементы НЕ 10 и И1, группу регистров 12,-12| , где п - количество сортируемых чисел, блок 13 управления , вход 14 запуска |устройства и вход 15 окончания рабо- :ты устройства. Выходы 1 6.j-16 блока 13 управления соединены соответственно с управляющим входом элемента :7 сравнения, входами разрешения счи тывания и записи операционных ре- :гистров 3-6, входами записи регист- :ров группы 12, входами Иачалр операции, Запись и Чтение СБП 1 и 2, стробирующими входами дешифраторов 8 и 9. Входы блока 13 управ- ;ления, подсоединены к выходам дешифраторов 8 и 9, элементов НЕ 10 и 11, :элемента 7 сравнения, выходам Конец операции СБП 1 и 2, выходу (т-И)-го разряда (т - количество разрядов- , сравниваемых чисел) регистра 3. Блок ;13 может, быть выполнен по известной схеме микропрограммного управления, ; Устройство, работает следую1Ц1Ш об I разом.

Первоначально сортируемые числа записываются в регистры, и после сигна.ла по входу 14 происходит их сдвиг в сторону регистров 12 с М1ад- шими номерами, при этом первое из чисел оказывается в регистре 3, З.ате осуществляется сравпение чисел, находящихся в регистрах 3 и 4. Если (РЗ) (Р4), то (Р4) (число, находящееся в регистре А) переписывается: в регистр 5 и в верпыну СБП 1. После окончания операции записи (что фиксируется сигналом па шине 177) число (РЗ) записьшается в регистр 4, а исходный массив в регистрах вновь сдвигается и происходит сравнение (РЗ) и (Р4).

В cj-гучае, если (РЗ) У (Р4) ,то (Р4) записывается в регистр б, а затем в СБП 2. Число из СБП 1 записывается в регистр 5 и затем в ре

гистр 4. Далее, происходит сравнение (Р4) и (РЗ). Если (Р4) (РЗ), то описанная последовательность операций повторяется, если же (Р4) if (РЗ), то (Р4) записьшается в СБП 1. Затем в СБП 1 переписывается (РЗ) через регистры 4 и 5, а затем - содержимое СБП 2, кроме последнего числа, причем момент окончания перезаписи из СБП 2 в СБП 1 определяется дешифратором 9. После сдвига исходного массива чисел в регистрах 12 работа устройства повторяется.

После поступления в регистр 3 числа, в (т+1)-м разряде которого находится единица (вначале это число было записано в регистре 12,,), (Р4) записывается в СБП 1, а затем туда же переписьшается и содержимое СБП 2j после чего на выходе 15 формируется сигнал окончания работы устройства

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

Устройство для сортировки чисел, содержащее группу из п регистров, где П количество сортируемых чисел и элемент сравнения, причем выходы разрядов . регистра, где i - 2,3 5... ,11, соединены с сортветст- вугощими информационными -входами t ()°-ro регистра, входы синхронизации всех регистров группы объединены, о т л и ч а ю щ е е с я тем, что,

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

, в него введены первьй и второй стековые блоки памяти, первый и второй дешифраторы, первьй и второй элементы НЕ, четыре операционных регистра, блок управления, а таюке (п+1)-й регистр группы, выходы разрядов которого соединены с соответствующими информационньши входами п-го регистра группы, выходы разрядов первого регистра группы соединены с соответствующими информационными входами , первого операционного регистра, выходы разрядов которого соединены с со- ответствуюЕщми информационными входами первой группы элемента сравнения и второго операционного регистра, выходы разрядов которого соединены с соответствующими информационными входами второй группы элемента срав- и с соответствующими информационными входами первой группы третьего и четвертого операционных регистров.

0

5

0

5

0

5

5 159

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

ного регистра, выходы разрядов адреса стековых блоков памяти соединены с соответствующими входами соответственно первого и второго дешифраторов выходы которых соединены соответственно с первым и BTopfciM входами блока.управления и через соответственно первый и второй элементы НЕ - с третьим и четвергьш входами блока управления, пятьш и шестой входы которого подключены соответственно к первому и второму выходам элемента сравнения, управляющий вход которого подключен к первому выходу блока управления,, выходы с второго по пя- тый которого соединены с входами

16

разрешения считывания соответственно с первого по четвертьй операционных регистров, шестой выход блока управления соединен с входом записи первого операционного регистра и всех регистров группы, седьмой, восьмой и девятый выходы блока управления соединены с входами записи (соответственно второго, третьего и четвертого операционных регистров выходы с десятого по пятнадцатый блока управления соединены соответственно с входами Начало операции, Запись и Чтение первого и второго стековых блоков памяти, выходы Коней операции которых соединены ответственно с седьмым и восьмым входами блока управления, шестнадцатый

и семнадцатый выходы которого соединены со стробирующими входами соответственно первого и второго дешифраторов, вход запуска устройства и выход (т+1)-го разряда первого операционного регистра, где m - количество разрядов сорт1фуемых чисел, соединены соответственно с девятым и деся- тым входами блока управления, восемнадцатый выход которого является

выходом окончания работы устройства.

Изобретение относится к вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит стековые блоки памяти (СБП) 1 и 2, операционные регистры 3-6, элемент сравнения 7, дешифраторы 8,9, элементы НЕ 10,11, группу регистров 12.1-12.N+1, где N - количество сортируемых чисел, блок управления 13, вход 14 запуска, выход 15 окончания работ. Сортируемый массив размещается в регистрах 12. Происходит перезапись отсортированной части массива из СБП 2 в СБП 1, пока не будет найдено место, в которое следует поместить очередной элемент сортируемого массива. 1 ил.