Разработка и исследование методов автоматизации проектирования устройств микропрограммного управления СЦВМ

В настоящее время метод микропрограммного управления находит все большее применение при проектировании устройств вычислительной техники (ВТ), в частности специализированных цифровых вычислительных машин (СЦВМ), и других средств обработки данных. На микропрограммном уровне реализуется сегодня не только система команд, но и отдельные компоненты системного программного обеспечения, диагностические комплексы, средства обеспечения совместимости, прикладные задачи. При том значительно возрастает объем микропрограммной подсистемы и удельного веса ее разработки в общем процессе проектирования СЦВМ. Разработка микропрограмм как правило идет параллельно с разработкой аппаратной подсистемы, а иногда может распространяться на весь период выпуска и использования СЦВМ.

В то же время современное микропрограммирование характеризуется значительной сложностью, обусловленной применением многоформатных микрокоманд, сложными системами адресации микропрограммной памяти, наличие^болыиого числа ограничений—нэ.^{сочетание} и последовательность микроопераций. Современные конструкции микропрограммной памяти требуют для ее изготовления: применения программно-управляемых автоматов и, следовательно, подготовки большого объема информации на управляющих носителях.

Все это повлекло за собой появление систем автоматизации микропрограммирования /7,12,19,26,28,30/45/. Эти системы, основанные на языках символического кодирования, или символического микропрограммирования /2,8,21,27/, позволили снизить трудоемкость кодирования микропрограмм и их подготовки для занесения в управляющую память, автоматизировать получение документации, подготовку информации для моделирования. Наиболее разработанными в существующих системах автоматизации микропрограммирования явля 5 ~ ются процедуры разделения слова микрокоманды на поля, оптимального распределения микроопераций по полям микрокоманды и связанная с этими проблемами задача минимизации длины слова микрокоманды. Существенное развитие в настоящее время получили языки символического микропрограммирования, предназначенные для описания алгоритмов микропрограмм. Это языки уровня «один к одному», позволяющие представить микрокоманду как последовательность микроопераций и операндов в символическом виде и в кодированной форме. Ряд таких языков обладает дополнительными возможностями — средствами макрорасширения, т. е. одновременного составления часто используемых фрагментов микропрограммсредствами микрокомпановки, .позволяющими автоматически «собирать» микрокоманды из микроопераций, логических условий и т. д. В результате работы транслятора системы автоматизации осуществляется преобразование символической микрокоманды во внутренний формат-запись, помещаемую в ячейку памяти микрокоманд.

Одну из основных трудностей при разработке систем автоматизации микропрограммирования составляет проблема оптимального размещения микропрограмм в управляющей памяти. Сложность решения этой проблемы вызвана большим количеством ограничений, накладываемых на выбор адреса управляющей памяти для размещения микрокоманды, Эти ограничения появляются из-за того, что в системах микропрограммирования, как правило, адрес перехода, к следующей микрокоманде формируемый при выполнении очередной микрокоманды, не может быть произвольным. Кроме того, ограничения на значения адреса накладывают особенности выбранного способа модификации адреса при организации в микропрограмме перехода по условию. Усложнение микропрограмм приводит к увеличению в составе микрокоманд удельного веса групп-преемников микрокоманд условного перехода. Это еще больше усложняет процесс размещения микропрограмм в управлящей памяти. Как уже отмечалось, процесс разработки микропрограмм при проектировании СЦВМ может распространяться на весь период разработки аппаратной части устройства, что приводит к необходимости вносить оперативные изменения в уже написанные и отлаженные микропрограммы. Часто это происходит после того, как наборы микропрограмм уже размещены в управляющей памяти, и трудоемкий процесс распределения памяти, поиск и исправление ошибок приходится повторять почти заново. Перечисленные трудности могут быть преодолены только в результате создания систем автоматизированного размещения микропрограмм в управляющей памяти.

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

В то же время этот метод обладает рядом преимуществ. В частности, заметно сокращается глубина декодирующих схем анализа условий, воздействующих на состояние любых разрядов адреса. При этом увеличивается скорость выборки микрокоманды из управляющей памяти, что является определяющим фактором для некоторых типов СЦВМ. Декодирующие схемы для разрядов адреса, участвующих в модификации при условном переходе, во всех разрядах оказываются почти одинаковы?,'м по оборудованию, что упрощает процедуру' трассировки при использовании схем малой и средней интеграции и тем более при изготовлении заказной СБИС (вентильная матрица). Однако, использование этого метода тормозится трудностями, возникающими при размещении набора микропрограмм в управляющей памяти.

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

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

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

