Устройство для организации очередей элементов данных Советский патент 1986 года по МПК G06F9/50 

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

43

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

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

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

2. Устройство по п. 1, о т л и - чающееся тем, что узел синхронизации содержит два формирователя импульсов, генератор импульсов, элемент задержки, имитатор циклов блока памяти, десять элементов И, шесть элементов ИЛИ, семь элементов IE, элемент И-НЕ и четыре элемента ЙПИ-НЕ, причем первый вход узла соединен с первым входом первого элемен та , второй и третий входы которого соединены соответственно с четвертым и пятым входами узла, выход первого элемента ИЛИ-НЕ соединен с первым входом первого элемента И, выход которого соединен с первыми входами п-ервого и второго элементов ИЛИ, выход первого элемента ИЛИ соединен с первыми входами второго и третьего элементов И, выход

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

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

ч

и с третьим выходом узла, третий вход которого соединен с четвертым входом второго элемента ИЖ и через шестой элемент НЕ с пятым входом третьего элемента И, второй выход имитатора циклов блока памяти соединен с первым входом четвертого элемента ШШ-НЕ, с вторым входом восьмого элемента И, с четвертым вьпсодом узла и через седьмой элемент НЕ с третьими входами пятого и седьмого элементов И, выход седьмого элемента И соединен с пятым входом второго элемента ИЛИ, шестой вход которого соединен с выходом восьмого элемента И, третий вход которого соединен с ВЫХОДОМ элемента И-НЕ и с пятым входом второго элемента И, шестой вход которого соединен с выходом четвертого элемента ИЛИ-НЕ, второй вход которого соединен с выходом третьего элемента ИЛИ-НЕ, второй вход которого соединен с входом генератора импульсов и с выходом второго элемента ИЛИ, седьмой вход которого соединен с выходом шестого элемента И и с вторым входом шестого элемента ИЛИ, выход которого соединен с третьим входом шестого элемента И, выход второго формирователя импульсов соединен с пятым выходом узла,

3. Устройство по п. 1, отличаю щ е е с я тем, что узел управления запуском и завершением операций содержит восемь элементов И, пять элементов ИЛИ, два элемента ИПИ-НЕ, элемент И-НЕ и пять элементов НЕ, причем первый вход узла соединен с первыми входами первого и второго элементов И и через первый элемент НЕ с первым входом третьего элемента И, выход которого соединен с первым входом первого элемента ШИ, выход которого соединен с первым входом второго элемента ИЛИ, вы ход которого соединен с первым входом етвертого элемента И, выход кото- рого соединен с вторым входом второг о и с первым входом тре-1ь г о элементов ИЛИ и через второй элемен НЕ с первым входом элемент з Н-ИЕ, выход которого соединен с третьим выходом узла, с первым входом пятого элемента И и через третий элемен НЕ с вторым входом третьего элемента ИЛИ, выход которого соединен с первым входом первого элемента ИПИ- НЕ и с ПЯТЫМ выходом узла, второй вход и вькод -первого элемента ИЛИ-Н соединены соответственно с четвертым входом и четвертым выходом узла восьмой вход которого соединен с третьим входом первого элемента ИПИ-НЕ и с первым входом шестого элемента И, выход которого соединен с BTOpbtti входом первого элемента ИЛИ, третий вход которого соединен с десятым входом узла, девятый вход которого соединен с вторыми входами первого, второго и третьего элементов И и с первым входом седьмого элемента И, выход которого соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с первым входом восьмого элемента И, выход которого соединен с вторым выходом узла и с вторым входо м четвертого элемента ИЛИ, третий и четвертый входы которого соединены с выходами соответственно первог и второго элементов И, шестой вход узла соединен с третьим входом второго элемента И и с первым входом второго элемента ИЛИ-НЕ, второй вход которого соединен с седьмым в:содом узла и с третьими входами первого и третьего элементов И, второй вход узла соединен с вторым входом седьмого элемента И, третий вход которого соединен с выходом второго элемента ИЯИ-НЕ, третий вход узла соединен с вторым входом пятого элемента И и через четвертый элемент НЕ с вторым входом шестого элемента И, выход пятого элемента И соединен с nepBbtM выходом блока и через пятый элемент НЕ с первым входом пятого элемента ИЛИ, выход которого соединен с вторыми входами

четпертогс) и Босьмог о лемонтон И, оди1П1адцатый иход узпа соединен с вторым входом пятого элемента ИЛИ и с вторым входом элемента И-НЕ, третий вход которого соединен с третьим входом восьмого элемента И и с пятым входом узла.

4. Устройство по п. 1, о т л и - чающее ся тем, что имитатор циклов блока памяти содержит элемент задержки, четыре элемента И, .четыре элемента ИЛИ и четыре элемента НЕ, причем, вход имитатора содинен с первым входом первого элемента ИЛР1, выход которого соединен первьм входом первого элемента И, второй вход первого элемента ИЛИ соединен с входом элемента задержки с выходом первого элемента И, с первыми входами второго элемента ИЛИ и третьего элемента ИЛИ, второй вход которого соединен с выходом второго элемента И, первый вход которого соединен с выходом третьего элемента ИЛИ и с входом первого элемента НЕ, выход которого соединен с вторым выходом имитатора и вторым входом второго элемента ИЛИ, выход которог соединен с вторым входом первого элемента И, третий вход которого соединен с выходом второго элемента НЕ, вход которого соединен с первым выходом элемента задержки,- второй выход которого соединен с входом третьего элемента НЕ, выход которог соединен с вторым входом второго элемента И, первый вход которого соединен с первыми входами третьего и четвертого элементов И, выход третьего элемен та И соединен с первым выходом имитатора, второй вход третьего элемента И соединен с выходом четвертого элемента НЕ, вход которого соединен с первым входом четвертого элемента ИЛИ и выходом четвертого элемента И, второй вход которого соединен с выхо- дом четвертого элемента ИЛИ, второй вход которого соединен с третьим выходом элемента задержки.

1

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

Цель изобретения - расширение класса решаемых задач,

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

