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

 

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

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

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

РЕСПУБЛИК (51)5 G 06 F 7, 06

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

H АВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР е (21) 4491098/24-24 (22) 25.07.88 (46) 23.09.90. Бюл. 1Ф 35 (71) Институт кибернетики им. В.И.Глушкова (72) E.Ë.Þùåíêî, Ю.Л.Иваськив, Г.Е.Цейтлин, В.С.Харям и Б.Я.Герасимов (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР

Н 1305659, кл. G 06 F 7/06, 1985.

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

Н 1267403, кл. G 06 F 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычисли

„,SU„1594521 А 1

2 тельной технике. Цель изобретения— повышение быстродействия. Устройство содержит стековые блоки памяти (СБП) 1 и 2, операционные регистры

3-6, элемент 7 сравнения, дешифраторы 8 и 9, элементы НЕ 10 и 11, группу регистров 12,-12,, где п — количество сортируемых чисел, блок 13 управления, вход 14 запуска, выход

15 окончания работ. Сортнруемый массив размещается в регистрах 12. Происходит перезапись отсортированной части массива из СБП 2 в СБП 1, пока не будет найдено место, в которое следует поместить очередной элемент сортируемого массива. 1 ил.

1594521

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

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

Устройство содержит стековые блоки памяти (СБП) 1 и 2, операционные регистры 3-6, элемент 7 сравнения, дешифраторы 8 и 9, элементы НЕ 10 и .11, группу регистров 12,-12 „,, где

n — количество сортируемых чисел, блок 13 управления, вход 14 запуска устройства и вход 15 окончания рабо:ты устройства, Выходы 16,-16 блока 13 управления соединены соответственно с управляющим входом элемента

7 сравнения, входами разрешения считывания и записи операционных ре гистров 3-6, входами записи регистров группы 12, входами "Начало опера- 25 ции", "Запись" и "Чтение" СБП 1 и 2, стробирующими входамп дешифраторов

8 и 9. Входы .17 -17 блока 13 управ9 ления, подсоединены к выходам дешифраторов 8 и 9, элементов HE 10 и элемента 7 сравнения, выходам "1<овец операции" СБП 1 и 2, выходу (тл+1)-го разряда (m — количество разрядов сравниваемых чисел) регистра 3. Блок

13 может быть выполнен по известной схеме микропрограммного управления.

Устройство работает следующим об разом, Первоначально сортируемые числа записываются в регистры, и после сигнала по входу 14 происходит их сдвиг в сторону регистров 12 с младшими номерами, при этом первое из чисел оказывается в регистре 3. Затем осуществляется сравнение чисел, находящихся в регистрах 3 и 4. Если

45 (РЗ) (Р4), то (Р4) (число, находящееся в регистре 4) переписывается: в регистр 5 и в верпину СБП 1. После окончания операции записи (что фиксируется сигналом на шине 17 ) число (РЗ) записывается в регистр 4, а исходный массив в регистрах вновь сдвигается и прои< ходит сравнение (РЗ) и (Р4) .

В случае, если (РЗ) (Р4),то (Р4) записывается в регистр 6, а затем - в СБП 2, Число иэ СБП 1 запи-. сывается в регистр 5 и затем в регистр 4. Далее происходит сравнение (Р4) и (РЗ). Если (Р4) > (РЗ), то описанная последовательность операций повторяется, если же (Р4) < (РЗ), то (Р4) записывается в СБП 1. Затем в СБП 1 переписывается (РЗ) через регистры 4 и 5, а затем — содержимое

СБП 2, кроме последнего числа, причем момент окончания перезаписи иэ

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

СБП 2, после чего на выходе 15 формируется сигнал окончания работы устройства.

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

Устройство для сортировки чисел, содержащее группу из и регистров, где и- количество сортируемых чисел и элемент сравнения„ причем выходы разрядов i-го регистра, где — 2,3,...,n соединены с соответствующими информационными входами

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

Техред М.Ходанич Корректор В.Гирняк

Редактор И.Дербак

Заказ 2829 Тираж 566 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðoä, ул. Гагарина,101

5 159452 выходы разрядов которых соединены с соответствующими информационными входами соответственно второй и третьей групп второго операционного регистра, а также с информационными входами соответственно первого и второго стековых блоков памяти, информационные выходы которых соединены с вторыми информационными входами соответственна третьего и четвертого операционных регистров, выходы разрядов третьего операционного регистра соединены с информационными входами третьей группы четвертого операционного регистра, выходы разрядов адреса стековых блоков памяти соединены с соответствующими входами соответственно первого и второго дешифраторов, выходы которых соединены соответст- 2О венно с первым и вторым входами I блока. управления и через соответственно первый и второй элементы НЕ— с третьим и четвертым входами блока управления, пятый и шестой входы 25 которого подключены соответственно к первому и второму выходам элемента сравнения, управляющий вход которого подключен к первому выходу блока управления,. выходы с второго по пятый которого. соединены с входами

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