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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, состоящее из т.ячеек, где га количество чисел в выходном множест ве, причем каждая ячейка содержит элемент сравнения и приемный регист выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, отли чающееся тем, что, с целью повышения быстродействия, каждая ячейка содержит коммутатор и регист результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информац онных входов коммутатора, установоч ные входы приемного регистра являются информационными входами ячейки , а выходы разрядов приемного регистра соединены с установочными входами регистра результата и с второй группой информационных входов коммутатора, а выходы коммутатора являются выходами ячейки, входы ус-, тановки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляюцим входом устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предыдущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства.

„,Я0„„1007099 А ум) G 06 F 7/08

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

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

РЕСПУБЛИК

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ с..

-- М

ОПИСАНИЕ ИЗОБРЕТЕНИЯ " ::, .;;,. д,, Н АВТОРСКОМ У СВИДЕТЕЛЬСТВУ

1 (21 ) 3284556/18-24 (22) 24.04.81 (46) 23.03.83. Бюл. М 11 (72) В.B. Заверин, В.Д. Заяц и В.С ° Осипов (53) 681.325.66 (088.8) (56) 1. Патент США М 4030077, кл. 340-172.5, 1976.

2. Авторское свидетельство СССР и 637810, кл. G 06 F 7/08, 1976 (прототип).

° \

° и с

