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

315

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

Цель изобретения - расширение области применения путем обеспечения возможности сортировки информации по признакам.

На чертеже приведена-схема устрой- ства.

Устройство содержит блоки 1 и 2

памяти, счетчики 3 и 4, входной регистр 5, регистры признака 6, размера 7, адреса 8, перезаписи 9, коррекции адреса 10, группу элементов И 11, мультиплексор 12, триггер 13, блок 14 синхронизации, информационные, входы 15, входы разрешения записи инфор1«1а- ции 16, признака 17, размера 18, ко- личества страниц 19, входы выбора 20 и 202 режима, вход 21 окончания записи-считывания, информационные выходы 22, выходь.1 готовности 23 и синхронизации 24.

Входной регистр 5 предназначен для промежуточного хранения сортируемой информации перед записью ее в блок 1 памяти в режиме сортировки, а также для записи адресов начала страниц памяти в блок 2 памяти в режиме подготовки, п-разрядный регистр 6 признака служит для фиксации первого слова, являющегося признаком сортируемой информации, поступающей на входы 15, т-разрядный регистр 7 размера хранит информацию о размере области на числовой оси, в пределах которой сортируемая информация идентифицируется одним признаком. Инфор- мация о размере области условно названа кодом размера, а размер области на числовой оси - фрагментом, при этом размер фрагмента может быть от

2° до 2™. Регистры признака 6 и размера 7 совместно с группой элементов И 11, содержащей m элементов И, формируют m младших разрядов адреса блока 2 памяти, который предназначен для хранения адресов начала страниц . памяти в блоке 1 памяти.

Блок 14 синхронизации вырабатывае тактовые сигналы, необходимые для работы устройства. Этот блок может быт выполнен по стандартной схеме микропрограммного управления и содержать ПЗУ, регистр и генератор импульсов.

k-разрядный счетчик 3 слов формирует k младших разрядов адреса бло

0 5

0 5 0

5

0

5

ка 1 памяти. От значения k зависит размер страницы памяти в блоке 1 памяти. Кроме этого, данный счетчик выдает сигнал заполнения страницы информацией, что является признаком перехода к свободной странице.

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

k-разрядный регистр 9 перезаписи и мультиплексор 12 служат для организации записи адреса первой свободной ячейки страницы в блок 2 памяти в процессе сортировки; кроме этого, посредством мультиплексора 12 по сигналу переполнения счетчика 3 слов производится запись содержимого счетчика 4 страниц (адреса перехода) в последнюю ячейку страницы.

Блок 1 памяти используется для записи отсортированной-информации. Предварительно определенная часть блока 1 памяти условно разбивается на страницы посредством записи в блок 2 памяти адресов первых ячеек страниц.

L-разрядный регистр 10 коррекции адреса служит для записи адреса перехода, считанного из последней ячейки страницы (по сигналу переполнения счетчика 3 слов), в регистр 8 адреса в процессе чтения отсортированной информации из блока 1 памяти.

Триггер 13 по выходу 23 готовности уведомляет внешнее устройство о готовности устройства сортировки к приему информации.

Устройство работает следующим образом.

Режим подготовки.

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

В исходном состоянии все регистры и счетчики обнулены (цепи нулевых установок на чертежах не показаны), Внешнее устройство по входам 20 устанавливает код режима подготовки. По входу 15 последовательно в устройство поступают данные о коде размера, о коде признака и адреса блока 1 памяти, которые последовательно сигналами по входам 18, 17 и 16 записываются в регистры размера 7| признака 6 и входной регистр 5, одновременно по R-входу происходит сброс триггера 13 (сброс готовности) и устанавливается на его втором выходе сигнал Начало цикла, который разрешает работу блока k синхронизации - происходит запись информации в блок 2 памяти по адресу, определяемому содержимым регистров размера 7 и признака 6. Пос- ледовательность записи: в первом такте выдаются сигналы С и Сд синхронизации входного регистра 5 и регистра 9 перезаписи, во втором такте выдается сигнал выбора С и А записи блока 2 памяти, затем вырабатывается сигнал, поступающий на вход триггера 13 и устанавливает устройство,в состояние готовности к приему следующей информации. Далее внешнее устройство изменяет код признака и информацию во входном регистре 5 (адрес блока 2 памяти) и снова повторяет цикл записи адреса начала следующей страницы в блок 2 памяти. Количество таких циклов записи равно количеству возможных значений признака.

Режим сортировки.

Внешнее устройство по входам 20 устанавливает код режима сортировки, по входу 15 данных - число страниц, зарезервированных в блоке 1 памяти (в начальный момент сортировки число страниц равно числу возможных значений признака), которое по сигналу с входа 19 записывается в счетчик А стра.ниц, затем на вход 15 поступает признак информации и сигналом с входа 17 записывается в регистр 6 признака. Далее на вход 15 последовательно поступает сортируемая информация, относящаяся к данному признаку. При поступлении первого слова сигналом с входа Тб происходит запись

с

tO15 20 25

5098716

его во -входной регистр 5, сброс триг30

35

40

45

50

55

гера 13, и блок 1 синхронизации начинает отрабатывать цикл записи в блок 1 памяти в следукхцей последовательности:

такт первый - выдается сигнал разрешения считывания С из блока 2 памяти - происходит считывание адреса блока 1 памяти;

такт второй - устанавливаются сигналы AJ, АЛ записи в счетчик 3 слов и регистр 8 адреса,

