Устройство для сортировки информации

 

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

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

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

РЕСПУБЛИК (19) (11) А1

ы) 4 G 06 F 7/06

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3956999/24-24 (22) 24.09.85 (46) 07.09.87. Бюп. )1 33 (7 1) Киевский завод электронных вычислительных и управляющих машин— головное предприятие Киевского производственного объединения "Электрон маш" им. В.И. Ленина (72) Н.Т. Пшеничный (53) 68 1.325(088.8) (56) Палернов А.А. и др. Методы упорядочения информации в цифровых системах. — М.: Наука, 1973..

Кнут Э. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. — М.: Мир, 1973.

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

У 1193957, кл. G 06 F 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦКИ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки информации, например в информационно-поисковых системах. Цель изобретения — увеличение быстродействия. Для достижения указанной цели система содержит блок 1 памяти, состоящий из двух узлов 4,5 памяти, блок

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

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

Цель изобретения — увепичение быстродействия.

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

Устройство содержит блок 1 памяти, блок 2 формирования адресов перемещений и блок 3 управления.

Блок 1 памяти предназначен для хранения исходного и упорядоченного массива, для выдачи ключей или их час тей, а также для выдачи и приема информационных ключей в процессе упоря— дочения. Блок 1 памяти содержит два узла 4 и 5 памяти с произвольной выборкой, регистр 6 адреса, регистр 7 данных, накопитель 8 и схему 9 управления памятью. Схема 9 управления памятью представляет собой дешифратор команд для узла памяти: запись в регистр 6 адреса + 1, запись в регистр

7 данных, запись (чтение) информации в (иэ) накопитель 8. Блок 2 предназначен для хранения служебной информации о сортируемом массиве, для подсчета кодов в обрабатываемых секциях ключа, для формирования адресов перемещения, а также для выдачи адресов перемещения в узлах 4 и 5 памяти на фазе перемещения.

Блок 2 (фиг.3) содержит узел 10 рабочих регистров, узел 11 памяти, буферный регистр 12 и арифметикологический узел 13. Регистры узпа 10 рабочих регистров имеют постоянное функциональное назначение и заполняются служебной информацией при загрузке устройства. Конкретный адрес регистра поступает из блока 3 управления. Узел 11 памяти предназначен для хранения результатов подсчета и адресов перемещения. Узел 11 памяти реализован по схеме, приведенной на ф иг. 2.

Блок 3 управления (фиг.4) предназначен для синхронизации и управления работой всех узлов системы и содержит узел 14 переключателей, регистр 15

При инициации работы системы начинается сортировка в первой (младшей) секции ключа. Блок 3 управления формирует микрокоманды, управляющие работой устройства (фиг.5). Во время инициации под управлением поля управления блока подсчета и сортировки кода микрокоманды код длины массива передается иэ узла 10 рабочих регистров в блок 3 управления. Затем начинается первая фаза сортировки — распределение, т.е. вычисление объема свободной памяти (необходимого для размещения в нем всех информационных слов с кодом i в сортируемой секции) 35977

«дреса микрокоман ч, регистр 16 микро— команд, узел 17 памяти микрокоманд, формирователь 18 синхроимпульсон, счетчик 9 длины массива, счетчик 20 длины информационного слова .

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

В исходном состоянии неупорядочен10 ный массив информации, например, из

16 информационных слов расположен в узле 4 памяти (фиг.ба). Узел 5 памяти свободен. В ячейках О, 1,2,3 находится первое информационное слово °

15 Разрядность ячейки равна минимально адресуемой единице в узлах 4 и 5 памяти, либо кратна ей. В нашем примере разрядность ячейки предполагается равной одному байту (8 разрядов).

20 В ячейках 4-7 находится второе информационное слово, в ячейках 60-63 — последнее, шестнадцатое информационное слово. Младший байт каждого слова, расположенный в ячейках 3,7, 11...63

?5 это первая секция — секция,с которой начинается сортировка. Старший байт каждого слова (четвертая секция) находится в ячейках 0,4...60. Пусть сортировка выполняется по признаку (клю30 чу) иэ младших двух байтов. Служебная информация о неупорядоченном массиве находится в узле 10 рабочих регистров: код 16 — длина массива (количество информационных слов), код 4 „ длина информационного слова в байтах, 35 код 2 — длина ключа в байтах, код 3 адрес первого байта первого от начала информационного слова, с которого начинается сортировка, код 60

40 адрес последнего (первого от конца) информационного слова, код 7 — максимальная величина кода в группе разрядов (байте) ключа.

1 1 Ч77

V.=K;С

1 м с О х p

I (полученного для кода при всех возможных значениях i) в ячейке i узла

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

7 вторбго кода сортируемой секции.

