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

пазона сортируемых чисел и орггтпиза- ции очередей элементов данных З ст- ройство содержит ячейки 1 анализа объединенные в виде прямоугольной матрицы,,первую и вторую группы элементов ИЛИ 2. и Sj причем каждьй стол бец матрицы содержит N ячеек,, где N 7/2, а каждая строка ма -.ор.иды содержит 1 ячеек, где 1 - такое что 1 k 3 m, k - количество разрядов в одной ячейке J m - количество, разрядов в сортируемых числах Ячейка ана лиза содержит узел памяти, схему г сравнения, узел формирования управляющих сигналов, включающий элементы И и ИЛИ, Ячейки в матрице и первая и вторая группы элементов ИЛИ связаны мелоду собой и с вне1 нп-1ми инИзобретение относится к вычислительной технике и может быть использовано в специализированных устрой- CTBaXs .предназначенных для сортировки массивов данных5 поступающих па-- раллельными кодами одно за другим в реальном масштабе времени,,

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

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

Устройство содержит ячейки 1 анализа, первую группу элементов ИЛИ 2., вторую группу элементов ИЛИ 3,первый выход, 4 отсорткрованиого числа устройства, второй выход 5 отсортированного числа устройства, информационный вход 6. вход 7 сравниваемых чисел, тактовый вход 3, первыми и второй разряды управляющего кОда 9, первый и второй выходы 10 результата сравнения, первый 11 и второй 12 входы установки режима устройства, дополнительный вход 13 51чейка

срормадионными и управляюйп г.я- входами таким образоМд что при вводе в устройство очередного числа оно записывается в ячейки той строки матрицы,, в ячейках которой уже было записано число 5 мепыпес вподимогОз но ближайгаее к нему., Числа хранимые в Л -гейках пред1з1дущмх строзс aтpИLrы которые являются равными или большими ло з -:ачбни о вводимого числа, сохра- без изменений. Числа, xpaiUi- мые в ячейках последуюптдк строк и той строки, в ячейки которой записывается вводимое число5 которые являются меньшими по значению вводимого, одновременно переписываются в ячейки соседних последччош-тх строк матрицы„ 3 ил

анализа содерлсит 14 памяти; схему 15 сравнения, узел 16 формирова- ния управля 0 цих сигналов котогый / содержит элементы И 17 и 18,, ИЛИ 19

Устройство (фиг, 1) ДЛЯ СОрТИрОВки чисел работает следующим образом

Перед началом фу;1кционирования ус Г ройство переводу1тся в исхсд юе состояние« Для этого в устройстве

0 предусмотрен режим начальной установки (РЫУ), В этом режиме на входе о устройства устанавливается код начальной установки,, на всех BXOIUIX 9 устанавливается код 00, на всех вхо5- дах 11 устанавливается логическая единица, а на всех входах 12 - логический ноль и ка вход 8 подают импульс синхронизаци -. под действием заднего фронта которого в ячейки

0 ка:вдой строки матрицы будет зап;асан один и тот же код начальной установки,. При нспользовании устройства для сортировки чисел 5 значения (L) кото- находятся в прадедах О 2--1 ,

- в качестве кода начальной уста1 овки - используе1 ся нулевой код, а тфи использовании ycTpoi cTBa для сортировки чисел значения (L), которых находятся )з прнгделах П i L - 2 -1 . в ка0 честве кода начальной установки используется, код, зкачеиие которого па.вно- П

31315967

Кроне режима РНУ в устройстве не редусмотрено шесть режимов функциоирования: режим сортировки Э(PC); ежим чтения (РЧ); режим хранения РХ); режим организации очередей лементов данных типа LIFO(PL); реим организации очередей элементов анных типа FIFO(PF); режим органиации очередей элементов данных ти- а ПРИОО(РП).

во вой че

10

ше чи то во ва ко и ли на ва ст ца за та ко на фо во ни ст но хо ва те яч ли 10 10 2 мя ва ро но вх яч ся уз ре

15

го

25

