Устройство сортировки данных для обработки событий при цифровом моделировании

Устройство сортировки данных для обработки событий при цифровом моделировании

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (191 (!1) А1 щ)5 G 06 F 7/06 15/20 .

3 :с:9

ИЫ1 П".

Б 1БЛ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н A BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4468863/24-24 (22) 01 . 08. 88 (46) 30. 10.90. Бюп. N 40 (71) Московский инженерно-физический. институт (72) M.È.Àðøàâñêèé, Ю.А.Дашковский и И.О.Чурюкин (53) 681.325 (088.8) (56) Патент США М 3714634, (кл. 364/900, опублик. 1973.

Патент США И 2088600, кл. 364/200, опублик, 1962. (54) УСТРОЙСТВО СОРТИРОВКИ gAHHbX

ДЛЯ ОБРАБОТКИ СОБЫТИЙ ПРИ ПИФРОВОМ

МОДЕЛИРОВАНИИ (5?) Изобретение относится к вычислительной технике и может быть использовано, в частности, в аппаратнопрограммных системах цифрового логического моделирования с фиксированны2 ми задержками для организации хранения событий. Целью изобретения является упрощение устройства. Устройство .содержит входной регистр 1, регистр 2 параметра, входы 3 слова данных и входы 4 параметра устройства, блок 5 памяти данных, блок 6 памяти заполнения текущих блоков и блок 7 номеров текущих блоков, первый 8 и второй 9 счетчики, блок 10 управления, первый мультиплексор 11,первую группу 12 триггеров, второй мультиплексор 13 и вторую группу 14 триггеров, третий мультиплексор 15 и третью группу 16 триггеров, четвертый мультиплексор 17, четвертую группу 18 триггеров, блок 19 памяти и пятый мультиплексор 20, Данное устройство позволяет сохранить объем памяти данных в М/2 раз, где М вЂ” число возможных значений параметра.. . 1 з.п. ф-лы, 5 ил.

1603368

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

Цель изобретения — упрощение устройства. 1О

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

Устройство содержит (фиг.1) входной регистр 1, регистр (счетчик) 2 параметра, входы 3 слова данных и входы 4 параметра устройства, блок 5 памяти данных, блок 6 памяти заполнения текущих блоков, и блок 7 памяти номеров текущих блоков, первый 8 и 25 второй 9 счетчики, блок 10 управления. Кроме того, устройство содержит цепочки из последовательно соединенных между собой первого мультиплексора 11 и первой группы 12 триггеров, О второго мультиплексора 13.и второй группы 14 триггеров, третьего мультиплексора 15 и третьей группы 16 триггеров, четвертого мультиплексора 17 и четвертой группы 18 триггеров, блок

19 памяти ссылок, пятый мультиплексор 20, управляющие входы 21 устройства, элемент ИЛИ 22, информационные выходы 23 устройства.

Блок 10 управления (фиг. 2) содержит регистр 24 адреса микрокоманды, 40 шифратор 25 адресации, регистр 26 микрокоманды, формирователь 27 тактовых импульсов, группу триггеров 28 режима, первую группу 29 элементов

И-HK вторую группу 30 элементов И-НЕ,45 первый 31 и второй 32 элементы ИЛИ, управляющий выход устройства 33.

Устройство можно использовать в аппаратно-программных системах циф- 50 рового. моделирования с фиксированными задержками для органиэации хранения планируемьгх событий в соответствии с временем планирования. При этом собы-. тие (адрес активного. выхода в. модели- 55 руемой схеме) играет роль слова дан-, ных, подлежащего сортировке, а индекс события во временном колесе (младшие разряды времени планирования) играют роль параметра, по которому осуществляется сортировка..

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

Устройство предназначено для работы совместно с внешними по отношению к нему средствами управления, например с ЭВМ. При этом ЭВМ обеспечивает приложение подлежащих сортировке слов данных и связанных с ними параметров соответственно к входу 3 слова данных и входу 4 параметра устройства, снятие отсортированной последовательности слов данных с информацион. нык выходов 23 устройства по сигналам на управляющем выходе 33 устройства, а также задает режим работы устройства подачей импульса на один из входов группы управляющих входов

21 устройства.

Устройство работает в режимах ожидания, инициализации, записи слова данных, последовательного чтения слов данных с заданным значением параметра (фиг.3). !

После подачи импульса на один из входов группы управляющих входов 21 устройства на одном из выходов группы триггеров режима 28 появляется "1".

По заднему фронту очередного тактового импульса, поступающего с выхода формирователя 27 тактовых импульсов, новое значение выходов группы триггеров 28 режима заносится в регистр

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

26 микрокоманды и с его выходов поступает на управляющие входы блоков устройства. Старшие выходы регистра

26 микрокоманды определяют номер следующей микрокоманды, который вместе с кодом режима и значениями признаков ветвления по заднему фронту тактового импульса записывается в регистре 24 адреса микрокоманды и, пос" тупая затем на входы шифратора 25 адресации, вызывает появление íà его выходах кода очередной мнкрокоманды, который по переднему фронту следующего тактового импульса заносится в регистр 26 микрокоманды. Ветвления в микропрограммах осуществляются подачей на входы регистра 24 адреса

5 16033 микрокоманды сигналов с выходов первого счетчика 8, второго счетчика 9, первого элемента ИЛИ 31 и второго элемента ИЛИ 32, играющих роль признаков ветвления. Последней микро5 командой каждого режима выходы группы триггеров 28 режима по R-входу сбрасываются в "0", и устройство переходит в режим ожидания, в каждом такте которого происходит формирование и запись в регистр 26 микрокоманды микрокоманды ожидания.

Алгоритмы микропрограмм работы устройства в различных режимах (фиг.4)15 реализуются функциональной таблицей шифратора 25 адресации (фиг.s). В описании алгоритмов использованы следующие обозначения:

n - код на выходах первого счет- 20 чика 8;

h - код на выходах второго счетчика 9; — код на выходах регистра (счетчика) параметра 2; 25 у — код на выходах первой группы триггеров 12;

x — код на выходах второй группы триггеров 14;

К вЂ” код на выходах третьей группы триггеров 16;

Z — код на выходах четвертой группы триггеров 18;

N — содержимое t-й ячейки блока

Ф памяти заполнения текущих блоков 6;

à — содержимое t-й ячейки блока памяти номеров текущих блоков 7;

L — содержимое х-й ячейки блока 40 х памяти ссылок;

М вЂ” число возможных значений параметра;

R — число блока памяти данных 5;

 — число блоков памяти данных 5 . 45

Значения R, М, В и N, где Н вЂ” максимальное количество сортируемых слов данных, на которое рассчитано уст ройство, выбираются равными целым степеням числа 2.

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

ЭВМ прикладывает подлежащее сортировке слово данных и значение связанного с ним параметра соответственно к входам 3 слова данных и входам

4 параметра устройства и импульсом, переводящим устройство в режим записи слова данных, заносит их во входной регистр 1 и регистр (счетчик). 2 параметра соответственно. "Единица" с второго выхода группы триггеров 28 режима, поступающая на вход выбора первого мультиплексора 11, вызывает передачу на.его выход информации с первой грунпы его информационныс входов. "Нуль" с третьего выхода группы триггеров 28 режима, поступая на входы выбора четвертого мультиплексора 17, второго мультиплексора 13 и третьего мультиплексора 15, вызывает передачу на их выходы информации с вторых групп информационных входов.

Первой микрокомандой микропрограммы записи номер текущего блока из блока

7 памяти номеров текущих блоков заносится через первый мультиплексор

11 в первую группу 12 триггеров, значение числа заполненных ячеек в текущем блоке из блока 6 памяти заполнения текущих блоков записывается в первый счетчик 8 через пятый мультиплексор 20; номер первого блока в списке свободных блоков с вьиодов второго счетчика 9 через четвертый мультиплексор. 17 записывается в четвертую группу 18 триггеров и через .второй мультиплексор 13 — во вторую группу 14 триггеров. Второй: микрокомандой слово данных с выходов вход- . ного регистра I заносится в блок 5 памяти данных по адресу, роль старших разрядов в котором играет номер блока, а младших — число заполненных ячеек в блоке. Третьей микрокомандой к содержимому первого счетчика 8 ло прямому счетному входу прибавляется единица. Если при этом содержимое счетчика не достигнет R (на. R-м выходе — ."0"), то четвертой микрокомандой оно запйсывается .в .бл.ок 6 памяти заполнения текущнх блоков по адресу, заданному значением параметра с выходов регистра (счетчика) 2 параметра. Микропрограмма записи слова данных завершается, -осуществляется переход.к микрокоманде ожидания.

В противном случае пятой микрокоман1603368 дой по R-входу сбрасывается в "0" первый счетчик 8, номер блока, который бып вторым в, списке свободных блоков, с выходов блока 19 памяти ссылок через третий мультиплексор 15 заносится в третью группу 16 триггеров.

Шестой михрокомандой номер блока с выходов третьей группы 16 триггеров заносится во второй счетчик 9, номер заполненного блока с выходов первой группы 12 триггеров записывается в блок,19 памяти ссылок; номер блока, который бып первым в списке свободных блоков, с выходов четвертой группы 15

18 триггеров записывается в блок 7 памяти номеров текущих блоков; нулевой код с выходов первого счетчика

8 заносится в блок 6 памяти заполнения текущих. блоков, осуществляется 20 переход к микрокоманде ожидания.

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

3ВМ выставляет значение параметра 30 на входе параметра 4 устройства и импульсом, переводящим устройство в режим последовательного чтения слов данных с заданным значением парамет" ра, заносит его .в регистр (счетчик) параметра 2. Так как на входы выбора четвертого мультиплексора 17, второго мультиплексора 13 и третьего мультиплексора 15 поступает "1" с третьего выхода группы триггеров 28 режима, 40 а. на вход выбора первого мультиплек сора 11 с второго выхода группы триггеров 28 режима поступает "0", то на их выходы передается информация соответственно с первых и с вторых 45 групп информационных входов. Первой микрокомандой номер блока иэ блока 7 памяти номеров текущих блоков через второй мультиплексор 13 заносится во вторую группу 14 триггеров и через третий мультиплексор 15 — в третью группу 16 триггеров; значения числа заполненных ячеек в текущем блоке выходов блока 5 памяти заполнения текущих блоков через пятый мультиплексор 20 записывается в первый счетчик 8; номер первого свободного блока с выходов второго счетчика 9 через первый мультиплексор 11 заносится в первую группу 12 триггеров. Если код. на выходе первого счетчика 8 не равен нулю (на выходе первого элемента ИЛИ 31 — "1"), второй микрокомандой иэ содержимого первого счетчика 8 по обратному счетному входу вычитается единица, а третьей микрокомандой из блока 5 памяти данных по адресу, роль старших разрядов которого играет номер текущего блока, а мпадших — номер последней заполненной ячейки в текущем блоке, считывается слово данных и по сигналу на управляющем выходе 33 устройства передается в ЭВМ. A далее, если на выходе первого элемента ИЛИ 31 — "1", осуществляется переход к второй микрокоманде. Если же код на выходе первого счетчика 8 стал равен нулю {на выходе первого элемента ИЛИ 31

"0" ), то четвертой микрокомандой номер блока, следующего за текущим в списке, соответствующем заданному значению параметра, с выходов блока

