Устройство для упорядочения слов

Устройство для упорядочения слов

Иллюстрации

Показать все

Реферат

 

Союз Советских

Социалистических

Республик

00 608153 (6l) дополиительное к айт с «.ну (22) Заявлено 26 11 75(21) 2193497/18-24 с присоединением заявки № (23) Приоритет (Я) У (. Кл.2

G 06 Р 7/00

Гасударственный комитет

Совете Министров СССР оо делам изооретеиий н открытий (43) Опубликовано 25.05.78Бюллетень № 19 (46) дата опуааниопаинп описании 1Г.Ои g$ (53) УДК 681.З-7 (088.8) (12} Аееторы пвобретенка

М. С. Белков, Е. А. Братапьский н С. С. Калиичев (7i} Заявитель (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ а СЛОВ

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

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

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

Наиболее близким техническим решением 1а является устройство для упорядочения п слов; содержащее регистр исходной информации, регистр управления из и групп разрядов, регистр результата (21.

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

Целью изобретения является повышение быстродействия устройства упорядочения. Это достигается тем, что оно содержит и дешифраторов, 4 и узлов уплотнения, 4 п коммутаторов; причем входы i-го (i = 1 —: n) дешифра-. тора соединены с выходами старших разрядов

i-ой группы регистра управления, первая груп па входов каждого j-го fj = 1 —. 4n j узла уплотнения соединена с соответствующим раз- 25

2 рядным выходом регистра исходной информации, вторая группа входов. — с выходом младших разрядов соответствующей группы регистра управления, а третья группа входов каждого j-го узла уплотнения соединена с выходом соответствующего дешифратора, первая и вторая группы выходов j-го узла уплотнения соединены соответственно с первой и второй группой входов. j-го коммутатора, а выходы всех коммутаторов — со входами регистра результата.

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

Устройство содержит регистр исходной информации 1, регистр управления 2 из п групп разрядов, регистр результата 3, дешнфраторов 4, 4 и узлов уплотнения 5, каждый с

3-мя групнамя входов н 2-мя группами выходов, и п коммутаторов 6 с 2-мя группами входов каждый; взводы i-ro дешифратора 4 (i = 1 —: и) соединены с выходами старших разрядов i-ой группы регистра управления 2; в j-м узле уплотнения 5 (j = I —:4п ) первая группа входов соединена с выходами регистра исходной информации l, вторая группа входов — с выходами младших разрядов сверх групп регистра управления 2, а третья группл

á08l.53

1О

ts го з с j-ми выходами дешифраторов 4, первая и вторая группы выходов j-го узла уплотнения 5 соединены соответственно с первой и второй группой входов )-го коммутатора 6, а выходы всех коммутаторов б — - со входами регистра результата 3.

Узлы 5, б могут быть реализованы различными известными способами. На фиг. 3 и фиг. 4 приведен пример реализации этих узлов.

Узел уплотнения 5 содержит блок сумматоров 7, уплотннтель кодов сдвига 8, уплотннтель информации 9 и уплотнитель младших разрядов 10. В узле уплотнения 5 первая группа входов-соединена с информационными входами уплотнения 9, а первая группа выходов— с выходами уплотнителя 9; вторая группа выходов соединена с информационными входами уплотнителя 10.

Входы уплотнители кодов сдвига 8 соединены с выходами блока сумматоров 7, а выходы узла 8 — с управляющими входами уплотнителей 9 и 10.

Коммутатор 6 содержит блок дешифраторов

11 и 4п концентраторов 12. Первая группа нкодон коммутатора 6 соединена с информационными входами всех концентраторов 12; вторая группа входов этого коммутатора — со входами блока дешифраторов 11, выходы которого соединены с управляющими входами концеитра- торов 12. Выходы концентраторов 12 являются выходами коммутатора 6.

Блоки 7 — 12 могут выполняться различными известными способами.

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

В нщальном состоянии в регистр 1 заносится исходная информация (n слов), à. в ре-гистр управления 2 — номера слов s упорядоченном массиве (адреса). Длина каждого адреса — logan разрядов. Код i-ro адреса М (1 = 1 —: п) имеет группу старших и группу младших разрядов. Каждая группа имеет длину ф- log,n разрядов; i-я группа старших разрядов поступает íà i-дешифратор 4 и дешифрнруется в нем; Группа младших разрядов всех адресов и исходная информация из регистра 1 подаются иа j-й.узел уплотнения 5 (j =. Il —;ttn)

j-е выходы всех дешифраторов 4 образуют j-to . маску управления, которая выделяет информацию и соответствующие группы младших разрядов адресов, значения которых лежат в интервале: (j — 1) оп —, 1 п — 1

8 узле 5 под управлением j-ой маски происходит выделение и уплотнение п слов и, соответствующих им, групп младших разрядов. Например информация xt хв хв х4 хь хв хт хв маска 0 0 1 0 1 1 1 0 результат se xe

В результате, на первой группе выходов узла 5 формируется плотный массив Мп слов, а на второй группе выходов — плотный массив соответствующих групп младших разрядов адресов.

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

4

Затем с выхода j-ro узла 5Я слов и групп младших разрядов адресов подаются на j-й коммутатор 6, где происходит упорядочение информации по младшим разрядам адресов.

На выходе коммутаторов 6 все слова оказываются окончательно расставленными по адресам регистра управления 2. Упорядоченный массив слов заносится в регистр результата 3 и на этом работа устройства заканчивается, На рис. 2 в качестве примера показана блок-схема быстродействующего устройства упорядочения для 16 слов.

В начальном состоянии в регистр 1 заносится исходная информация (16 слов), а в регистр управления 2 — номера слов в упорядоченном массиве (адреса). Длина каждого адреса 4 разряда. Код i-го адреса (i 1 —: 16) имеет группу старших н группу младших разрядов, каждая группа имеет длину 2 разряда, i-я группа старших разрядов поступает íà 1-Й дешифратор 4 и дешифрируется в нем. Группы младших разрядов всех адресов и исходная информация (l6 слов) из регистра подаются íà j-й узел уплотнения 5 (j =- 1 —: 4); j-e выходы всех дешифраторов 4 образуют j-ю маску управления, которая выделяет информапию и соответствующие группы младших разрядов адресов, значения которых лежат в интервале: 4(j — 1) —: — 4j — 1.

Найример, первые выходы всех дешифраторов 4 образуют маску, которая в первом узле 5 из 16 слон и 16 групп младших разрядов адресов выделяет те, адреса которых лежат в интервале: 0 —; 3.

В узле 5 под управлением j-й маски происходит выделение и уплотнение 4 слов и соответствующих им. групп младших разрядов. В результате на первой группе выходов узла 5 формируется плотный массив 4 слов, а на второи группе выходов — плотный массив соответствующих групп младших разрядов адресов.

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

Затем с выхода j-го узла 5 слова 4 и 4 группы младших разрядов подаются иа j-й коммутатор б, где происходит упорядочение информации уже по младшим разрядам адресов.

Разовая коммутация — есть произвольная перестановка и исходных разрядов (или слов).

Пример I; информация х> хв хз х4 хв хв х хв адреса 3 .l 2 4 7 8 6 5 результат хв Х1 х2 х4 ху хв хв х>

Концентрация . есть выборка одного из исходных разрядов (или слов}.

Пример 2. информация х! хх хз х4 Хв Хв Ху Хв адрес выборки 5 результат хв

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

Таблица 1

16 64 256 1024

24 36 46 58

80 216 448 800 и, слов

Т, т

Тр,т

Таким образом, применение предложенного устройства позволяет существенно сократить время упорядочения массива слов. Например, при реализации такого устройства иа ннтеграль ных схемах серии 133 («Логика — 2») за 1 мк. сек. можно упорядочить массив нз 256 слов, а на устройстве — прототипе (при прочих равных условиях) — лишь из 32 слов.

Затраты оборудования в предлагаемом устройстве (L ) и в устройстве — прототипе (Lq) составляют:

L C -п и

Еи Сь п-)Офзп где С и C> — некоторые константы, зависящие от набора логических элементов и реализации основных узлов.

Быстродействие предлагаемого устройства, т.е. время упорядочения слов, равно:

Т, = T„hhAA+ Т,=.. . Т лл = С (logpA

Т,.„„=С 1он п где: С н С вЂ” некоторые константы, зависящие от набора логических элементов.

В таблице l приведены результаты расчета

Т для п в пределах от lá до 1024 слов. Лля сравнения там же приведено быстродействие устройства — прототипа (Т 1

Т = .Сз logq n где: С вЂ” некоторая константа, зависящая от набора логических элементов.

Отсюда следует, что характер роста I. u

L> в широких пределах примерно одинаков и дополнительные затраты оборудования при полученном выигрыше быстродействия иезначи5 тельны.

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

Устройство для упорядочения пслов,,содержащее регистр исходной информации, регистр управления из и групп разрядов, регистр результата, отличающееся тем, что с целью повышения быстродействия, оно содержит и дешифраторов, 1п узлов уплотнения, ï коммутаторов, причем входы.i-ro (i l —: п) дешнфратора соединены с выходами старших разрядов i-ой группы регистра.управления, первая группа входов каждого j-го (j = 1 —: 4n } узла уплотнения соединена с соответствующим разрядным выходом регистра исходной информа20 ции, вторая группа входов с выходом младших разрядов соответствующей группы регистра управления, третья группа входов каждого

j-го узла уплотнения соединена с выходом соответствующего дешифратора, первая и вторая группы выходов j-го узла уплотнения соединены соответственно с первой и второй группой входов j-го коммутатора, выходы — всех коммутаторов — со входами регистра результата.

Источники информации, принятые во внимание при экспертизе:

l. США патент 3428946, 340 †1.2, 1972.

2, Папернов А. А., Подымов В. Я. Методы упорядочения информации в цифровых системах, М., «Наука», 1973, стр. 133 — 138. Редактор P. Антонова

Заказ 2802 33

Составитель Р..Яворский

Тек ред О. Л угон ая Корректор H. Туонца

Тираж 826 . Додпысное

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

I I 3035, Москва, )К-35, Раушская наб., д. 4/5

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