автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка и исследование методов автоматизации проектирования устройств микропрограммного управления СЦВМ

Введение

ГЛАВА I. СИСТЕМЫ АВТОМАТИЗАЦИИ МИКРОПРОГРАММИРОВАНИЯ

И СУЩЕСТВУЮЩИЕ МЕТОДИКИ АВТОМАТИЗИРОВАННОГО

РАЗМЕЩЕНИЯ МИКРОПРОГРАММ В УПРАВЛЯЮЩЕЙ

ПАМЯТИ.

ГЛАВА П. ОСНОВНЫЕ ПРИНЦИПЫ МЕТОДИКИ АВТОМАТИЗИРОВАННОГО

РАЗМЕЩЕНИЯ МИКРОПРОГРАММ В УПРАВЛЯЮЩЕЙ ПАМЯТИ.

2.1. Способы модификации адреса при организации условного перехода

2.2. Теоретико-множественный подход при представлении исходной информации . Э

2.3. Трудности распределения УП при отсутствии алгоритма. Ai

2.4. Методика размещения МП в УП. Постановка задачи.

2.4.1. Критерий размещения

2.4.2. Структурирование задачи

2.5. Методика размещения связок в связке Sj,p

2.5.1. Условия размещения связок Sai,mt в связке Sj,p

2.5.2. Методика получения списка размещений B>j

2.5.3. Графовое представление укрупненной связки 5j,p вывода.

ГЛАВА Ш. П УРОВЕНЬ ИЕРАРХИИ. РАЗМЕЩЕНИЕ СВЯЗОК П РОДА Sj,P

В СВЯЗКЕ Ш РОДА S. 7<

3.1. Метрическое представление управляющей памяти S как связки Ш рода. Ч\

3.2. Условия размещения укрупненных связок П рода Sj,p в связке S

3.2.1. Формализация условий плотного размещения связок

Sj,p N типов в УП.

3.3. Способы размещения связок Sj,p в связке Ш рода S . 82.

3.4. Оценка сложности размещения множества МК в УП с помощью разработанной методики.

3.5. Критерий разбиения Lpa5" регистра адреса микрокоманды на зоны Kj

3.6. Рекомендации разработчику микропрограммного устройства.

3.7. Этапы методики автоматизированного размещения МП в УП.

3.7.1. Обработка анкеты заказчика

3.7.2. Разбиение множества разрядов РАМ на зоны Kj

3.7.3. Комплектование укрупненных связок П рода Sj,p связками I рода Sai7mi,.1СЦ

3.7.4. Комплектование связки Ш рода S укрупненными связками Sj,p вывода.ю

ГЛАВА 1У. ОПИСАНИЕ БИБЛИОТЕКИ ПРОГРАММНЫХ МОДУЛЕЙ . W

4.1. Описание данных программного обеспечения.1^2.

4.2. Описание блок-схемы программного сегмента CONCATENACIA. 1И

4.3. Описание блок-схемы подпрограммы GENERATOR

4.4. Описание блок-схемы подпрограммы RANG .

4.5. Описание блок-схемы подпрограммы ZONA

4.6. Описание блок-схемы программного сегмента KUB

4.7. Характеристики комплекса программ. <2.

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

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

Все это повлекло за собой появление систем автоматизации микропрограммирования /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) На основании разработанных алгоритмов создана библиотека программных модулей, позволяющая автоматизировать процесс разме -щения МП в УП, перераспределения УП в случае внесения изменений в набор уже размещенных МП.

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

1.С. Введение в теорию множеств и общую топологию. - М.: "Наука" 1977. - 267 с.

2. Арлазарова А.В., Арутюнян Б.С. и др. Микропрограммный ФОРОС - ассемблер - Ml®. - "Вопросы проектирования программного обеспечения для управляющих вычислительных комплексов, Т/ИНЭУМ, 1977 вып. 66, с. 64-66.

3. J} Арутюнян Б.С., Погосянц Г.М. Подход к описанию функции перехода к следующей микрокоманде в микропрограмме. - Тр./ИНЭУМ, 1979, вып. 76, с. 54-76.