Адрес 7 — это адрес 3 первого кода, модифицированный на длину информационного слова. Узел 4 памяти выполняет чтение по адресу 7 и пересылает счи— танный код в блок 2 для обработки.

<ок 3 управления выполняет подсчет количества считанных кодов сортируемой секции. После чтения последнего кода ячейки 63 узла 4 памяти и передачи его в блок 2 для обработки в блоке 3 управления появится условие окончания подсчета. К этому моменту в каждой ячейке i блока 2, где возможная величина кода в группе (байте) будет указан объем Ч; свободной памяти, необходимый для размещения в нем всех информационных слов. с кодом в сортируемой секции (фиг.бб, строка 2). где К вЂ” количество кодов в сортируемой секции, равных

С вЂ” длина информационного слова (коэффициент масштабирования)

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

На третьей фазе сортировки первой секции для каждого расположенного в

55 узл(4 памя Гп ннфо1)ма цпонно1 О < лов<я отыскивается соответствующий адрес перемещения и осуществляется перемещение этого информационного слова в узел 5 памяти по найденному адресу.

Для поиска адресов перемещения коды сортируемой секции последовательно читаются из узла 4 памяти, начиная со старших или младших разрядов, в зависимости от способа их формирования на втором этапе. Если на втором этапе в каждой ячейке i узла 11 памяти блока 2 получена сумма содержимого всех ячеек > i минус длина информационного слова, то для поиска адресов перемещения коды сортируемой секции последовательно читаются из узла 4 памяти, начиная со старших адресов, а упорядочение осуществляется по уменьшению величины кода ключа.

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

В любом случае очередной код сортируемой секции, считанный из узла 4 памяти, используется как адрес ячейi узла 11 памяти блока 2, где имеется искомый адрес перемещения. При каждом обращении в ячейку i ee содержимое уменьшается на длину информационного слова и вновь указывает истинный адрес перемещения для очередного информационного слова с кодом в сортируемой секции. После перемещения всех информационных слов в узле 5 памяти оказывается частично упорядоченный массив по кодам первой секции.

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

В рассматриваемом примере адрес

63 (сохранившийся после чтения последнего кода первой секции) первого от конца кода сортируемой секции из блока 2 по шине данных пересылается в узел 4 памяти. Считанный по адресу 63 код 7 поступает в блок 2, где из ячейки 7 узла 11 памяти считывается адрес

12 перемещения первого от конца информационного слова. Адрес 12 перемещения пересылается в узел 5 памяти, а

5 13359 начальный адрес 60 первого от конца информационного слова пересыпается из блока 2 в узел 4 памяти. Далее под. управлением полей управления узлами

4 и 5 памяти (фиг.5) микрокомандами

5 блока 3 управления выполняется перемещение информационного слова из ячеек

60-63 узла 4 памяти в ячейки 12-15 узла 5 памяти. Модификация адреса на единицу при перемещении информационного слова из узла 4 памяти в узел 5 памяти осуществляется в регистрах адреса этих устройств, при этом данные с выхода узла 4 памяти поступают непосредственно на вход данных узла 5 памяти, что позволяет сократить время перемещения. После перемещения всего информационного слова блок 3 управления инициирует передачу из блока 2 2п в адрес 59 (формируемый как 63 минус

4) второго от конца кода сортируемой секции. Код 7, считанный из ячейки

59 узла 4 памяти, используется как адрес ячейки узла 11 памяти, в кото- 25 рой записан адрес 8 перемещения, сформированный в блоке 2 как 12 минус

4 еще при выборке адреса 12. Адрес

8 перемещения пересыпается из узла 4 н узел 5 памяти в адрес 56 (формируе- до мый как 60 минус 4) второго от конца информационного слова. После перемещения из узла 4 памяти в узел 5 памяти второго от конца информационного слова блок 3 управления инициирует передачу из блока 2 в адрес 55 третьего от конца кода сортируемой секции.

Код 4 из ячейки 55 узла памяти используется для выборки из узла 11 памяти адреса 52 перемещения третье- 40

ro от конца информационного слова, а затем осуществляется перемещение этого слова из узла 4 памяти в узел

5 памяти. После перемещения из узла

4 памяти в узел 5 памяти последнего информационного слова сортировка по убыванию кодов первой секции оконче— на (фиг.бв). Код длины ключа уменьшается на единицу в блоке 2 и анаЛизируется на нуль. Если результат

50 не равен нулю, то блок 3 управления осуществляет переход к сортировке по .кодам второй секции.

Сортировка во второй секции также выполняется за три фазы: распределе55 ние, формирование адресов перемещения и перемещение. При этом узел 5 . памяти — сортируемый массив, а узел

4 памяти свободен. Перед началом распре77 б деления ячеек местной памяти блок 2 обнуляется, код 16 длины массива передается из блока Z в блок 3 управления для анализа конца подсчета, а адрес 3 первой гоуппы разрядов (байта) первой секции преобразуется в адрес первого кода второй секции (уменьшается на единицу). После этой подготовки начинается распределение.