19 памяти ссылок через четвертый мультиплексор 17 заносится в четвертую группу 18 триггеров. Если этот номер не равен нулю .(на выходе второго элемента ИЛИ 32 — "1"), гятой микрокомандой во второй счетчик 9 с выходов третьей группы 16 триггеров заносится номер освобожденного блока, в блок 7 памяти номеров текущих блоков с выходов четвертой группы 18 триг r ер о в з аписыва ет ся номер сл едующего блока в списке, в блок памяти ссыпок с выходов первой группы 11 триггеров помещается номер первого блока в списке свободных блоков, в первый счетчик 8 через пятый мультиплексор 20 заносится число (К-1) и осуществляется переход к третьей микрокоманде. Если же на выходе второго элемента ИЛИ 32 появится "1", то шестой микрокомандой осуществляется переход к микрокоманде ожидания, и микропрограмма последовательного чтения слов данных с заданным значением параметра за верша етс я .

Задача режима инициализации — назначить первые блоки в списках, соответствующих различным значениям па- раметра, и объединить оставшиеся блоки в списке свободных блоков. В качестве генераторов значений параметра и номеров блоков 5 памяти данных используются соответственно регистр (счетчик) 2 параметра и второй счет1603368

10 чик 9, работающие в счетном режиме под управлением блока управления.

