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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (si)s G 06 F 7/08

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

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

ПРИ ГКНТ СССР

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

Вп

Рог,1

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4840994/24 (22) 28.05.90 (46) 07.04.92, Бюл. М 13 (72) И.Е. Анкудинов, А.M. Зыков, С.А. Удинцев и Н.Н. Шипилов (53) 681.325,5 (088.8) (56) Авторское свидетельство СССР

Ф 1179317, кл. G 06 F 7/08, 1985.

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

М 1474639, кл. G 06 F 7/08, 1987. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительнойтехнике, Цель изобретения— повышение быстродействия. Устройство содержит блок выделения минимального чисА1 Az An, Ы,, 1725215 А1 ла (БВМЧ) 1, регистр исключения отсортированных чисел (РИОС) 2, блоки определения числа единиц в двоичном коде (БОЧЕ) 3, 4, блок памяти (БП) 5, выходные регистры 6 отсортированных чисел, элементы ИЛИ 7, Среди исходных чисел БВМЧ 1 определяет и отмечает минимальное число (числа). БОЧ Е 4 и 3 определяют соответственно, сколько минимальных чисел выделено БВМЧ вЂ” C> и сколько их уже было отсортировано(сколько единиц записано в РИОС 2) — C>. Полученные коды поступают на адресные входы БП 5, который формирует маску типа

"Окно", содержащую единицы в остальных разрядах. Выделенное минимальное число записывается в отмеченные выходные регистры 6. 1 табл„2 ил.

1725215

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

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

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

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

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

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

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

Цель изобретения — повышение быстродействия устройства за счет совмещения во времени процессов выделения наименьших чисел и формирования из них упорядоченного массива, Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее блок выделения минимального числа, регистр исключения чисел, первый блок определения числа единиц и группу элементов ИЛИ, причем входы i-ro числа устройст8a (i = 1, 2,...,п; n — количество сортируемых чисел) соединены соответственно с информационными входами i-й группы блока выделения минимального числа, прямые выходы разрядов регистра исключения чисел — с входами первого блока определения числа единиц, введены второй блок определения числа единиц, блок памяти и п выходных регистров, причем инверсный выход i-го разряда регистра исключения чисел соединен с i-м разрешающим входом блока выделения минимального числа, i-й адресный выход которого соединен с входом установки i-ro разряда регистра исключения чисел в единичное состояние, i-м входом второго блока определения числа единиц и первым входом i-го элемента

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

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

Устройство содержит (фиг.1) блок 1 выделения минимального числа, регистр 2 исключения отсортированных чисел, первый 3 и второй 4 блоки определения числа единиц в двоичном коде, блок 5 памяти, и выходных регистров 6 отсортированных чисел (и — размер обрабатываемых числовых массивов), группу из и двухвходовых элементов ИЛИ 7, информационные входы сортируемых чисел А, Ag, ..., An, вход "НУ" начальной установки устройства, информационные выходы отсортированных чисел  — B2 — ... В,, выход а окончания работы устройства.

1725215

Блок 1 выделения минимального числа (фиг.2) содержит прямоугольную матрицу иэ и х k ячеек анализа, где k — разрядность сортируемых чисел. Каждая ячейка 1и, где

i = 7,ri, 1 = 1,k, имеет вход разрешения Рд, выход разрешения Рц, информационный вход aii и информационный выход. Ячейки анализа, образующие отдельную строку матрицу, соединены последовательно по входам и выходам разрешения. Входы разрешения ячеек 111, 121„...ln 1 первого столбца являются разрешающими входами блока 1. Выходы разрешения ячеек 1>р, 1гк„.„ln k последнего столбца являются адресными выходами блока 1. Информационные входы ячеек 1-й строки образуют информационные входы сортируемого числа Ai = анаа...aw. Информационные выходы ячеек объединены по столбцам и образуют информационные выходы Ь, bz,...,bk блока 1.

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

10 импликации.

Элементы 7-10 выполняются по схеме, обеспечивающей реализацию функции

МОНТАЖНОЕ И в точках соединения выходов.

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

При этом на каждом h-М шаге из текущего множества еще не отсортированных чисел

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

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

Сортируемые числа, образующие неупорядоченный массив, подаются через входы Ai Az Àn устройства в блок 1 выбора минимального числа. Одновременно на вход "НУ" устройства подается сигнал начальной установки, по которому производится асинхронное обнуление всех разрядов регистра 2. С инверсных выходов регистра 2 на соответствующие входы блока

