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

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

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

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

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

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

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

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

адреса мт крокомаи 1, регистр 16 микрокоманд, узел 17 памяти микрокоманд, фop o poвaтeль 18 синхроимпульсов,

счетчик 19 длины массива, счетчик 20 /ушны информационного слова.

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

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

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

В ячейках 4-7 находится второе информационное слово, в ячейках 60-63 - последнее, шестнадцатое информационное слово. Младший байт каждого слова, расположённый в ячейках 3,7, 11...63 это первая секция - секция,с которой начинается сортировка. Старший байт каждого слова (четвертая секция) находится в ячейках О,4...60. Пусть сортировка выполняется по признаку (ключу) из младших двух байтов. Служебная информация о неупорядоченном массиве находится в узле 10 рабочих регистров: код 16 - длина массива (количество информационных слов), код 4 длина информационного слова в байтах, код 2 - длина ключа в байтах, код 3 - адрес первого байта первого от начала информационного слова, с которого начинается сортировка, код 60 адрес последнего (первого от конца) информационного слова, код 7 - максимальная величина кода в группе разрядов (байте) ключа.

50

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

55

Г ri4 11

coxpaiitniiie каждого ре:)у.пьтата V.

от п щ у с чи с за ни эт мя м ад с у ад ся ма дл п ти т мл щ ти п ис об ум сл пе ци се ма ва по

(тюлученног о для кода iipsi всех возможных значениях 1) в ячейке 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, где i - возможная величина кода в группе (байте) будет указан объем V; свободной памяти, необходимый для размещения в нем всех информационных слов, с кодом i в сортируемой секции (фиг.66, строка 2).

V. К;. С,

где К - колич ество кодов в сортируемой секции, равных ij С - длина информационного слова (коэффициент масштабирования)

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

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

5

0

5

0

5

0

5

0

5

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

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

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

513

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

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

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

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

по кодам второй секции.

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

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

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

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

Формирование адресов перемещения на второй фазе вьшолняется в блоке 2. После второй фазы в каждой ячейке

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

Третья фаза сортировки по кодам второй секции отличается лишь тем, что узел 5 памяти является передающим, а узел 4 памяти приемным. Коды второй секции последовательно, начиная со старших адресов ЗУ 5, 62, 59,

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

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

5

0

5

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

При-сортировке информационных слов Q содержимое той же ячейки на длину

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

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

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

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

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

50

3 управления в поле управления узлом g RJ узла 11 рабочих регистров и ячей- 11 памяти микрокоманды вьщает-для узла 11 памяти операцию Чтение-модификация записи. Содержимое ячейки i, первый раз равное нулю, читается и подается на первый информационный вход арифметико-логического узла 13. На второй информационный вход арифметико-логического узла 13 из регистра операции Чтение для узла 10 рабочих регистров задаются полем управления узлом рабочих регистров микрокоманды. Арифметико-логический узел 13 под управлением поля управления арифметико-логическим узлом выполняет сумми55

ку 7 узла 11.памяти. Затем читается и суммируется содержимое ячейки 6 узла 11 памяти и регистра R- узла 10 рабочих регистров. Результат запоминается в рабочем регистре R- и в ячейке 6 узла 11 памяти. Суммирование продолжается до обработки содержимого ячейки О в узле 11 памяти и получения результатов согласно фиг.66, строка 3.

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

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

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

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

размещения всех информационных слов с кодом i в сортируемой секции.

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

слова. Для этого в регистре R; узла 10 рабочих регистров формируется дополнительный код длины информационного слова. Затем максимальный код 7 группы разрядов (преимущественно максимально возможный код) из узла 10 рабочих регистров пересьшается на адресный вход узел 11 памяти. Управляющие сигналы из блока 3 управления вызывают чтение содержимого ячейки 7 узла 11 памяти и содержимого регистра RJ узла 10 рабочих регистров. Эта информация суммируется на арифметико-логического узла 13, а-результат, равный 12, пишется в регистр

50

g RJ узла 11 рабочих регистров и ячей-

55

ку 7 узла 11.памяти. Затем читается и суммируется содержимое ячейки 6 узла 11 памяти и регистра R- узла 10 рабочих регистров. Результат запоминается в рабочем регистре R- и в ячейке 6 узла 11 памяти. Суммирование продолжается до обработки содержимого ячейки О в узле 11 памяти и получения результатов согласно фиг.66, строка 3.

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

и

06ошибке через .гход переполнения блока 2 поступает в блок 3 ynpasnetniH где вызывает прекращение onepaipiH сортировки ,

Адреса перемещения также могут быт получены путем суммирования результатов, полученных в узле 11 памяти на первой фазе так, что в каждой ячейке i узле 11 памяти образуется сумма содержимого всех ячеек f:i минус длина информационного слова. Для этого в регистре RJ узла 10 рабочих регистров формируется дополнительный код длины информационного слова. Затем код О пересылается на адресный вход узла 11, содержимое ячейки О узла 11 памяти суммируется с содержимым регистра RJ узла 10 рабочих регистров, а ре- зультат заносится в ту же ячейку О узла 11 памяти и в регистр R; узла 10 рабочих регистров для использования в следующем ш-1кле суммирования. Далее содержимое ячейки 1 узла 11 памяти суммируется с новым значением регистра RJ узла 10 рабочих регистров, а результат заносится в ячейку 1 узла 11 памяти и в регистр RI узла 10 рабочих регистров. Суммирование продолжа- ется до обработки содержимого ячейки

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

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

Нажатие кнопки Сброс в узле 14 переключателей устанавливает систему в исходное состояние, в том числе ад- рее первой микрокоманды в регистре 15 адреса микрокоманд. Нажатие кнопки Пуск инициирует работу формирователя 18 синхроимпульсов, который формирует серию синхроимпульсов. С появле- нием синхроимпульсов начинается выборка микрокоманд из схемы 17 памяти микрокоманд и фиксация их в регистре 16 микрокоманд. С выхода регистра 16 микрокоманд управляющие сигналы поступают в блок 1 памяти и в блок 2.

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

Текущая последовательность микрокоманд изменяется при изменении условий ветвления, т.е. при появлении сигналов переполнения;

I li

-с .1ЫУ.(1л;1 счетчика 19 длины мпс.- сива после с ОрлГиггкп кодог ccip тируемой секции,

-с вьЕХода сч(П чика 20 длины слова после перемещения очередного информа- )Ц1онного слова на фазе перемещения,

-из блока 2 при ошибке.

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

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

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

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

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

1 113

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

10

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

15

0

ИзЗ

Риг.З

из 2

из г

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

Адреса местной поня/пи uncKZ

Ра)нер попита Зия инугор/тционмыч cfft с

Адреса перемещенияitaBoni

Бнмти

Заказ 4048/43 Тираж 672

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

ЛЗрееа JW

ч- акция tcmapaa)

3-я cfKttuf

Z-f секция

1-я сгнция 1пмОшм)

Адреса 3V5 if- секция J-я сеяния г-я секция 1-я секция

Подписное