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

Изобретение относится к автомати ке и вычислительной технике и может быть использовано в системах обрабо :ки информации при реализации технических бредств цифровых вычислительных машин и дискретной автоматики. Известно многокаскадное сортировочное устройство, содержащее магазинные памяти для упорядочения списка входных чисел, состоящее из М каскадов, соединённых ПослеДова теяьно, каждый из которых состоит из межкаскадных средств памяти, стека, элементов памяти, Средств сравнения С :) Недостатками этого устройства являются его сложность и неоднородность структуры вследствие использования принципа разбиения сортируемых чисел на группы и многокаска ного сравнения. Известно также устройство для сортировки п-разрядных чисел, содер -жащее m ячеек, каждая из которых содержит элементы сравнения, приемный регистр, переключатели, элемент ИЛИ, элементам, триггер, узлы запре та, регистр результата, причем выходы приемного регистра соединены с первой группой входов элементов сравнения, вторая группа входов которых подключена к выходам регистра результата 2 , Недостатком этого устройства явл ется низкое быстродействие, посколь ку для сортировки m чисел, каждое из которых содержит п-разрядов, тре буется т(п+1)тактов работы, что определяется принципом поразрядного формирования в регистре результата очередного сортируемого числа. Целью изобретения является повыше ние быстродействия. Поставленная цель достигается тем, что устройство, состоящее из m ячеек, где tn - количество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регисГр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационных входов . коммутатора, установочные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соедине-i ны с установочными входами регистра результата и с второй группой входов коммутатора, а выходы коммутатора являются выходами ячейки, входы установки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с в.хр дом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входбм устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предыдущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства. ; Это позволяет уменьшить время -сортировки до 2т тактов вследствие применения конвейерного метода и проведения операции сравнения одновременно по всем h разрядам сортируемых чисел. На чертеже представлена схема устройства. Устройство сосгсмг из m одинаковых ячеек Ц,...,1,, где т- крличество чисел в выходном Множестве, причем каждая ячейка содержит приемный регистр 2, регистр 3 результата, элемент k сравнения и коммутатор 5 при этом выходы приемного регистра 2 соединены с первой группой информационных входов элемента 4 сравнения, вторая группа информационных входов которой подключена к выходам регистра 3 результата, а инф рмационные входы 6 ячейки соединены с установочными входами приемного регистра 2, выходы которого соединены с установочными входами регистра 3 результата и с первой группой входов коммутатора 5 вторая группа входов которого подключена к выходам регистра 3 результата, а группа выходов коммутатора 5 является группой выодов 7 ячейки, причем входы установки приемного регистра 2 и регистpa 3 результата в исходное состояние подключены к входу 8 установки устройства в исходное состояние, а вход управления записью приемного регистр

2и первый вход упраВ |1ения записью регистра 3.результата соединены с входом 9 тактовых сигналов устройства; второй вход управления записью регистра 3 резу/А тата и управляющий вход коммутатора 5 подключены к выходу элемента k сравнения, управляющий вход 4 оторого подключен к управляющему входу 10 устройства, информационные входы б каждой ячейки 1, кроме первой, соединены с выходами

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

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

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

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

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

Дальнейшее описание работы для определенности приведено для случая выделения наибольших чисел. В этом случае регистры 3 результата всех щячеек перед началом работы должны быть установлены в нулевое состояние. По тактовому сигналу очередное число со входов б записывается в приемный регистр 2 ячейки Ц. Записанное число сравнивается элементом 4 сравнения с содержимым регистра

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

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

число из регистра 3 результата ячейки Ц в приемный регистр 2 ячейки Тл.

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

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

2 tn Р

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

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

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

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

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

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

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

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

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