Устройство (фиг. 1) содержит блок 1 памяти, блок 2 управления, счетчик 3 адресов считывания, счетчик А адресов записи, мультиплексор 5 адресов, реверсивный счетчик 6, дешифратор 7, выходной регистр 8 данных, входной мультиплексор 9 данных, узел 10 сравнения адресов, выходы 1 контроля состояния, очереди устройства, сигнальный вход 12 устройства,, входы 13 и 14 режима устройства, выходы 15 и 16 дешифратора 7, выход 17 элемента И группы блока 2, выходы 18-24 блока 2, выход 19 блока управления, выход 20 блока управления, выход 21 блока управления первую группу 25 информационных выходов устройства, первую группу 26 информационных входов устройства, выход 27 блока 2, выход 28 блока 2, регистр 29 указателей, мультиплексор 30 указателей, вторую группу 31 информационных выходов устройства, ре- гистр 32 указателей, выходы 33-35 блока 2, мультиплексор 36 указателей, регистр 37 указателей, регистр 38 указателей, вход 39 блока 2, выход 40 блока 2, выход 41 блока 2, выход 42 блока 2, вторая группа 43 информационных входов устройства, выходы 44-47 блока 2, вход 48 блока 2, выход 49 блока 2, восьмой вход 50 блока 2, узел 51 сравнения приори- тетов, входной регистр 52 данных, выходы 53 и 54 блока 2, входной ре- г истр 55 данных, выход 56 контроля

43г

готовности устройства, вход 5 задания типа очереди устройства, ьход , 58 задания типа очереди устройства, узел 59 сравнения признаков, регистр 60 состояния, выход 61 блока 2, выход 62 блока 2, вход 63 блока 2, входы 64 режима устройства, .вход 65 управления классом решаемых задач устройства, выход 66 контроля результата устройства, вход 67 блока 2.

Блок 2 (фиг. 2) содержит группу элементов И 68, триггеры 69, узел 70 формирования последовательности микрокоманд, узел 71 синхронизации, дешифратор 72, узел 73 управления запуском и завершением операций, группу входов 74 узла

70,вход 75 узла 73 управления, первый выход 76 узла 73, второй выход 77 узла 73, вход 78 узла 73, входы 79 и 80 узла 73, выход 81 узла 73, выходы 82 и 83 узла 71, вход 84 установки начального состояния узла 70, выход 85 узла 73, вход 86 узла 73, входы 87-89 узла 73, входы 90 и 91 узла 71,выход 92 узла

71,группы 93 и 94 выходов 70, вход 95 узла 73, соответственно одиннадцатый и десятый входы 96 и 97 узла 73, группы 98 и 99 выходов узла 70, входы 100-104 узла 71.

Узел 71 (фиг. 3) содержит элемент ИЛИ 105, элементы И 106 и 107, элементы ИЛИ 108, формирователь 109 импульсов, формирователь ПО импульсов, генератор 111 импульсов, элементы ИПИ-НЕ 112, имитатор 113 циклов блока памяти, элемент ИЛИ 114, элемент И 115, элемент НЕ 116, элемент 117 задержки, элементы И 118, элемент И-НЕ 119, элементы ИЛИ-НЕ 120, элемент ИЛИ 121.

Узел 73 (фиг. 4) содержит элемент И-НЕ 122, элемент ИЛИ 123, элемент ИЛИ-НЕ 124, элемент ИЛИ 125, элементы И 126, элемент ИЛИ-НЕ 127, элементы И 128, элементы ИЛИ 129, элементы НЕ 130.

Имитатор 113 (фиг. 5) содержит элемент задержки 131, элементы НЕ 132, элементы ИЛИ 133, -элементы И 134 и 135.

Блок I представляет собой модуль специализированного оперативного запоминающего устройства (СЗУ), построенный на больших интегральных схемах (БИС) (например, БИС ОЗУ

типа К565 РУ1А) с использованием при необходимости микросхем малой и средней интеграции (например, как это сделано в модуле ОЗУ-НЦОЗД), и предназначен для хранения (запоминания) элементов и структуры очередей а также для записи (включения в очередь), считывания (исключения из очереди) элементов очередей.

Блок 1 работает следующим образом.

В исходном состоянии на управляющих входах блока 1 устанавливается нулевой код (например, код 00). В блоке 1 предусматривается запуск двух основных операций: операции записи и считывания. При операции записи на адресных входах устанавливается код адреса ячейки памяти, в которой предполагается запомнить информацию (элемент очереди), код которой устанавливается на информационных входах. Через время, равное времени установки кодов адреса и информации на соответствующих входах, на управляющих входах формируется код записи (например, код 11), под действием которого коды адреса и информации запоминаются во внутренних регистрах блока 1, запускается операция записи.

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

051434

Блок 2 управления (фиг. 2) пред- назначен для формирования соответствующих управляющих сигналов для блока 1, мультиплексоров и счетчиков и 5 синхросигналов для счетчиков и регистров .

Узел 70 формирования последовательности микрокоманд предназнат чен для формирования определенной

10 последовательности кодов-микрокоманд на выходах четырех групп выходов в зависимости от определенного кода, установленного на входах 74 узла 70. Коды микрокоманд формиру15 ются на тридцати трех выходах

узла 7П. В узле 70 необходимо предусмотреть аппаратные средства для хранения не менее чем 57-ми 42-битных микрокоманд. Девять бит микро20 команд используется для организации внутренних связей между микрокомандами, В качестве запоминающей среды используется программируемая логическая матрица (Ш1М). Структурная

25 схема узла 70 аналогична структурной схеме БИС УП типа К1883РТ1. Коды микрокоманд, хранимых в узле 70, и структура их связей определяются алгоритмами функционирования устQ ройства, которые описаны при описании работы устройства.

Узел 70. работает следующим образом. В исходном состояниии на всех выходах узла 70 устанавливается ло5 гический ноль независимо от кода на входах 74. При формировании первого импульса синхронизации на входе 83 синхронизации, на выходах узла 70 устанавливается(через опреде0 ленное время)код первой микрокоманды микропрограммы, соответствующей коду, установленному на входах 74, Каждый новый код-микрокоманда формируется на выходах у зла 70 после

5 появления на входе 83 синхронизации очередного импульса синхронизации. На выходах узла 70 формируются коды микрокоманд, каждая из которых условно разбита на четыре внешних

0 управляющих поля в соответствии с группами выходов узла 70, Группе 93 выходов узла 70 соответствует поле управления запуском регистров, счетчиков и блока 1; группе 94

5 выходов узла 70 - поле управления мультиплексорами и режимами функционирования счетчиков; группе 98 вы- , ходов узла 70 - поле управления за

5. 12