1 поступают единичные сигналы Р, Pz, ..., Рп, разрешающие анализ в блоке 1 всех и сортируемых чисел.

В блоке 1 среди чисел А>, А2,...,А отыскивается минимальное число В() = мин (А1, Az...., An). Код этого числа передается с информационных выходов блока 1 на информационные входы всех регистров 6. На адресных выходах блока 1 формируется набор сигналов v>, vz, ..., vn, в котором единичными значениями отмечаются позиции выделенного числа B(>) в исходном массиве.

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

Блоком 4 определяется количество единичных сигналов в наборе ч1, ч2, ..., vn. Получаемый при этом на выходах блока 4 код

С () = с1 с2 ...с q, где q = )1092 (и+1)(, показывает, сколько наименьших чисел, равных

В(1), содержится в исходном массиве. Одновременно блоком 3 подсчитывается количество единиц, находящихся в разрядах регистра 2. Код C(1) = c1cz" cq = О, формируемый на выходах блока 3, показывает, сколько чисел исходного массива уже отсор15 тировано, Коды С (1) и С((ц с выходов блоков 4 и 3 поступают на адресные входы блока 5 памяти. Блок 5 формирует и-разрядную маску типа "окно", содержащую серию из C(>) еди20 ниц в разрядах с (С()+1)-го по (С(ц +С (1)-й и нули в остальных разрядах, Блок 5 может быть выполнен в виде ПЗУ емкостью 4ч и-разрядных слов. Пример

"прошивки" ПЗУ для случая и = 4 приведен

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

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

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

40 разрядами маски, Содержимое остальных регистров бсср y1 — 6n не меняется. Одновременно набором сигналов v>, ч2, „vn, поступающих с адресных выходов блока 1, устанавливаются в "1" разряды регистра 2, соответствующие позициям выделенного числа В() в исходном массиве. Тем самым эти числа исключаются из дальнейшего рассмотрения в блоке 1, поскольку количество нулевых сигналов на разрешающих входах Р>, Р2„„,Р> блока 1 возрастает на величину С (1) В результате текущее множеI ство сортируемых чисел сокращается за

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

В очередном такте работа устройства повторяется аналогичным образом. При этом на выходах блоков 4 и 3 формируются к о Д ы С(2) и С(2) = С(1) + С(1) = С (1) соответственно, а на выходах блока 5 обра1725215

15

I зуется маска с "окном" шириной в С (2) разрядов и левой границей, равной С(2) + 1.

При этом очередное число B(z) > В(1), выделенное блоком 1, принимается на регистры бс 1 +1 — бс 1 + с 2, а в регистре 2 дополнительно устанавливаются в единичное состояние С (2) разрядов, соответствующих позициям числа Вр) в исходном массиве.

Таким образом, в каждом h-м такте работы устройства текущее множество сортируемых чисел сокращается исключением из

1 него С (ь) одинаковых наименьших чисел, а текущее множество уже отсортированных чисел пополняется этими числами, Формируемое блоком 5 "окно" смещается от такта к такту вправо. Единичные сигналы, снимаемые с прямых выходов регистра 2, отмечают позиции уже отсортированых чисел, а единичные сигналы на инверсных выходах регистра 2 — позиции еще не отсортированных чисел в исходном массиве.

Отсортированные к концу h-го такта числа

В1 <В2 <... Вс(Ь) находятся в регистрах

61 — 6С(ц, Сортировка исходного массива заканчивается в Н-м такте, где НС(1, 2, ...,n)— количеству попарно различных чисел среди

А1, Az, Ап. В этом такте на выходах блоков

4 и 3 формируются величины С(н) и С(), причем С () + C() = и. Одновренно на выходах всех элементов ИЛИ 71 — 7л появляются единичные сигналы, что приводит к выработке единичного признака а, свидетельствующего об окончании процесса сортировки. К концу Н-го такта по очередному синхроимпульсу последнее из Н чисел, выделенных блоком 1, принимается в регистры 6о)1)+1—

6п, В следующем такте на входы А1, A2, ..., An устройства можно подавать очередной массив сортируемых чисел, Блок 1 выделения минимального числа работает следующим образом.