Во второй секции оно выполняется так же, как и в первой. При этом адреса кодов сортируемой секции поступают из блока 2 в узел 5 памяти. Коды считываются из ячеек узел 5 памяти и передаются в блок 2, где выполняется распределение в зависимости от вели-. чины поступающих кодов. После однократной передачи всех кодов второй секции из узла 5 памяти в блок 2 в каждой ячейке i узла 11 памяти этого устройства окажется код, указывающий необходимый размер памяти для размещения всех информационных слов, содержащих код i во второй секции (фиг.бг, строка 2) .

Формирование адресов перемещения на второй фазе выполняется в блоке

2. После второй фазы в каждой ячейке узла 11 памяти будет записан адрес перемещения первого от конца массива информационного слова с кодом i во второй секции (фиг.бг, строка 3).

Третья фаза сортировки по кодам второй секции отличается лишь тем, что узел 5 памяти является передающим, а узел 4 памяти приемным. Коды второй секции последовательно, начиная со старших адресов ЗУ 5, 62, 59, 54...2, читаются и пересылаются по шине данных в блок 2. Каждому коду в узле 11 памяти блока 2 соответствует адрес перемещения, указывающий по какому адресу в узел 4 памяти необходимо переместить из узла 5 памяти информационное слово с кодом i во второй секции. При каждом обращении в ячейку i за адресом перемещения ее содержимое уменьшается на длину информационного спова. После перемещения всех информационных слов из узла 5 памяти в узел 4 памяти в последнем окажется массив, упорядоченный по ключу из двух групп разрядов (байтов), хотя сортировка во второй секции выполнялась без анализа кодов первой секции (фиг.бд).

Для полного упорядочения исходного массива необходимо выполнить столь

1335977 циклов сортировки, сколько групп разрядов (секций) содержит ключевое слово (ключ) . Окончательно упорядоченный массив информации окажется расположенным в узле 4 памяти или в узле 5

5 памяти в зависимости от того, четное или соответственно нечетное число групп разрядов содержит ключ.

При сортировке информационных слов 10 в порядке увеличения кода ключа — на второй фазе в каждой ячейке i узла

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

Объем сортируемой информации определяется емкостью одного из узлов 4 и 5 памяти с произвольным доступом, т.е. может быть равен 1-4 байтам.

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

Блок 2 (фиг.4) работает следующим образом.

В исходном состоянии служебная информация находится в постоянно распределенных регистрах узла 10 рабочих регистров. Перед обработкой каждой секции все ячейки узла 11 памяти блока 2 обнуляются под управлением сигналов иэ блока 3 управления.

При распределении каждый код сортируемой секции величиной i, поступаю- 40 щий из узла 4 памяти в узел 5 памяти, подается на адресный вход узла 11 памяти и таким. образом адресует ячейку i узла 11 памяти. В это время блок

3 управления в поле управления узлом 45

1i памяти микрокоманды выдает для узла 11 памяти операцию "Чтение-модификация записи". Содержимое ячейки первый раз равное нулю, читается и подается на первый информационный вход арифметико-логического узла 13.

На второй информационный вход арифметико-логического узла 13 из регистра операции "Чтение" для узла 10 рабочих регистров задаются полем управления узлом рабочих регистров микрокоманды.

Арифметико-логический узел 13 под управлением поля управления арифметико-логическим узлом выполняет суммирование, а результат записывается в ту же ячейку i узла 11 памяти. Первый код величиной i поступивший из блока

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

На второй фазе формирование адресов перемещения, указанных на фиг.бб (строка 3), выполняется путем суммирования результатов, полученных в узле 11 памяти на первой фазе. При этом в каждой ячейке i узлов 11 памяти образуется сумма содержимого всех ячеек i минус длина информационного слова. Для этого в регистре К узла

10 рабочих регистров формируется дополнительный код длины информационного слова. Затем максимальный код 7 группы разрядов (преимущественно максимально возможный код) из узла 10 рабочих регистров пересыпается на адресный вход узел 11 памяти. Управляющие сигналы из блока 3 управления вызывают чтение содержимого ячейки

7 узла 11 памяти и содержимого регистра К узла 10 рабочих регистров.

Эта информация суммируется на арифметико-логического узла 13, а -результат, равный 12, пишется в регистр

R узла 11 рабочих регистров и ячей1 ку 7 узла 11.памяти, Затем читается и суммируется содержимое ячейки 6 узла 11 памяти и регистра R узла

10 рабочих регистров. Результат запоминается в рабочем регистре R u

J в ячейке 6 узла 11 памяти. Суммирование продолжается до обработки содержимого ячейки 0 в узле 11 памяти и получения результатов согласно фиг.бб, строка 3.