вершением операций, а группе 99 выходов - поле управления синхронизацией и циклами. Длина (р битах) каждого поля микрокоманды определяется количеством выходов соответству ющей группы выходов узла 70 (фиг. 2). Если на выходах узла 70 устанавливается последняя микрокоманда микропрограммы, то на выходах 96 и 97 устанавливается соответствующий код Конец операции (КО), под действием которого обеспечивается перевод узла 70 в исходное состояние, путем формирования на входе 84 установки начального состояния узла 70 высо- кого уровня напряжения после окончания действия импульса синхронизации на входе 83 и блокировка формирования последующего импульса синхронизации на входе.83. При подаче сигнала (логической единицы) на вход 84 установки начального состояния узла 70 всегда обеспечивается перевод его в исходное состояние. Если микрокоманда, установленная на выходах узла 70, не является последней, то через определенное время, не меньшее времени цикла функционирования блока 70, на его выходах может быть установлена следующая микрокоманда выполняемой микропрограммы под действием следующего импульса синхронизации на входе 83, причем какая микропрограмма выбирается для выполнения определяется кодом на входах 74 узла 70. При из- менении кода на входах 74 в определенный момент формирования последовательности кодов микрокоманд после окончания действия предшествующего импульса синхронизации в момент дей- ствия очередного импульса синхронизации обеспечивается изменение последовательности формирования кодов- микрокоманд на выходах узла 70, если это предусмотрено алгоритмом функционирования. Поэтому входы 74, соединенйые с входами 39 и 48 блока 2, выполняют функцию входов условных переходов. При установлении нового кода на входах 74 узла 70 и начального состояния узла 70 обеспечивается готовность узла: 70 для формирования последовательности кодов микрокоманд новой микропрограммы В случае, если очередной синхроим- пульс на входе 83 не формируется, то установленный на выходах узла 70 код микрокоманды удерживается неограни-

0

5

1

s 0 5 0 5 0 5 0 5

43 .6

чённо долго, если отсутствует сигнал на входе 84.

Входы 74 узла 70 можно условно разбить на две группы: первую группу входов начальных адресов микропрограммы и вторую группу входов условных переходов, В первую группу входов входят входы 74, соединенные с выходами узла 72, кроме входа, соединенного с входом 91 узла 71. Во вторую группу входов входят входы 74, соединенные с входом 91 узла 71

и с входами 39 и 48 блока 2. I

Микрокоманда, используемая в узле 70, разбивается на две группы полей: группу полей внешнего управления и группу полей организации связей между микрокомандами. Группа полей в организации связей ме;аду микрокомандами состоит из двух полей: поля управления (ПУ) и поля следующего адреса (ПСА). Поле ПУ представляется не менее, чем тремя битами (разрядами), а поле ПСА - не менее, чем шестью битами (разрядами) . В поле управления задаются коды, разрешающие или запрещающие использование кода на второй группе входов узла 70 для формирования адреса следующей микрокоманды, которое осуществляется.при подаче сигнала на вход 83 узла 70 при нулевом уровне напряжения на входе 84 узла 70. Код с входов первой группы входов узла 70 и код поля следующего удреса всегда используются для формирования адреса любой следующей микрокоманды. Так как код на входах первой группы входов узла 70 и на соответствующих выходах узла 72 остается неизменным в течение всего времени вьшолнения одной микрокоманды, кодирующей алгоритм вьшолнения одной операции, то этот код является одинаковым для всех микрокоманд одной микропрограммы. Указанный код используется как старшая часть (разряды) адреса микрокоманды микропрограммы. Формирование последовательности кодов микрокоманд осуществляется благодаря заданию последовательности кодов адресов в поле ПСА каждой микрокоманды, которые являются разными в разных микрокомандах и используются как младшая часть (разряды) адреса текущей ми- крокоманды. Код на второй группе входов узла 70 используется для

7

формирования средней части адреса (битов адреса между старшей и младшей частями адреса). В случае, если условные переходы отсутствуют в микрокоманде, код средней частоты адреса равен исходному (например нулевому). В предлагаемом устройстве при любом ветвлении последовательности микрокоманд учитывается только одно условие, т.е. наличие сигнала только на одном из трех входов второй группы входов узла 70, При этом возможно, что при анализе одного и того же условия, например, наличия сигнала на входе 39, на выходе 48 сигнал может присутствовать или не присутствовать. В этих случаях для одного и того же условия могут формироваться два различных адреса одной и той же первой микро- команды обоих ветвей (последовательностей микрокоманд) условного перехода. В этом случае кодирование последовательностей микрокоманд оставшейся части микропрограммы дубли- руется в управляющей памяти. Это не влияет на эффективность использовани управляющей памяти в предлагаемом

устройстве.

Приведем подробный алгоритм функционирования узла 70 формирования последовательности микрокоманд. В исходное состояние узел 70 переводится при установке на входе 84 высокого уровня напряжения. При этом иа выходах групп 98,99, 93 и 94 выходов узла 70 устанавливается исходный код, который может быть нулевым. При этом на входах 74 может быть установлен произвольный код. Любое состоя- ние (в том числе и исходное) узла 70 не изменяется при изменении состояния входа 83 при установке (удержании) на входе 84 узла 70 высокого уровня напряжения. При отсутствии (снятии) высокого уровня напряжения с входа 84 и отсутствии сигнала на входе 83 узел 70 остается в исходном состоянии или в состоянии, установленном при подаче последнего сигнала на вход 83 произвольно долго. Под состоянием узла 70 в данном случае понимается состояние выходов групп 93, 94, 98 и 99 выходов узла 70. При этом состояния входов 74 узла 70 могут произвольно изменяться. При наличии на входе 84 логического нуля и подаче на вход 83 узла 70 сиг

8

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

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

ожидаемым, определяется типом выполняемой операции (микропрограммы) и типом микрооперации. Если микро9