Режим PC. После режима РНУ, при котором в ячейках каждой строки матрицы запоминается код со значением П / О, на каждом входе 9, .на разрядах соответственно 20 и 21 устанавивается код 10. На всех входах 11 и 12 устанавливается логический ноль, кроме входа верхней строки матрицы, на котором устанавливается один и тот же код первого числа из массива . сортируемых чисел. Если первым числом является число со значением И, то после действия синхросигнала на входе 8 содержимое ячеек матрицы не изменяется и устройство остается: в исходном состоянии, так как на всех выходах 10 устанавливается код 10 или 01, под действием которого на выходах всех элементов ИЛИ 2иЗ сфор- о мируется логическая единица и на входах установки режимов записи всех ячеек -устанавливается код 11, при котором узлы 4 памяти устанавливаются в режим хранения (РХ), Если первым числом является число, значение (Б), которого больше П, т.е. Б П, то узлы памяти в ячейках первой строки устанавливаются в режим 1Рз записи со входа 6, а ячеек j-x строк- в режим 2Рз записи с выхода ячеек (j-l)-x строк, где -j 2,...,N.

После действия синхросигнала на входе 8 устройства код первого числа со входа 6 устройства записывается в узлах памяти ячеек первой строки. В ячейки последующих остальных строк переписывается код начальной установки из ячеек предьздущих строк матрицы ячеек.

После записи кода первого числа на входы 6 и 7 устройства устанавливается один и тот же код второго числа из массива оставшихся чисел. Если значение (Б) второго числа оказывается меньше или равно П, т.е. Б П, то после действия синхросигнала на входе 8 содержимое ячеек не изменяется по указанной вьше причи

Q

35

40

55

не

а также вследствие того,что пер- вое число, хранимое в ячейках первой строки матрицы/ячеек, имеет значение (А) большее П,, т.е. А П,

не

Если значение второго числа больше П, но меньше или равно первому числу со значением А, т.е. П , то в этом случае на выходе 10 первой строки матрицы ячеек усуанавли- вается код 10 или 01, под действием которого на выходе элемента ИЛИ 2 и элемента ИЛИ 3 этой строки устанавливается логическая единица.Так как на входе 11 первой строки и, следовательно, на выходе элемента 2 этой строки установлена логическая единица, то на входах установки режима записи всех ячеек верхней строки устанавливается код 11, под действием которого в узлах памяти ячеек устанавливается режим РХ, т.е. код информации, записанный в ячейках первой строки, сохраняется без изменений. Так как в ячейках остальных строк хранится код начальной- установки со значением П Б, то на выходах элементов ИЛИ 2 и 3 устанавливается логический ноль. В результате на входах установки режима записи ячеек второй строки матрицы устанавливается код 01, так как на выходе 10 первой строки устанавливается код 10 или 01, а на выходе элемента ИЛИ. 2 - логическая единица. В узлах памяти ячеек второй строки устанавливается режим 1Рз, т.е. в ячейки.второй строки записывается код, установленный на входе 6 устройства. На входах установки режима записи всех , ячеек остальных строк устанавливается код 00, под действием которого в узлах памяти ячеек устанавливается режим 2Рз, т.е. в ячейки каждой последуюш;ей оставшейся строки переписаны коды начальной установки из ячеек, хранятся коды чисел, меньших числа, код которого установлен на входах 6 и 7 устройства, но больших

П, то аналогичным образом переписываются числа, коды которых хранятся в ячейках j-й строки в ячейки (j+1)-й строки, где 3 j N. Если значение второго числа больше значения первого, т.е. Б А, то на всех выходах 10 устанавливается код 00. Следовательно, на выходах всех элементов ИЛИ 2 и 3, кроме элемента ИЛИ 2 первой строки, устанавливается логический

513

ноль, а на его выходе устанавливается логическая единица. /На входах установки режимов записи всех ячеек первой строки устанавливается код 01, под действием которого в узлах памяти ячеек.первой строки устанавливается режим 1Рз т.е. в ячейки первой.строки записывается код, установленный на входе 6 устройства.

На входах установки режима записи ячеек всех остальных строк (2 , j i N, 1 .i 1) устанавливается код 00, под действием которого в узлах памяти ячеек устанавливается режим 2Рз. Это значитJ что в ячейки второй строки переписан код числа, хранимого в ячейках первой строки, В ячейки третьей строки переписан код числа, хранимого в ячейках второй строки, и т.д. в ячейках N-й строки переписан код числа, хранимого в ячейках (К-1)-й строки.

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