4. Арутюнян Б.С. Об одном методе размещения микропрограмм в постоянной памяти. - Вопросы радиоэлектроники, серия ЭВТ, 1976, вып. 7, с. 13-17.

5. Арутюнян Б.С. Алгоритм и реализация размещения микропрограмм в управляющей памяти в рамках системы автоматизации построения микропрограмм МИФ. - Тр./ИНЭУМ, 1981, № 87, с. 52-58.

6. Гб\ Асцатуров P.M., Ковалев О.С., Мальцев К.А., Пашковская Р.Б. 0 выборе способа задания адреса ми!фокоманды. - Вопросы радио vэлектроники, серия ЭВТ, 1973, вып. 8, с. 37-45.

7. Асцатуров P.M., Мальцев Н.А. Система автоматизации проектирования ЭВМ с микропрограммным управлением. - Вопросы радиоэлектроники, серия ЭВТ, 1970, вып. 8, с. I42-I5I.

8. Асцатуров P.M., Чернецкий JI.B. Язык символического кодирования микропрограмм. - Вопросы радиоэлектроники, серия ЭВТ, 1970, вып. 8, с. 152-158.

9. Баранов С.И. Синтез микропрограммных автоматов. М.: "Энергия", 1979, с. 231.г 10 i

10. Белицкий Р.И., Малиновский Б.Н. Оптимальное размещение микропрограмм в страничной микропрограммной памяти. - Вычислительные средства и вспомогательное оборудование систем, 1977,с. 64-68.

11. Брейер М. Теория и методы автоматизации проектирования вычислительных систем. М. "Мир", 1977, с. ,281.

12. Брейер М. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных. М. "Мир", 1979, с. 457.

13. Буль Е.С., Фрицнович Г.Ф. Распределение ми1фоопераций по полям ми!фокоманд в автоматах с программируемой логикой. -Вычислительная техника, Каунас, 1976, с. 12-14.

14. Валантинас И.И., Марцинкявичус В.В. Метод минимизации длины слов постоянного запоминающего устройства. - Вычислительная техника, 1976, Каунас, с. 46-49.

15. Вейтас В.Т. Вычисление количества слов в управляющей памяти, необходимого для размещения микропрограмм. - Вычислительная техника, Каунас, 1976, с. 43-45.

16. Вейтас В.Т., Жинтелис Г.Б. Типовые фрагменты структур а адресации микропрограммных устройств управления. - Управляющие системы и машины, 1975, № 4, с. 76-83.

17. Вейтас В.Т., Жинтелис Г.Б. Методика разбиения микропрограмм при их размещении в сегментированной управляющей памяти.- Вычислительная техника, Вильнюс, 1977, с. 72-76.

18. Вейтас В.Т., Шульцас П.М. Особенности реализации алгоритма разбиения микропрограмм - Вычислительная техника, Вильнюс, 1977, с. 76-79.

19. Вейцман И.Н., Чернецкий Л.В. Синтаксически ориентированная^ система автоматизации микропрограммирования. - Вопросы радиоэлектроники, серия ЭВТ, 1976, вып. 13, с. 53-60.

20. Голубкин В.Н., Тимофеев В.В., Емелеев Э.Т., Якимов И.М.- Подсистема автоматизированного проектирования микропрограмм. -

21. Вопросы радиоэлектроники, серия ЭВТ, 1982, вып. 7, С. 49-54.

22. Евстифеева Т.И., Погосянц Т.М. Входной язык и принципы настройки системы подготовки микропрограмм МИФ. - Труды ИНЭУМ, 1981, № 87, с. 48-51.

23. Егиазарян В.В. Об оптимальном распределении управляющей памяти для горизонтальных микропрограмм. - Вопросы радиоэлектроники, серия ЭВТ, 1979, вып. 9, с. 30-35.

24. Егиазарян В.В. 0 размещении ми1фопрограммных автоматов. - Вопросы радиоэлектроники, серия ЭВТ, 1975, вып. 13,с. 81-86.