команда является первой в микропро- грамме, то в качестве кодов средней и младшей частей кодов адреса микрокоманды используются исходные (нулевые) коды. По сформированному адресу новой микрокоманды в узле 70 осуществляется выбор кода новой микрокоманды и установка его на выходах 93, 94, 98 и 99 (с запоминанием во внутренних регистрах узла 70), При этом запоминаются коды полей ПУ и ПСА микрокоманды, после чего сразу же аппаратными средствами в узле 70 начинается анализ кода поля управления новой микрокоманды и фор- мирование внутренних управляющих сигналов в узле 70, обеспечивающих при появлении нового сигнала на входе 83 использование в качестве средней части кода адреса последующей микрокоманды кода, установленного на входах второй группы входов узла 70 или кода средней части кода адреса текущей микрокоманды (в зависимости от кода, .установленного в поле управления микрокоманды) . С появлением нового сигнала на входе 83 узла 70 описанный алгоритм функционирования узла повторяется, При появлении сигнала на входе 83, обеспечивающего смену кода микрокоманды на выходах узла 70, установка высокого уровня напряжения на входе 84, переводящего узел 70 в исходное состояние, предотвращается вплоть до выборки и исполнения текущей микрокоманды. Смена кода на входах 74 узла 70, соединенных с вьгхода ми узла 72, кроме входа, соединенного с входом 91 узла 71, возможна только с переводом узла 70 в исходное состояние, так как установка нового кода на указанных выходах узла 72 возможна только при установке логического нуля на выходе 85 узла 7 73, что неотвратимо ведет к установке на входе 84 узла 70 высокого уровня напряжения.

Узел 71 синхронизации предназначен для формирования импульсов синх низации для других узлов блока 2 и на соответствующих выходах блока 2 через элементы И 68 - управляющих сигналов запуска блока 1 через триггеры 69, а также для управления циклами, т.е. управления многократ- HiiiM повторением управляющих сигнало и синхросигналов под действием одно

4310

и той же микрокоманды без пов : орно- го формирования кода микрокоманды на выходах узла 70,

Имитатор 113 предназначен для формирования управляющего сигнала для запуска блока 1 и отслеживания момента готовности операций в блоке 1 после его запуска, т.е. имитирует цикл обращения блока 1.

Имитатор 113 работает следующим образом.

В исходном состоянии на входе имитатора и первом выходе устанавливается логический ноль, а на втором выходе - логическая единица. Запуск имитатора осуществляется при необходимости запуска блока путем подачи на вход сигнала (логической единицы). Через время, равное времени включения имитатора, на первом выходе имитатора формируется сигнал (логическая единица) для управления запуском блока 1. На втором выходе имитатора устанавливается логический ноль, означающий, что в блоке 1 запущена операция, и блок не может быть использован для запуска новой операции. Сигнал запуска имитатора с входа имитатора поступает через первый элемент ИЛИ 133 и И 134 на вход 13 элемента задержки. Затем появляется сигнал на первом выходе элемента 131 задержки, Этот сигнал через элемент НЕ 132 блокирует элемент И 134, на выходе которого устанавливается логический ноль, который через второй элемент ИЛИ 133 распространяется на второй вход первого элемента И 134, окончательно предотвращая его включение независимо от времени сохранения сигнала запуска на входе имитатора. В результате через элемент 131 задержки распространяется импульс. На втором выходе элемента 131 появляется сигнал (высокий уровень напряжения), обеспечивающий установку нулевого уровня напряжения на первом выходе имитатора,

Узел 71 синхронизации работает следующим образом,

В исходном состоянии запуск узла осуществляется при установке логического нуля на входе 81, Генератор 111 импульсов начинает генерировать последовательность импульсов, в соответствии с которой формирователь 110 импульсов форми11

рует последовательность импульсов синхронизации на выходе 83 узла 71, Всякий раз импульс с выхода генератора 1 I I подается на третий выход 80 узла 71 и используется как управляю- цщй сигнал для узла 73.

В каждый такт работы, определяемый промежутком времени между моментами появления импульсов от выхода генератора 111, узел 71 может функционировать в одном из пяти режимов: режиме синхронизации без запуска блока 1 (71Р| ); режиме синхронизации перед запуском блока 1 (71Р); режиме синхронизации после запуска блока 1 (71Р); режиме управления циклами при поиске по приоритету (71Р); режиме управления циклами при поиске по признакам и при просмотре (71Pj).

Определенньм режим задается соответствующим кодом управляющих сигналов группы 99 выходов узла 70, т.е. режим функционирования узла 71 задается полем управления синхронизацией и циклами микрокоманды.

Рассмотрим более подробно особенности функционирования узла 71 в каждом режиме.

При режиме 7IP, на входах устанавливается код 01000, После окончания действия импульсов на выходе генератора 111 на выходе элемента НЕ 116 устанавливается высокий уровень напряжения, в результате чего включается элемент И 118. Высокий уровень напряжения с выхода элемента И 118 распространяется через элемент И 107 и элемент ИЛИ 108 и запускает формирователь 109 импульсов, На выходе 92 формируется импульс синхронизации, который, проходя через открытые элементы И 68 блока управления, обеспечивает переключения соответствующих регистров и счетчиков устройства. Одновременно высокий уровень напряжения появляется на выходе 78, используемый для синхронизации узла 73 при определенных режимах его функционирования. Другие выходы узла при этом остаются без изменений до смены кода микрокоманды, происходящей с появлением очередного импульса на выходе генератора 111 и формирователя 110 и на выходе 83 узла 71,

При режиме 7IP входах устанавливается код 11000. После окон10

15

20

25

0514312

чаиия действия импульса на выходе генератора 111 на выходе 92 узла 71 формируется импульс синхронизации аналогично тому, как это осуществля- ется при режиме 71Р . Одновременно через определенный промежуток времени, достаточный, чтобы после действия импульса синхронизации к моменту запуска блока I в устройстве прекратились переходные процессы, включая и время установки адреса и данных на соответствующих .входах блока I, запускается имитатор 113, Необходимая задержка запуска блока I обеспечивается задержкой запускающего сигнала элементом 117 задержки, элементом ИЛИ 108, элементом И 115 и задержкой включения имитатора 113, После запуска имитатора 113 на выходе 82 узла 71 появляется высокий уровень напряжения, который устанавливает на управляющих входах 22 код запускаемой операции блока 1 с помощью триггеров 69 блока 2,

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

Работа узла 71 в других режимах происходит аналогично, но на его входах формируются другие коды.

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

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

В исходном состоянии на входах 75,95,78,80,87,88,89 и 97 и на выходах 77, 85 устанавливается логи- 55 ческий ноль, на выходах 76,81 и 84 и на входе 79 - логическая единица. Запускается узел 73 при установке .на входах 75 и 86 логической единицы,

30

35

40

45

13

