Система упорядочения информации Советский патент 1978 года по МПК G06F17/24 

1

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

Известны системы упорядочения информации, выполненные как на базе универсальных вычислительных машин, так и на базе слециализированных устройств 1. Системы упорядочения на базе универсальных ЭЦВМ используют специальные программы упорядочения, содержащие целый ряд служебных операций (выборка команд, формирование промежуточных адресов, проверка условия выхода из цикла и т.д.), результатом чего является большая затрата машинного времени.

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

Недостатком известной системы сортировки информации является ее малое быстродействие.

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

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

На чертеже приведена структурная схема системы.

Она содержит блок памяти 1, состоящий из двух запоминающих устройств (ЗУ) 2 и 3. Выходы синхросигналов 4 и 5, а также информационные вход 6 и выход 7 блока памяти 1 соединены соответственно с первым и вторым входами синхросигналов и первыми информационными выходом и входом коммутатора 8. Второй информационный выход коммутатора 8 соединен с первым входом блока 9 разделения массива, управляющий вход-выход которого соединен с первым входом-выходом блока 10 управления. Второй выход блока 10 управлеНИН соединен с управляющим входом 8 коммутатора. Первый и второй выходы синхросигналов коммутатора 8 соединены с соответствующими входами первого 11 и второго 12 адресных компараторов, управляющие входы-выходы которых соединены соответственно с третьим и четвертым входами-выходами блока управления 10. Выход первого компаратора 11 соединен со вторым входом блока 9 разделения массива, информационный выход которого соединен с информационными входами первого 13 и второго 14 буферных запоминающих блоков (БЗБ), первые и вторые входы синхросигналов которых подключены к соответствующим выходам синхросигналов соответственно блока 9 разделения массива и второго компаратора 12. Выходы экстремальных состояний БЗБ 13 и 14 соединены с соответствующими входами блока Ю управления, а их информационные выхо ды через элемент ИЛИ 15 - со вторым информационным входом коммутатора 8.

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

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

В исходном состоянии ЗУ 2 является пергдающим, а ЗУ 3 - приемным, причем неупорядоченный массив информации расположен в ЗУ 2. По команде из блока 10 управления коммутатор 8 осуществляет связь точек А и А , Б и Б , В и В , Г и Г . ЗУ 2 включается на чтение, а ЗУ 3 -- на запись информации. Из блока 10 управления в первый адресный компаратор 11 заносится код начального адреса неупорядоченного массива информации, расположенного в ЗУ 2, а также код его объема. Б.ЛОК 10 управления настраивает блок 9 разделения массива на анализ младшего разряда признака слов массива.

После этих приготовлений начинается начальный просмотр массива. При вращении дискового ЗУ 2 синхроимпульсы с выхода синхросигналов 4 блока памяти 1 через коммутатор 8 поступают на вход первого адресного компаратора И. В момент сравнения кода текущего адреса дискового ЗУ 2 с кодом начального адреса упорядочиваемого массива, записанным в компаратор 11, синхроимпульсы с его выхода начинают поступать на вход блока 9 разделения массива. Одновременно с этим с информационного выхода 7 блока памяти 1 через коммутатор 8 на вход блока 9 разделения массива поступает собственно информация. Информация подается последовательным кодом Р.зряд за разрядом и тактируется синхроимпульсами. При прохождении каждого слова массива через блок 9 разделения в определенном такте производится анализ кода младщего разряда его признака. Если в младщем разряде признака очередного слова массива содержится код «Ь, то блок 9 разделения массива вырабатывает импульс и Посылает его в блок 0 управления, который эти импульсы подсчитывает. Собственно информация из блока Э разделения при начальном просмотре массива никуда не передается. После того, как весь массив информации будет просмотрен блоком 9 разделения, в блоке 10 управления бyдet подсчитано число слов массива, содержащих код «1 в младщем разряде признака.

После начального просмотра массива производится подготовка к первому этапу упорядочения. Для этого из блока 10 управления в адресный компаратор 11 опять заносится код начального адреса неупорядоченного массива информации, расположенного в ЗУ 2, и код его объема. Во второй адресный компаратор 52 из блока 10 управления заносятся коды первого и второго начальных адресов на дисковом ЗУ 3, начиная с которых в ЗУ 3 будут записываться слова упорядочиваемого массива, содержащие соответственно «1 и «О в младщем разряде признака. При этом код второго начального адреса вычисляется как сумма кода первого начального адреса и кода числа слов массива, содержащих «1 в младщем разряде признака, полученного в результате начального просмотра массива. Блок 0 управ: Ленин настраивает блок 9 разделения массива на анализ младщего и следуюшь10 второго.разрядов признака. БЗБ 13 и 14 обнуляются (очищаются).