Сигналы "0", поступающие с второго и третьего выходов группы триггеров 28 режима на входы выбора четвертого мультиплексора 17, второго мультиплексора 13, третьего мультиплексора

15 и первого мультиплексора 11, вызывают передачу на выходы мультиплексоров информации с вторых групп информационных входов.

Первой микрокомандой микропрограммы инициализации по R-входу сбрасы- 15 ваются в "0" регистр (счетчик) 2 параметра, первый счетчик 8 и второй счетчик 9. Второй микрокомандой код (номер блока) с выхода второго счетчика 9 через четвертый мультиплексор

17 заносится в четвертую группу 18 триггеров. Третьей микрокомандой номер блока с выхода четвертой группы

18 триггеров заносится в блок 7 памяти номеров текущих блоков по адресу, поступающему с выходов регистра (счет12 триггеров помещается в блок памяти чика) 2 параметра; по тому же адресу в блок 6 памяти заполнения текущих блбков с выходов первого счетчика 8 помещается нулевой код; содержимое 30 второго счетчика 9 по счетному входу увеличивается на единицу. Если при этом содержимое второго счетчика 9 не стало равным максимально возможному значению параметра (на М-м выходе второго счетчика 9 — "0"), четвертой микрокомандой через мультиплексор 17 в группу 18 триггеров заносится код с выходов второго счетчика 9, содержимое регистра (счетчика) 2 парамет- 40 ра по счетному входу увеличивается на единицу и осуществляется переход к третьей микрокоманде. Если же на