При этом на выходе элемента И-НЕ 22, выходе 81 узла и через элемент И 126 на выходе 77 узла устанавливается логический ноль. Логический ноль на выходе 81 узла 73 обеспечивает запуск узла 71. Логический ноль, установившись на выходе 76, устанавливается одновременно и на выходе 56 устройства, информируя внешнюю систему, в которой используется устройство о том, что операци в устройстве запущена. При этом с помощью элементов НЕ 130 и Ш1И 1 29 на выходе 85 узла устанавливается логическая единица, обеспечивая формирование управляющего .кода на выходе узла, а на выходе 84 - логический нооТь. После, установки на выходе 85 логической единицы и формиро вания определенного кода на выходах дешифратора 72 на входах 87-89 может установиться логическая единица. 1 .

Если логическая единица установилась на входе 89, то на выходе 84 через элемент ИЛИ-НЕ 127 устанавливается логический ноль, который удерживается в течение времени, пока на входе 89 держится логическая единица благодаря чему предотвращается установка узла 70 в исходное состояние. При этом, когда на входе 79 узла 73 устанавливается логический ноль, на первом входе элемента И 128 устанавливается логическая единица, на втором входе которого уже установлена логическая единица с входа 89 узла. На выходе элемента И 128 устанавливается логическая единица, под действием которой через элемент 125 и с помощью элемента И 126, элементов ИЛИ 129 и НЕ 116 на выходе элемента И-НЕ 122 и выходе 81 узла устанавливается логическая единица. Появление логической единицы на выходе 81 узла обеспечивает блокировку функционирования узла 71 и, следовательно, всего устройства. При этом на выходе 85 узла 73 удерживается логическая единица. Когда блок 1 готов к новому запуску, на входе 75 узла 73 устанавливается логическая единица, благодаря чему на выходе 81 узла 73 также устанавливается логическая единица, означающая, что можно осуществлять перезапуск логической единицы на входе 75 узла 73. Перезапуск логической единицы на входе 75 осуществляется установкой на

25

05143- 14 ,

входе 75 логического нуля на ,)смя, не меньшее времени, необходим го для установки на выходе 85 узла 73 логического нуля и приведения узла

5 70 в исходное состояние под действием логической единицы, после установ-. ки ее на выходе 84 узла 73, после чего на входе 75 узла 73 вновдз устанавливается логическая единица, Пос10 ле перезапуска логической еди.ггицы на входе 75 узла 73 описанные пе|)еключе- ния элементов узла повторяются. - Когда операция Просмотреть очередь должна быть эаверщена, на выходах уз15 ла 70 формируется код соответ твую- щей микрокоманды, в котором ня, двух выходах третьей группы выходе--i узла 70 и на входах 96 и 97 узла .5 устанавливается логическая единица.

20 Попытка перезапуска логич1: хой единицы на входе 75 узла 73 смены кода на выходах дешифратора 72 приводит лишь к повторению последней (завершающей) микрокоманд ло

Если логическая единица устанав- ливается на входе 87 узла 73, то через элемент ИЛИ-НЕ 124 блокируется первый элемент И 126, а второй элемент И 126 подготавливаетск для включения. При этом в процессе выполнения операции Найти элемент данных в очереди по признаку чри обнар-ужении требуемого элемента данных (элемента, код которого

35 содер :(ит требуемый код-признар:) на входе 92 узла устанавливается логическая единица, а при установке кода следующей (последней) микрокоманды на входах 95 и 96 узла 73 устанавливается единица, в результате чего включается элемент И 126, и через элемент ИЛИ 123 и третий элемент И 126 на втором выходе 77 узла 73 устанавливается единица, инфсрмируя внешнюю систему о успешном выполнении операции. Одновременно под действием логической единицы на входе 96 через элементы ИЛИ 125 и 129, четвертый элемент И 126,

50 элемент НЕ 116,, элемент И-НЕ 122 и элемент И 128 на выходе 76 узла при единице на входе 79 устанавливается логическая единт1,а, информирующая внешнюю систему через

55 выход 56 устройства о том, что устройство готово для нового запуска. После появления логической единицы на выходе 76 узла 73 на входе

30

40

45

13

75 устанавливается логический ноль, если не требуется выполнения новой операции, В результате узел 73 приводится 1в исходное состояние. Если, нри вынолненнни онерации Найти элемент данных в очереди по признаку, требуемый элемент данных содержащий нризнак-код не обнаружен, то на входе 95 логическая единица не устанавливается, а после просмотра всех элементов данных устанавливается код последней микрокоманды, такой же, как и в случае обнаружения элемента данных. Однако в этом случае на выходе 76 узла 73 удерживается логический ноль котор ж после появления логической единиды на выходе 77 узла 73 означает, что операция завершена, но требуемый элемент данных не найден.

Завершение функционирования узла 73 осуществляется всегда при установке на входе 96 логической единицы при выполнении последней микрокоманды и при установке на входе 79 логической единицы. В этом случае на выходе 76 узла устанавливается логическая единица. При этом на выходе 8 удерживается логическая единица, а н выходе 84 - логический ноль. В исходное состояние узел 73 переводится при установке на входе 76 логического нуля.

Блок 2 управления (фиг. 2) работает следующим образом.

В исходное состояние блок 2 управления устанавливается при установке в исходное состояние всего устройства и усех узлов блока 2. При этом на всех входах и выходах блока 2, кроме выхода 56 и входов блока 2, соединенных с входами дешифратора 72 устанавливается логический ноль. Состояния входов блока 2, соединенных с входами дешифратора 72, могут быть произвольными. На выходе 56 блока 2 устанавливается логическая единица. Перед запуском блока 2 на входах 65, 57, 58, 63, 13, 14, 17 и 16 устанавливается комбинация кодов, задающая класс решаемых задач тип очереди, вид операции над элементами данных, состояние очереди. При этом на входе 86 узла 73 может установиться, логическая единица, означа ющая, что разрешен запуск блока 2 и выполнение задаваемой на входах 63, 13 и- 14 операции над элемен

ю )5 0

5 0

0

5

5

