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

м

IO

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

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

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

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

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

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

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

Цель изобретения - повышение быстродействия устройства за счет совмещения во времени процессов выделения наименьших чисел и формирования из них упорядоченного массива.

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

определения числа единиц и группу элементов ИЛИ, причем входы 1-го числа устройства (i 1, 2п; п - количество сортируемых

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

п выходных регистров, причем инверсный выход 1-го разряда регистра исключения чисел соединен с i-м разрешающим входом блока выделения минимального числа, 1-й адресный выход которого соединен

с входом установки i-ro разряда регистра исключения чисел в единичное состояние, i-м входом второго блока определения числа единиц и первым входом 1-го элемента ИЛИ группы, второй вход которого подключей к прямому выходу 1-го разряда регистра исключения чисел, вход установки в нулевое состояние которого является входом начальной установки устройства, информационные выходы блока выделения минимального числа соединены с информационными входами всех выходных регистров, выходы первого и второго блоков определения числа единиц - с адресными входами блока памяти, i-й выход

которого соединен с входом разрешения записи 1-го выходного регистра, выходы разрядов которого являются информационными выходами i-й группы устройства, тактовый вход устройства соединен с тактовыми входами всех регистров, выходы всех элементов ИЛИ группы объединены монтажным И и являются выходом окончания работы устройства.

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

Устройство содержит (фиг.1) блок 1 выделения минимального числа, регистр 2 исключения отсортированных чисел, первый 3

и второй 4 блоки определения числа единиц в двоичном коде, блок 5 памяти, п выходных регистров 6 отсортированных чисел (п - размер обрабатываемых числовых массивов), группу из п двухвходовых элементов ИЛИ 7,

информационные входы сортируемых чисел Ai, A2, ..., Ар, вход НУ начальной установки устройства, информационные выходы отсортированных чисел Bi 62 ....-ЈВп, выход а окончания работы устройства.

Блок 1 выделения минимального числа (фиг.2) содержит прямоугольную матрицу из n x k ячеек анализа, где k - разрядность сортируемых чисел. Каждая ячейка 1ц, где i 17n, I 1,k, имеет вход разрешения Рц, выход разрешения Рп, информационный вход аи и информационный выход. Ячейки анализа, образующие отдельную строку матрицу, соединены последовательно по входам и выходам разрешения. Входы разрешения ячеек Н 1,12 i,...,ln 1 первого столбца являются разрешающими входами блока 1. Выходы разрешения ячеек Hie. l2kIn k последнего столбца являются адресными выходами блока 1. Информационные входы ячеек 1-й строки образуют информационные входы сортируемого числа At - anai2...aik. Информационные выходы ячеек объединены по столбцам и образуют информационные выходы bi, D2,...,bk блока 1.

Ячейка )ц анализа состоит из повторителя 8, элемента 9 равнозначности и элемента 10 импликации.

Элементы 7-10 выполняются по схеме, обеспечивающей реализацию функции МОНТАЖНОЕ И в точках соединения выходов.

В основу работы устройства положен алгоритм последовательного сокращения множества сортируемых чисел. Алгоритм включает Н шагов, где Н - количество попарно различных чисел в исходном массиве. При этом на каждом h-м шаге из текущего множества еще не отсортированных чисел исключается группа из С (ь) одинаковых наименьших чисел.

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

Сортируемые числа, образующие неупорядоченный массив, подаются через входы Ai, A2,...,An устройства в блок 1 выбора минимального числа. Одновременно на вход НУ устройства подается сигнал начальной установки, по которому производится асинхронное обнуление всех разрядов регистра 2. С инверсных выходов регистра 2 на соответствующие входы блока 1 поступают единичные сигналы Pi, P2, .... Рп. разрешающие анализ в блоке 1 всех п сортируемых чисел.

В блоке 1 среди чисел Ai, А2Ап отыскивается минимальное число В(1) мин (Ai, А2, ..., An). Код этого числа передается с информационных выходов блока 1 на информационные входы всех регистров 6. На адресных выходах блока 1 формируется набор сигналов vi, V2vn, в котором единичными значениями отмечаются позиции выделенного числа В{1) в исходном массиве.

Сформированный набор сигналов vi, V2, ..., vn поступает на входы установки в 1 разрядов регистра 2 и на входы блока 4.

Блоком 4 определяется количество единичных сигналов в наборе vi, V2vn. Получаемый при этом на выходах блока 4 код С (1) ci С2 ...c q, где q log2 (п+1), показывает, сколько наименьших чисел, равных В(1), содержится в исходном массиве. Одно0 временно блоком 3 подсчитывается количество единиц, находящихся в разрядах регистра 2. Код С(1) ciC2...Cq 0; формируемый на выходах блока 3, показывает, сколько чисел исходного массива уже отсор5 тировано.

