Система упорядочения информации

 

П ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

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

Республик (l1) 608161

К АВТОРСКОМУ СВИДИТВЛЬСТВУ (61) Дополнительное к авт, свид-ву(22} Заявлеио 04.07.75(21) 2151285/24 с присоединением заявки 34(23) Приоритет(43) Опубликовано 25.05.786юллетень И 19 (45) Дата опубликования описания 1 .о . Я. (51) М. Кл.

G 06 F 15/00

& 06 F 7/24

Гаатдарстаенный неьнпет

Сената Мкннатрае СССР на делам нзобретвннй н нтнрмтнй (Д) УДК 681.325 (088. 8) (72) Авторы изобретеиия

В. С. Погорелов и А. М. Романкевич

Киевский ордена Ленина политехнический институт имени

50-летия Великой Октябрьской социалистической революции (71) Заявитель (54) СИСТЕМА УПОРЯДОЧЕНИЯ ИНФОРМАЦИИ

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

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

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

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

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

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

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

1$

60 ные выходы через элемент ИЛИ вЂ” — co вторым информационным входом коммутатора.

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

Она содержит блок памяти 1, состоящий иэ двух запоминающих устройств (ЗУ) 2 и 3.

Выходы синхросигналов 4 и 5, а также информационные вход б и выход 7 блока памяти 1 соединены соответственно с первым и вторым входами синхросигналов и первыми информационными выходом и входом коммутатора 8.

Второй информационный выход коммутатора 8 соединен с первым входом блока 9 разделения массива,. управляющий вход.-выход которого соединен с первым входом-выходом блока !О управления, Второй выход блока 10 управления соединен с управляющим входом 8 коммутатора. Первый и второй выходы синхроснгналов коммутатора 8 соединены с соответствую щими входами первого 11 и второго 12 адресных компараторов, управляющие входы-выходы которых соединены соответственно с третьим и четвертым входами-выходами блока управления 10. Выход первого компаратора 11 соединен со вторым входом блока 9 разделения массива, информационный выход которого соединен с информационными входами первого 13 и второго 14 буферных запоминающих блоков (БЗБ), первые и вторые входы синхросигналов которых подключены к соответствующим выходам синхросигналов соответственно блока 9 разделения массива и второго компаратора 12.

Выходы экстремальных состояний ЬЗБ 13 и 14 соединены с соответствующими входами блока 10 управления, а их информационные выходы через элемент ИЛИ 15 — со вторым информационным входом коммутатора 8.

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

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

В исходном состоянии ЗУ 2 является передающим, а ЗУ 3 — приемным, причем неупорядоченный массив информации расположен в ЗУ 2. По команде из блока 10 управления коммутатор 8 осуществляет связь точек А и

А, Б и Б, В и В, Г и Г . ЗУ 2 включается на чтение, а ЗУ 3 — на запись информации.

Иэ блока 10 управления в первый адресный компаратор l заносится код начального адреса неупорядоченного массива информации, расположенного в ЗУ 2, а также код его обьема.

Блок !О управления настраивает блок 9 разделения массива на анализ младшего разряда признака слов массива.

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

«1» в младшем разряде признака.

После начального просмотра массива производится подготовка к первому этапу упорядочения. Для этого из блока !О управления в адресный компаратор 11 опять заносится код начального адреса неупорядоченного массива информации, расположенного в ЗУ 2, и код его объема. Во второй адресный компаратор 12 из блока !О управления заносятся коды первого и второго начальных адресов на дисковом

ЗУ 3, начиная с которых в ЗУ 3 будут записываться слова упорядочиваемого массива, содержащие соответственно «!» и «0» в младшем разряде признака. При этом код второго начального адреса вычисляется как сумма кода первого начального адреса и кода числа слов массива, содержащих «1» в младшем разряде признака, полученного в результате начального просмотра массива. Блок 10 управления настраивает блок 9 разделения массива на анализ младшего и следующе о второго разрядов признака, БЗБ 13 и 14 обнуляются (очищаются) .

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

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

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

Этот адрес при возобновлении обращения s

ЗУ 2 на следу)ощем обороте диска будет служить. «обновленным» начальным адресом упорядочиваемого массива.

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

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

ЗУ 3 по нужному адресу. Если вся информация будет считана с блока 14 и записана в ЗУ 3, блок 14 со свОего вых<)д» BKcTp8 ) ))hных с1ктояний пошлет сигнал в блок 10 ун()авл ilè)). который, в свою очередь, подаст сигнал в компаратор.12, и последний прекратит подачу сннхросигналов на блок !4. В моменты прекращения подачи синхросигналов на вторые входы синхросигналов первого и второго БЗБ 13 и

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

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

Второй этап упорядочения -- по второму раз ряду признака. Приведенная процедура упорядочения должна применяться к уже частично упорядоченному в результате предыдущего этапа массиву, расположенному в ЗУ 3. На втором этапе упорядочения ЗУ 3 должно быть передающим, а ЗУ 2 — приемным. Поэтому по команде с блока 10 управления коммутатор 8 осуществляет связь точек А с Г, Г и А, Б с В, В с Б. ЗУ 3 переключается на чтение, а

ЗУ 2 — на запись информации. Далее блок 10 управления заносит в компаратор Il код начального адреса массива, расположенного в

ЗУ 3, и код его объема. В компаратор 12 заносятся коды первого и второго начальных адресов на ЗУ 2, начиная с которых в ЗУ 2 будут записываться слова массива, содержащие соответственно «1» и «О» во втором разряде признака. При этом второй начальный адрес вычисляется на основании подсчитанных на предыдущем этапе упорядочения числа слов массива, содержащих «1» во втором разряде признака. Блок 10 управления настраивает блок 9 разделения на анализ второго и третьего разрядов признака. БЗБ 13 и 14 обнуляются. После этих приготовлений производится второй этап упорядочения массива. Работа системы на втором этапе упорядочения происходит точно так же, как на первом. В процессе упорядочения по второму разряду признака производится так же подсчет числа слов массива, содержащих «1» в третьем разряде признака.

После окончания второго этапа упорядочения в ЗУ 2 будет записан массив, состоящий из двух подмассивов слов, содержащих соответственно «1» и «О» во втором разряде признака.

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

ЗУ 2 или в ЗУ 3, в зависимости от того, четное или соответственно нечетное число разрядов содержит признак, Аналогично упорядочению массива в порядке убывания кода признака может быть произведено упорядочение массива в порядке возрастания кода признака его слов.

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

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

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

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

1. Папернов А. А., Подымов В. Я. Методы упорядочения информации в цифровых системах М., Наука, 1973.

2. Патент Франции М 2052292 кл. G 06 Г

15/00, 1971.

0НИИПИ Заказ 280233

Тираж 826 Подписное

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