тами u;ii;iib.x, или удерживаться логи- чески ногь 5 означающий, что выполнение заданной операции запрещено. Запуск блока 2 осуществляется путем усугановки на первом входе блока логической единицы. При этом, если на вькоде 86 дещифратора 72 удерживается логический ноль, то запуска не происходит, и состояние выходов узлов и блока не изменяется. Если на выходе 86 установилась логическая единица, то осуществляется запуск блока 2, При этом вначале запускается узел 73, На выходе 85 узла 73 устанавливается логическая единица, подаваемая на вход дещифратора 72 и обеспечивающая формирование управляющего кода на выходах дешифратора, а на выходе 81 узла 73 устанавливается логичес- кий ноль, подаваемый на вход узла 71 и обеспечивающий запуск узла 71, На выходе 66 узла 73 устанавливаемся при этом логический ноль, подаваемый на выход 66 блока 2 и означающий, что блок управления запущен. Па выходе 84 узла 73 устанавливается логический ноль, разрешающий запуск узла 70, После за- иу.ско узла 71 на выходе 83 узла 71 . появляется первый импульс синхронизации, запускающий узел 70. На выходах узла 70 формируется (через время, равное циклу работы узла 70) код первой микрокоманды микропрог- раммы, начальный адрес которой задается кодом на входах 74, который состоит из управляющего кода, установленного на входах 74, соединенных- с выходами дешифратора 72 и нулевым кодом, установленным на входах 74, соединенных с входами 39 и 48 блока 2. В зависимости от кодов микрокоманды, сформировавшихся на выходах 98 и 99 групп выходов узла 70, задается соответствующий режим функционирования соответственно узла 73 и 71 через входы 96, 97 узла 73 и входы 100-I04 узла 71. Режим функционирования узла 73 задается управляющими сигналами с соответствующих выходов дешифратора 72 через входы 87-89 узла -73, на которых уста- ,чавливается логическая единица при коде задаваемой операции на входах 63, 12 и 14 дешифратора 72 и управляющим сигналом с входа 67 блока 2. I

Возможны два режима формирования

управляющих сигналов блока 2.

17

При первом режиме на выходах группы 93 узла 70 после формирования кода микрокоманды устанавливается код, логическая единица каждого разряда которого обеспечивает включение того логического элемента И 68, выход которого соединен с выходом еЗло- ка управления, на котором предусматривается появление импульса синхронизации Или счетного импульса для счетчиков устройства в рассматриваемом такте блока 2, под которым понимается промежуток времени между моментами появления импульсов синхронизации на выходе 92 узла 71. При этом импульс синхронизации на выходе 92 и, следовательно, на соответствующих выходах блока 2 управления 17, I9i 23, 24, 33, 40, 41, 42, 47, 49, 53, 54, 61 и 62, по- является с задержкой относительно момента появления кода микрокоманды на выходах узла 70 и, следовательно, кода на выходах группы 94 выходов узла 70 и на выходах 18, 20, 21, 27, 28, 34, 35, 44, 45 и 46 узла 2, равной переходным процессам в мультиплексорах и счетчиках устройства, вызванных действием управляющих сигналов с выходов блока 2, соединенных с выходами группы 94 выходов узла 70. Затем через время, равное времени установки удреса и данных на соответствующих входах блока 1, на выходах 22 блока 2 может сформироваться запускающий код для блока 1, соответствующий определенной операции в блоке 1, если это пре дусмотрено микрокомандой. Код опре- деленной операции для блока 1 зада- ется с двух выходов группы 93 выходов узла 70 через триггеры 69 и, следовательно, выходы 22 блока 2 под действием логической единицы с

выхода 82 узла 71.

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

4318

73, на выходах 22 блока 2 формируется управляющий код для запуска блока 1 | вследствие формирования логической единицы на выходе 82 узла 71. Затем через время, равное времени завершения операции считывания в блоке 1, но не меньщее времени удержания управляющих сигналов на управляющих выхо- . дах 22 блока 2 и соответствующих управляющих входах блока 1, при кото- . ром обеспечивается нормальное завер- щение операции в блоке 1, т.е. после установки на выходах 22 нулевого кода на соответствующих выходах блока 2 из выходов блока управления, соединенных с выходами элементов И 68, формируются управляющие импульсы синхрониза- или под действием импульса синхронизации, появляющегося на выходе 92 узла 71. Каждый раз при появлении импульса синхронизации на выходе 83 узла 7 на выходе 80-узла 71 появляется логическая единица на время, пока не будет заменен код .микрокоманды на выходах узла 70, благодар чему на выходе 84 узла 73 удерживает- ся логический ноль и предотвращается преждевременньй (не предусмотренный алгоритмом функционирования блока 2) перевод узла 70 в исходное состояние. При появлении следующего импульса синхронизации на выходе 83 узла 71 осуществляется (через время, равное циклу работы узла 70) установка на выходах узла 70 кода новой микрокоманды, которая вновь задает один из двух описанных режи мов формирования управляющих сигналов блока 2. При этом режим формирования управляющих сигналов блока 2 может непрерывно повторяться без формирования импульса синхронизации на выходе 83 узла 71. Это имеет место, когда в узле 71 устанавливается режим 71Р и 71. В этом случае последовательное формирование управляющего сигнала на выходах 22 блока 2 и импульсов синхронизации на соответствующих выходах блока 2, соединенных с выходами элементов 68. многократно повторяется при одном и том же коде микрокоманды на выходах узла 70 до тех пор, пока не произойдет формирование импульса синхронизации на выходе 83 узла 71 и смена кода микрокоманды на выходах узла 70, Импульс синхронизации на выходе 83 узла 71 появля19 . Ется ТОЛЬКО при появлении логической единицы на входе 50 блока 2, когда узел 71 находится в режиме 71Р или когда узел 71 находится в режиме 71Ру, или при появлении логической единицы на входах 90 и 92 узла 71, когда узел 71 находится в режиме 71Pj , а на выходах дешифратора 72 устанавливается соответствующий код. При этом формирование .импульса синхронизации на выходе 83 узла 71 осуществляется после перезапуска логической единицы на входе 12 блока 2, При установке комбинации логических единиц на входах 74, соединенных входами 39 и 48 блока 2, обеспечивается формирование новых трех последовательностей кодов микрокоманд дпя одних и тех же определенных микропрограмм.

Первый режим формирования упр ав- ляющих. сигналов блока 2 устанавли7 вается при режимах функционирования 71Р, , 71 Pj узла 71 . Второй режим формирования управляющих сигналов блока 2 устанавливается при режимах функционирования 71Pj, 71P, 71Р5. узла 71. Управляющими сигналами с выходов группы 98 выходов узла 70, с входов 96 и 97 узла 73 обеспечи, вается управление установкой логической единицы на выходах 66 и 56 блока 2 через выходы соответственно 76 и 77 узла 73. Логическая единица на выходе 66 блока 2 устанавливается в определенные моменты вьшолне- ния операций над элементами данных в устройстве, оговоренные при описании узла 73, и отражает этап или результаты выполнения операций в устройстве. В большинстве случаев логическая единица на выходе 66 блок 2 устанавливается при установке логической единицы на входе 97 узла 73 и выходе 78 узла 71. В остальных случаях установка логической единицы на выходе 66 блока 2 осуществляется при установке логической единицы на выходе 17 блока 2, входе 96 узла 73. На выходе 56 устанавливается логическая единица при установке на выходах узла 7 кода последней микрокоманды микропрограммы, под управлением которой реализуется алгоритм функционировани блока управления и устройства при запуске в устройстве любой операции 1над элементами данных. Установка логической единицы-на выходе 56 блок