При суммировании не должно быть переполнения из арифметико-логического узла 13. Если оно имеется, это признак ошибки в устройстве ° Сигнал

113 ч7; об ошибке через выход пере((олнения блока 2 поступает в блок 3 управления, где вызывает прекращение опера(гни сортировки °

Адреса перемещения также могут быть получены путем суммирования результатов, полученных в узле 11 памяти на первой фазе так, что в каждой ячейке узле 11 памяти образуется сумма содержимого всех ячеек i минус длина информационного слова. Для этого в регистре RJ узла 10 рабочих регистров формируется дополнительный код длины информационного слова. Затем код 0 пересылается на адресный вход узла

11, содержимое ячейки 0 узла 11 памяти суммируется с содержимым регистра

К узла 10 рабочих регистров, а результат заносится в ту же ячейку 0 узла 11 памяти и в регистр R узла 10 рабочих регистров для использования в следующем ггикле суммирования. Далее содержимое ячейки 1 узла 11 памяти 25 суммируется с новым значением регистра R ° узла 1О рабочих регистров, а результат заносится в ячейку 1 узла

11 памяти и в регистр R узла 10 рабоJ чих регистров. Суммирование продолжа- 30 ется до обработки содержимого ячейки

7 узла 11 памяти (преимущественно до максимально возможного кода в сортируемой группе).

Блок 3 управления системой (фиг.4) работает следующим образом.

Нажатие кнопки "Сброс" в узле 14 переключателей устанавливает систему в исходное состояние, в том числе адрес первой микрокоманды в регистре 15 адреса микрокоманд. Нажатие кнопки

"Пуск" инициирует работу формирователя 18 синхроимпульсов, который формирует серию синхроимпульсов. С появле- 45 нием синхроимпульсов начинается выборка микрокоманд из схемы 17 памяти микрокоманд и фиксация их в регистре

16 микрокоманд. С выхода регистра 16 микро(команд управляющие сигналы поступают в блок 1 памяти и в блок 2.

Формат микрокоманд показан на фиг.5. Микрокоманды иэ схемы 17 памяти микрокоманд читаются, управляя процедурами сортировки в системе.

Текущая последовательность микрокоманд изменяется при изменении условий ветвления, т.е. при появлении сигналов переполнения. с н((>:о;я < ((т ((f Y,» 1 .1 длины (1:1(.

c((Р(l (l0(. (Ð об j(:(P от к(((3(. \. õ к (if (îå (. ор тируемой секции, с выхода счетчика 20 длины слова после перемещения очередного информационного слова на фазе перемещения, — из блока 2 при ошибке.

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

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

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

3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок управления содержит регистр адреса микрокоманд, узел памяти микрокоманд, регистр микрокоманд, счетчик длины массива, счетчик длины информационного

11 1335977 1 с слова, формирователь синхроимлульсов нен с информационным входом поля ади узел переключателей, причем входы реса следующей.микрокоманды регистра у овий ветвления блока соединены с адреса микрокоманц, второй выход узинформационными входами счетчика дли- ла памяти микрокоманд соединен с ин5 ны массива и счетчика длины слова, формационным входом регистра микрокопервый выход узла переключателей сое- манд, выходы счетчиков длины массива динен с входами сброса регистра адре- и длины информационного слова соедиса микрокоманд и регистра микрокоманд иены с информационными входами полей второй выход узла переключателей сое- 1< ветвления регистра адреса микрокодинен с входом запуска формирователя манд, первый и второй выходы регистра синхраимпульсов, первый выход форми= микрокоманд соединены с первым и вто— рователя синхроимпульсов соединен с рым выходами блока соответственно, входами строба регистра адреса микро- третий выход регистра микрокоманд команд и регистра микрокоманд, вход 15 соединен с входом тактирования формипризнака ошибки блока соединен с вхо- рователя синхроимпульсов, второй и дом останова работы регистра адреса третий выходы которого соединены с микрокоманд, выход регистра адреса входами асинхронной загрузки и суммимикрокоманд соединен с адресным вхо- рования счетчиков длины массива и дом узла памяти микрокоманд, первый о длины информационного слова соответвыход узла памяти микрокоманд соеди- ственно.

1 3. 3597 7

Фиг 1 я0реса 00е о-ю сенция 1стариая)

J-я сенцом

2-я сенция

1-ю сенция (люадмая) 0 1 2 5 ц g 6 7 АРреса лестнои лолямги Юсй2

0 0 0 0 2г 12 у 1ф реглер налюти аюю ин(рорлоциоммуа eargr б0 ба 00 02 20 16 !2 Adpeca перелещемия нойолг

Аореса ЛЮ

0-я сенция

0-я сениия

z- сенция

1-s сенция

Фиг. б

ВН1ИПИ Заказ 4048/43 Тираж 672

Подписное

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4