Предположим, что отсортировано и хранится в устройстве (п-1) чисел и подается очередное М-е число, где , Если это число больше числа, код которого хранится в ячейках первой строки, то код его записан в ячейках первой строки, а коды чисел, хранимые в ячейка:х ка)здой предьщу- щей строки, переписаны в ячейки последующих соседних строк, как это бьшо описано выше, так как в ячейках остальных строк хранятся коды чисел, значение которых меньше значения, числа, код которого хранится в ячейках первой строки. Если М-е число меньше меньшего отсортированного числа, но больше П, то код его записан в ячейки п-й строки, как это имело место при записи второго числа в ячейки второй строки. Если М-е число меньше или равно П, то оно не записано в устройстве также как иве случае с первым и вторым числами.

Положим, что значение (L) М-го чи ла меньше или равно числу, код которого хранится в ячейках j-й строки, но больше числа, код которого хранится в ячейках (+1)-й строки. В этом случае код М-го числа будет записан в ячейки (з + О-й строки. Коды чисел, хранимые в яче.йках строк с

76

номерами большими, перепишутся в ячейки соседних строк с большими номерами, а коды чисел, хранимые в ячейках с номерами меньшими j, останутся

без изменений,.Указанный случай аналогичен случаю записи второго числа в ячейке второй строки с тем отличием, что коды 10 или 01 на выходе Югр , где j, благодаря которым на

выходах соответствуюш х элементов ИЛИ устанавливается логическая единица и на входах установки режимов записи j ячеек (, ) с номерами j устанавливается код 11, задающий

режим хранения (РХ) узлов памяти ячеек, формируются как результат того, что значения чисел, хранимых в ячейках указанных строк, больше значения М-го числа.

I .

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

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

сортируемых чисел. В качестве признака тог.о, что в устройстве хранит- , ся N отсортированных чисел является установка на выходах 4 кода со значением отличным от П или формирование на выходе 10 N-й строки матри.цы кода 00 при установке на входе 7 устройства кода со значением П. В противном случае на выходе 10 N-й строки устанавливаете. код 10 или 01..

Для расположения чисел в обратном порядке, т.е. в ячейках первой строки - минимального числа, а в ячейках N-й строки - максимального числа достаточно на входы 6 и 7 устройства подавать дополнительные коды чисел,как это делается в известном устройстве. Однако в предлагаемом устройстве не обязательно затрачивать время и аппаратные средства на преобразование

прямых кодов чисел в дополнительные коды, а можно осуществлять считывание массива N отсортированных чисел из устройства в обратном порядке с выходов 5, что является дополнитель-

ным эффектом в предлагаемом устройстве.

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

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

Режим РЧ. Возможны два случая задания режима чтения в устройстве. В первом случае для задания режима чтения на всех входах 9 устанавливается код 00, на всех входах 11 устанавливается логический ноль, а на всех входах 12 - логическая единица. Затем на вход 8 устройства подают синхросигнал, под действием которого число, хранимое в ячейках j-ой строки где 2- j 5 N, переписывается в ячейки (з-1)-й-строки, благодаря связи выходов ячеек j-й строки со входа ш ячеек (з-1)-й строки, а также благодаря тому, что на выходах элементов ИЛИ 2 устанавливается логический ноль, а на выходах элементов ИЛИ 3 устанавливается логическая единица, и, следовательно, на входах установки режима записи всех ячеек

устанавливается код -10, под действием которого в узлах памяти всех ячеек устанавливается режим ЗРз. Код числа, хранимый в ячейках первой строки, может быть считан внешней системой с выхода 4 устройства под

-

действием, например, того же синхро сигнала, которьй подается на вход устройства.

После окончания действия синхросигнала на входе 8 код числа, хранимого в ячейках первой строки, стирается (удаляется из устройства), а на его место записывается код числа, хранимого в ячейках второй с троки, в которые записывается код числа, хранимого в ячейках третьей строки и т.д. В ячейки N-й строки записывается код начальной установки. Установка на выходе 4 устройства после режима РЧ кода начальной установки является признаком того, что все отсортированные числа считаны (удалены) из устройства, устройство находится в исходном состоянии и вновь может быть использовано для сортировки новых чисел без установки режима РНУ. Считывание отсортированных чисел из устройства в рассматриваемом случае осуществляется, начиная с

максимального числа и кончая минимальным.

Во втором случае для задания режима чтения на всех входах 9 уста- с навливается код 00, на всех входах 11 и 12 устанавливается логический ноль. На вход 8 подается синхросигнал, под действием которого число код которого хранится в ячейках j-й

fO строки, где 1 j N, переписывается в ячейки (з+1)-й строк, на входах установки режима записи всех ячеек устанавливается код 00, под действием которого в узлах памяти всех

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

20 же синхросигнала, который подается на вход 8 устройства в режиме чтения. После окончания действия синхросигнала на входе 8 код числа, хранимого в ячейках N-й строки, стирается (уда ляется) из устройства, а в ячейки 1-й строки записывается код -начальной установки. Установка на выходе 4 после режима чтения в устройстве кода начальной установки, при условии, что до задания режима чтения устанавливался код, отличный от кода начальной установки, является признаком, что все отсортированные числа считаны (выведены) из устрой- 35 ства и оно готово для сортировки новых чисел без установки РНУ,

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

30

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

9,

Режим РХ. Для задания режима РХ на всех входах 11 и 12 и, следовательно, на выходах элементов ИЛИ 2 и 3 устанавливается логическая единица, В результате на входах установки режима.записи всех ячеек устанавливается код 11, при котором узлы памяти ячеек устанавливаются в режим хранения и коды, хранимые в ячейках, не изменяются под действием синхросигнала, независимо от состояний, входов 6 и 7 устройства.

Режим PL. Возможны несколько способов использования предлагаемого устройства для организации очередей элементов данньгх типа LIFO, Рассмотрим в качестве примера один способ, когда организация очереди элементов данных типа LIFO осуществляется путем задания соответствующего режима функционирования устройства. Этот режим аналогичен режиму PC с тем отличием, что при записи очередного элемента данных в устройство код ег устанавливают на входе 6, а на входе 7 устройства устанавливают (постоянно) код с максимальным значением, т.е. равный 2 -1, где m - количество разрядов устройства. В качесве элементов данных могут использоваться числа со значением (L) (О L ).

Каждый новый элемент данных воспринимается в устройстве как наибольшее число по отношению к числам,хранимым в устройстве, так как оно воспринимается равным , а в устройстве хранятся числа со значением меньшим 2 -1. В результате каждый новьш элемент очереди записывается в ячейки первой строки. При этом в качестве кода начальной установки в устройстве используется нулевой код. Установка на выходе 4 устройства не нулевого кода является признаком того, что очередь заполнена, т.е. в устройстве нет свободных ячеек памяти. Считывание элементов очереди осуществляется через выход 4 устройства в любой момент путем задания режима РЧ.

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

596710

Режим PF, ,Режим PF аналогичен описанному режиму PL с тем отличием,что на входе 7 устройства постоянно устанавливается нулевой код. В качестве

элементов данных могут использоваться числа со значением (L) , где m - количество разрядов в устройстве. В качестве кода начальной установки устройства используется

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

5 при условии, что в ячейках (-1)-й строки уже записан не нулевой код, т.е. предьщулщй элемент данных. Считывание элементов данных осуществляется через выход 4 устройства путем

0 задания в устройстве режима РЧ.

Режим РП. Режим РП аналогичен режиму PC, с тем отличием, что на К старших разрядах, где К т, га - количество разрядов устройства, входов

5 5 и 7 устанавливается код величины приоритета очередного элемента данных очереди. Значение (ПЭ) кода величины приоритета может находиться

ff

в пределах О ПЭ 2 -1, код элемен- 0 та данных очереди для занесения его в очередь устанавливается на (m-k) младших разрядах входа 6 устройства. На (m-k) младших разрядах входа 7 устройства устанавливается нулевой 5 код. В качестве кода начальной установки в устройстве используется нулевой код. Значение (L) кода элемента данных может быть равным 2(.

0

В результате в устройстве осуществляется сортировка чисел, устанавливаемых последовательно на входе 7 устройства с учетом толь5 ко их k старших разрядов, так как- код k старших разрядов сортируемых чисел устанавливается также и на k старших разрядах входа 7 устройства, на (m-k) младших разрядах ко0 торого устанавливается нулевой код. Если коды приоритета элемента данных, код которого хранится в устройстве, и элемента данных, код которого устанавливается на входе 7

5 устройства, равны, то из таких элементов данных внутри приоритетной очереди элементов в устройстве организуется очередь FIFO, так как код элемента данных вместе с кодом приоn1

ритета,. хранимые в устройстве, образуют двоичное ЧИСЛО; которое всегда больше или равно двоичному числу,установленному на входе 7, при условии что на k старших разрядах чисел (т.е, коды приоритетов) равны, В результате элементы данных в устройстве запоминаются в порядке, определяемом значением приоритета элемента k старших разрядах устройства;так как сортировка двоичных чисел, обра- зованньвд кодом приоритета и кодом элеглента данных, в устройстве осуществляется только с учетом значений приоритета. При этом элемент данных с максимальным приоритетом запоминается в ячейки первой строки. С читы- ваг1Йе элементов очереди осуществляется с Biaxoica 3 устройства в порядке убывания приоритетов элементов.

Несколько предлагаемь х устройств :.5О}кно конструктивным способом параллельно переключать друг к другу; обеспечивая тем сортировку чисел с большим количеством разрядов .

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

Устройство для сортировки чиселэ содержащее матрицу ячеек анализа, кансдая из которых содержит узел памяти, узел формирования управляющих сигналов, включающий два элемента И и элемент ИЛИ, причем в i j-й ячейке анализа 5 где i 1 , „ . . Д , 1 / k количество разрядов в одной ячейке анализа, m количество разрядов в сравниваегчых числах, j l,.,.,, где N - количество сортируемых чисел, выход первого элемента И узла формирования управляющих сигналов соединен с первым входом элемента ИЛИ узла формирования управляющих ; сигналов, выход которого является выходом первого результата сравнения i-j-K ячейки анализа, тактовый вход устройства соединен с синхро- входом .ждого узла памяти ячейкр анализа, информационный выход i-k-й ячейки анализа, где ...s N-15 соединен с первым информационным входом узла памяти i- (k+ t)-й ячейки анализа5 информационные выходы i ячейки анализа являются i-й группой разрядов первого выхода отсортированного числа устройства, i-я группа разрядов входа наращива67 12

ПИЯ количества сравниваемых ч .сел

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

формировани управляющих сигналов qij-й ячейки анализа, где ,,sc5lj- соединены с выходом второго реззшь- тата сравнения (q-1) 3-й ячейки ана- ли за„ выход второго результата сравнения l j-й ячейки анализа является J-M выходом второго результата сравнения устройства, отличающееся тем, что, с целью расширения функциональных возможностей

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

анализа введена схема сравнения,

узел памяти содержит k элементов памяти „ причем в 1-.-й ячейке анализа первы.й и. второй выходы схемы сравнения соединены с информационными

входами первого и второго элементов И узла формт- рования управляющих сигналов соответственно, выход второго элемента И узла формирова.ния управляющих сигналов является выходом вто

рого результата сравнения i-j-й ячейки анализй... выход узла памяти i j-й ячейки анализа является информационным выходом i-j-й ячейки анализа и соединен с первым информационным входом схемы сравнения, второй информационный вход схемы сравнения ячейки анализа является i-й группой ра.зрядов входа сравниваемых чисел устройства, второй вход элемента ИЛИ узла формирования управляющих сигналов l-j-й ячейки анализа является J-M входом второго разряда управляющего кода устройства 5 выход первого результата сравнения l-j-й ячейки

анализа является j-ь вь5ходом первого результата сравнения устройства, второй вход элеь;ента ИШ-1 узла форш1- рования управляющих сигналов ячейки анализа подключен к выходу

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

третий информационны/5: вход узла памяти р-и ячейки анализа, где 1., соединен с информационным выходом (р+1) Л-й ячейки анализа, первый вход j-ro элемента ИПИ первой группы соединен с J-M входом первой группы входов установки режима устройства, j-й выход первой группы установки режима записи устройства соединен с первым входом установки режима записи узла памяти i j-x ячеек анализа и с выходом j-ro элемента ИЛИ первой группы, второй и третий входы которого соединены с (j-1)-ми выходами первого и второго результатов сравнения устройства, j-й вход второй группы входов установки режима устройства соединен с первым входом j-ro элемента

ИЛИ второй группы, выход которого соединен с вторым входом установки режима записи узлов памяти i-j-x ячеек анализа и с i-м выходом второй группы выходов режима записи устройства, i-e выходы первого и второго результатов сравнения устройства соединены с вторым и третьим входами i-ro элемента ИЛИ второй группы, выходы узла памяти 1:1-ячейки анализа являются i-й группой разрядов второго выхода отсортированного чис- ла устройства, дополнительные входы первого и второго результатов сравнения устройства соединены с вторым и третьим входами элемента ИЛИ первой группы.

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