0514320

2 означает, что операция, заданная на входах 63, 13 и 14 блока 2, выполнена, и устройство готово для запуска новой операции, код которой можно

5 заранее установить на входах 63, 13 и 14 блока 2 после запуска предыдущей операции. Запуск новой операции осуществляется путем перезапуска логической единицы на входе 12 блока 2.

10 При этом после установки на входе 12 блока 2 логической единицы блок 2 управления переводится в исходное состояние. При этом состояния входов 57,58 и 65 должны сохраняться в те15 чение всего времени после включения и начала функционирования устройства. При изменении состояний указанных входов блока 2 осуществляется перевод блока 2 и всего устройства в ис20 ходное состояние путем формирования общего импульса сброса на общей шине сброса (не показана).

Счетчик 3 адресов считывания предназначен для формирования и хране25 ния кодов адресов блока 1, в которых записан и хранится первый элемент данных в очереди, и представляет . собой реверсивный счетчик с возможностью занесения кода информации с

2Q установочных информационных входов под действием соответствующего управляющего сигнала.

Мультиплексор 5 предназначен для подключения к адресным входам -блока

5 1 и входам соответствующих групп входов мультиплексоров 30 и 36 выходов или счетчика 3, или счетчика 4, или регистра 29, или регистра 32 в зависимости от установленного на

0 управляющих входах мультиплексора 5

управляющего кода.

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

Выходной регистр 8 данных, также как и первый 52 и второй 55 входные регистры данных, предназначен для

5 приема, хранения и передачи кодов элементов данных.

Входной мультиплексор 9 данных предназначен для подключения входов

21

первой группы 26 входов устройства или выходов первого входного регистра 52 дапных, или выходов регистра 8 данных к входам второго входного регистра данных в зависимости от кода, установленного на управляющих входах мультиплексора,

Узел 10 сравнепия адресов предназначен для сравнения кода адресов с выходов счетчика 3 и регистра 37 и формирования управляющего сигнала логической единицы на выходе при совпадении кодов на группах входов.

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

Первьй вход 12 у(тройства предназначен для запуска или перезапуска блока управления и устройства.

В исходном состоянии на входе 2 устанавливается логический ноль. При установке на входе 12 логической единицы может произойти запуск устройства.

Второй вход 13 устройства и вход 14 устройства являются вместе с входом 63 входами 64 задания вида операции над элементами данных в очереди

Группа 25 информационных выходов устройства предназначена для формирования кодов выводимых злементов данных.

Группа 26 информационных входов устройства предназначена для установки кодов вводимых в очередь эле- ментов данных, а также установки на .определенных входах группы кода- признака при выводе и поиске элементов данных по признаку.

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

Мультиплексор 30 и мультиплексор 36 предназначены для подключения соответствующих источников кодов информации к входам регистров соот

0

5

о

Q

0

5

5

14322

ветственно 32 и 37 с целью формирования требуемого кода указателя элементов данных очереди при вводе или выводе элементов данных из очереди. Код указателя в данном случае представляет .собой код адреса определенной ячейки блока 1..

Группа 31 информационных выходов устройства предназначена для формирования кодов вьшодимых элементов данных вместе с первой группой 25 выходов при использовании устройства для решения задач буферизации элементов данных в виде очередей. В других случаях группа 31 выходов не используется.

Группа .43 входов устройства предназначена для установки кодов, вводимых в очередь элементов данных вместе с группой 26 входов при использовании устройства для решения задач буферизации элементов данных в виде очередей. В других случаях использования устройства группа 43 входов не используется,,

Узел 51 сравнения приоритетов предназначен для сравнения кодов приоритетов элементов данных-, выводимых из очереди на выходы группы 25 выходов устройства и элементов данных, вводимых в очередь через группу 26 входов устройства и запоминаемых в регистре 52 данных,

Узел 59 сравнения признаков предназначен .для сравнения кода признака элемента данных, код которого ,установлен на выходах регистра 8 и кода признака, установленного на определенной группе выходов ре- - гистра 52.

Входы 57 и 58 задания типа очереди предназначены для задания типа очереди, организуемой с помощью устройства.

Регистр 60 состояния предназначен для временного хранения кода количества элементов очереди, формируемого счетчиком 6 при проведении поиска элемента в очереди.

Вход 65 управления классом решаемых задач предназначен для настройки устройства на решение определенного класса задач.

Выход 66 контроля результата устройства предназначен для информирования внешней системы, в которой уст-, ройство используется, о результатах

23

выполнения операций в устройстве и для фиксирования определенного момента выполнения операций в устройстве путем установки на выходе 66 логической единицы.

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

В начальное исходное состояние после включения устройство переводится путем формирования на общей :шине сброса (не показана) импульса сброса, переводящего все регистры, счетчики, узлы и блоки устройства в исходное состояние. При этом на всех управляющих входах устройства устанавливается логический ноль. После сброса на выходах 11 контроля состояния очереди должен установиться код, на выходе 56 контроля готовности устройства должна устано диться логическая единица, а на выходе.66 контроля результата устанавливается логический ноль, означащие, что устройство готово для запуска и использования. Заренее опре деляется класс решаемых задач и тип очереди, для организации которой . предлагается использовать устройств после чего на входе 65 задания класса решаемых задач устанавливается соответствующий код класса решаемых задач, на выходах 57 и 58 устанавливается соответствующий код типа очереди. Установленные коды должны схраняться в течение всего времени использования устройства по выбранному назначению. При любом изменении указанных кодов, а также при установке кода на выходе 17 и входе 16 блока 2 после завершения очередной операции в устройстве вновь формируется импульс сброса, и устройство переводится в рабочее исходное состояние, при котором на входах 57, 58 и 65, а также на вхо- дах 64 может быть установлен произ- вольный код. Код операции над элементами данных в устройстве задается на входах 64. Первой операцией над элементами данных может быть только операция ввода первого (нового) элемента данных в очередь.

После установки кода элемента данных на входах 26 и 43 и кода типа операции.на входах 64 устройства через время, равное переходным процессам, в блоке управления на входе 12 устанавливается логическая

143

24

5

0 5 0 5 о „ ,

5

0

5

единица, запускающая устройство для выполнения заданной операции. После запуска устройства, если операция , принята к выполнению, на выходе 56 контроля готовности устройства устанавливается логический ноль, который в сочетании с логической единицей на входе 12 устройства означает, что устройство запущено для выполнения операции над элементами данных. Через определенное время, определяемое сложностью алгоритма вьшолнения операции, на выходах 56 и 66 устройства устанавливается логическая единица, означающая, что операция успешно завершена, и устройство готово для выполнения новой операции над элементами данных очереди. При этом на выходе 66 логическая единица может появиться раньше, чем на выходе 56, что определяется алгоритмом выполнения и видом операции. После того, как бып осуществлен запуск устройства, и на выходе 56 установился логический ноль, на входах 64 может быть заранее установлен код новой (следующей) операции, без нарушения выполнения предшествующей операции .

После установки логической единицы на выходе 66 устройства на входах 26 и 43 может быть установлен код нового элемента данных. О ередная операция может б.ыть запущена и устройстве только после установки на выходе 56 логической единицы. При этом перезапуск устройства осуществляется путем установки на входе 12 логического нуля на время, не меньшее времени перевода блока 2 управления в исходное состояние, с последующей установкой на входе 12 логической единицы. Если при этом запускается операция вывода элемента данных из очереди, то в момент установки кода выводимого элемента данных на выходах 25 и 31 на выходе 66 устанавливается логическая единица. При этом во всех случаях, когда элементы данных очереди выво- .дятся из очереди, коды этих элементов устанавливаются на выходах 25 и 31. При этом момент установки ко- доз на выходах 25 и 31 отмечается установкой на выходе 66 логической единицы.

I В устройстве реализуется несколько алгоритмов функционирования

iF соответствии с количеством разрешенных кодов на входах 57 и 58, 65 и 64 устройства. Каждый алгоритм представляет собой последовательность микроалгоритмов, каждый из ко- торых выполняется за один такт устройства. Под тактом устройства понимается промежуток времени между моментами появления импульсов синхронизации на выходах блока 2 управ- пения, соединенных с выходами элементов И 68 блока 2, Каждый алгоритм кодируется микропрограммой, хранимой в узле 70 блока 2 или определенной последовательностью микро- команд микропрограммы, кодирующей несколько алгоритмов. Каждый микроалгоритм кодируется кодом одной микрокоманды. Кодом каждой микрокоманды кодируется также и связь каж- дои предыдущей микрокоманды следовательно, микроапгоритмов) с последующей, а также и возможное изменение этих связей в требуемый момент. При каждом алгоритме функцио- нирования в устройстве обеспечивается выполнение определенной операции .над элементами данных при заданном классе решаемых задач и типе, организуемой очереди в соответствии с pea- лизуемым способом организации очереди.