Далее начинается первый этап упорядочения - по младшему разряду признака. Как и при начальном просмотре массива, в момент сравнения кода текущего адреса ЗУ 2 с кодом начального адреса, записанным в компаратор П, осуществляется подача в блок 9 разделения информации и синхронизирующих сигналов. Блок разделения, как и при начальном

просмотре, осуществляет анализ младшего разряда признака каждого слова. Прошедшие через блок 9 разделения слова будут поступать на информационные входы первого и второго БЗБ соответственно 13 и 14. При этом, если в младшем разряде признака данного слова содержится «1, то блок 9 разделения подает синхросигналы на первый вход .синхросигналов первого БЗБ 13, а если в младшем разряде признака данного слова содержится «О. то блок 9 подает синхросигналы на первый вход синхросигналов второго БЗБ 14. Таким образом, при прохождении через блок 9 разделения упорядочиваемый массив информации будет делиться на два подмассива слов, а именно на подмассив слов, содержащих «1, и подмассив слов, содержащих «О, в младшем разряде признака. Эти подмассивы будут записываться соответственно в первый 13 .и второй 14 БЗБ. Блоки 13 и 14 могут иметь недостаточную емкость и поэтому в процессе работы могут переполняться информацией. В шучае переполнения хотя бы одного из блоков 13 или 14 они подают сигналы переполнения в блок 10 управления с выходов экстремальных состояний.

Блок 10 управления в этом случае подает соответствующий сигнал в компаратор 11 и тот прекращает подачу синхросигналов (а значит и информации) на блок 9 рааделения. При этом в компараторе 11 запоминается адрес дискового ЗУ 2, на котором произошло прерывание подачи информации в блок 9 разделения. Этот адрес при возобновлении обращения в ЗУ 2 на следующем обороте.диска будет служить «обновленным начальным адресом упорядочиваемого массива.

При вращении дискового ЗУ 3 его синхросигналы с выхода 5 блока памяти через коммутатор 8 будут поступать на вход второго адресного компаратора 12. В момент сравнения кода текущего адреса ЗУ 3 с кодом первого начального адреса, записанного в компаратор .12, с его выхода на второй вход синхросигналов первого БЗБ 13 начнут поступать синхросигналы. Находящаяся в блоке 13 информация будет из него считываться и последовательным кодом через элемент ИЛИ. 15 и коммутатор 8 поступать на информационный вход 6 блока памяти 1 и записываться по нужному адресу в дисковое ЗУ 3. Если вся информация будет считана с блока 13 и записана в ЗУ 3, блок 13 со своего выхода экстремальных состояний подаст соответствующий сигнал в блок 10 управления. Блок 10 управления, в свою очередь, подаст сигнал в компаратор 12 и последний прекратит подачу синхросигналов на БЗБ 13. В м.омент сравнения кода текущего адреса ЗУ 3 с кодом второго начального адреса, записанного в компаратор 12, с его выхода начнут поступать синхросигналы на вгоррй вход синхросигналов БЗБ 14. Информация с блока 14 будет считываться и через элемент ИЛИ 15 и коммутатор 8 будет поступать на вход 6 блока памяти 1 и записываться в ЗУ 3 по нужному адресу. Если вся информация будет считана с блока 4 и записана в ЗУ 3,