На горизонтальные ряды ячеек анализа 11 l1k, 121 l2k, ..., ln1 ink подаются двоичные коды сортируемых чисел А1, A2, ..., А, так, что ац соответствует старшему, а к— младшему разряду l-ro числа. Из всех и входных кодов анализируются только те, для которых на разрешающих входах блока

1 присутствуют сигналы логической "1".

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

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

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

"1" (Рц-- ан = 0 только при a;i = 0 и Ри = 1).

Таким образбм, исключение числа Ai из анализа в блоке 1 равносильно его замене максимальным числом, содержащим единицы во всех разрядах.

Если хотя бы одно из участвующих в сра внении чисел содержит "0" в старшем разряде, то этот "0" передается на выход элемента

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

=1), а на выходе b1 блока 1 сформирован сигнал логического "0" (Ь1 = О), то это означает, что А не является минимальным среди анализируемых чисел. В таком случае на выходе элемента 9 равнозначности ячейки )ц появляется сигнал логического

"0" (ацЭЬ1 = 1)0 = О), который распространяется через повторители 8 ячеек li2 — lik u появляется на i-м адресном выходе блока

1 в виде нулевого сигнала ч1, Появление сигнала логического "0" на входах разрешения ячеек iiz — lik создает условия для получения на выходах элементов 10 импликации этих ячеек сигналов логической "1".

Тем самым число4; исключается из дальнейшего анализа по оставшимся младшим разрядам.

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

В ЯЧЕйКаХ 112 — l1k, l22 — l2k ..., 1п2 — ink анализа протекают процессы, аналогичные рассмотренному.

Таким образом, выделение минимального числа блоком 1 происходит в результате распространения сигналов по строкам ячеек анализа слева направо. Значения разрядов выделенного числа появляются на информационных выходах Ь1,Ь2,.„,bk блока 1, а позиции выделенного числа, занимаемые им в исходном массиве, отмечаются сигналами логической "1" на соответствующих адресных выходах ч1, ч2,...,чп блока 1.

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

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

1725215

Tg> 75 + Т1 + 710 + 115 + Т16, (1) I где а — время срабатывания блока выделе- 30 ния минимального числа;

1 г — время суммирования двух k-разрядных кодов на сумматоре; тю — время приема информации в регистр; 35

t т ь- время срабатывания блока определения числа единиц; ы — время приема информации в счетчик, Для заявляемого устройства длительность 40 такта работы определяется выражением (2) Тз = Г1, + гз + T5 + б, где г1 — время срабатывания блока 1 выде- 45 ления минимального числа; тз — время срабатывания блока 3 определения числа единиц;

25 — время срабатывания блока 5 памя50 гв — время приема информации в регистры 6.

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

Тр- T, >t>, показывающего, что длительность такта работы базового объекта превышает длительность такта работы заявляемого устройства быстродействие. Указанное преимущество достигается. исключением из исходного массива группы одинаковых наименьших чисел на каждом шаге сортировки. Действительно, сортировка исходного массива, содержащего 5

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

Минимальный выигрыш (в 2 раза) имеет место, когда исходный массив не содержит одинаковых чисел. В этом случае сортировка массива базовым объектом требует 2п тактов, 20 а заявляемым устройством — n тактов.

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

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

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

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

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

Устройство для сортировки чисел, содержащее блок выделения минимального числа, регистр исключения чисел, первый блок определения числа единиц и группу элементов ИЛИ, причем входы i-го числа устройства (i = 1, 2, .„.,и, n — количество сортируемых чисел) соединены соответственно с информационными входами i-й группы блока выделения минимального числа, прямые выходы разрядов регистра исключения чисел соединены с входами первого блока определения числа единиц, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй блок определения числа единиц, блок памяти и и входных регистров, причем инверсный выход i-го разряда регистра исключения чисел соединен с i-м разрешающим входом блока выделения минимального числа, 1-й адресный выход которого соединен с входом установки i-го разряда регистра исключения чисел в единичное состояние, i-м входом второго блока определения числа единиц и первым входом i-го элемента ИЛИ группы, второй вход которого подключен к прямому выходу i-го разряда регистра исключения чисел, вход установки в нулевое состояние которого является входом начальной установки устройства, информационные выходы блока выделения минимального числа соединены с информационными входами всех выходных регистров, выходы первого и второго блоков определения числа единиц соединены с адресными входами блока памяти, i-й выход которого соединен с входом разрешения записи 1-го выходного регистра, выходы разрядов которого являются ин11

1725215

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