М-м выходе второго счетчика 9 появится 1", то пятой микрокомандой код с 45 выхода второго счетчика 9 через.мультиплексор 13 заносится в группу 14 триггеров, шестой микрокомандой содержимое второго счетчика 9 по счетному входу увеличивается на единицу и седьмой микрокомандой с выходов второго счетчика 9 через мультиплексор 11 заносится в группу 12 триггеров. Затем, если содержимое второго счетчика 9 не равно числу блоков в блоке 5 памяти данных (на В-M выходе второго счетчика 9 — "0"), восьмой микрокомандой код с выходов группы ссылок по адресу, поступающему с выходов группы 14 триггеров, девятой микрокомандой содержимое второго счетчика 9 через мультиплексор 13 заносится в группу 14 триггеров, и осуществляется переход к шестой микрокоманде. Если же на В-м выходе второго счетчика 9 появится "1", то десятой микрокомандой его содержимое по R-входу сбрасывается в нуль, а код с выходов группы 14 триггеров записывается в блок памяти ссыпок.

Одиннадцатой микрокомандой нулевой код с выходов второго счетчика 9 через мультиплексор 11 заносится в группу 12 триггеров и через мультиплексор 13 — в третью группу 14 триггеров. Двенадцатой микрокомандой содержимое второго счетчика 9 по счетному входу увеличивается на единицу, а в блок 19 памяти ссылок с выходов группы 12 триггеров заносится нулевой код. Если после этого содержимое второго счетчика 9 не станет равным максимальному возможному числу значений параметра (на М-м выходе второго счетчика 9 — "0"), тринадцатой микрокомандой через мультиплексор

13 оно заносится в группу 14 триггеров, и осуществляется переход к двенадцатой микрокоманде. Если же на

М-м выходе второго счетчика 9 появится "1", то четырнадцатой микрокомандой, осуществляющей- переход к микрокоманде ожидания, микропрограмма инициализации завершается.

Таким образом, предлагаемое устройство позволяет сократить объем памяти данных в М/2 раз, что приводит к упрощению всего устройства.

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

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

1603368 второй входы которого соединены с со ответствующими входами задания режимов группы устройства, входы задания режимов группы которого соединены с