В устройстве реализуется следующий способ организации очередей элементов данных. Очереди элементов данных типа первый вошел - первый вышел (FIFO) или стека, когда реализуется принцип последний вошел - первый вьшел (LIFO), при решении задач буферизации организуются путем построения списка элементов данных в блоке 1, элементы которого упорядочиваются соответствующим образом благодаря записи их в последовательно расположенных соседних ячейках блока 1, причем адрес ячейки, в которой хранится первый элемент, и адрес ячейки, в которой хранится последующий элемент списка, формируется и хранится в счетчиках 3 и 4 При этом свободные ячейки блока 1 учитываются как ячейки, адреса которых находятся между адресом перво элемента и последнего в сторону возрастания двоичных кодов адресов. Приоритетные очереди элементов данных, когда реализуется принцип входят в произвольном порядке

5 0 5 0

5 5 0

5

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

для вводав очередьи типа очередей. I

Для приоритетных очередей элементы списка упорядочивс1ются в соответствии с номером приоритета, код которого содержится в каждом элементе данных. Адрес ячейки, где хранится первый элемент очередей, хранится в специальном запоминающем узле-счетчике 3. При этом в ячейку, в которой хранится последующий элемент Любой очереди, в качестве указателя записывается адрес нулевой ячейки - нулевой код, а нулевая ячейка блока 1 не используется для записи элементов данных при организации приоритетных очередей при любом классе решаемых задач и при организации любых очередей при решении задач управления. В нулевой ячейке блока 1 в этих случаях всегда хранится нулевой код. При организации приоритетных очередей каждый элемент данных, кроме основной информации, должен содержать информацию о приоритете, который присвоен элементу данных. Код приоритета располагается в строго фиксированном месте элемента данньк и записывается в соответствующую ячейку блока 1 вместе с элементом данных в строго фиксированных разрядах ячейки. Коды приоритета могут представляться двоичными числами. При вводе очередного элемента данных в приоритетную очередь осуществляется последовательное считьшание Э1 ементов данных, начиная с элемента с наивысшим приоритетом, в порядке убывания приоритетов и сравнение приоритета каждого считанного элемента данных с приоритетом вводимого в очередь

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

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

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

элементов данных на информационных выходах 25 устройства, начиная с первого элемента данных очереди и до тех пор, пока код признака - содержимое элемента данных, представляющее код информации, располагаемый в определенном месте элемента данных - не совпадет с кодом признака, установленного на определенной группе входов 26 устройства, который сравнивается с соответствующим кодом признака каждого считываемого из блока 1 элемента данных) и удаления обнаруженного Элемента данных путем изменения кода указателя предьщущего элемента очереди, поиска элемента в очереди по признаку (содержимому) элемента (осуществляемому также, как и при вьгооде элемента очереди по признаку, без вьгеода элемента данных из очереди) , модификации (изменения) содержания элемента данных, найденных по признаку или при просмотре. Под признаком в данном случае понимается двоичный код части информации, содержа- щейся JB элементе данных, расположенный в строго определенном месте элемента данных. Благодаря возможности указанных операций над элементами данных очередей обеспечивается организация списков элементов данных, представляющих собой структуры управляющих таблиц, используемых в операционных системах для управления вычислительными процессами .

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

J9

Фг/г./

64

67 27 28 5 5 0 22 22 J J5 JJ

2U

50

20 21 48

2

65-5758 Фиг.г

15 16

Mf7

30 9f

м80

y

|Ш I

fw rfel

Ш I - W2