блок 14 со своего выхода чкстремальны.х .()(.таяний пошлет сигнал в блок 10 управления, который, в свою очередь, подаст сигнал в ко.ипаратор.12, и последний прекратит подачу синхросигналов на блок 14. В моменты прекращения подачи синхросигналов на вторые входы синхросигналов первого и второго БЗБ 13 и 14 в компараторе 12 запоминаются соответствующие адреса, на которых произо1лло прерывание записи информации в ЗУ 3. Эти адроса будут являться соответственно первым и вторым «обновленными начальными адресами компаратора 12 при записи в ЗУ 3 следуюп1.ей порции информации. Есйи оба БЗБ 13 и 14 не переполнены, на следующем обороте передающего ЗУ 2 произойдет сравнение текущего адреса. ЗУ 2 с «обновленным начальным адресом компаратора 11, и приведенная процедура работы системы повторится. В процессе упорядочения массива информации блок 9 разделения попутно осуществляет анализ следующего, второго разряда признака проходящего через него слова и посылает импульс в блок 10 управления каждый раз, когда во втором разряде признака слово содержится «I. Первый этап упорядочения массива закончится, когда все слова массива будут пропущены через блок 9 разделения массива и записаны в ЗУ 3 {счетчик объема пересылаемого массива в компараторе 11 обнулится). В результате этого этапа массив информации будет частично упорядочен, т. е. упорядочен по младшему разряду признака. Весь частично упорядоченный массив информации будет компактно расположен в ЗУ 3, т. е. оба подмассива его слов, содержащих соответственно «1 и «0 в младщем разряде признака, будут расположены один за другим без пустых участков между ними. Этого удалось добиться .благодаря вычислению второго начального адреса, записываемого в компаратор 12, по результату подсчета числа слов массива, содержащих « в младщем разряде признака, при начальном просмотре массива.

Второй этап упорядочения --по второму раз ряду признака. Приведенная процедура упорядочения должна Применяться к уже частично упорядоченному в результате предыдущего эта-. па массиву, расположенному в ЗУ 3. На втором этапе упорядочения ЗУ 3 должно быть передающим, а ЗУ 2 - Приемным. Поэтому по команде с блока 10 управления коммутатор 8 осуществляет связь точек А с Г, Г и А, Б с В, В с Б. ЗУ 3 переключается на чтение, а ЗУ 2 - на з;а.пись информации. Далее блок 10 управления заносит в компаратор II код начал1 ного адреса массива, расположенного в ЗУ 3, и код его объёма. В компаратор 12 заносятся коды первого и второго начальных адресов ни ЗУ 2, начиная с которых в ЗУ 2 будут записываться слова массива, содержащие соответственно «1 и «О во втором разряде признака. При этом второй начальный адрес вычисляется на основании подсчитанных на предыдущем этапе упорядочения числа слов массива. Содержащих «Ь во втором разряде признака. Блок 10 управления настраивает блок 9 ра:(деления на анализ второго и третьего разрядов признака. БЗБ 13 и 14 обнуляются. После этих приготовлений производится второй этап упорядочения массива. Работа системы на втором этапе упорядочения происходит точно так же, как на первом. В процессе упорядочения по второму разряду признака производится так же подсчет числа слов массива, содержащих «1 в третьем разряде признака. После окончания второго этапа упорядочения в ЗУ 2 будет записан массив, состоящий из двух подмассивов слов, содержащих соответственно «I и «О во втором разряде признака. Для полного упорядочения исходного маесива необходимо столько этапов упорядочения, сколько разрядов имеет признак, по которому ведется упорядочение. При этом названная процедура упорядочения применяется каждый раз к массиву, частично упорядоченному на предыдущем этапе. Окончательно упорядо чеиный в порядке убывания кода признака массив информации окажется расположенным в ЗУ 2 или в ЗУ 3, в зависимости от того, четное или соответственно нечетное число разрядов содержит признак. Аналогично упорядочению массива в поряд ке убывания кода признака может быть произведено упорядочение массива в порядке возрастания кода признака его слов. Блок памяти в предлагаемой системе упорядочения может быть выполнен на ЗУ с большим информационным объемом, например на магнитных дисках или барабанах, следовательно с помощью этой системы можно упорядочить массивы информации сколь угодно большой величины. Предложенную систему можно ввести в качестве составной части в систему обработки данных, в которой она может освободить центральный процессор от выполнения часто встречающейся процедуры упорядочения больших массивов информации. Учитывая прос тоту технической реализации и экономию машинного времени, которую дает система, можно считать, что ее применение целесообразно.

8 Формула изобретения Система упорядочения информации, содержащая блок памяти, первый и второй выходы синхросигналов и информационные вход и выход которого соединены соответственно с первым и вторым входами синхросигналов и первыми информационными выходом и входом коммутатора, блок разделения массива, первый вход которого соединен, е вторым информационным выходом коммутатора, блок управления, первый вход-выход которого соединен с управляющим входом-выходом блока разделения массива, а второй выход блока управления соединен с управляющим входом коммутатора, отличающаяся тем, что, с целью повышения быстродействия, она содержит первый и второй компараторы, первый и второй буферные запоминающие блоки, элемент ИЛИ, причем первый и второй выходы синхросигналов комму-, татора соединены с соответствующими входами первого н второго компараторов, управляющие входы-выходы которых соединены соответственно с третьим и четвертым входами-выходами блока управления, выход первого компаратора соединен с вторым входом блока разделения массива, информационный выход которого соединен с информационными входами первого и второго буферных запоминающих блоков, первые и вторые входы синхросигналов которых подключены к соответствующим выходам синхросигналов соответственно блока разделения массива н второго компаратора, выходы экстремальных состояний первого и второго буферных запоминающих блоков соединены с соответствующими входами блока управления, а их информационные выходы через элемент ИЛИ - с вторым информационным входом коммутатора. Источники ииформации, принятые во внимание при экспертизе: 1.Папернов А. А., Подымов В. Я. Методы упорядочения ннформации в цифровых системах М., Наука, 1973. 2.Патент Франции № 2052292 кл. G 06 F 15/00,1971.