Ф соответствующими одноименными входами блока управления, входы признака первой группы которого соединены с выходами разрядов данных первого счетчика, входами младших разрядов адреса блока 1О памяти данных и информационным входом блока памяти заполнения текущих блоков, вход адреса которого соединен с входом адреса блока памяти номеров текущих блоков и выходом регистра па- 15 раметра, вход записи которого соединен с выходом элемента ИЛИ и с входом записи входного регистра, информационный вход которого является входом слова данных устройства, информацион- 2О ный выход которого соединен с выходом блока памяти данных, входы старших разрядов адреса которого соединены с разрядами выхода блока памяти номеров текущих блоков и первыми инфор- 25 мационными входами первого, второго и третьего мультиплексоров, выходы которых соединены с информационными входами триггеров первой, второй и третьей групп соответственно, прямые выходы триггеров первой группы соединены с информационными входами блока памяти ссылок, адресные входы которого соединены с прямыми выходами триггеров второй группы, прямые выходы триггеров третьей группы соединены с информационными входами второго счетчика, выходы данных блока памяти ссылок соединены с первыми информационными входами четвертого мульти- 40 плексора и вторыми информационными входами третьего мультиплексора, выходы четвертого мультиплексора соединены с информационными входами триг- геров четвертой группы, прямые выходы 45 которых соединены с входами признака второй. группы блока управления и информационными входами блока памяти номеров текущих блоков, выходы разрядов данных второго счетчика соеди- > иены с вторыми информационными входами первого, второго, четвертого мультиплексоров и входами признака третьей группы:блока управления, первый выход которого соединен с входом выбора первого мультиплексора, второй .

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

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

И-НЕ, группу триггеров режима, два элемента ИЛИ, регистр адреса микрокоманды, шифратоР адресации, регистр микрокоманды, формирователь тактовых импульсов, выход которого соединен с входами синхронизации регистра адреса микрокоманды и регистра микрокоманды, информационный вход которого соединен с выходом шифратора адресации, информационный вход которого соединен с выходом регистра адреса микрокоманды, первый вход данных которого соединен с прямым выходом первого триггера режима группы и пер1603368

1б 03368

Входы

Вы коды

9 10 11 52 1 2 5 4 5 6 7 8 9 70 11 12 0

16 77

Z1 2

Ожидание

ХХХХ 0000001 111 700

1 О 1

000

Инициализация

О а аоо

Х Х о а

070

Q 1 а 01

1 7

006

101

111

100

010

Х Х

0 О

О О

ОО1

000

Х Х

О 1

10 О

100

011 а

Х О

О 0

Оо

0O1

0 О

<05

О 0

100

1 О

Оо

100

1 0

101

010

ХХ

f 0f

000

О 1

f00

110 а7

О 1

101 о 0

010

Х Х

100

011

Х Х

1ОО

О7

11 7

О f 7 а О

0ОО о а

Х Х

100

7 О

100

Л X

017

10<

1 О.о

005

711

101

Х Х

100

0 f ао

О О

10 1

1 О

000

Х Х

100 ооа х о

О О

7а1

70f

О 01

1 0

ОOG

101

Х 1 а 00

Зал

LCD

О 01

С.О 7

10f

000

Х X

07О

Х Х аоо

171

1 О

01 1

1! 157

101 аоаа а а

1 о

0Qf

X Х

f0f

17177 О

1 а

000

ОООО

001

Хх а 7

f ОО

10 7

10771 о 1 с с

О а аоо

107

11 100

О О

Х Х /г ; и е

fIG 7 о а 7

001

1а1

О 7

Х Х

010

101 ааааа

1 а х

Х Х

10 71

101 оос

X Х

О а а

077

101

7 100 f

О 1 ас10 х о а 7 о

1.01 о х хо

О а 7

001

Х 0

Х-Лнй е значеню xoda

Составитель А.Иванов

Техред Л. Серд окова Корректор Л. Осауленко

Pедактор M. Келемеш

Заказ 3385 Тираж 571 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101

0 а

f 0

1ааа оооо

70ОО

0001:1

7 7 1i 1

70 11

1 10 10

1 0 1

10f