° а с (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, состоящее из m ячеек, где mколичество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, каждая ячейка содержит коммутатор и регистр результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационных входов коммутатора, установочФ ные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединены с установочными входами регистра результата и с вто" рой группой информационных входов коммутатора, а выходы коммутатора являются выходами ячейки, входы ус-. тановки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход . управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предыдущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства.

1 1007

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

Известно иногокаскадное сортировочное устройство, содержащее магазинные памяти для упорядочения . д списка входных чисел, состоящее из

И каскадов, соединенных последова-. тельно, каждый из которых состоит из межкаскадных средств памяти, стека, элементов памяти, Средств сравнения 1 g .

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

Известно также устройство для сортировки п-разрядных чисел, содер,жащее т ячеек, каждая из которых содержит элементы сравнения, прием" ный регистр, переключатели, элемент

ИЛИ, элемент И, триггер, узлы запрета, регистр результата, причем вы" ходы приемного регистра соединены Зф с первой группой входов элементов сравнения, вторая групга входов ко" торых подключена к выходам регистра результата (2 j .

Недостатком этого устройства является низкое быстродействие, посколь3$ ку для сортировки m чисел, каждое из которых содержит п-разрядов, требуется т(п+1}тактов работы, что определяется принципом поразрядного формирования в регистре результата

49 очередного сортируемого числа.

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

Поставленная цель достигается тем, что устройство, состоящее из тп ячеек, где m - -количество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр результата„ причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационных входов . коммутатора, установочные входы при099 2 емного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соедине ны с установочными входами регистра результата и с второй группой входов коммутатора, а выходы коммута" тора являются выходами ячейки, входы установки приемного регистра и регистра результата s исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с вхо дом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом. управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группОй выходов предыдущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства.

Это позволяет уменьшить время ,сортировки до 2 т тактов вследствие применения конвейерного метода и проведения операций сравнения одновременно по всем т разрядам сортируемых чисел.

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

Устройство состойт из м одинаковых ячеек 1, ...,1п„ где m - крличество чисел в выходном Множестве, причем каждая ячейка содержит приемный ре-. гистр 2, регистр 3 результата, элемент 4 сравнения и коммутатор 5, при этом выходы приемного регистра 2 соединены с первой группой информационных входов элемента 4 сравнения, вторая группа информационных входов которой подключена к выходам регистра 3 результата, а информационные входы 6 ячейки соединены с установочными входами приемного регистра

2, выходы которого соединены с установочными входами регистра 3 результата и с первой группой входов коммутатора 5, вторая группа входов которого подключена к выходам регистра 3 результата, а группа выходов коммутатора 5 является группой выходов 7 ячейки, причем входы установки приемного регистра 2 и регист99 4 число из регистра 3 результата ячейки 2< в приемный регистр 2 ячейки 2.

В этом случае по очередному тактовому сигналу происходит перезапись чисел из регистра 3 результата ячейки 11 в приемный регистр 2 ячейки 2g и из приемного регистра 2 ячейки 1„ в регистр 3 результата ячейки 11.

Если же число в приемном регистре

2 не больше числа в регистре 3 результата, то на группу информационных выходов ячейки поступает число, хра-. нящееся в приемном регистре 1, и по очередному тактовому сигналу про" исходит перезапись числа из приемно" го регистра 2 ячейки 1„ в приемный регистр 2 ячейки 1 . По этому же тактовому сигналу происходит запись . в приемный регистр 2 ячейки 1 сле1 дующего числа последовательности.

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

3 10070 ра 3 результата в исходное состояние .подключены к входу 8 установки устройства в исходное состояние, а вход управления записью приемного регистра

2 и первый вход управления записью

% регистра 3. результата соединены с входом 9 тактовых сигналов устройства, второй вход управления записью регистра 3 результата и управляющий вход коммутатора 5 подключены к вы- р ходу элемента 4 сравнения, управляющий вход которого подключен к управляющему входу 10 устройства, информационные входы б каждой ячейки

У кроме первой, соединены с.выходами

7 предыдущей ячейки 12, а информационные входы б первой ячейки 1 1 являются информационными входами устройства.

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

Перед началом сортировки прием"

we регистры 2 и регистры 3 резуль.!тата всех ячеек устанавливаются в исходное состояние сигналом на входе

8 устройства. На вход 9 устройства поступает последовательность тактовых сигналов. Сортируемая последовательность чисел поступает на информационные входы 6 перв и ячейки

11, В каждом такте работы.на вход

ЭФ б поступает одно число из этой последовательности, .В зависимости от значенйя сигнала на управляющем входе устройства в регистре 3 резуль. тата устройства выделяется внаиболь- ших или наименьших чисел;

Дальнейшее описание работы для определенности приведено для случая . выделения наибольших чисел. В этом случае регистры 3 результата всех ! а ячеек перед началом работы должны ,быть установлены в нулевое состояние. flo тактовому сигналу очередное число со входов 6 записывается в приемный регистр 2 ячейки 1 1. Запи:санное число сравнивается элементом

4 сравнения с содержиийм регистра

3 результата. Если содержимое приемного регистра 2 больше содержимого регистра 3 результата, то элемент

4 сравнения вырабатывает сигнал, который поступает на второй вход управления записью регистра 3 результата и по тактовому сигналу разрешает. перезапись числа из приемного регистра 2 в регистр 3 результата. Этот

we сигнал поступает на вход комму" татора 5, который перезаписывает

Работа в ячейках 22,...,2 происходит аналогично работе в ячейке К

В результате сортировки, из последовательности чисел в регистрах 3 результата устройства выделяются m наибольших чисел, причем они распо= ложены в по2.ядке убывания величины, начиная с первой ячейки.

Время сортировки составляет 2m тактов, что достигается применением конвейерного метода и проведением операции сравнения одновременно по всем и-разрядам сортируемых чисел.

Сравнение с известным устройством показывает, что выигрыш в быстро" действии у данного устройства соси+1 тавляет раз, где и- разрядность сравниваемых чисел.

В отличие от известного данное устройство не требует предварительной загрузки в устройство всех сорти- . руемых чисел.

В отличие от известного устройства не требуются дополнительные устройстСоставитель В. Горохов

Техред M.Êîâòóðà

Корректор. Y). макаренко

Редактор Т. Кугрышева

Заказ 2140/72 Тираж 704 Подписное

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

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

Филиал ППП "Патент", t-. Ужгород, ул. Проектная, 4

5 1007099 б ва памяти для хранения отсортирован" Количество чисел во входной посленых чисел, что сокращает количество довательности не ограничено, при оборудования. этом из них выбирается m наибольших.,