Коды С (1) и С(1) с выходов блоков 4 и 3 поступают на адресные входы блока 5 памяти. Блок 5 формирует п-разрядную маску типа окно, содержащую серию из С(1) еди0 ниц в разрядах с (С(1)+1)-го по (C(i) +C (ij-й и нули в остальных разрядах.

Блок 5 может быть выполнен в виде ПЗУ емкостью 4Ч n-разрядных слов. Пример прошивки ПЗУ для случая п 4 приведен

5 в таблице. Ячейки ПЗУ, адреса которых в таблице не указаны, могут содержать произвольную информацию.

С выходов блока 5 разряды сформированной маски поступают на входы разреше0 ния записи регистров 6. При этом i-й разряд маски подается на вход разрешения записи регистра б| и разрешает либо запрещает прием информации этот регистр с информационных выходов блока 1.

5 По очередному синхроимпульсу (цепи синхронизации на фиг.1 не показаны) код наименьшего числа В(1), выделенного блоком 1, принимается в регистры 61 - 6cV разблокированные по записи единичными

0 разрядами маски. Содержимое остальных регистров 6ci +i. 6n не меняется. Одновременно набором сигналов vi, vavn,

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

5

0

входах Pi, P2Рп блока 1 возрастает на

величину ). В результате текущее множество сортируемых чисел сокращается за счет исключения из него С (1) одинаковых наименьших чисел.

5 в очередном такте работа устройства повторяется аналогичным образом. При этом на выходах блоков 4 и 3 формируются

КОДЫ С(2) И С(2) С(1) + С(1) С (1)

соответственно, а на выходах блока 5 образуется маска с окном шириной в С (2) разрядов и левой границей, равной С(2) +1. При этом очередное число В(а) В(1), выделенное блоком 1, принимается на регистры +1 - 6c i + С2- а в регистре 2 дополнительно устанавливаются в единичное состояние С (2) разрядов, соответствующих позициям числа В(2) в исходном массиве.

Таким образом, в каждом h-м такте работы устройства текущее множество сортируемых чисел сокращается исключением из него С (h) одинаковых наименьших чисел, а текущее множество уже отсортированных чисел пополняется этими числами. Формируемое блоком 5 окно смещается от такта к такту вправо. Единичные сигналы, снимаемые с прямых выходов регистра 2, отмечают позиции уже отсортированых чисел, а единичные сигналы на инверсных выходах регистра 2 - позиции еще не отсортированных чисел в исходном массиве. Отсортированные к концу h-го такта числа Вч 82 ... Вс(п) находятся в регистрах 6i -беде.

Сортировка исходного массива заканчивается в Н-м такте, где НЈ{1, 2, ...,п} - количеству попарно различных чисел среди Ai, A2, ...,АП. В этом такте на выходах блоков 4 и 3 формируются величины С(н) и С(н), причем С (н) + С(н) п. Одновренно на выходах всех элементов ИЛИ 1 - In появляются единичные сигналы, что приводит к выработке единичного признака а, свидетельствующего об окончании процесса сортировки. К концу Н-го такта по очередному синхроимпульсу последнее из Н чисел, выделенных блоком 1, принимается в регистры 6он)+ 1 - 6П. В следующем такте на входы Ai, A2, ...-, An устройства можно подавать очередной массив сортируемых чисел.

Блок 1 выделения минимального числа работает следующим образом.

На горизонтальные ряды ячеек анализа

111 - Hk, l2T l2kIn1 - Ink ПОДЭЮТСЯ ДВОИЧные коды сортируемых чисел Ai, A2, ..., An так, что аи соответствует старшему, aik - младшему разряду 1-го числа. Из всех п входных кодов анализируются только те, для которых на разрешающих входах блока 1 присутствуют сигналы логической 1.

В блоке 1 использован алгоритм поразрядного сравнения чисел.

Если число Ai не участвует в сравнении, то на разрешающем входе Pi блока 1 присутствует сигнал логического О. Данный сигнал распространяется через повторители 8 всех ячеек анализа i-й строки и появляется на выходе блока 1 в виде нулевого сигнала исключения vj. В каждой ячейке анализа i-й

строки нулевой сигнал разрешения Рн поступает на второй вход элемента 10 импликации, создавая условия для появления на выходе этого элемента сигнала логической

1 ( 0 только при аи 0 и Рц 1). Таким образом, исключение числа А) из анализа в блоке 1 равносильно его замене максимальным числом, содержащим единицы во всех разрядах.

0 Если хотя бы одно из участвующих в сравнении чисел содержит О в старшем разряде, то этот О передается на выход элемента 10 импликации и появляется на информационном выходе bi блока 1, поскольку вы5 ходы всех элементов 10 первого столбца соединены по схеме МОНТАЖНОЕ И,

Если участвующее в сравнении число AI содержит единицу в старшем разряде (аи 1), а на выходе Ы блока 1 сформирован

0 сигнал логического О (bi 0), то это означает, что AI не является минимальным среди анализируемых чисел. В таком случае на выходе элемента 9 равнозначности ячейки in появляется сигнал логического

