Указания методические к выполнению курсового проекта «Проектирование процессора эвм» по курсу «Организация эвм, комплексов и систем» для студентов дневного отделения специальности 2201 Ижевск 2001г МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РФ ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Т.Ф. Юминова К.Ю.Петухов МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению курсового проекта «Проектирование процессора ЭВМ » по курсу «Организация ЭВМ, комплексов и систем» для студентов дневного отделения специальности 2201 Ижевск 2001г. ВВЕДЕНИЕ Самостоятельная работа студентов – важнейшая часть процесса подготовки специалистов. Она активно способствует развитию творческого подхода к решению тех или иных задач, учит анализу и обоснованию принимаемых технико-экономических решений. Центральное место в самостоятельной работе студентов по курсу “Организация ЭВМ, комплексов и систем” занимает курсовой проект. Курсовые проекты выполняются по индивидуальным заданиям, утвержденным кафедрой. Объектом проектирования является процессор ЭВМ общего назначения, предназначенный для реализации заданного набора команд из системы команд ЕС ЭВМ, отличающейся широким распространением и универсальностью. Выполнение курсового проекта преследует цель привития навыков проектирования структуры ЭВМ в целом и отдельных ее узлов, в первую очередь процессора. В ходе проектирования возникает необходимость неформального использования знаний, полученных на лекционных, практических и лабораторных занятиях, преодоления своеобразного “психологического барьера” в виде первой достаточно сложной и самостоятельной работы по специальности. Методические указания к выполнению курсового проекта включают в себя описание: функциональной и структурной организации проектируемого процессора, принципов адресации информации и процедур обращения к основной и регистровой памяти, а также форматов данных и команд, используемых при разработке процессора. Приведены исходные данные для проектирования. В методических указаниях дано описание системы команд ЕС ЭВМ, определены основные этапы разработки функциональных микропрограмм отдельных операций, приведены примеры микропрограмм, описана методика объединения микропрограмм, определен порядок проектирования управляющих автоматов с жесткой и программируемой логикой. 1. ТЕМАТИКА И СОДЕРЖАНИЕ КУРСОВОГО ПРОЕКТА Целью курсового проекта является решение комплекса вопросов, связанных с проектированием процессора ЭВМ. Разработка процессора проводится в следующих аспектах: разработка функциональных микропрограмм заданных команд, объединение микропрограмм, привязка микропрограмм к структуре операционного автомата процессора, разработка структуры операционного автомата и управляющего автомата процессора. Исходные данные для проектирования определяются номером задания и выбираются из таблицы 1. Задание на курсовой проект содержит следующие исходные данные : - набор команд, реализуемых проектируемым процессором (описание команд в [1]); - емкость оперативной памяти (ОП); - ширина выборки из ОП (длина слова ОП); - тип управляющего автомата с жесткой логикой; - система элементов для разработки принципиальных электрических схем; -способ адресации микрокоманд для управляющего автомата с программируемой логикой. 1.1. Основные этапы проектирования 1. Разработка функциональных микропрограмм заданных команд. Для описания команд используется язык функционального микропрограммирования (Ф-язык), позволяющий в компактной форме отразить алгоритмы выполнения операций [1,2]. 2. Объединение функциональных микропрограмм. 3. Разработка структурно-функциональной микропрограммы (в виде таблицы) и структурной схемы процессора. 4. Проектирование управляющего автомата с жесткой логикой. 5. Проектирование управляющего автомата с программируемой логикой. 1.2. Содержание пояснительной записки к курсовому проекту В пояснительной записке (ПЗ) должны быть отражены все этапы проектирования. Оформлять ПЗ следует в соответствии с ЕСКД (ГОСТы 2.105-79, 2.106-68). Рекомендуется придерживаться следующей последовательности в изложении материала. 1. Описание функциональной организации проектируемого процессора Для каждой операции, реализуемой процессором, приводится описание алгоритма ее выполнения [1], форматы данных и команды, особые случаи, приводящие к прерываниям, установка признака результата. При описании операций следует игнорировать аспекты, связанные с обработкой прерываний, средствами схемного контроля и защиты памяти, формированием дополнительной цифры мантиссы в командах арифметики с плавающей запятой и т.п. На основе алгоритма для каждой операции разрабатывается блок-схема алгоритма ее выполнения, а затем функциональная микропрограмма (Ф-МП), отображающая все этапы выполнения операции: выборку команды, формирование адресов и чтение операндов из памяти, обработку операндов в соответствии с выбранным алгоритмом выполнения операции, установку признака результата (при необходимости), запись результата в память. Необходимо учитывать возможные состояния процессора: ОСТАНОВ-РАБОТА; ОЖИДАНИЕ-СЧЕТ; СУПЕРВИЗОР-ЗАДАЧА, а также фиксировать особые случаи, ведущие к прерыванию программы. Описание алгоритмов арифметических операций необходимо сопровождать примерами выполнения операций над числами уменьшенной длины (4-8 двоичных разрядов).Следует увязывать между собой Ф-МПы, т.е. однотипные действия выполнять с использованием одних и тех же внутренних слов и микроопераций. Поясняющие текст рисунки и таблицы можно размещать в ПЗ по ходу изложения или на отдельных листах. 2. Объединение функциональных микропрограмм Объединение Ф-МПм возможно за счет наличия в разных микропрограммах одинаковых микрокоманд или блоков (нескольких операторных и условных вершин). В результате объединения минимизируется общее количество операторных и условных вершин. Объединение производится без учета выборки команд из памяти (этап выборки команды разрабатывается сразу в объединенном варианте, т.е. с учетом всех возможных длин команд). Исходные микропрограммы могут быть объединены с учетом формализованных принципов объединения по алгоритму С.И.Баранова [5]. Пример объединения приведен в разделе (5) методических указаний. Объединенная функциональная микропрограмма вычерчивается на отдельном листе. Описание процесса объединения приводится в ПЗ. 3. Разработка структурной схемы процессора Структурная электрическая схема проектируемой ЭВМ должна содержать оперативную и сверхоперативную памяти, связанные через магистраль (М) с процессором (рис.1). Операционный автомат процессора разрабатывается на схеме с точностью до операционных элементов с указанием всех связей между элементами схемы, управляющих и осведомительных сигналов. Отражается связь процессора с оперативной и регистровой памятью. Для выявления всех связей в ОА и множества управляющих и осведомительных сигналов должна быть разработана структурно-функциональная таблица. Рекомендуется использовать структуру ОА с общими микрооперациями (МО) с последовательной комбинационной частью [2]. Каждой микрокоманде объединенной Ф-МПы ставится в соответствие набор управляющих сигналов, инициирующих ее выполнение в рамках разработанной структуры (строка структурно-функциональной таблицы). При этом учитываются все особенности структуры процессора: длина слова оперативной памяти (ОП), разрядность схем комбинационной части ОА, связь ОА процессора с ОП и регистровой памятью (РП) (см. табл.1). Каждому логическому условию (ЛУ) Ф-Мпы ставится в соответствие осведомительный сигнал. В структуру ОА должны быть введены комбинационные схемы – формирователи осведомительных сигналов. Все нетривиальные решения обосновываются. Набор операционных элементов, схем формирования осведомительных сигналов и состав регистров памяти ОА должен быть минимальным. Структурно-функциональная таблица приводится в ПЗ, а схема электрическая структурная проектируемого процессора – на отдельном листе графической части курсового проекта (лист 2). 4. Проектирование управляющего автомата с жесткой логикой Управляющий автомат (УА) с жесткой логикой разрабатывается для фрагмента Ф-МПы, содержащего от 20 до 30 операторных вершин. Тип УА указан в задании на проект. Все этапы проектирования УА описываются в ПЗ и иллюстрируются необходимыми таблицами и рисунками. Схема электрическая принципиальная УА с жесткой логикой вычерчивается на отдельном листе графической части (лист 3) в соответствии с ЕСКД на базе заданной серии интегральных микросхем [3,4]. Перечень элементов приводится в приложении к ПЗ или на листе схемы. Рассчитываются затраты времени на формирование управляющих сигналов и переключение УА в следующее состояние (такт УА). Временные параметры микросхем определяются по справочнику [3,4] . 5. Проектирование управляющего автомата с программируемой логикой УА с программируемой логикой проектируется для всей объединенной Ф-МПы. С учетом заданного способа адресации микрокоманд разрабатывается формат микрокоманды (МК), проводится оптимальное распределение управляющих сигналов по полям операционной части микрокоманды. Все управляющие и осведомительные сигналы кодируются. Схема электрическая функциональная УА приводится на отдельном листе графической части (лист 4). В ПЗ обосновывается выбор формата МК. Для фрагмента МПы (можно использовать исходный фрагмент для УА с жесткой логикой) проводится процедура размещения микрокоманд в памяти в соответствии с заданным способом адресации микрокоманд. Таблица 1 Варианты исходных данных для проектирования Номер варианта Коды команд Емкость ОП (Кбайт) Длина слова ОП (байт) Тип УА с жесткой логикой Серия интегральных микросхем Способ адресации микрокоманд 1 2 3 4 5 6 7 1. 2. 3. 4. 5. 38,5С,86 30,BE,4C 28,59,49 8F,95,1E 32,4C,46 256 128 512 1024 2048 8 4 4 2 2 МИЛИ 133 134 155 176 500 1 2 6. 7. 8. 14,7C,06 33,7E,45 70,3C,44 4096 128 256 4 4 8 МУРА 530 531 533 3 Продолжение табл. 1 1 2 3 4 5 6 7 9. 10. 11. 12. 13. 14. 31,BE,40 54,2C,87 8A,55,34 15,3A,5A 41,3E,5E 13,7A,B7 1024 64 128 512 1024 256 8 2 2 4 4 8 МИЛИ 555 561 564 1500 1531 1533 3 1 2 15. 16. 17. 18. 19. 20. 10,5D,24 89,2A,46 8B,7E,05 07,3B,5B 3E,94,59 34,4B,7B 2048 128 64 512 2048 256 8 2 8 4 2 2 МУРА 1561 133 134 155 176 500 3 1 21. 22. 23. 24. 25. 12,7B,86 2B,95,4A 18,7D,19 86,BF,34 2C,BB,82 1024 128 4096 512 256 8 4 4 2 8 МИЛИ 531 533 555 561 564 2 26. 27. 28. 29. 10,2C,46 8D,6B,07 15,6F,98 58,5D,24 1024 2048 512 128 8 4 4 8 МУРА 1500 1531 1533 1561 3 30. 31. 32. 33. 34. 42,6C,19 78,BF,1A 6B,BA,07 22,97,5B 23,7F,87 256 64 2048 512 128 8 2 2 8 8 МИЛИ 133 134 155 176 500 1 2 35. 36. 37. 38. 39. 21,69,82 20,4C,5C 6C,94,1F 13,6C,96 48,3B,4B 256 64 2048 256 512 4 4 2 2 8 МУРА 531 533 555 561 564 3 40. 41. 42. 43. 44. 24,BB,47 16,79,98 8E,29,60 14,3F,8A 16,2E,8F 128 1024 64 128 4096 8 4 4 2 2 МИЛИ 1500 1531 1533 1561 133 1 2 45. 46. 47. 48. 15,7B,44 88,6A,1A 07,69,54 78,1C,40 512 1024 2048 512 8 8 4 4 МУРА 134 155 176 500 3 Продолжение табл. 1 1 2 3 4 5 6 7 49. 50. 51. 52. 53. 54. 05,7A,90 8C,2B,45 60,90,1F 89,3A,54 48,6B,06 8E,2D,96 128 256 1024 64 256 512 2 2 8 8 4 4 МИЛИ 531 533 555 561 564 1500 1 2 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 3C,86,59 8A,3D,55 11,2F,97 8C,29,06 18,7C,1C 30,BA,4A 14,3D,98 8C,2A,17 56,39,92 15,7A,5A 128 64 2048 128 256 512 1024 64 512 128 2 2 8 8 4 4 2 2 8 8 МУРА 1531 1533 1561 133 134 155 176 500 530 531 3 1 2 65. 66. 67. 68. 69. 44,7D,07 97,2D,47 87,2E,5E 32,5C,86 8E,30,49 4096 64 2048 256 512 4 4 2 2 8 МИЛИ 533 555 561 564 1500 3 70. 71. 72. 73. 74. 41,6D,1D 8D,6E,16 96,39,8C 68,1C,4B 46,7E,1E 128 1024 2048 128 256 8 4 4 2 2 МУРА 1531 1533 1561 133 134 1 75. 76. 77. 78. 79. 12,7F,43 28,40,44 95,2F,5F 8F,2B,5B 8B,3E,91 512 64 1024 2048 128 8 8 4 4 2 МИЛИ 155 176 500 530 531 2 80. 81. 82. 83. 84. 50,3F,82 70,3A,57 58,39,87 07,6D,5D 8D,6E,1E 4096 512 64 1024 2048 2 8 8 2 2 МУРА 555 561 564 1500 1531 3 1 85. 86. 87. 88. 89. 90. 15,7F,57 20,90,44 88,3C,5C 43,79,05 11,7E,1A 40,3F,97 128 256 512 64 1024 2048 4 4 8 8 4 8 МИЛИ 1533 1561 133 134 155 176 2 3 Продолжение табл. 1 1 2 3 4 5 6 7 91. 92. 93. 94. 95. 47,3C,82 39,4A,97 8E,6C,06 70,1C,8B 15,3D,44 128 4096 512 128 1024 2 8 8 2 2 МУРА 500 530 531 533 555 1 96. 97. 98. 99. 100. 33,4B,86 40,2E,5E 50,3F,98 96,79,13 23,5D,87 2048 64 256 512 128 8 2 4 4 8 МИЛИ 561 564 1500 1531 1533 2 3 101. 102. 103. 104. 32,69,8A 12,3A,57 14,3E,5E 7E,1E,30 1024 2048 64 4096 2 8 8 4 МУРА 1561 133 134 155 1 105. 106. 107. 108. 109. 110. 2E,5F,18 10,7A,91 29,86,1E 8A,3C,5C 07,37,40 60,2F,86 512 128 1024 2048 64 256 4 2 2 8 2 4 МИЛИ 176 500 530 531 533 561 2 3 Способы адресации микрокоманд: 1- принудительная с двумя адресами; 2- принудительная с одним адресом; 3- естественная. 2. ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ ЭВМ 2.1. Состав устройств ЭВМ ЭВМ состоит из процессора, основной (оперативной) памяти (ОП), регистровой (сверхоперативной) памяти (РП) и средств ввода-вывода информации (рис.1). Процессор выбирает из ОП команды и выполняет все операции за исключением операций ввода-вывода (ОВВ). ОВВ инициируются процессором и выполняются средствами ввода-вывода (на рис.1 не показаны). ОП обеспечивает хранение байтов информации, предельное число которых (предельная емкость ОП) равна 224 =16777216 байт. Различные модели ЭВМ имеют разную емкость ОП: от 216 =64 Кбайта (1 Кбайт =210 байт=1024 байт) до 4096 Кбайт в старших моделях. Рис. 1. Структурная схема ЭВМ В ЭВМ адресуется каждый байт ОП. За одно обращение к ОП записываются или читаются несколько байтов информации (слово ОП): 1, 2 или 4 - в младших моделях, 4 или 8 - в старших. РП используется для увеличения быстродействия процессора и состоит из 16 регистров общего назначения РОН[0:15](0:31), каждый из которых обеспечивает хранение 32-разрядного слова, и из четырех регистров с плавающей запятой РПЗ[к](0:63), где к=0,2,4,6, каждый из которых обеспечивает хранение 64-разрядного слова. РОН идентифицируются номерами регистров - 0,1,...,15, а РПЗ - номерами 0,2,4,6. Каждому РОН соответствует одна ячейка РП, каждому РПЗ - две ячейки РП, т.е. РОН[0:15] = РП[0:15], РПЗ[0] = РП[16].РП[17], РПЗ[2] = РП[18].РП[19] и т.д. РОН используются в качестве индексных регистров, базовых регистров, а также для хранения слов и полуслов, участвующих в операциях общего назначения. РПЗ хранят только числа с плавающей запятой. 2.2. Элементы информации и их адресация В ЕС ЭВМ основным элементом информации, адресуемым и обрабатываемым как целое, является байт (рис.2). Рис. 2. Машинные элементы информации фиксированной длины Двоичные разряды байта нумеруются слева направо значения- ми 0,1,..,7. На основе байтов строятся полуслова (2 байта), слова (4 байта), двойные слова (8 байтов), называемые элементами информации фиксированной длины. Тип элемента информации (операнда) указывается кодом операции (КОП), который одновременно определяет и длину операндов (1,2,4 или 8 байтов). Байты, хранимые в ОП, адресуются двоичными числами от 0 до 2К -1, где 2К - емкость ОП. Адрес элемента информации, состоящего из нескольких байтов, определяется адресом самого левого байта. Емкость ОП не должна превышать 224 байтов (емкость ОП указана в задании на проект). Адрес, выходящий за пределы фактической емкости ОП, (что может быть результатом ошибки в программе), рассматривается как неправильная адресация (А) и выполнение программы прекращается. Элементы информации фиксированной длины должны располагаться в ОП с адреса, кратного числу байтов в элементе (правило целочисленной границы). Из этого следует, что адрес байта может быть произвольным, адрес полуслова должен быть четным, адрес слова - кратен четырем, а адрес двойного слова - восьми (рис.3). Нарушение изложенного правила рассматривается как неправильная спецификация адреса (S) и обращение к ОП блокируется. Рис. 3. Адресация элементов информации 2.3. Форматы данных и команд В ЭВМ обрабатываются данные следующих типов: целые двоичные числа, числа с плавающей запятой, десятичные числа, логические значения. Целые двоичные числа могут быть представлены в коротком и длинном форматах (рис. 4а). Нулевой разряд - знак числа. Целые числа хранятся в памяти в двоичном дополнительном коде. Числа с плавающей запятой могут быть представлены в коротком и длинном форматах (рис.4б). Нулевой разряд - знак числа. Характеристика Х(1:7) равна порядку числа, увеличенному на 64, и определяет значение порядка в диапазоне от -64 до +6З. Мантисса чисел представляется в прямом коде в шестнадцатеричной системе счисления и является числом меньше 1. Числа с плавающей запятой могут храниться в памяти ненормализованными. Рис. 4. Форматы элементов информации: а) целые числа; б) числа с плавающей запятой; в) логическая информация Логические значения (логические величины) могут иметь длину 1, 4 или 8 байтов (рис. 4в). Логическая величина передается и обрабатывается как одно целое. В ЕС ЭВМ команды представляются в пяти форматах: RR, RX, RS, SI, SS (рис. 5). (Формат SS здесь не рассматривается). Рис. 5. Форматы команд ЭВМ ЕС Первый байт команды содержит код операции КОП. Первые два разряда КОП(0:1) определяют формат команды: 00 – RR, 01 – RX, 10 – RS, 11 – SS. В зависимости от формата команды операнды выбираются из регистровой или основной памяти. Результат операции записывается обычно по адресу первого операнда. В формате SI второй операнд I2 выбирается непосредственно из команды. Поля R1, R2 и R3 являются адресами соответственно первого, второго и третьего операндов, хранящихся в регистровой памяти (РОН или РПЗ). Поля В1, В2, D1, D2, X2 содержат информацию об адресах первого и второго операндов, хранящихся в ОП (см. “Формирование адресов операндов”). 3. СТРУКТУРНАЯ ОРГАНИЗАЦИЯ ЭВМ Структура проектируемой ЭВМ в общем виде представлена на рис.6. Процессор состоит из операционного автомата (ОА) и управляющего автомата (УА), которые связаны с основной и регистровой памятью. 3.1. Структура процессора ОА процессора служит для хранения слов информации, выполнения микроопераций (МО) над ними и вычисления логических условий (ЛУ), зависящих от слов. УА обеспечивает требуемый порядок выработки наборов управляющих сигналов (следования МО) на основе заданных микропрограмм (МП). ОА процессора рекомендуется строить на основе принципа общих микроопераций [2]. ОА разделяется на две части: память ОА и комбинационную часть (рис. 6 см. в приложении). Память ОА состоит из N регистров. Рабочие регистры РА, РВ, РС и т.д. используются для хранения операндов и внутренних слов МП. Длина их определяется длиной операндов и особенностями выполняемых команд. Длина регистра команд РК назначается исходя из максимальной длины команд заданного набора. Счетчик адреса команд (СЧАК) хранит и модифицирует адрес команды. Так как адрес команды всегда кратен полуслову, то длина СЧАК определяется емкостью ОП в полусловах, т.е. log2 Е -1 , где Е- емкость ОП в байтах. Буферный регистр (БР) необходим для хранения неиспользованной части слова ОП в процессе выборки команд из ОП и имеет длину 1 или 3 полуслова при 32 или 64-разрядном слове ОП соответственно. Память ОА связана с комбинационной частью шинами А, В и С. На шины А и В посредством управляющих сигналов из множеств {a} и {b} выбираются операнды, вступающие в микрооперацию, а шина С используется для занесения результатов МО в память ОА. Операционный автомат подключен к магистрали М, связывающей его с ОП и РП через регистр Z. Комбинационная часть ОА служит для выполнения множества МО над словами, выбранными на шины А и В, и вычисления значений ЛУ из множества X, необходимых для реализации МП. Комбинационная часть ОА содержит следующие операционные элементы комбинационного типа: формирователь кодов (ФК), сдвигатель (СДВ), комбинационный сумматор (КСМ) и формирователи осведомительных сигналов (Ф). ФК необходим для формирования обратного кода слова, находящегося на шине В (F:= B ), выделения поля слова (F:=В(1:31) ), формирования константы (F:= const ). Возможна прямая передача слова с входной шины ФК на выходную (F:=В ). Все МО на ФК инициируются управляющими сигналами из множества {f}. СДВ служит для выполнения МО сдвига слова вправо или влево на нужное количество разрядов k (S:= L k ( F) или S:= R k ( F) , где k=1,2,…) и для прямой передачи слова через СДВ (S:= F ). МО сдвига инициируются управляющими сигналами из множества {s}. Если при выполнении МО сдвига необходимо запоминать значение спадающего разряда (оно может быть использовано в дальнейшем), то в структуру вводим дополнительный триггер. На рис.6 показан триггер L, связанный со старшим разрядом СДВ. МО сдвига в этом случае запишется: L. S:= L 1 ( F). Основное назначение КСМ - выполнение МО суммирования чисел (K:= A+ S или K:= A+ S+1 ). Кроме этого, КСМ может выполнять логические МО (К:=А vS ; К:=А &S; К:= A ÅS ), микрооперации счета (К:=А+1; К:= S+1 ) и прямую передачу слова на шину K (K:= A; K:= S ). Все МО КСМ инициируются управляющими сигналами из множества {k}. П – триггер для запоминания переноса при сложении (вводится в структуру ОА при необходимости). Результат МО фиксируется в промежуточном регистре Z управляющим сигналом z1 на время одного такта, а затем может быть передан в память ОА по шине С (управляющие сигналы {c}), в ОП или РП через магистраль М (управляющие сигналы {m}) или в адресный регистр АР (управляющие сигналы {r}). Например, сложная микрокоманда РА:=РВ+ R 1 ( ) может быть реализована в предлагаемой структуре ОА следующим образом: А:=РВ; В:=РС; F:= ; S:= R 1 ( F); К:=А+ S; Z:= K; РА:= Z. Хранение признаков результата, состояний процессора и режимов работы обеспечивает совокупность триггеров, образующих регистр состояний процессора (РСП). Регистр РСП представляет собой часть регистра слова состояния процессора (ССП) ЭВМ. В нем фиксируются все особые случаи выполнения команды (сигналы прерываний), устанавливаются режимы работы и состояния процессора, признак результата (см. рис.10). Если одна из заданных команд использует ССП полностью (т.е. ССП является операндом), то нет необходимости вводить в структуру регистр РСП. В этом случае СЧАК также принадлежит регистру ССП (0:63). 3.2. Оперативная память В ОП емкостью Е байтов хранятся 16, 32 или 64- разрядные слова. Слово читается и записывается в 0П всегда целиком за одно обращение к ОП. Адрес слова, к которому производится обращение, указывается в регистре адреса оперативной памяти (АОП). Длина регистра АОП вычисляется как log2 ЕС , где ЕС - емкость ОП в словах (ЕС =Е/ l, где l – длина слова ОП в байтах). Слово памяти, которое записывается или читается из ОП, размещается в регистре слова ОП (РОП). Длина регистра РОП (0:l-1), где lÎ{16,32,64}. Операция в ОП возбуждается сигналами чтения из ОП (ЧТОП) и записи в ОП (ЗПОП). Момент окончания цикла обращения к ОП отмечается сигналом занятости ОП ZОП , так как цикл ОП имеет длительность, большую такта работы процессора. Таким образом, синхронизация работы процессора и ОП обеспечивается за счет ждущих вершин графа микропрограммы. Рис.6. Базовая структурная схема процессора Обмен информацией между ОА и ОП происходит через магистраль М и промежуточный регистр Z. Адрес слова, которое необходимо прочитать или записать в ОП, предварительно формируется в адресном регистре АР, связанном с АОП шиной, управляемой сигналами из множества {r}. Длина АР равна log2 E , т.е. АР хранит адрес байта в ОП. Обмен информацией между процессором и ОП происходит следующим образом. Пусть необходимо прочитать слово информа­ции (команду, операнд) из ОП по адресу А, сформированному в одном из рабочих регистров памяти ОА. В первом такте адрес А передается в АР через регистр Z (рис. 7). Во втором такте А из АР загружается в регистр АОП и подается управляющий сигнал чтения ЧТОП. Нулевое значение осведомительного сигнала Zоп отмечает окончание цикла чтения ОП и, следовательно, прочитанное слово появилось в регистре слова ОП РОП. В третьем такте слово информации передается из РОП через магистраль М и регистр Z в память ОА. Функциональная микропрограмма чтения из ОП приведена на рис.7а. В дальнейшем МО передачи будут записываться укрупнено, т.е. вместо трех МО: М:=РОП, Z:=М, Слово:=Z запишем: Слово:=РОП. Функциональная микропрограмма записи слова в ОП по адресу A представлена на рис.7б. Рис. 7. Функциональные микропрограммы: а) чтение слова из ОП; б) запись слова в ОП по адресу А 3.3. Регистровая память РП [0:23](0:31) является внутренней (сверхоперативной) памятью процессора. Длина регистра слова РП (РРП) - 32 разряда. Адрес регистра указывается в 5-разрядном регистре адреса РП (APП). Чтение и запись в РП инициируются сигналами ЧтРП и ЗпРП, соответственно. При обращении к РОН с полусловом или словом любое значение адреса от 0 до 15 является допустимым. При обращении к РОН с двойным словом адрес должен быть четным, (если адрес у РОН нечетный – нарушение спецификации адреса (S)). При обращении к РПЗ со словом или двойным словом (числа с плавающей запя­той) адрес РПЗ должен быть четным и меньше восьми. В ином случае фиксируется нарушение спецификации адреса РПЗ (SP). Сопряжение ОА процессора с РП организовано через магистраль (рис. 1,6). Сигнал занятости РП отсутствует, т.к. цикл РП (чтение или запись) укладывается в такт процессора. В формате команды под адрес РП (номер регистра) отводится четырехразрядное поле (R, B или X). Обращение к определенному виду регистров (РОН или РПЗ) зависит от кода операции в команде (типа операнда). Для обращения к POH за целым числом, базовым адресом, индексным приращением, кодом логической величины или адресом необходимо установить старший разряд адреса АРП(1) в нуль. Для обращения к РПЗ за числом с плавающей запятой АРП(1) устанавливается в единицу. Разряды АРП(2:5) определяются по­лем R , В или Х в команде. Обращение к регистрам РП за двойным словом выполняется за два цикла. Функциональные микро­программы чтения слова из POH с адресом R и записи двой­ного слова в РПЗ с адресом R приведены на рис. 8. Рис. 8. Функциональные микропрограммы: а) чтение слова из РОН R; б) запись двойного слова в РПЗ R 3.4. Функционирование ОА во времени Такт работы процессора Т разделяется на такт управляющего автомата ТУА и такт операционного автомата ТОА (рис. 9). Такт ОА состоит из последовательности микротактов t1 , t2 и t3 . В каждом микротакте выполняются отдельные действия (этапы МО), определяемые структурой ОА (рис. 6). В микротакте t1 производится выборка слов (операндов) на шины А и В и преобразование слов в комбинационной части ОА (т.е. на ФК, СДВ, КСМ). В микротакте t2 резуль­тат с выхода КСМ передается в регистр Z, а в микротакте t3 можно передавать содержимое регистра Z в память ОА, АР или через М в ОП, РП. Длительность микротактов определяется многофазной сис­темой синхронизирующих сигналов (рис. 9б). Сигнал СУА синхронизирует работу УА, С1 - запоминание информации в регистре Z , а С2 - запись результата в память ОА, АР, РП, ОП. C указанными микротактами и синхросигналами следует связать все другие возможные передачи информации. Рис.9. Временные диаграммы работы процессора В регистре Z информация сохраняется только в течение одного такта, т.е. обновляется по каждому сигналу С1 . Для обра­щения к РП отводится такт процессорного времени. При этой цикл чтения из РП должен укладываться в микротакт t1 , а в микротакте t2 прочитанное слово заносится в регистр Z. Цикл записи в РП должен укладываться в микротакт t3 . Ана­логично распределяются во времени действия, связанные с обра­щением к ОП. Длительность микротакта t1 должна быть достаточной для выдачи слов из памяти ОА на шины А и В и выпол­нения всех преобразований на ФК, СДВ, КСМ. 4. ПОРЯДОК ВЫПОЛНЕНИЯ ОСНОВНЫХ ОПЕРАЦИЙ В ЕС ЭВМ 4.1. Структура микропрограммы Алгоритм выполнения каждой заданной команды следует представить в виде функциональной микропрограммы (Ф-МП), от­ражающей все этапы ее выполнения. Микропрограмма должна начинаться с выборки команды из ОП. Адрес команды задается содержимым СЧАК. Процедура выборки команды определяется длиной слова ОП и форматом выбирае­мой команды. Перед выборкой очередной команды необходимо проанализировать состояние процессора "РАБОТА - СТОП", так как выполнение программы процессором начинается только после нажатия кнопки "ПУСК" на инженерном пульте ЭВМ. Порядок функционирования процессора зависит от программного состояния "ОЖИДАНИЕ-СЧЕТ". В состоянии "СЧЕТ" (ССП(14)=1) происходит обычная выборка и выполнение команд. В состоянии "ОЖИДАНИЕ" команды не выполняются, процессор ждет внешний сигнал прерывания. Это состояние указывается в регистре РСП (или в слове состояния процессора ССП). Общая структура микропрограммы приведена на рис. 10. Рис. 10. Структура микропрограммы 4.2. Выборка команды из ОП Программа, представляющая собой последовательность ко­манд различных форматов, размещается в ОП. В ЕС ЭВМ исполь­зуются команды длиной 1,2 и 3 полуслова (в заданиях на проект нет команд длиной 3 полуслова). Для того, чтобы выполнить команду, ее необходимо прочитать из ОП в регистр команд (РК). В зависимости от формата выбираемой команды и ситуации, предшествовавшей выборке данной команды, необходимо выполнить различную совокупность микроопераций для передачи команды из ОП в РК. Команды любого формата начинаются с целочисленной границы полуслова. Команды длиной в полуслово в 64-разрядной ОП могут располагать­ся в виде, представленном на рис. 11. Слово ОП может содержать полностью команду или только ее часть. В 8-байтовом слове ОП могут содержаться, например, две команды формата RX, или четыре команды формата RR, или два поля по полуслову, принадлежащие различным командам, и команда RS и т.д. Структурная схема, ориентированная на реализацию выбор­ки команд из ОП с длиной слова 64 разряда, представлена на рис. 12. Функциональная микропрограмма выборки команд при­ведена на рис. 11. (емкость ОП принята равной 256 Кбайтов). Адрес выбираемой команды хранится в счётчике адреса ко­манд. СЧАК имеет длину, равную log2 E- l (17 разрядов), так как адрес команды любого формата кратен полуслову. Адрес­ный регистр основной памяти (АОП) имеет длину log2 E (15разрядов). Значение последних двух разрядов СЧАК указы­вает, с какого полуслова в ячейке ОП начинается выбираемая команда. При выполнении программы команды обычно выполняются последовательно, т.е. адрес следующей команда в СЧАК на 1 или 2 (в зависимости от длины исполняемой команды) больше адреса текущей команды. Причиной нарушения естественного по­рядка следования команд может явиться результат выполнения команды перехода. Для отметки порядка следования команд введем в структуру триггер перехода (ТП) - один из разрядов регистра РСП. Если команды выполняются последовательно, то ТП=0. В процессе выполнения команда перехода при занесении в СЧАК адреса перехода ТП устанавливается в 1. В структуре ОА процессора присутствует буферный регистр (БР), который используется только на этапе выборки команды из ОП. В БР заносится часть слова ОП с целью исключения повтор­ного чтения ячейки ОП. В приведенном примере (слово ОП 8 бай­тов) длина БР - 3 полуслова. При длине слова ОП 2 байта необ­ходимости в БР не возникает. Если ТП=0, то содержимое БР ис­пользуется для формирования команды в РК. Если ТП=1, управле­ние передано команде, отсутствующей в БР и, следовательно, его содержимое не может быть использовано. При выборке команды адресуемое полуслово (вся команда формата RR или половина команды RX,RS,SI) передает­ся в РК (0:15) (см. рис. 11, 12 в приложении). Затем анализируется длина команды (РК(0:1)=00 для команд формата RR) и либо выборка заканчивается увеличением СЧАК на 1, либо команда в РК допол­няется вторым полусловом, а СЧАК увеличивается на 2. Наибольшую сложность представляет случай, когда команда начинается с последнего полуслова в ячейке ОП и длина ее рав­на слову. Из БР берется первое полуслово выбираемой команды. Это полуслово, т.е. БР (32:47), передается в регистр команд РК (0:15), СЧАК увеличивается на I и происходит повторное обращение к ОП. Из вновь прочитанного слова ОП первое полусло­во передается в разряды РК (16:31), а остальные три полусло­ва, являющиеся новыми командами, запоминаются в БР. В Ф-МПе следует провести разметку операторных и условных вершин: МОi отметить управляющим сигналом уi , МКj (операторную вершину) – Yj , а ЛУк (условную вершину) - осведомительным сигналом Хк . При этом одинаковые МО и ЛУ отмечаются одинаково во всех микро­программах, а каждую следующую МК Yj в одной микропрограмме отмечают с добавлением штриха (т.е. Y1 j ) (см. рис. 11, 13 в приложении). 4.3. Формирование адресов операндов Способ формирования адресов операндов определяется форматом исполняемой команды. В формате RR оба операнда нахо­дятся или в РОН, или в РПЗ. РОН адресуются числами от 0 до 15. РПЗ имеют адреса 0, 2, 4, 6. Адрес РПЗ может быть задан некорректно, если он отличен от вышеназванных четырех чисел. Этот случай вызывает прерывание выполнения команды и называется неправильной спецификацией с плавающей запятой (SP). При формировании адреса РП старший разряд АРП(I), определяющий обращение к РОН или РП3, задается кодом операции, а четыре младших разряда - полем R команды. В формате RX второй операнд находится в ОП. Исполнительный адрес в этом случае вычисляется сложением трех составляющих: A2=D2+[POH(B2)]+[POH(X2)]. Здесь D2 - сме­щение, непосредственно находящееся в формате команды, а поля Х2 и В2 команды определяют номера РОН, в которых хранятся значения индексного приращения и базового адреса соответствен­но. В формате RS второй операнд также находится в ОП, но, в, отличие от формата RХ, адрес А2 не индексируется и A2=[РОН(В2)]+ D2 . В формате SI первый операнд находится в ОП и его адрес А1=[РОН(В1)]+ D1 . Второй операнд I2 содержится непосредственно в формате команды в разрядах (8:15) и имеет длину 1 байт. Если поля В1, В2 или Х2 равны нулю, то соответствующая компонента -адреса также равна нулю, т.е. базовые адреса и ин­дексные приращения не могут размещаться в РОН(0). 4.4 Система команд ЕС ЭВМ Операции с целыми числами С помощью набора команд с целыми числами осуществляются операции двоичной арифметики над операндами, которые, с одной стороны, могут быть адресами, индексами и счетчиками, а с дру­гой - представлять собой целые двоичные числа со знаком. На­бор команд предусматривает загрузку, сложение, вычитание, сравнение, умножение, деление, запись в память (передачу опе­ранда из РП в ОП) и сдвиги арифметические. Операции двоичной арифметики выполняются как операции над целыми двоичными числами. Числа хранятся в памяти и вступают в операцию в дополнительном коде. Для выпол­нения операций следует использовать алгоритмы, описанные в [2,6]. Разрешается использовать алгоритмы умножения и деле­ния в прямых кодах, для чего операнды перед началом операции следует преобразовать в прямой код, а отрицательный результат - в дополнительный код. Операции с плавающей запятой Эти команды служат для выполнения арифметических и по­сылочных операций над числами с плавающей запятой, представленными в коротком и длинном форматах. Длина операнда определяется кодом операции. Так как характеристика представляет собой целое число, а мантисса - число с фиксированной запятой, то действия над числами с плавающей запятой Рис. 12. Структурная схема выборки команд из ОП (длина слова ОП 8 байтов) производятся от­дельно над характеристиками и мантиссами по правилам обработ­ки целых чисел и чисел с фиксированной запятой. При выполнении арифметических операций контролируются случаи переполнения и исчезновения порядка. Если действия над характеристиками проводятся в дополнительном модифици­рованном коде, то о переполнении порядка свидетельствует появление кода 01 в двух знаковых разрядах модифицированного кода, а код 11 указывает исчезновение порядка [2,6,8]. При выполнении всех операций над знаками чисел, а также в операциях сложения, вычитания и сравнения устанавливается признак результата в регистре РСП. Логические операции Набор команд логической обработки данных предназначен для выполнения широкого класса логических операций, в кото­рых операнды рассматриваются как группы байтов и, за исклю­чением команд редактирования, трактуются как нечисловая ин­формация. Набор логических операций включает в себя пересылки, сравнение кодов, побитовые логические операции, проверки битов и сдвиги кодов. В результате выполнения всех операций логического срав­нения, поразрядных операций, а также операций проверки устанавливается признак результата. Операции переходов Набор команд переходов предназначен для выбора одного из двух направлений продолжения программы (ветвление прог­рамм или организация циклов). Кроме того, с помощью этих команд организуются обращения к подпрограммам (переход с возвратом). Переход реализуется путем засылки адреса перехода в качестве нового адреса команды в СЧАК. В процессе выполнения всех операций в регистре РСП устанавливаются признаки состояния процессора и признаки перехо­да, такие как: А - неправильная адресация; S - неправильная спецификация; SР - неправильная спецификация с плавающей запятой; Е - переполнение порядка; LS - потеря значимости; U - исчезновение порядка; FK - особый случай деления в плавающей запятой; IF - переполнение в операции с фиксированной точкой; IK – особый случай деления с фиксированной точкой; ТП – значение триггера перехода; ПрР(1:2) – признак результата. 4.5. Выполнение команд Ф-МПа каждой отдельной команды разрабатывается на основе словесного алгоритма ее выполнения [1]. Чтение операнда из ОП и запись результата в ОП по исполнительному адресу А1 или А2 производится после проверки адреса на правильность адресации (А) и спецификации (S). При правильной адресации адрес не должен быть длиннее адреса байта ОП (в нашем примере - 18 разрядов). Иначе возникает попытка обращения за пределы физической емкости ОП. Проверка адреса на правильность спецификации связана с длиной операнда (см. рис.3). Обмен с ОП происходит только словами ОП. Если операндом команды является часть слова ОП, то необходимо прочитать в регистр Z все слово ОП, а затем выделить его часть (байт, полуслово) в соответствии с младшими разрядами адреса. При записи в ОП единицы информации короче длины слова ОП содер­жимое ячейки ОП читается в регистр Z и соответствующая часть слова ОП заменяется операндом. Таким образом сформиро­ванное слово ОП записывается в ту же ячейку ОП. Если длина операнда превышает длину слова памяти, то чтение и запись производится за несколько обращений к памяти. В качестве примера рассмотрим выполнение команды “Сложение” (формат RX, код операции 5А). Словесный алгоритм в упрощенном виде выглядит следующим образом. Второй операнд складывается с первым операндом, и сумма помещается на место первого операнда. В сложении участвуют все 32 бита каждого операнда. Необходимо выявить переполнение, которое вызывает программное прерывание. При переполнении полученный знаковый бит суммы остается без изменения. Переполнение возникает, если при сложении положительных чисел сумма получается с отрицательным знаком, а при сложении отрицательных чисел с положительный знаком. Признаки результата: 0 - сумма равна 0; 1 - сумма мень­ше 0; 2 - сумма больше 0; 3 - переполнение. Программные прерывания: доступ (неправильное обращение к ОП, т.е. А и S); переполнение с фиксированной точкой (IF).Ф-МП выполнения операции сложения целых чисел приведена на рис. 13. После выборки команды формата RХ из ОП в РК (см. рис. 11 в приложении) формируется исполнительный адрес второго операнда А2 путем базирования и индексирования в рабочем регистре РА памяти ОА. С учетом длины регистра РА (0:31) адрес А2 проверяется на правильность адресации и спецификации. Если адрес сформирован неверно, в регистре РСП устанавливается причина прерывания выполнения команды (А или S ).Затем производится чтение второго операнда длиной 4 байта из ОП с длиной слова 8 байтов в рабочий регистр РА. Пер­вый операнд читается из РОНа с адресом R 1 в рабочий регистр РВ (0:31). Операнды (целые числа со знаком) проверяются на равенст­во 0. Если хотя бы один из операндов равен 0, устанавливает­ся признак результата в регистре РСП и результат записывается в РОН с номером R1 . Если операнды не равны 0, то производится их сложение и сумма формируется в регистре РА. Так как необходимо выявить переполнение, которое может возник­нуть только при сложении чисел с одинаковыми знаками, в микропрограмме (рис.13 в приложении) фигурируют две микрокоманды сложения ( Y31 и Y1 31). В соответствии со значением суммы устанав­ливается признак результата и сумма записывается на место первого операнда. Рис.13. Микропрограмма выполнения команды "Сложение" (слово ОП - 8 байтов) Продолжение рис.13. 5.ОБЬЕДИНЕНИЕ СТРУКТУРНО-ФУНКЦИОНАЛЬНЫХ МИКРОПРОГРАММ С ИСПОЛЬЗОВАНИЕМ МАТРИЧНЫХ СХЕМ АЛГОРИТМА Исходным материалом для построения объединённой функциональной микропрограммы (Ф-МП) являются разработанные Ф-МП отдельных операций [1]. Каждая Ф-МП должна быть размечена: микрокоманды (операторные вершины) – символами из множества {Y}, логические условия – символами из множества осведомительных сигналов {x} или переменными кода операции {p}. Одинаковые микрокоманды отмечаются одними и теми же символами Yl в разных Ф-МП. Если в одной Ф-МП встречается несколько одинаковых операторных вершин Yl, то каждая последующая из них обозначается символом Yl c добавлением штриха ( Yl 1 , Yl 11 и т.д.) Размеченные Ф-Мпы называются граф-схемами алгоритма (структурно-функциональными микропрограммами СФ-МП). Алгоритм объединения СФ-МП рассмотрим на примере объединения трёх ГСА (ГСА1, ГСА2, ГСА3 ), представленных на рис.14а,b,c. Объединение выполняется в несколько этапов. 5.1. Построение матричных схем алгоритма (МСА) Для каждой ГСА Гq строится МСА Мq . Мq – квадратная матрица, строки которой отмечены операторами Y0 , Y1 ,…, Yt , а столбцы – Y1 , …, YT , YK (здесь Yt – микрокоманда (оператор) ГСА Гq , t=1,…T; Y0 и YK - начальный и конечный операторы, соответственно. На пересечении строки Yi и столбца Yj матрицы записывается функция перехода от оператора Yi к оператору Yj МСА М1 , М2 , М3 приведены в табл.2,3,4. Если в одной ГСА Гq имеется несколько операторов Yi , Yi 1 , Yi 11 и т.д., то в дальнейшем они рассматриваются как различные. Если в некоторой строке МСА переменная xi встречается либо только в прямом (xi ), либо только в инверсном значении ( ), то эта переменная определяет ждущую условную вершину ГСА. Каждая МСА Mq ( q=1,…,Q ) кодируется вектором, длина которого N ]log2 Q[.Закодируем М1 , М2 , М3 следующим образом: М1 -(00); М2 -(11); М3 -(01). Каждой МСА ставится в соответствие определяющая конъюнкция Pq = . В нашем примере P1 = ; Р2 =р 1 р 2 ; Р3 = . Рис.14а. Исходные граф-схемы алгоритмов(ГСА1) Рис.14б.Исходные граф-схемы алгоритмов (ГСА2) Таблица 2 Y1 Y2 Y3 Y4 Y5 Y6 YK Y0 x1 x3 x6 Y1 x2 Y2 x3 x6 Y3 x3 x6 Y4 x4 x3 Y5 x4 Y6 1 Таблица 3 Y1 Y2 Y 1 2 Y3 Y4 Y7 YK Y0 x7 Y1 x2 Y2 x5 Y 1 2 1 Y3 x5 Y4 x4 Y7 1 Таблица 4 Y1 Y2 Y3 Y4 Y7 YK Y0 x1 x5 Y1 x2 Y2 X5 Y3 X5 Y4 x4 Y7 1 5.2. Построение объединенных подматриц Задача объединения ГСА Г1,…, ГQ может быть разбита на несколько независимых подзадач меньшей размерности. Для этого исходные МСА Мq (q=1,…,Q) разбиваются на подматрицы Mq 1 ,…, Mq Tq таким образом , что для любых двух подматриц Mq P и Mq S (p,s {1,…,Tq }) пересечение множеств исходящих и входящих операторов пусто: Aq P Aq S = , Bq P Bq S = (где {A} –исходящие, а {B} – входящие операторы). Метод разбиения для МСА М1 иллюстрируется рис. 15. Подматрицы, полученные в результате разбиения МСА М1 , М2 , М3 , приведены на рис.18. На множестве всех полученных таким образом подматриц (см. рис.18) введём отношение объединимости, согласно которому две подматрицы Mq S и Mr f объединимы (Mq S Mr f ), если и только если пересечение множеств их исходящих или входящих операторов не пусто: (( Aq S Ar f ) ( Bq S Br f ))=1, где Aq S (Bq S ) и Ar f (Br f ) - множества исходящих ( входящих ) операторов подматриц Mq S и Mr f соответственно . Очевидно, что это отношение рефлексивно , симметрично, но не транзитивно. Построим граф этого отношения. Каждой подматрице ставится в соответствие вершина графа. Две вершины Mq S и Mr f соединяются ребром, если Mq S Mr f (рис.16). Тогда, очевидно, для нахождения множества всех объединимых подматриц необходимо найти все компоненты связности этого графа. Подматрицы, попавшие в одну компоненту , подлежат объединению. В графе на рис. 16 четыре подграфа( подграф может состоять и из одной изолированной вершины). Значит необходимо решать 4, но существенно более простые задачи объединения следующих подматриц: ; ; ; ; Таким образом, множество объединимых подматриц , , порождает одну объединённую подматрицу и т.д. Построение объединенных подматриц выполняется следующим образом. 1). Строки объединённой подматрицы обозначим операторами , входящими в объединение множеств исходящих операторов в подматрицах , порождающих объединенную подматрицу . Точно так же столбцы её обозначим операторами, входящими в объединение множеств входящих операторов в порождающих подматрицах. 2).Элемент ij (т.е. стоящий на пересечении Yi и Yj ) объединенной подматрицы равен , где ( ij )q -элемент МСА Мq , стоящий на пересечении строки Yi и столбца Yj . Объединенные подматрицы М0 1 , …, М0 4 приведены на рис.19. Каждый оператор Yi отмечает только один столбец и только одну строку во всем множестве объединенных подматриц, что вытекает из способа их построения. 5.3. Учет распределения сдвигов Так как выбранные коды МСА являются кодами операций для каждой из реализуемых команд, ни один оператор внутри граф-схем не меняет значений переменных p1 ,…,pN (относительно этих переменных имеем пустое распределение сдвигов). В связи с этим полученные объединенные подматрицы можно упростить. Так переход к Y2 1 в подматрице М0 1 происходит всегда при р1 =р2 =1 ( в столбце Y2 1 не встречаются другие определяющие коньюнкции , кроме р1 р2 ). Поэтому в строке Y2 1 (см. подматрицу М0 4 ) заменяем р1 р2 на 1. Аналогичным образом просматриваются все столбцы в подматрицах М0 1 , …, М0 4 и делаются соответствующие упрощения в строках. Удаляемые переменные и обведены кружком. 5.4. Построение системы скобочных формул перехода Тот факт, что от любого оператора ГСА или МСА Yi (i=0,1,…,T) возможен переход к операторам из множества {Y1 ,…Yj ,…,YT , YK } можно описать с помощью выражения Yi , (1) где -функция перехода от Yi к Yj ; Yj - отмеченная булева функция. Формулы вида (1) носят название формул перехода. Множество формул перехода для всех i=0,1,…,T образует систему формул перехода . Систему формул перехода для объединенной ГСА получим в виде подсистем формул перехода для каждой из объединенных подматриц. Например, для подматрицы М0 3 имеем формулу перехода: = . (2) Представление формулы перехода в виде Yi xl A l B, где xl {x1 ,…,xL ,p1 ,p2 }, а A и B - подформулы перехода, не зависящие от xl , носит название приведения (разло­жения) формулы перехода по переменной xl . Продолжая приве­дение подформул А и B по другим переменным до тех пор, пока во внутренних скобках не окажутся выражения вида (xp Yn p Yr ), xp { x1 ,…,xL ,p1 ,p2 }; Yn ,Yr {Y1 ,…,YT ,YK }, получим скобочную Формулу перехода для оператора Yi . Если в некоторой строке объединенной подматрицы во всех ненулевых членах некоторая переменная xp встречается толь­ко без инверсии (xp ) или только с инверсией ( p ), этой переменной в ГСА соответствует ждущая условная вершина, и при получении скобочной формулы перехода эту переменную нужно прежде всего вынести за скобку. Получим выражение вида Yi xp (А) или Yi p (A), где А - подформула, не содержащая xp . При получении подсистемы скобочных формул перехода необ­ходимо учесть их неполную определенность, которая может воз­никнуть в следующих случаях: I). Если число Q объединяемых ГСА меньше 2N , т.е. не все наборы значений переменных p1 ,…,pN используются для кодирования МСА M1 ,…,MQ , все формулы перехода не определены на неиспользуемых наборах значений переменных p1 ,…,pN . 2). Если оператор Yt не встречается в каких-либо МСА Mq (q=1,…,Q),то формула перехода для Yt не определена на тех наборах значений переменных, которыми закодирована МСА Мq . Так, выражение (2), дополненное термами, включающими в себя неиспользованный код операции , имеет вид: . Это дает возможность сократить переменную p1 . После приведения к скобочной форме формулы перехода для Y4 получим: . (3) Скобочной формуле перехода однозначно соответствует подграф ГСА (рис.17). Рис. 15. Разбиение МСА М1 Рис. 16. Граф объединяемых подматриц Рис. 17. Подграф объединенной ГСА На основе объединенных подматриц получаем следующую сис­тему скобочных формул перехода: М : ( (p2 ( ) ( ( ))) ( ( ( ))); Y2