Содержание к диссертации
Введение
Глава I. Обзор литературы и постановка задач 11
1.1. Обзор литературы 11
1.2. Принципы построения системы автоматизации подготовки микропрограмм МИФ 17
1.3. Задача размещения микропрограмм в управляющей памяти 18
1.4. Минимизация длины слова микропрограммной памяти 17
Глава 2. Задача кодирования микрооперации в слове микропрограммного ЗУ 31
2.1. Постановка задачи кодирования микроопераций в слове ЗУ 31
2.2. Способ покрытий множества микроопераций своими подмножествами при решении задачи кодирования 32
Глава 3. Анализ структуры микропрограммы и функции перехода к следующей микрокоманде 43
3.1. Представление микропрограммы орграфом и задача размещения микропрограмм в управляющей памяти 43
3.2. Исследование структур адресации 55
3.3. Способ описания функции адресации 65
Глава 4. Принципы реализации системы автоматизации подготовки микропрограмм миф и описание алгоритмов 75
4.1. Микропрограммный ассемблер МИФ 75
4.2. Символический язык описания микропрограмм 80
4.3. Реализация описания ФА в МИФ 84
4.4. Алгоритмы и комплекс программ, реализующие размещение микропрограмм 96
4.5. Последовательная дисциплина в микропрограммировании 120
Заключение 124
Литература 127
Приложение
- Принципы построения системы автоматизации подготовки микропрограмм МИФ
- Постановка задачи кодирования микроопераций в слове ЗУ
- Представление микропрограммы орграфом и задача размещения микропрограмм в управляющей памяти
- Микропрограммный ассемблер МИФ
Введение к работе
В материалах ХХУІ съезда, относящихся к вопросу интеграции науки с производством, в частности, было сказано: "Поистине революционные возможности открывают создание и внедрение миниатюрных электронных управляющих машин, промышленных роботов. Они должны получить самое широкое применение".
Ни одна электронная управляющая машина не может обойтись без устройства управления, при разработке которого в последнее время предпочтение отдается микропрограммному принципу управления.
Настоящая работа посвящена проблемам автоматизации разработки средств микропрограммного управления.
Актуальность проблемы. Микропрограммирование в настоящее время получило самое широкое распространение. Микропрограммирование используется в центральных процессорах, в контроллерах ввода/вывода, в управлении дисплеями, в системах автоматизированной обработки сигналов, при построении компиляторов, реализации функций операционных систем и т.д. Особенно широкое применение микропрограммное управление получило в связи с появлением микропроцессоров.
Разработка средств микропрограммного управления - трудоемкая и сложная задача, поэтому автоматизация микропрограммирования становится необходимостью, и не только потому, что разработчик освобождается от рутинной работы, а главным образом потому, что средства, предоставляемые системами автоматизации, позволяют повысить качество и скорость разработки. Последнее обстоятельство тем более важно, поскольку производи - 5 -тельность и стоимость ЭВМ существенно зависят от степени совершенства средств микропрограммного управления.
В этой связи актуальность разработки эффективных систем автоматизации микропрограммиирования не вызывает сомнений. Задачи, связанные с автоматизацией разработки средств микропрограммного управления, решены далеко не полностью, тем более, что требование известной универсальности систем автоматизации привносит дополнительные и весьма существенные трудности.
Предметом исследования являются принципы построения системы автоматизации микропрограммирования применительно к задачам автоматического размещения микропрограмм в управляющей памяти и минимизации длины слова микропрограммной памяти при кодировании микроопераций.
Целью работы является разработка принципов построения системы автоматизации микропрограммирования МИФ ассемблерного типа (т.е. основанной на языке микропрограммирования ассемблерного типа), не ориентированной на конкретную микропрограммную базу и решение возникающих при этом задач, представляющих основную трудность, а именно: автоматическое размещение микропрограмм в управляющей памяти и минимизация длины слова микропрограммной памяти при кодировании микроопераций.
Решение этих задач в рамках системы автоматизации подготовки микропрограмм, не ориентированной на конкретную микропрограммную базу, достаточно затруднено, т.к. их решение (особенно задачи размещения) в сильной степени зависит от характеристик конкретной микропрограммной базы. Однако разрешение этой проблемы значительно повышает универсальность системы автоматизации, что делает ее более эффективной.
Поставленная цель достигается:
- разработкой принципов построения системы подготовки микропрограмм МИФ;
- новым подходом к кодированию микроопераций;
- анализом логической структуры микропрограммы и механизма адресации;
- разработкой способа описания логической структуры микропрограммы на символическом уровне;
- разработкой процедурного способа описания механизма адресации в микропрограмме;
- разработкой алгоритмов и соответствующего комплекса программ, реализующих размещение символических микропрограмм в управляющей памяти и кодирования адресных полей микрокоманд в соответствии с заданной системой адресации.
Метод исследования базируется на использовании аппарата теории множеств, алгебры, теории графов, комбинаторики, микропрограммирования и экспериментальных методов.
Научная новизна работы. Новые научные результаты заключаются в следующем:
- предложен компромиссный подход к построению системы автоматизации микропрограммирования, позволяющий сочетать преимущества систем, основанных на языках микропрограммирования разных уровней;
- предложен подход к решению задачи кодирования микроопераций в слове управляющей памяти, позволяющий получить минимальное решение;
- разработан процедурный способ описания механизмов адресации в микропрограмме, позволяющий настраивать систему авто - 7 матизации микропрограммирования на конкретную микропрограммную базу при решении задач кодирования и размещения микрокоманд;
- предложен способ описания логической структуры микропрограммы на символическом уровне, позволяющий вкупе с описанием механизма адресации реализовать корректное кодирование и размещение микрокоманд.
Практическая ценность работы. Результаты диссертационной работы позволяют научно обоснованно решать такие важные в практике разработки и создания микропрограммных средств управления вопросы, как минимизация длины слова микропрограммной памяти при кодировании микроопераций, автоматическое размещение микропрограмм в управляющей памяти, наглядное описание логики микропрограммы на символическом уровне, наглядное и компактное описание механизма адресации.
Реализация и внедрение результатов исследований. Работа проводилась в соответствии с планом основных научно-исследовательских и опытно-конструкторских работ ИНЭУМ по темам № 0889 954090 и № 0889 276350 соответственно и планом важнейших работ по новой технике Минприбора № 508109. Полученные результаты реализованы в рамках системы автоматизации построения микропрограмм, разработанной в Институте электронных управляющих машин и принятой Межведомственной комиссией в сентябре 1980 г. Программы реализованы на машинах М4030, M4030-I и ЕС ЭВМ и составляют более 5000 операторов языка Ассемблера.
Система внедрена в организациях г.г. Москвы, Еревана, Киева и Вильнюса. Экономический эффект от внедрения системы составляет 40 тыс. рублей в год.
В целом работа выполнялась в рамках целевой комплексной программы ГКНТ 0.80.14. "Создать и освоить в производстве комплекс перспективных средств вычислительной техники, включая электронные вычислительные машины (ЭВМ) с производительностью до I млрд. операций в секунду, мини- и микро- ЭВМ, микропроцессоры, переферийное оборудование и программные средства".
Апробация результатов работы. Основные результаты диссертационной работы доложены и обсуждены на семинаре "Разработка, эксплуатация и развитие систем автоматизированного проектирования РЭА" (Москва, 1978), конференциях молодых ученых и специалистов (Москва, ИНЭУМ, 1977, 1978, 1979; Ереван, ЕрНИИММ, 1980), семинаре по проблеме "Микропроцессоры в системах управления" (Москва, ИПУ, 1982), Втором Всесоюзном совещании "Автоматизация проектирования и конструирования" (Ленинград, ЛИТМО, 1983).
Публикации. По материалам диссертации опубликовано десять печатных работ.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, приложений, списка литературы, изложена на 135 страницах машинописного текста, содержит 16 рисунков, список литературы включает 74 наименования.
Принципы построения системы автоматизации подготовки микропрограмм МИФ
Исследование систем автоматизации микропрограммирования показывает, что с ростом уровня используемого языка микропрограммирования затраты на разработку в общем сокращаются, но за это приходится платить понижением эффективности получаемого микрокода.
Изложенные соображения предполагают поиск компромиссного решения. В качестве одного из возможных решений можно предложить следующее: выбор уровня ассемблерных языков, но с использованием различных конструкций, применяемых в языках более высокого уровня и системных средств с целью сокращения трудоемкости разработки. С другой стороны, поскольку существенным недостатком ассемблерных языков является их ориентированность на конкретную вычислительную систему - стремление к универсальности микроассемблера. Именно эти принципы реализованы при построении системы МИФ (см.приложение I).
В литературе описан ряд систем автоматизации микропрограммирования. Большинство из них являются узкоспециализированными, т.е. ориентированы на работу с конкретной микропрограммной базой [2.10, II, 12, 21, 23, 26, 36, 38І . Следующим шагом на пути универсализации являются системы, ассемблерные по уровню используемого языка, но настраиваемые в соответствии с конкретными условиями [2.1, 4, 22, 24, ЗІ, 4ІІ (также реализовано в системе МИФ). Другой подход к настройке реализуют синтаксически ориентированные системы, настройка которых производится путем задания грамматики исходного языка [2.14, 17, 19, 25, 33, 40І . И, наконец, системы, использующие языки микропрограммирования высокого уровня [2.16,29]. Реализации этих принципов в системе МИФ посвящена глава 4.
Результатом работы системы автоматизации микропрограммирования является микрокод, физически расположенный в управ -ляющей памяти. Микрокод должен определять содержание как операционных, так и так называемых адресных полей микрокоманд, в которых содержится информация, необходимая для формирования адреса перехода. Содержимое адресных полей и само расположение микрокоманд в памяти в сильной степени взаимосвязано и далеко не случайно, а зависит от механизма адресации, принятого в данной микропрограммной базе. Оптимальное и корректное кодирование адресных полей микрокоманд и размещение их в памяти - необходимая и вместе с тем весьма сложная задача,
В литературе, относящейся к системам автоматизации микропрограммирования этому вопросу уделяется мало внимания. В основном известные системы ориентированы на определенный тип механизма адресации [2.21, 40}. Отдельные же статьи І2.27, 30, 39, 62, 67] , посвященные размещению, предлагают различные алгоритмы решения, относящиеся к тому или иному аспекту задачи»
Естественным желанием было бы иметь возможность решать эту задачу автоматически, не ориентируясь на конкретную микропрограммную базу и в рамках единой системы подготовки микропрограмм.
В настоящей работе эта задача решена в рамках системы автоматизации микропрограммирования МИФ [2.1, 4].
Идея предлагаемого способа решения основана на том, что настройка на конкретный механизм адресации, имеет процедурную основу и задается программистом в виде описания на языке моделирования ФОРОС [2.35]. Трансляция и анализ текста описания позволяет при помощи соответствующих алгоритмов производить корректное и эффективное размещение заданных в символическом виде микропрограмм. Подробное решение задачи изложено в главах 3 и 4 работы.
Другой задачей, решаемой на этапе формирования микрокоманд, является задача минимизации длины слова микропрограммной памяти при кодировании микроопераций. Уменьшение длины слова микропрограммной памяти позволяет сократить как объем памяти (достаточно заметить, что уменьшение слова даже на один разряд, помноженный на число слов, дает ощутимый эффект), так и соответствующую аппаратуру.
В настоящей работе предлагается способ решения этой задачи, отличный от предлагаемых ранее и всегда приводящий к минимальному решению. Критическому обзору литературы по этому вопросу и точной постановке задачи посвящен параграф 1«4.
Постановка задачи кодирования микроопераций в слове ЗУ
Пусть задано конечное множество микроопераций А-\(Ьі 0-2 .- 0-KJ і на котором задано бинарное отношение несовместимости R - не рефлексивное, симметричное, не транзитивное. Микрокоманда есть любое подмножество А попарно совместимых микроопераций, т.е. находящихся в отношении 1Н . ЗАДАЧА. Так закодировать элементы множества А в t полях ("t - целое положительное число), чтобы удовлетворялись два требования. 1. Возможность представления любой микрокоманды как набора микроопераций из различных полей. 2. Минимальность длины слова ЗУ. Первое требование необходимо для реализации выборки нужных микроопераций, т.к. нет возможности одновременной выборки двух микроопераций из одного и того же поля. Так что если две микрооперации совместимы, т.е. существует принципиальная возможность вхождения их в одну микрокоманду, то необходимо, чтобы существовало по меньшей мере два различных поля, в одном из которых закодирована одна микрооперация, а в другом - другая. Нетрудно видеть, что это наиболее общая постановка задачи кодировки множества микроопераций путем выделения подмножеств микроопераций и кодирования их в различных полях, обеспечивающая как реализуемость любых микропрограмм, так и мини- мальность занимаемого объема ЗУ. Из введенных определений следует, что множеством всех микрокоманд будет М -\т\пК 7 VCU , Ш(CU \Я aj)) где А - множество всех подмножеств множества А . Обозначим через Г множество всех покрытий множества А множеством A f т.е. T cov-A . ОПРЕДЕЛЕНИЕ,2.1. Покрытие"$Г назовем допустимым, если для любого її! Є М существует инъективное отображение р из № в % такое, что Vai tnCQ-i 9CO.0V Заметим, что для одних и тех же № и таких отображений может быть несколько. Множество всех допустимых покрытий обозначим через Го Условимся длиной микрокоманды Ш М называть число содержащихся в ней микроопераций и обозначать через \Гп\ . Аналогично длиной покрытия %\ будет число 1 1 входящих в него подмножеств множества А , которые будем называть классами покрытия X Длину самой длинной микрокоманды из М обозначим через б о . Из определения 2.1 непосредственно следует, что На множестве Г0 введем функцию следующим образом. где ІПІ обозначает наименьшее целое число, не меньшее \\ , а наличие единицы в выражении функции 4 связано с необходимостью кодирования состояния отсутствия операции. НЕОРЕМА 2.1. Решением задачи является покрытие у из Го такое, что для любого покрытия"6i из о верно Множество таких покрытий обозначим через ttlttl io . Доказательство. Поскольку W\VY\ io есть допустимое покрытие, то для него существует отображение Ц) » которое обеспечивает требование представимости любой микрокоманды, как набора микроопераций из различных полей (первое требование задачи). Второе же требование обеспечивается минимальностью значения функции \ для X , т.е. длины слова ЗУ. Рассмотрим отображение в из т М в такое, что образом произвольной микрооперации Q-». из W будет множество всех классов из "tf , содержащих &1 ТЕОРЕМА 2.2. Для того, чтобы покрытие было допустимым, необходимо и достаточно, чтобы для любой микрокоманды ХЛ из М число входящих в нее микроопераций было меньше либо равно числу классов из , которым принадлежат микрооперации из ft\ Иными словами Доказательство теоремы следует непосредственно из известной теоремы о системе различных представителей. Необходимо только отметить, что
Представление микропрограммы орграфом и задача размещения микропрограмм в управляющей памяти
Код ГП\ определяет проверку значения условия из УL а (число возможных значений СЦ ). При этом I -й разряд адреса следующей микроинструкции принимает значение результата проверки условия из Y1. В каждом ПТІ имеются кодовые комбинации для безусловной установки соответствующего разряда РА в "I" или "О" (считается, что они входят в У1 ). Зцесь и далее через СПУ обозначается схема проверки условий перехода. Типовой фрагмент С А разрешает условный переход по одному из 2 направлений. Примером использования данного варианта для условного ветвления являются процессоры системы 360 фирмы IBM , модели 40 и 50. 3.2. В микроинструкции наряду с Ш\ закодированы и ПА і , 1= 1,...,S . Имеется однозначное соответствие между ПТі. и П А I . Как и в 3.1, каждое ПЦ определяет проверку одного условия из У1 . Процедура вычисления адреса следующей микроинструкции заключается в следующем: проверяется условие из У ; если результат проверки положителен, адрес следующей микро-инструкции модифицируется содерскимым ПАл в текущей микроин-инструкции, иначе проверяется условие из У2 , и т.д. до про- верки условия из У . Если результат проверки У положителен, адрес модифицируется П к s. , иначе к адресу текущей микроинструкции прибавляется единица. Способ реализует условный переход по одному из S+ 1 направлений. В целях ускорения проверка условий, определяемых всеми и I , производится параллельно. Окончательное решение принимается схемой приоритета (СП), на выходе которой имеется сигнал, соответствующий положительному результату проверки условия из Y1 с высшим приоритетом. Если результаты проверки всех условий У1"., 1=-4 ..., отрицательны, СП вырабатывает сигнал для управления схемой (+1) в Р к . Рассмотрение типовой фрагмент С к применяется в процессоре модели 45 системы Spectra фирмы RCA ,,в котором введена специальная микроинструкция проверки и перехода. В каждом ПТ закодированы все возможные условия переходов. 3.3. Способ условного перехода, использующий для формирования адреса перехода содержимое регистров перехода. В микроинструкции имеются следующие поля, относящиеся к формированию адреса перехода: ГПч, {.« 1, ...,S ПоУП и поле номера регистра перехода (ПНРП ). В данном типовом фрагменте ЗД имеется триггеров хранения результатов проверки условий переходов (ТХРПі ) и соответствующих им S регистров хранения адреса перехода (PXAFU ). В каждом ПТ закодированы взаимно непересекающиеся подмножества условий переходов У1", Iе 4 , .. . , s . Условия, заданные всеми ПТ , проверяются параллельно, а результаты проверки запоминаются в соответствующих ТХУП { . Опрос ТлУП производится приоритетно. Это определяется схемой выборки адреса перехода (СБМ1 ). ПНРП управляет выборкой и записью содержимого ПА в один из РХЛПі . Таким образом, если код в По 7 И указывает на условный переход, подразумевается, что в rXAu хранятся некоторые адреса, переданные в ранее выполнявшихся микроинструзсциях, и в TXVD хранятся результаты тестовых проверок, выяоляен-ных также в предыдущих микроинструкциях. Определяется "ПСУПі, имеющий высший приоритет и 91 » и содержимое РХАП t передается в РА Если все с- 0,1 1, ...,S , адрес следующей микроинструкции вычисляется прибавлением і к содержимому РА . Вышерассмотренная схема реализует условный переход по одному из S+1 направлений. Примером ЭВМ, использующей типовой фрагмент СА з.З. является система Н4200 фирмы HoheyweLL 4. Функциональный переход. В формировании адреса следующей микроинструкпии участвует содержимое определенных регистров РОУ , с=» 1, ..., s , или их частей в ОУ. Части регистров ОУ рассматриваются в данном типовом фрагменте С А как отдельные регистры. Номер регистра І указывается кодом в поле функционального перехода (ПФП) текущей микроинструкции. В общем случае функциональным переходом модифицируется только часть разрядов в РА. -Примеры применения функционального перехода (например, перехода из микропрограммы выборки команды на микропрограмму выполнения) можно найти в большинстве микропрограммных ЭВМ: в EC-I020, в модели 45 системы Spec"tr-a фирмы RCA . в модели 40 системы 360 фирмы 1ВИ , в модели 50.
Микропрограммный ассемблер МИФ
Результаты, полученные в главе 3 позволяют решить задачи, возникающие в процессе разработки системы автоматизации микропрограммирования. Эта глава посвящена реализации полученных результатов в виде комплекса программ, являющегося основой микропрограммного ассемблера МИФ [2.2,4,6,8,9]. Микропрограммный ассемблер МИФ (см. приложение I), построенный на базе системы ФОРОС, предназначен для автоматизации следующих этапов разработки микропрограммного устройства управления вычислительной машины: - разработка микропрограмм; - кодирование микропрограмм; - размещение микропрограмм в микропрограммной памяти; - отладка микропрограмм и логики микропрограммного процессора; - компоновка микропрограмм; - ведение документации. МИФ включает в себя: - средства для настройки на конкретную микропрограммную базу; - язык для описания микропрограмм на символическом уровне; - транслятор с этого языка; - язык для описания механизма адресации; - транслятор с этого языка; - систему отладки микропрограмм и логики микропрограммного процессора путем моделирования; - средства для подключения пользовательских программ, ориентированных на выдачу управляющей информации для программаторов ПМК и (или) заводской документации на содержимое БМК. Структурная схема микроассемблера представлена на рис.5. Ядром системы является МИФ-транслятор. Разработанные для МИФ-транслятора правила записи микрокоманд достаточно просты и охватывают любую запись микрокоманды ассемблерного типа. Для настройки транслятора на выбранную ассемблерную запись служит управляющая информация, называемая шаблоном. Шаблон и текст микропрограммы являются входной информацией МИФ, которая может быть введена транслятором с карт или из библиотеки исходных текстов. Язык символического кодирования микропрограмм предназначен для описания алгоритмов микропрограмм. Этот язык уровня "один к одному", позволяющий представить микрокоманду как последовательность микроопераций и операндов в символическом виде и в кодированной форме, записывать константы непосредственно в различных системах счисления, адресовать память на символическом уровне. Кроме того, конструкции языка представляют возможность задавать необходимые данные и управляющую информацию, обеспечивающие работу транслятора и программы размещения. МИФ-транслятор производит дешифрацию и кодировку микропрограммы согласно правилам, указанным в шаблоне. Кодирование микрокоманд, как известно, состоит в том, что содершшо- му каадого поля в слове микрокоманда ставятся в соответствие коды. Вообще говоря, адресные части микрокоманд становится возможным определить только после размещения микрокоманд в памяти (придания адресов) в соответствие с заданной функцией выборки следующей микрокоманды. Оцной из спепифик микропрограммирования является возможность задания как группы микрокоманд, следующих за данной, так и способа ветвления в нее, описываемого функцией адресации. Для нужд автоматического размещения разработан язык, позволяющий описывать заданную функцию адресации. На основании этого описания и исходного микропрограммного модуля на символическом языке реализуется автоматическое размещение микропрограмм в управляющей памяти. Являющаяся составной частью транслятора фаза размещения при необходимости определяет местоположение микрокоманды в микропрограммной памяти на основе задаваемых системе процедур перехода (функций адресации). Функции адресации также являются входной информацией МИФ и хранятся в отдельной библиотеке. Результатом работы МИФ является протокол трансляции -распечатка символического текста микропрограммы с указанием замеченных при трансляции ошибок и распечатка кодированной формы микрокоманд с указанием приданных им адресов, а также карта занятости микропрограммной памяти (см. приложение 2). Кроме того, в специальный файл связи выводится текст микропрограммы в кодированной форме и адреса микрокоманд в МП.