25. Ерицян В.А., Мурадян A.JI. Алгоритм автоматического размещения микропрограмм в управляющей памяти. - Вопросы радиоэлектроники, серия ЭВТ, 1980, вып. 15, с. 95-99.

26. Жинтелис Г.Б. К вопросу о минимизации длины управляющих слов постоянного запоминающего устройства - Вычислительная техника, Каунас, 1976, с. 24-27.

27. Забара С.С., Мльнер А.Д. и др. Автоматизированная система микропрограммирования АСПРОМ. - УС и М, 1977, № 6, с.36-41.

28. Забара С.С., Мильнер А.Д. Некоторые вопросы автоматизации микропрограммирования: универсальный язык и транслятор. -УС и М, 1975, № 5, с. 52-57.

29. Забара С.С., Мильнер А.Д. Общая структура и функциональные возможности системы автоматизации микропрограммирования - Механизация и автоматизация управления., 1975, № 5, с. 36-38.

30. Забара С.С., Мильнер А.Д. Автоматизированная система микропрограммирования АСПРОМ. Точка зрения пользователя - УС и М, 1976, № I.

31. Забара С.С. Принципы построения автоматизированной системы микропрограммирования. - УС и М, 1977, № 5, с. 52-57.

32. Мильнер А.Д., Кантор В.Г., Ковалевская Е.В. Размещение микропрограмм в управляющей памяти. - Вычислительная техника, Вильнюс, 1977, с. 90-93.

33. Оре. Теория графов. М. Мир, 1980, с. 277.

34. Q381 Парфенова Н.А., Титков В.И., Феофанова Л.М. Размещение микропрограмм в управляющей памяти. - Вопросы радиоэлектроники, серия ЭВТ, 1978, вып. I, с. 30-32.

35. Петросян Э.А. Уплотнение микропрограмм. - Вопросы радиоэлектроники, серия ЭВТ, 1975, вып. 13, с. 87-91.40^ Петросян А.В., Шукурян Ю.Г., Размещение микропрограмм. - Вопросы радиоэлектроники, серия ЭВТ, 1974, вып. 9, с. 8-15.

36. Алгоритм уменьшения объема двухуровневой микропрограммной памяти / Сыров В.В. Линии и микро-ЭВМ в АСУТП и научном эксперимента. Киев, 1981, с. 55-61.

37. Автоматизация проектирования микропрограммных управляющих устройств. / Лазарев В.Г., Пийль Е.И., Янылина Л.К. Ло~ гическ. упр. м., 1981, М. 1981, № 2, с. 91-97.

38. Система автоматизации микропрограммирования. /Ефимова Б.М. Климова Е.В., Лазаренко И.В., Рысаков А.А. Вычислит, системы и комплексы. Л., 1981, с. 91-94.

39. Хассон С. Микропрограммное управление. Выпуск 2. "Мир", 1974, с. 477.

40. Потемкин М.С., Пирогова М.А. Выбор числа подмножеств адресов в оптимальном размещении микропрограмм в управляющей « памяти. - Тр./Моск. энерг. ин-т, 1981, вып. 555, с. I38-I4I.

41. Пирогова М.А. Алгоритмизация оптимального размещения микропрограмм в управляющей памяти. - Тр./№оск. энерг. ин-т, 1981, вып. 544, с. 28-31.

42. Microprogramming the series 3000. Revision A-\976, Intel Corporation

43. Thomas B.T.,TubrujM.S.,Gaida O.E. -TKe mo<Uar ^re architecture through the staelc / register based adress wodt-iica.-hO" / Firmware Microprogram. Restruct. Hardware.

44. РгосЛИР Work Gonf. bnz. 4Ш .h™$>tcrdam,mO,51оуЛ status report . "7-tli cuwiuciL workshop owprogra^mlns', <974, P

45. Sriwam B.R., Choudhury A.k.

46. An adress generation sbewe to minimize tbe corrfcrol mewori/ recjurements ^ microprogrammed digital computers.—1.t. Э. electron., №0, v.48, tf* 6, p. 457-470.