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

(5) Изобретение лительной техник пользовано, в ча программных сист ческого моделиро относится к выч и может быть истности, вмах цифроания с ф паратноого л ыиксир она ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕН АВТОРСКОМУ СПИ)кл, 364/900, опублик.Патент США Иф 208860кл. 364/200, опублик,(54) УСТРОЙСТВО СОРТИРОВКИ ДАННЬХДЛЯ ОБРАБОТКИ СОБЫТИЙ ПРИ ПИФРОВОММОДЕЛИРОВАНИИ 51)5 С 06 Р 7/06 15/20 ми задержками для организации хранения событий. Ц ью изобретения является упрощение устройства. Устройство .содержит входной регистр 1, регистр 2 параметра, входы 3 слова данных и входы 4 параметра устройства,блок 5 памяти данных, блок 6 памятизаполнения текущих блоков и блок 1номеров текущих блоков, первый 8 ивторой 9 счетчики, блок 10 управления, первый мультиплексор 11,первуюгруппу 12 триггеров, второй мультиплексор 13 н вторую группу 14 триггеров, третий мультиплексор 15 итретью группу 16 триггеров, четвертый мультиплексор 17, четвертую группу 18 триггеров, блок 1.9 памяти ипятый мультиплексор 20, Данное устройство позволяет сохранить объемпамяти данных в М/2 раз, где М - число возможных значений параметра1 з.п. ф-лы, 5 ил.120 Изобретение относится к вычислительной технике и может быть использовано, в частности, в аппаратнопрограммных системах цифрового логи 5ческого моделирования с фиксированными задержками для организации хранения событий.Цель изобретения - упрощение устройства, 1 ОНа фиг.1 дана структурная схемапредлагаемого устройства; на фиг.2 -то же, блок управления; на фиг.З -таблица кодировки режимов работыустройства; на фиг.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 элементовИ-НЕ, вторую группу 30 элементов И-НЕ,4первый 31 и второй 32 элементы ИЛИ,управляющий выход устройства 33,Устройство можно использовать ваппаратно-программных системах цифрового. моделирования с фиксированнымизадержками для органиэации храненияпланируемых событий в соответствии свременем планирования. При этом собы-,тие (адрес активного выхода в. модели-руемой схеме) играет роль слова дан-,ных, подлежащего сортировке, а индекс события во временном колесе(младшие разряды времени планирова" ния) играют роль параметра, по которому осуществляется сортировкаУстройство работает следующим образом.Устройство предназначено для работы совместно с внешними по отношениюк нему средствами управления, например с ЭВМ. При этом ЭВМ обеспечиваетприложение подлежащих сортировкеслов данных и связанных с ними параметров соответственно к входу 3 словаданных и входу 4 параметра устройства, снятие отсортированной последовательности слов данных с информационнык выходов 23 устройства по сигналам на управляющем выходе 33 устройства, а также задает режим работыустройства подачей импульса на одиниз входов группы управляющих входов21 устройства.Устройство работает в режимах ожидания, инициализации, записи словаданных, последовательного чтенияслов данных с заданным значениемпараметра (Фиг.З),После подачи импульса на один извходов группы управляющих входов 21устройства на одном из выходов группытриггеров режима 28 появляется "1".По заднему фронту очередного тактового импульса, поступающего с выходаформирователя 27 тактовых импульсов,новое значение выходов группы триггеров 28 режима заносится в регистр24 адреса микрокоманды и с его выходов поступает на входы шифратора 25адресации, на выходах которого формируется код первой микрокомандысоответствующего режима, Этот кодпо переднему Фронту следующего тактового импульса записывается в регистр26 микрокоманды и с его выходов поступает на управляющие входы блоковустройства. Старшие выходы регистра26 микрокоманды определяют номер следующей микрокоманды, который вместес кодом режима и значениями призна"ков ветвления по заднему фронту тактового импульса записывается в регистре 24 адреса микрокоманды и, пос"тупая затем на входы шифратора 25адресации, вызывает появление на еговыходах кода очередной мнкрокоманды,который по переднему фронту следующего тактового импульса заносится врегистр 26 микрокоманды. Ветвленияв микропрограммах осуществляютсяподачей на входы регистра 24 адреса68 6ных блоков и осуществляется коррекция списков.ЭВМ прикладывает подлежащее сортировке слово данных и значение связанного с ним параметра соответственно к входам 3 слова данных и входам 4 параметра устройства и импульсом, переводящим устройство в режим записи .слова данных, заносит их во входной регистр 1 и регистр (счетчик). 2 параметра соответственно. "Единица" с второго выхода группы триггеров 28 режима, поступающая на вход выбора первого мультиплексора 11, вызывает передачу на.его выход информации с первой грунпы его информационньв входов. фНуль" с третьего выхода груп- пы триггеров 28 режима, поступая на входы выбора четвертого мультиплексора 17, второго мультиплексора 13 и третьего мультиплексора 15, вызывает передачу на их выходы информации с вторых групп информационных входов. .Первой микрокомандой микропрограммы записи номер текущего блока из блока 7 памяти номеров текущих блоков заносится через первый мультиплексор 11 в первую группу 12 триггеров, значение числа заполненных ячеек в текущем блоке иэ блока 6 памяти заполнения текущих блоков записывается в первый счетчик 8 через пятый мультиплексор 20; номер первого блока в списке свободных блоков с вьиодов второго счетчика 9 через четвертый мультиплексор.17 записывается в четвертую группу 18 триггеров и через .второй мультиплексор 13 - во вторую группу 14 триггеров. Второй:микро- командой слово данных с выходов вход- . ного регистра 1 заносится в блок 5 памяти данных по адресу, роль старших разрядов в котором играет номер блока, а младших - число заполненных ячеек в блоке. Третьей микрокомандой к содержимому первого счетчика 8 по прямому счетному входу прибавляется единица. Если при этом содержимое .счетчика не достигнет К (на.К-м выходе - ."0"), то четвертой микрокомандой оно запйсывается .в блок 6 памяти заполнения текущих блоков по адресу, заданному значением параметра с выходов регистра (счетчика) 2 параметра. Микропрограмма записи слова данных завершается, осуществляется переход.к микрокоманде ожидания, В противном случае пятой микрокоман 516033микрокоманды сигналов с выходов первого счетчика 8, второго счетчика 9,первого элемента ИЛИ 31 и второгоэлемента ИЛИ 32, играющих роль признаков ветвления. Последней микро 5командой каждого режима выходы группы триггеров 28 режима по К-входусбрасываются в "0", и устройство переходит в режим ожидания, в каждомтакте которого происходит формирование и запись врегистр 26 микрокоманды микрокоманды ожидания,Алгоритмы микропрограмм работыустройства в различных режимах (фиг.4)15реализуются функциональной таблицейшифратора 25 адресации (фиг.5), Вописании алгоритмов использованы следующие обозначения:и - код на выходах первого счетчика 8;Ь - код на выходах второго счетчика 9;- код на выходах регистра (счетчика) параметра 2; 25у - код на выходах первой группытриггеров 12;х - код на выходах второй группытриггеров 14;К - код на выходах третьей группытриггеров 16;Е - код на выходах четвертой группы триггеров 18;Н - содержимое С-й ячейки блокаФпамяти заполнения текущих блоков 6;35Г - содержимое й-й ячейки блокапамяти номеров текущих блоков 7;Ь - содержимое х-й ячейки блока 40хпамяти ссылок;М - число возможных значений параметра;К - число блока памяти данных 5;В - число блоков памяти данных 5. 45Значения К, М, В и И, где Б - максимальное количество сортируемых словданных, на которое рассчитано уст"ройство, выбираются равными целымстепеням числа 2. . 50В режиме записи снова данных осуществляется запись подлежащего сортировке слова данных в блок 5 памятиданных, который является текущим всписке блоков, соответствующем заданному значению параметра. Если послеэтого в текущем блоке не останетсясвободных ячеек, то к списку добавляется новый блок иэ списка свобод 1603368дой по К-входу сбрасывается в "0" первый счетчик 8, номер блока, который бып вторым в, списке свободных блоков, с выходов блока 19 памяти ссылок через третий мультиплексор 15 заносится в третью группу 16 триггеров. Шестой михрокомандой номер блока с выходов третьей группы 16 триггеров заносится во второй счетчик 9, номер заполненного блока с выходов первой группы 12 триггеров записывается в блок,19 памяти ссылок; номер блока, который был первым в списке свободных блоков, с выходов четвертой группы 15 18 триггеров записывается в блок 7 памяти номеров текущих блоков; нулевой код с выходов первого счетчика 8 заносится в блок 6 памяти заполнения текущих. блоков, осуществляется 20 переход к микрокоманде ожидания.В режиме последовательного чтения слов данных с заданным значением параметра слова данных считываются из текущего блока 5 памяти данных, 25 а после его опустошения осуществляется переход к следующему блоку в спис.ке блоков, соответствующем заданному значению параметра.ЭВМ выставляет значение параметра 30 на входе параметра 4 устройства и импульсом, переводящим устройство в режим последовательного чтения слов данных с заданным значением парамет" ра, заносит его .в регистр (счетчик) параметра 2. Так как на входы выбора четвертого мультиплексора 17, второго мультиплексора 13 и третьего мультиплексора 15 поступает "1" с третьего выхода группы триггеров 28 режима, 40 а. на вход выбора первого мультиплек сора 11 с второго выхода группы триггеров 28 режима поступает "О", то на их выходы передается информация соответственно с первых и с вторых 45 групп информационных входов, Первой микрокомандой номер блока иэ блока 7 памяти номеров текущих блоков через второй мультиплексор 13 заносится во вторую группу 14 триггеров и через третий мультиплексор 15 - в третью группу 16 триггеров; значения числа заполненных ячеек в текущем блоке с выходов блока 5 памяти заполнения текущих блоков через пятый мультиплексор 20 записывается в первый счетчик 8; номер первого свободного блока с выходов второго счетчика 9 через первый мультиплексор 11 заносится в первую группу 12 триггеров. Если код. на выходе первого счетчика 8 не равен нулю (на выходе первого элемента ИЛИ 31 - 1"), второй микрокомандой иэ содержимого первого счетчика 8 по обратному счетному входу вычитается единица, а третьей микрокомандой из блока 5 памяти данных по адресу, роль старших разрядов которого играет номер текущего блока, а мпадших - номер последней заполненной ячейки в текущем блоке, считывается слово данных и по сигналу на управляющем выходе 33 устройства передается в ЭВМ. А далее, если на выходе первого элемента ИЛИ 31 - "1", осуществляется переход к второй микрокоманде. Если же код на выходе первого счетчика 8 стал равен нулю (на выходе первого элемента ИЛИ 31 "0"), то четвертой микрокомандой номер блока, следующего за текущим в списке, соответствующем заданному значению параметра, с выходов блока 19 памяти ссылок через четвертый мультиплексор 17 заносится в четвертую группу 18 триггеров. Если этот номер не равен нулю,(на выходе второго элемента ИЛИ 32 - "1"), гятой микрокомандой во второй счетчик 9 с выходов третьей группы 16 триггеров заносится номер освобожденного блока, в блок 7 памяти номеров текущих блоков с выходов четвертой группы 18 триггеров записывается номер следующего блока в списке, в блок памяти ссыпок с выходов первой группы 11 триггеров помещается номер первого блока в списке свободных блоков, в первый счетчик 8 через пятый мультиплексор 20 заносится число (К) и осуществляется переход к третьей микрокоманде. Если же на выходе второго элемента ИЛИ 32 появится "1", то шестой микрокомандой осуществляется переход к микрокоманде ожидания, и микропрограмма последовательного чтения слов данных с заданным значением параметра завершается.Задача режима инициализации - назначить первые блоки в списках, соответствующих различным значениям па- раметра, и объединить оставшиеся блоки в списке свободных блоков, В качестве генераторов значений параметра и номеров блоков 5 памяти данных используются соответственно регистр (счетчик) 2 параметра и второй счет 1603368 1 Очик 9, работающие в счетном режимепод управлением блока управления.Сигналы "О, поступающие с второго итретьего выходов группы триггеров 28режима на входы выбора четвертогомультиплексора 17, второго мультиплексора 13, третьего мультиплексора 15 и первого мультиплексора 11, вызывают передачу на выходы мультиплексоров информации с вторых групп информационных входов. Первой микрокомандой микропрограммы инициализации по К-входу сбрасываются в "О" регистр (счетчик) 2 параметра, первый счетчик 8 и второйсчетчик 9. Второй микрокомандой код(номер блока) с выхода второго счетчика 9 через четвертый мультиплексор 20 17 заносится в четвертую группу 18триггеров. Третьей микрокомандой номер блока с выхода четвертой группы18 триггеров заносится в блок 7 памяти номеров текущих блоков по адресу,поступающему с выходов регистра (счет 12 триггеров помещается в блок памяти чика) 2 параметра; по тому же адресув блок 6 памяти заполнения текущихблоков с выходов первого счетчика 8помещается нулевой код; содержимое 30второго счетчика 9 по счетному входуувеличивается на единицу. Если приэтом содержимое второго счетчика 9не стало равным максимально возможному значению параметра (на М-м выходевторого счетчика 9 - "О"), четвертоймикрокомандой через мультиплексор 17в группу 18 триггеров заносится кодс выходов второго счетчика 9, содержимое регистра (счетчика) 2 параметра по счетному входу увеличиваетсяна единицу и осуществляется переходк третьей микрокоманде. Если же наМ-м выходе второго счетчика 9 появится 1", то пятой микрокомандой код с 45выхода второго счетчика 9 через.мультиплексор 13 заносится в группу 14триггеров, шестой микрокомандой содержимое второго счетчика 9 по счетному входу увеличивается на единицуи седьмой микрокомандой с выходоввторого счетчика 9 через мультиплексор 11 заносится в группу 12 триггеров. Затем, если содержимое второгосчетчика 9 не равно числу блоков вблоке 5 памяти данных (на В-м выходевторого счетчика 9 - "О"), восьмоймикрокомандой код с выходов группы ссылок по адресу, поступающему с выходов группы 14 триггеров, девятоймикрокомандой содержимое второго счет.чика 9 через мультиплексор 13 заносится в группу 14 триггеров, и осуществляется переход к шестой микрокоманде. Если же на В-м выходе второго счетчика 9 появится "1", тодесятой микрокомандой его содержимоепо К-входу сбрасывается в нуль, акод с выходов группы 14 триггеровзаписывается в блок памяти ссыпок.Одиннадцатой микрокомандой нулевойкод с выходов второго счетчика 9через мультиплексор 11 заносится вгруппу 12 триггеров и через мультиплексор 13 - в третью группу 14 триггеров. Лвенадцатой микрокомандой содержимое второго счетчика 9 по счетному входу увеличивается на единицу,а в блок 19 памяти ссылок с выходовгруппы 12 триггеров заносится нулевой код. Если после этого содержимоевторого счетчика 9 не станет равныммаксимальному возможному числу значений параметра (на М-м выходе второго счетчика 9 - "О"), тринадцатоймикрокомандой через мультиплексор13 оно заносится в группу 14 триггеров, и осуществляется переход к двенадцатой микрокоманде. Если же наМ-м выходе второго счетчика 9 появится "1", то четырнадцатой микрокомандой, осуществляющей переход к микрокоманде ожидания, микропрограмма инициализации завершается,Таким образом, предлагаемое устройство позволяет сократить объемпамяти данных в М/2 раз, что приводит к упрощению всего устройства.формула изобретения1. Устройство,.сортировки данных для обработки событий при цифровом моделировании, содержащее входной регистр, блок. памяти данных, регистр параметра и бпок управления, причем информационный вход блока памяти данных соединен с выходом входного регистра, о т л и ч а ю - щ е е с я тем, что, с целью упрощения устройства, в него введены пять мультиплексоров, четыре группы триггеров, блок памяти заполнения текущих блоков, блок памяти номеров текущих блоков, блок памяти ссылок, два счетчика и элемент ИЛИ, первый ивторой входы которого соединены с соответствующими входами задания режимов группы устройства, входы задания режимов группы которого соединены с соответствующими одноименными входами блока управления, входы признака первой группы которого соединены с выходами разрядов данных первого счетчика, входами младших разрядов адреса блока 1 О памяти данных и информационным входом блока памяти заполнения текущих блоков, вход адреса которого соединен с входом адреса блока памяти номеров текущих блоков и выходом регистра па раметра, вход записи которого соединен с выходом элемента ИЛИ и с входом записи входного регистра, информационный вход которого является входом слова данных устройства, информацион О ный выход которого соединен с выходом блока памяти данных, входы старших разрядов адреса которого соединены с разрядами выхода блока памяти номеров текущих блоков и первыми инфор мационными входами первого, второго и третьего мультиплексоров, выходы которых соединены с информационными входами триггеров первой, второй и третьей групп соответственно, прямые выходы триггеров первой группы соединены с информационными входами блока памяти ссылок, адресные входы которого соединены с прямыми выходами триггеров второй группы, прямые выходы триггеров третьей группы соединены с информационными входами второго счетчика, выходы данных блока памяти ссылок соединены с первыми информационными входами четвертого мульти О плексора и вторыми информационными входами третьего мультиплексора, выходы четвертого мультиплексора соединены с информационными входами триг- геров четвертой группы, прямые выходы 45 которых соединены с входами признака второй группы блока управления и информационными входами блока памяти номеров текущих блоков, выходы разрядов данных второго счетчика соединены с вторыми информационными входами первого, второго, четвертого мультиплексоров и входами признака третьей группы:блока управления, первый выход которого соединен с входом выбора первого мультиплексора, второй.-55 выход блока управления соединен с входами выбора второго, третьего и четвертого мультиплексоров, третий выход блока управления соединен с входом сброса первого счетчика, вход параллельной записи которого соединен с четвертым выходом блока управления, пятый и шестой выходы которого соединены соответственно с входом сброса и входом параллельной записи второго счетчика, с седьмого подесятый выходы блока управления соединены соответственно с синхровходами триггеров четвертой, первой, второй и третьей групп, одиннадцатый выход блока управления соединен с входом выбора пятого мультиплексора, первый информационный вход которого соединен с выходом блока памяти заполнения текущих блоков, а второй информационный вход - с входом "1" устройства, выход пятого мультиплексора соединен с информационным входом первого счетчика, с двенадцатого по пятнадцатыйвьходы блока управления соединенысоответственно с входами записи блокапамяти номеров текущих блоков, блокапамяти заполнения текущих блоков,блока памяти ссылок и блока памятиданных, шестнадцатый выход блока управления является выходом сопровождения информации устройства, семнадцатый и восемнадцатый выходы блока управления соединены с входамн сброса и прямого счета регистра параметра соответственно, девятнадцатый выход блока управления соединен с прямым счетным входом второго счетчика, двадцатый и двадцать. первый выходы блока управления соединены соответственно с прямым и обратным счетными входами первого счетчика, информационный вход регистра параметра является входом слова параметра устройства,2.Устройство по п.1, о т л ич а ю щ е е с я тем, что блок управления содержит две группы элементов И-НЕ, группу триггеров режима, два элемента ИЛИ, регистр адреса микро- команды, шифратор адресации, регистр микрокоманды, Формирователь тактовых импульсов, выход которого соединен с входами синхронизации регистра адреса микрокоманды и регистра микрокоманды, информационный вход которого соединен с выходом шифратора адресации, информационный вход которого соединен с выходом регистра адреса микрокоманды, первый вход данных которого соединен с прямым выходом первого триггера режима группы и пер 13141603368ными входами первых элементов И-НЕпервой и второй групп, первые входывторых элементов И"НЕ первой и второй групп соединены с прямым выходомвторого триггера режима группы, нервым выходом блока управления и вторымвходом данных регистра адреса микрокоманды, третий вход данных которогосоединен с,прямым выходом третьего 10триггера режима группы и с первымивходами третьих элементов И-НЕ первойи второй групп и вторым выходом блокауправления, вторые входы элементовИ-НЕ первой группы соединены с первым разрядом выхода регистра микрокоманды, второй разряд выхода которого соединен с вторыми входами элементов И-НЕ второй группы, разрядывыхода с третьего по восемнадцатыйрегистра микрокоманды являются выхо-.дами блока управления с третьего повосемнадцатый соответственно, входы .задания режимов которого соединеныс входами установки триггеров режима 25группы соответственно, входы сброса которых соединены с выходами элементов И-НЕ первой группы соответственно, входы признака первой .группы бло-.ка управления соединены с входамипервого элемента ИЛИ, выход которогосоединен с четвертым входом данныхрегистра адРеса микрокоманды, пятыйвход данных которого соединен со старшим входом признака первой группы блока управления, входы признака второйгруппы которого соединены с входамивторого элемента ИЛИ, выход которогосоединен с шестым входом данных регистра адреса микрокоманды, седьмойи восьмой входы данных которого являются входами признака третьей группы блока управления., девятнадцатый,двадцатый и двадцать первый выходыкоторого являются выходами элементовИ-НЕ второй группы соответственно,разряды с девятнадцатого по двадцатьвторой выхода регистра микрокомандысоединены соответственно с входамиданных с девятого по двенадцатый ре-.гистра адреса микрокоманды.11 б 03368 Входы Вы коды 9 10 11 72 1 2 Д 4 5 б 7 В 9 70 11 12 75 1 б 72 27 2 Ожидание 0 Х Х ххххх Оооаоо 1171700 Х Х 1 О ООО Инацоаоизациа О ОХ ха ОО Х Х о а 07 а 001 1 7 ХООО 1 О ООХ 111 100 000 010 Х Х О ОХ а 0 хаа 1 000 Х Х 001 10 0 10 011 а Х О ООХ ОО ха 01 000 010 ООХ Х 001 Х 1 100 000 11 7 100 1 0 ООХ Х 010 ХХ 1 0 101 7 ООО 00110 001 1 О ООХ хо 1 а Х Х 100 7011 а ах Х Х 1 О 7 7 оа 0017 7 аах 000 о а Х Х ООХ 100 ха 11 1 О 100 О ах 001 711 Х Х 100 001 ООХ 1 а 1 О ООС Х Х оса х а аах х 7 а 1 7 1 001 Х 10 ООХ Ооа 7 0 Х 1 ООО 0 01 О 7 10 Х ХООО Х Х 0 Х 1 аааа 1 010 Х Х 7 а Оааао 7 011 1 0 а О 1 ОХ Ха Р 1 Х Х 1 ОХ Оба Ха 01 Хх 100 ХО С О Х Ь/г; ау,/д 7 а 7 О а 7 001 1 а О 1 Х Х Х 010 1 О 7 ООООО 1 а Х Х О 11 а 1 а 071 ООС хааа Х Х 010 011 1 О 01 х а с 10 хаа 1 О ХОО 7 01 Х О Х а Оао 1 О О 001 10 аа 010 ХОО 7 О 1 Х Х-Людое значение охода Составитель А.Иванов Техред Л, Сердокова Корректор Л, Осауленко Редактор М. Келемеш Заказ 3385 Тираж 577 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Рауйская наб., д. 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101 Х 1 0.0 Х 100 хаас Х 000 Запаса аа;ааа