5 О (an®bi Ш) 0), который распространяется через повторители 8 ячеек z - hk и появляется на i-м адресном выходе блока 1 в виде нулевого сигнала VL Появление сигнала логического О на входах разре0 шения ячеек Ii2 - lik создает условия для получения на выходах элементов 10 импликации этих ячеек сигналов логической 1. Тем самым число АГ исключается из дальнейшего анализа по оставшимся младшим раз5 рядам.

Если все участвующие в сравнении числа содержат единицу в старшем разряде, то на информационном выходе bi блока 1 появляется сигнал логической 1. В этом слу0 чае сравнение чисел продолжается по оставшимся младшим разрядам. При этом в ячейках h2 - hk, I22 - 2k, .... In2 - Ink анализа протекают процессы, аналогичные рассмотренному.

5 Таким образом, выделение минимального числа блоком 1 происходит в результате распространения сигналов по строкам ячеек анализа слева направо. Значения разрядов выделенного числа появляются

0 на информационных выходах bi,b2bk

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

5 В качестве базового объекта выбрано устройство (4) для сортировки чисел - прототип заявляемого изобретения.

Существенным техническим преимуществом заявляемого устройства перед базовым объектом является более высокое

быстродейртвие. Указанное преимущество достигается исключением из исходного массива группы одинаковых наименьших чисел на каждом шаге сортировки. Действительно, сортировка исходного массива, содержащего Н попарно различных чисел, выполняется базовым объектом за (Н+n) тактов. Заявляемое устройство осуществляет сортировку такого же массива за Н тактов, обеспечивая повышение быстродействия в(Н+п)/Н(1 +п/Н) раз. Максимальный выигрыш в быстродействии в (п+1) раз достигается в том случае, когда исходный массив состоит из п одинаковых чисел. В этом случае сортировка массива базовым объектом занимает (п+1) тактов, а заявляемым устройством - I такт. Минимальный выигрыш (в 2 раза) имеет место, когда исходный массив не содержит одинаковых чисел. В этом случае сортировка массива базовым объектом требует 2п тактов, а заявляемым устройством - п тактов.

Сравнение базового объекта и заявляемого устройства по длительности такта работы показывает следующее.

Длительность такта работы базового объекта составляет

Tg Т5 + Т1 + + Т15 + Т16,(1)

где Т5 - время срабатывания блока выделения минимального числа;

т - время суммирования двух к-разряд- ных кодов на сумматоре;

TIO - время приема информации в регистр;

Т15- время срабатывания блока определения числа единиц;

т тб - время приема информации в счетчик.

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

Тз Т1. + ГЗ + Г5 + Тб,

где п - время срабатывания блока 1 выделения минимального числа;

тз - время срабатывания блока 3 определения числа единиц;

Т5 - время срабатывания блока 5 памяти;

Те - время приема информации в регистры 6.

Из выражений (1) и (2) следует справедливость соотношения

Tj-Тз ti,

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

по крайней мере на время г суммирования двух k-разрядных чисел.

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

10 высоким быстродействием.

При необходимости поочередной выдачи отсортированных чисел заявляемое устройство может быть использовано совместно с любым известным устройством

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

20

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

25 блок определения числа единиц и группу элементов ИЛИ, причем входы 1-го числа

устройства 0 1,2, п, п - количество

сортируемых чисел) соединены соответственно с информационными входами i-й

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

35 повышения быстродействия, в него введены второй блок определения числа единиц, блок памяти и п входных регистров, причем инверсный выход 1-го разряда регистра исключения чисел соединен с i-м

40 разрешающим входом блока выделения минимального числа, i-й адресный выход которого соединен с входом установки 1-го разряда регистра исключения чисел в единичное состояние, i-м входом второго

45 блока определения числа единиц и первым входом 1-го элемента ИЛИ группы, второй вход которого подключен к прямому выходу 1-го разряда регистра исключения чисел, вход установки в нулевое

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

55 регистров, выходы первого и второго блоков определения числа единиц соединены с адресными входами блока памяти, i-й выход которого соединен с входом разрешения записи i-ro выходного регистра, выходы разрядов которого являются информационными выходами i-й группы устройства, тактовый вход устройства соединен с тактовыми входами всех регистров,

выходы всех элементов ИЛИ группы объединены монтажным И и являются выходом окончания работы устройства.

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит блок выделения минимального числа (БВМЧ) 1, регистр исключения отсортированных чисел (РИОС) 2, блоки определения числа единиц в двоичном коде (БОЧЕ) 3, 4, блок памяти (БП) 5, выходные регистры 6 отсортированных чисел, элементы ИЛИ 7. Среди исходных чисел БВМЧ 1 определяет и отмечает минимальное число (числа). БОЧЕ 4 и 3 определяют соответственно, сколько минимальных чисел выделено БВМЧ - Ci и сколько их уже было отсортировано (сколько единиц записано в РИОС 2) - Ci. Полученные коды поступают на адресные входы БП 5, который формирует маску типа Окно, содержащую единицы в остальных разрядах. Выделенное минимальное число записывается в отмеченные выходные регистры 6. 1 табл., 2 ил. Ё

I

-

,

г-Лф

4

//I

ii

. V . t

п-Ц

&