Научная, новизна полученных результатов состоит в следующем:

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

2) предложено оригинальное представление управляющей памяти в виде метрического пространства, которое получаемся в ре.

— 8 зультате произведения метрических пространств, эквивалентных выделенным в памяти структурам — что позволило выявить порядок в задаваемом массиве ветвящихся микрокоманд ;

3) такое представление управляющей памяти позволило свести сложную переборную задачу размещения микропрограмм в управляющей памяти к построению стандартных таблиц, по которым в подмножествах адресов управляющей памяти, также имеющих метрическое представление, осуществляется плотное размещение исходных групп микрокоманд — преемников при условном переходе.

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

Апробация работы и публикации. Основные положения работы докладывались и обсуждались на IX Всесоюзном совещании — семинаре «Актуальные проблемы автоматизации проектирования ЭШ» (май 1981 г. Симферополь), на научной конференции «Проблемы создания и развития АСНИ, САПР и информационно-вычислительных комплексов», посвященной 60-летию образования СССР (МЭИ, 1982 г.), на техническом совете отделов № 179, 251 (Москва, НИИЦЭВГ, 1982 г.). По материа 9 ~ лам работы опубликовано 3 статьи, одна из которых в соавторстве. Материалы диссертации отражены также в трех отчетах по НИР, проводимых кафедрой ВТ МЭИ, исполнителем которых являлся автор.

Объем работы*1 Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержание диссертации изложено на 128 страницах, включает в себя 55 рисунков.

Список литературы

содержит 53 наименования.

ЗАКЛЮЧЕНИЕ

.

В заключение следует’отметить, что предложенная методика остается открытой для внесения изменений и дальнейшего развития. При увеличении объема управляющей памяти и разрядности РАМ в методике может быть добавлен Ш уровень иерархии переборных задач, построенный по тем же принципам, что и первые два. В этом случае вводится понятие связки 1У рода Sw, которая комплектуется связками Ш рода S по таблицам типов окомплектования, полученным аналогично таблицам типов комплектования связки S связками П рода Sj, p.

Выделению в памяти структур Sw соответствует разделению РАМ на зоны П рода Ко, в рамках каждой из которых осуществляется разбиение части РАМ на зоны I рода — знакомые нам Kj.

Данная методика применима и для страничной и модульной организации памяти. Размещение МП в УП может осуществляться не только с помощью разработанной библиотеки программных модулей. Разработчик, пользуясь предложенной методикой, без программ осуществляет распределение памяти за 2−3 дня. Без методики, как уже говорилось, размещение производится за 2−3 месяца.

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

В плане решения основной проблемы, поставленной в диссертации, заключающейся в разработке методики автоматизированного размещения МП в УП, получены следующие основные результаты.

I) На основании анализа существующих систем автоматизации микропрограммирования и методик размещения МП в УП показано, что большинство из них ориентировано на наиболее простые способы формирования АСМК при ветвлениях, связанные с модификацией младших w разрядов адреса. Обоснован выбор наиболее общего способа модификации адреса, при котором любые разряды адреса изменяются содержимым п регистров ветвления (п = 10 * 15), скммарная разрядность которых превосходит разрядность РАМ. Данный способ позволяет существенно увеличить быстродействие адресных схем МК.

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

3) Введено оригинальное метрическое представление УП, что позволило свести каждую подзадачу размещения МП в УП к построению стандартных таблиц типов комплектования. Структурный подход к задаче размещения позволил на каждом из уровней полученной иерархии переборных задач применять подобные методы решения: на I уровне в подмножествах всех адресов УП, также имеющих метрическое представление, осуществляется плотное размещение исходных групп ветвления в соответствии с таблицами типов комплектованияна П уровне во всем множестве адресов УП размещаются подмножества адресов, укомплектованные на I уровне, по аналогичным таблицам. Таким образом была решена задача общности.

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

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

6) На основании разработанных алгоритмов создана библиотека программных модулей, позволяющая автоматизировать процесс размещения МП в УП, перераспределения УП в случае внесения изменений в набор уже размещенных МП.

Таким образом решена задача размещения Ш в УП для способа формирования АСМК типа «функциональный переход», для наиболее общего случая модификации адреса МК при ветвлениях, при котором схемы анализа условий могут изменять содержимое любых разрядов РАМ.