такт третий - выдаются сигналы С и Cg синхронизации разрешения входного регистра 5 и регистра 8 адреса - установка информации на входе данных блока 1 памяти и адреса, одновременно снимается сигнал С разрешения считывания из блока 2 памяти

такт четвертый - выдается сигнал А, записи - запись информации в блок 1 памятиi

такт пятый - устанавливаются сигналы У на счетном входе счетчика 3 СЛОВ;

такт шестой - вырабатывается сигнал Конец цикла - установка готов- кости устройства.

При поступлении последнего слова текущего признака внешнее устройство выставляет сигнал по входу 21 Конец записи/чтения. При наличии этого сигнала, по окончании записи в блок 1 памяти блоком k синхронизации в пятом такте снимается сигнал С синхронизации входного регистра 5 и устанавливается сигнал УЗ на счетном входе счетчика 3 слов, далее устанавливаются сигналы Ад записи в регистр 9 перезаписи, Сg синхронизации регистра 9 перезаписи, У ,3, и С , управления и синхронизации мультиплексора 12, происходит запись информации из счетчика 3 слов в регистр 9 перезаписи и установка ее на двунаправленных информационных шинах блока 2 памяти, а в седьмом такте сигналами А записи и Cj синхронизации информация записывается в блок 2 памяти, т.е. происходит запись адреса следующей незанятой ячейки данной страницы в блоке 1 памяти. В восьмом такте устанавливается триггер 13, и внешнее устройство выдает новый код признака.

При заполнении страницы в блоке 1 памяти счетчик 3 слов выдает в блок 1А синхронизации сигнал переполнения. По этому сигналу происходит следующее:

снимается сигнал С синхронизации входного регистра 5, устанавливается сигнал С, синхронизации мультиплексора 12 и в следующем такте сигналом А, записи происходит запись содержимого счетчика блоков в блок 1 памяти (запись адреса перехода на начало свободной страницы), далее сигналом Ag записи происходит запись этого же адреса в регистр 8 адреса. Если по заполнении страницы внешнее устройство выдало сигнал Конец записи/чтений, то одновременно с записью адреса перехода в блок 1 памяти происхо- дит его запись в блок 2 памяти сигналами Дозаписи и Cj синхронизации. По окончании сортировки ячейки блока 1 памяти с адресами, хранящимися в блоке 2 памяти, внешнее устрой- ство прописывает кодом-признаком конец информации (код-признак представляет собой ключевое слово, которое идентифицируется внешним устройством) Режим чтения.

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

По окончании чтения информации, относящейся к данному признаку, что определяется по считыванию внешним

5

О 5 0 з

0

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

Устройство для сортировки информации, содержащее два блока памяти, два счетчика, блок синхронизации и группу элементов И, причем первый и второй входы выбора режима устройства соединены соответственно с первым и вторым входами блока синхронизации, первый, второй, третий и четвертый выходы которого соединены соответственно с входами управления записью первого и второго блоков памяти и первого счетчика и счетным входом первого счетчика, пятый выход блока синхронизации является выходом синхронизации устройства, выходы первого блока памяти являются информационными выходами устройства, отличающееся тем, что, с целью расширения области применения путем обеспечения возможности сортировки информации по признакам, в него введены входной регистр, регистр признака, регистр размера, регистр перезаписи, регистр коррекции адреса, мультиплексор и триггер, причем группа информационных входов устройства соединена с информационными входами входного регистра, регистра признака, регистра размера и второго счетчика, входы разрешения записи которых подключены к входам разрешения записи соответственно информации, признака, размера и количества страниц устройства, выходы разрядов входного регистра соединены с информационными ехо- дами первого блока памяти, выход i-ro разряда регистра признака, начиная с младшего (,2, ..., га; m - количество разрядов регистра размера), и выход i-ro разряда регистра размера соединены соответственно с первым и вторым входами i-ro элемента И группы, выходы которой и выходы групп из п - m старших разрядов регистра признака, где п - количество разрядов регистра признака, соединены соответственно с группами младших и старших разрядов адреса второго блока памяти.

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

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

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение области применения устройства путем обеспечения возможности сортировки информации по признакам. Устройство содержит блоки памяти (БП) 1, 2, счетчики 3, 4, входной регистр 5, регистры признака 6, размера 7, адреса 8, перезаписи 9, коррекции адреса 10, группу элементов И 11, мультиплексор 12, триггер 13, блок синхронизации 14 и имеет информационные входы 15, входы разрешения записи информации 16, признака 17, размера 18, количества страниц 19, входы выбора режима 20, вход окончания записи-считывания 21, информационные выходы 22, выходы готовности 23 и синхронизации 24. Устройство последовательно принимает пачки слов, первое из которых является признаком, а следующие - данными, относящимися к этому признаку. Данные размещаются в БП 1, логически разбитом на страницы, количество которых не меньше, чем количество возможных значений признака. Адрес первой свободной ячейки каждой страницы содержится в БП 2 и увеличивается по мере поступления данных с соответствующим признаком. При заполнении страницы в ее последнюю ячейку и по соответствующему адресу БП 2 записываеться адрес перехода на свободную страницу БП 1, в которую теперь будут записываться данные, относящиеся к этому признаку, и т.д. При считывании происходит выборка данных из нужной страницы до тех пор, пока не будет обнаружен конец данных текущего признака или адрес перехода на новую страницу. 1 ил.