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

ОЮЗ СОВЕТСКИХ ОЦИАЛИСТИЧЕСКИРЕСПУБЛИК в 4 С.ч ОПИСАНИЕ ИЗОБРЕТЕН НА ЮГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ СКОМУ СВИДЕТЕЛЬСТВ(7 1) Киевский завод электронных вычислительных и управляющих машин - головное предприятие Киевского производственного объединения "Электрон маш" им. В.И. Ленина(56) Палернов А.А. и др. Методы упорядочения информации в цифровых системах. - М.: Наука, 1973Кнут Э. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. - М.: Мир, 1973.Авторское свидетельство СССР У 1193957, кл. С 06 Г 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИН- ФОРМАЦИИ 7) Изобретение относится к вычисли ельной технике и может быть использовано в специализированных системахобработки информации, например в информационно-поисковых системах. Цельизобретения - увеличение быстродействия. Для достижения указанной целисистема содержит блок 1 памяти, состоящий из двух узлов 4,5 памяти, блок3 управления и блок 2 подсчета и сортировки кодов. Блок 1 памяти выполнениз запоминающих устройств с произвольной выборкой, соединенных между собойшиной данных. Сортировка выполняетсяодновременно по группе одноименныхразрядов ключа (секции), начиная смладшей секции. В каждой секции вначале формируются адреса перемещения,а затем осуществляется перемещениевсех информационных слов в свободныйузел памяти по этим адресам. Послесортировки по всем секциям массив будет упорядочен по величине ключа влексикографическом смысле независимоот количества секций в ключе. 2 з.п.ф-лы, 6 ил.Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки инФормации.Цель изобретения - увеличениебыстродействия.На фиг.1 дана блочная схема системы; на фиг.2 - структурная схема блока памяти с произвопьной выборкой;на фиг.3 - структурная схема блокаформирования адресов перемещений; наФиг.4 - структурная схема блока управления; на фиг.5 - формат микрокоманды; на Фиг.6 - пример, поясняющийпроцесс сортировки.Устройство содержит блок 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 переключателей, регистр 1545 50 55 При инициации работы системы начинается сортировка в первой (младшей) секции ключа, Блок 3 управления Формирует микрокоманды, управляющие работой устройства (фиг.5). Во время инициации под управлением поля управления блока подсчета и сортировки кода микрокоманды код длины массива передается иэ узла 10 рабочих регистров в блок 3 управления. Затем начинается первая фаза сортировки - распределение, т.е, вычисление объемасвободной памяти (необходимого для размещения в нем всех информационных слов с кодомв сортируемой секции) 35977дреса микрокоманде, регистр 16 микро -команд, узел 17 памяти мцкрокоманд,формирователь 18 синхроимпульсон,счетчик 9 длицы массива, счетчик 20длины информационного слова,Система при сортировке по убываниюработает следунпцим образом.В исходном состоянии неупорядочен 10 ный массив информации, например, из16 информационных слов расположен вузле 4 памяти (фиг.ба), Узел 5 памяти свободен. В ячейках О, 1,2,3 находится первое информационное слово15 Разрядность ячейки равна минимальноадресуемой единице в узлах 4 и 5 памяти, либо кратна ей. В нашем примере разрядность ячейки предполагаетсяравной одному байту (8 разрядов).О В ячейках 4-7 находится второе информационное слово, в ячейках 60-63 - последнее, шестнадцатое информационноеслово, Младший байт каждого слова,расположенный в ячейках 3,7, 11635 это первая секция - секция,с которой начинается сортировка. Старший байт каждого слова (четвертая секция) находится в ячейках 0,460. Пусть сортировка выполняется по признаку (клю 30 чу) иэ младших двух байтов. Служебнаяинформация о неупорядоченном массивенаходится в узле 10 рабочих регистров: код 16 - длина массива (количество информационных слов), код 4З длина информационного слова в байтах,35код 2 - длина ключа в байтах, код 3адрес первого байта первого от начала информационного слова, с которого начинается сортировка, код 6040 адрес последнего (первого от конца)информационного слова, код 7 - максимальная величина кода в группе разрядов (байте) ключа.(полученного для кода при всех возможных значениях д) в ячейкеузла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 управления появится условиеокончания подсчета. К этому моментув каждой ячейке д блока 2, гдевозможная величина кода в группе(байте) будет указан объем Ч; свободной памяти, необходимый для размещения в нем всех информационных слов.с кодомв сортируемой секции(фиг,бб, строка 2),где К - количество кодов в сортируемой секции, равныхС - длина информационного слова(коэффициент масштабирования)Результаты первой фазы используются на второй для формирования адресов перемещения типа "куда", т.е. адресов, указывающих в какое место свободного узла памяти необходимо переместить очередное информационное слово из узла памяти с неупорядоченной информацией. Адреса перемещения могут быть получены в блоке 2 несколькими вариантами.На третьей фазе сортировки первой секции для каждого расположенного в 5 10 15 20 25 30 35 40 45 Ф 50 55 узл 4 памяти нпфо 1)мационного слов отыскивается соответствующий адрес перемещения и осуществляется перемещение этого информационного слова в узел 5 памяти по найденному адресу, Для поиска адресов перемещения коды сортируемой секции последовательно читаются из узла 4 памяти, начиная со старших или младших разрядов, в зависимости от способа их формирования на втором этапе. Если на втором этапе в каждой ячейкеузла 11 памяти блока 2 получена сумма содержимого всех ячеекд минус длина информационного слова, то для поиска адресов перемещения коды сортируемой секции последовательно читаются из узла 4 памяти, начиная со старших адресов, а упорядочение осуществляется по уменьшению величины кода ключа. Если в каждой ячейке 1 получена сумма содержимого всех ячеекминус длина информационного слова, то для поиска адресов перемещения коды сортируемой секции последовательно читаются из узла 4 памяти, начиная с младших адресов, а упорядочение осуществляется по увеличению кода ключа, В любом случае очередной кодсортируемой секции, считанный из узла 4 памяти, используется как адрес ячейузла 11 памяти блока 2, где имеется искомый адрес перемещения. При каждом обращении в ячейку д ее содержимое уменьшается на длину информационного слова и вновь указывает истинный адрес перемещения для очередного информационного слова с кодом в сортируемой секции. После перемещения всех информационных слов в узле 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 памяти поступают 15непосредственно на вход данных узла 5памяти, что позволяет сократить времяперемещения. После перемещения всегоинформационного слова блок 3 управления инициирует передачу из блока 2 20в адрес 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 и анаЛизируется на нуль. Если результат50не равен нулю, то блок 3 управленияосуществляет переход к сортировкепо .кодам второй секции.Сортировка во второй секции такжевыполняется за три Фазы: распределе 55ние, формирование адресов перемещения и перемещение. При этом узел 5. памяти - сортируемый массив, а узел4 памяти свободен. Перед началом распре. лбделения ячеек местной памяти блок 2 обнуляется, код 16 длины массива передается из блока 2 в блок 3 управления для анализа конца подсчета, а адрес 3 первой гоуппы разрядов (байта) первой секции преобразуется в адрес первого кода второй секции(уменьшается на единицу). После этой подготовки начинается распределение. Во которой секции оно выполняется так же, как и в первой. При этом адреса кодов сортируемой секции поступают из блока 2 в узел 5 памяти. Коды считываются из ячеек узел 5 памяти и передаются в блок 2, где выполняется распределение в зависимости от вели-. чины поступающих кодов. После однократной передачи всех кодов второй секции из узла 5 памяти в блок 2 в каждой ячейке 1 узла 11 памяти этого устройства окажется код, указывающий необходимый размер памяти для размещения всех информационных слов, содержащих код ). во второй секции (Фиг.бг, строка 2) .Формирование адресов перемещения на второй фазе выполняется в блоке 2. После второй Фазы в каждой ячейкеузла 11 памяти будет записан адрес перемещения первого от конца массива информационного слова с кодомво второй секции (фиг.бг, строка 3).Третья фаза сортировки по кодам второй секции отличается лишь тем, что узел 5 памяти является передающим, а узел 4 памяти приемным. Коды второй секции последовательно, начиная со старших адресов ЗУ 5, 62, 59, 542, читаются и пересылаются по шине данных в блок 2. Каждому кодув узле 11 памяти блока 2 соответствует адрес перемещения, указывающий по какому адресу в узел 4 памяти необходимо переместить из узла 5 памяти информационное слово с кодомво второй секции. При каждом обращении в ячейкуза адресом перемещения ее содержимое уменьшается на длину информационного спова. После перемещения всех информационнь 1 х слов из узла 5 памяти в узел 4 памяти в последнем окажется массив, упорядоченный по ключу из двух групп разрядов (байтов), хотя сортировка во второй секции выполнялась без анализа кодов первой секции (фиг.бд).Для полного упорядочения исходного массива необходимо выполнить стольациклов сортировки, сколько групп разрядов (секций) содержит ключевое слово (ключ) . Окончательно упорядоченный массив информации окажется расположенным в узле 4 памяти или в узле 55 памяти в зависимости от того, четное или соответственно нечетное число групп разрядов содержит ключ.При сортировке информационных слов 10 в порядке увеличения кода ключа - на второй фазе в каждой ячейке 1 узла 11 памяти получают сумму содержимого всех ячеек , уменьшенную на длину информационного слова. В этом случае на третьей фазе при поиске адресов перемещения коды сортируемой секции читают, начиная с младших адресов узла памяти, содержащего неупорядоченный массив.20Объем сортируемой информации определяется емкостью одного из узлов 4 и 5 памяти с произвольным доступом, т,е. может быть равен 1-4 байтам. Предлагаемую систему можно ввести в ,25 качестве составной части в систему обработки данных, в которой она может освободить процессор от выполнения процедур сортировки информации.Блок 2 (фиг.4) работает следующим образом.В исходном состоянии служебная информация находится в постоянно распределенных регистрах узла 10 рабочих регистров. Перед обработкой каждой секции все ячейки узла 11 памяти блока 2 обнуляются под управлением сигналов иэ блока 3 управления.При распределении каждый код сортируемой секции величиной , поступаю щий из узла 4 памяти в узел 5 памяти, подается на адресный вход. узла 11 памяти и таким образом адресует ячейкуузла 11 памяти. В это время блок 3 управления в поле управления узлом 45 11 памяти микрокоманды выдает для узла 11 памяти операцию "Чтение-модификация записи". Содержимое ячейки первый раз равное нулю, читается и подается на первый информационный вход арифметико-логического узла 13. На второй информационный вход арифметико-логического узла 13 из регистра операции "Чтение" для узла 10 рабочих регистров задаются полем управления узлом рабочих регистров микрокоманды. Арифметико-логический узел 13 под управлением поля управления арифметико-логическим узлом выполняет суммирование, а результат записывается вту же ячейку 1 узла 11 памяти. Первыйкод величиной 1, поступивший из блока1 памяти, увеличивает содержимоеячейки узла 11 памяти на длину одногоинформационного слова. Второй код величиной , поступивший в произвольный момент времени, снова увеличиваетсодержимое той же ячейки на длинуинформационного слова. После поступления всех кодов сортируемой секциив устройство и обработки их в каждойячейке 1 в узле 11 памяти оказываетсякод, равный произведению количествакодов величинойна длину одногоинформационного слова, т.е. содержимое ячейки 1 узла 11 памяти указывает размер памяти, необходимый дляразмещения всех информационных словс кодомв сортируемой секции.На второй фазе формирование адресов перемещения, указанных на Фиг.бб(строка 3), выполняется путем суммирования результатов, полученных в узле 11 памяти на первой фазе, При этомв каждой ячейкеузлов 11 памяти образуется сумма содержимого всех ячеекминус длина информационногослова. Для этого в регистре К узла10 рабочих регистров формируется дополнительный код длины информационного слова. Затем максимальный код 7группы разрядов (преимущественно максимально возможный код) из узла 10рабочих регистров пересыпается на адресный вход узел 11 памяти, Управляющие сигналы из блока 3 управлениявызывают чтение содержимого ячейки7 узла 11 памяти и содержимого регистра К узла 10 рабочих регистров.Эта информация суммируется на арифметико-логического узла 13, а результат, равный 12, пишется в регистрК узла 11 рабочих регистров и ячейку 7 узла 11,памяти, Затем читаетсяи суммируется содержимое ячейки 6узла 11 памяти и регистра К узла10 рабочих регистров. Результат запоминается в рабочем регистре К ив ячейке 6 узла 11 памяти. Суммирование продолжается до обработки содержимого ячейки 0 в узле 11 памятии получения результатов согласно фиг.бб, строка 3.При суммировании не должно быть переполнения из арифметико-логического узла 13. Если оно имеется, это признак ошибки в устройствеСигналоб ошибке через выход переполнения блока 2 поступает в блок 3 управления, где вызывает прекращение операггии сортировки.5Адреса перемещения также могут быть получены путем суммирования результатов, полученных в узле 11 памяти на первой фазе так, что в каждой ячейке 1 узле 11 памяти образуется сумма содержимого всех ячеек 1 минус длина информационного слова, Для этого в регистре К узла 10 рабочих регистров формируется дополнительный код длины 15 информационного слова. Затем код 0 пересылается на адресный вход узла 11, содержимое ячейки 0 узла 11 памяти суммируется с содержимым регистра К узла 10 рабочих регистров, а результат заносится в ту же ячейку 0 узла 11 памяти и в регистр К узла 10 рабочих регистров для использования в следующем ггикле суммирования. Далее содержимое ячейки 1 узла 11 памяти 25 суммируется с новым значением регистра К узла 1 О рабочих регистров, а результат заносится в ячейку 1 узла 11 памяти и в регистр К узла 10 рабочих регистров. Суммирование продолжается до обработки содержимого ячейки 7 узла 11 памяти (преимущественно до максимально возможного кода в сортируемой группе).35Блок 3 управления системой (фиг.4) работает следующим образом.Нажатие кнопки "Сброс" в узле 14 переключателей устанавливает систему в исходное состояние, в том числе адрес первой микрокоманды в регистре 15 адреса микрокоманд. Нажатие кнопки "Пуск" инициирует работу формирователя 18 синхроимпульсов, который формирует серию синхроимпульсов. С появле нием синхроимпульсов начинается выборка микрокоманд из схемы 17 памяти микрокоманд и фиксация их в регистре 16 микрокоманд, С выхода регистра 16 ьгикрооманд управляющие сигналы поступают в блок 1 памяти и в блок 2.Формат микрокоманд показан на фиг.5. Микрокомандьг иэ схемы 17 памяти микрокоманд читаются, управляя процедурами сортировки в системе.Текущая последовательность микро- команд изменяется при изменении условий ветвления, т.е. при появлении сигналов переполнения. с ныхо;я г и т пк 11 длины ма. -сгР после обработк 1 нссх колог ( ор -тируемой секции,с выхода счетчика 20 длины словапосле перемещения очередного информационного слова на фазе перемещения,- из блока 2 при ошибке.Формула изобретения1. Устройство для сортировки информации, содержащее блок памяти, блок управления, причем входы условий блока управления соединены с информационными входами-выходами первого и второго узлов памяти блока памяти, первый выход блока управления соединен с управляющими входами первого и второго узлов памяти блока памяти, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, в него введен блок формирования адресов перемещений, информационные входы-вьгходы которого соединены с входами условий блока управления, выход признака сбоя блока формирования адресов перемещений соединен с входом признака ошибки блока управления, второй выход блока управления соединен с входом управления блока формирования адресов перемещений.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что узел памяти содержит регистр данных, регистр адреса, накопитель и схему управления памяти, причем информационный вход- выход узла соединен с информационными входами регистра данных, регистра адреса и с информационным выходом накопителя, информационный выход регистра данных соединен с входом данных накопителя, информационный выход регистра адреса соединен с входом адреса накопителя, вход управления узла соединен с входом схемы управления памятью, управляющие выходы с первого по третий которого соединены с входом строба регистра данных, с входом стробирования и суммирования регистра адреса и с входом строба накопителя соответственно.3. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок управления содержит регистр адреса микро- команд, узел памяти микрокоманд, регистр микрокоманд, счетчик длины массива, счетчик длины информационного11 13:35977 1 сслова, формирователь синхроимлульсов нен с информационным входом поля ади узел переключателей, причем входы реса следующей микрокоманды регистра у овий ветвления блока соединены с адреса микрокоманц, второй выход узинформационными входами счетчика дли- ла памяти микрокоманд соединен с ин 5ны массива и счетчика длины слова,формационным входом регистра микрокопервый выход узла переключателей сое- манд, выходы счетчиков длины массива динен с входами сброса регистра адре- и длины информационного слова соедиса микрокоманд и регистра микрокоманд иены с информационными входами полей второй выход узла переключателей сое б ветвления регистра адреса микрокодинен е входом запуска формирователя манд, первый и второй выходы регистра синхроимпульсов, первый выход форми- микрокоманд соединены с первым и вто - рователя синхроимпульсов соединен срым выходами блока соответственно, входами строба регистра адреса микро- третий выход регистра микрокоманд команд и регистра микрокоманд, вход 15 соединен с входом тактирования формипризнака ошибки блока соединен с вхо- рователя синхроимпульсов, второй и дом останова работы регистра адреса третий выходы которого соединены с микрокоманд, выход регистра адреса входами асинхронной загрузки и суммимикрокоманд соединен с адресным вхо- рования счетчиков длины массива и дом узла памяти микрокоманд, первый о длины информационного слова соответвыход узла памяти микрокоманд соеди- ственно.13.35977 Юдрега 7 ИСю-югенция 1 стариаю д ю сенцию г-ю сенция 1-ю сенцию 1 люадмаю) абОЫгв 16 1 Я А/реса лерелегаенгле юб ия юрегаФ.ю сен 7.ю сен 2"Р се 1.ю се Фиг, б ВНИИПИ Заказ 4048/43 Тираж 672 ПодписиПроизв.-полигр. пр-тие, г, Ужгород, ул. Проектная О 1 г 5 ц Х б 7 АФега лестнои лалюли О О О б й 17 ц 1 б Рознер лалюти Зю инграр а 17 Ы глацианлм ееюЮ снайл цию нцию нция