автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Интеллектуальные системы логического проектирования Ts - согласованных цифровых устройств

Нижегородский государственный технический университет

На правах рукописи

БАЖАНОВ Юрий Сергеевич

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ Т8- СОГЛАСОВАННЫХ ЦИФРОВЫХ УСТРОЙСТВ

Специальность 05.13.01- «Управление в технических системах»

Автореферат диссертации на соискание ученой степени доктора технических наук

Нижний Новгород 1998

Работа выполнена на кафедре «Вычислительная техника» Ниж* городского государственного технического университета

Научный консультант:

член-корреспондснт РАН, профессор Кондратьев В. В.

Официальные оппоненты:

доктор технических наук, профессор Домрачев В.Г., доктор технических наук, профессор Кирьянов К.Г., доктор технических наук, профессор Иванов А.Л.

Ведущая организация: Научно- производственное предприяти «Полет» (г. Н. Новгород).

Защита состоится "Я" ол^яШ 1998г. в час. на заседанш диссертационного совета Д.063.85.02 в Нижегородском государственно* техническом университете по адресу: 603600, г. Нижний Новгород, ГСП 41, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке НГТУ Автореферат разослан

1998г.

Ученый секретарь диссертационного совета

А.П. Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА НАУЧНОГО НАПРАВЛЕНИЯ И ВЫПОЛНЕННЫХ ИССЛЕДОВАНИЙ

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

Вопросы структурно- временного согласования (кратко TS-согласования) цифровых вычислительных устройств и систем (ЦВУ и ЦВС) получили фундаментальное развитие в работах А.Г. Алексенко, С.И. Баранова, В.М. Глушкова, В.А. Горбатова, Е.А. Дроздова, А.Д. Закревского, У. Квайна, В.Г. Лазарева, О.Б. Лупанова, С.А. Майорова, Р. Миллера, В.А. Мищенко, Дж. Неймана, Д.А. Поспелова, Д. Рота, А. Фридмана, C.B. Яблонского и других российских и зарубежных ученых.

Высказывание о необходимости структурно- временного согласования ЦВУ и ЦВС восходит еще к Дж. Фон Нейману, отмечавшему в своей теории организации сложных автоматов, "... что одним из решающих свойств вычислительных машин является равновесие: равновесие между быстродействием отдельных частей, баланс между быстродействием одной части и размерами других частей".

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

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

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

возложенные на систему вычисления с минимальными аппаратурными затратами за время, не превышающее наперед заданной величины.

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

Автоматический процесс формирования логики работы ТБ-согласованных ЦУ в настоящее время не мыслим без использования интеллектуальных систем проектирования (ИСпроект). Интерес к разработке интеллектуальных систем логического проектирования ЦУ обусловлен тем, что ФЛП является достаточно сложным и трудоемким процессом, остающимся до сих пор слабо алгоритмизированным и носящим эвристический характер, так как большая доля работ по синтезу логических схем ЦУ выполняется не машиной, а человеком.

Огромную роль в процессе поиска хороших логических схем (ЛС) играет опыт. За долгие годы работы многих поколений разработчиков в области ФЛП ЦУ накоплен значительный по объему опыт синтеза ЛС, предназначенных для реализации многих типовых функций. Наличие такого опыта, разбросанного по многочисленным литературным источникам и сосредоточенного в головах высококвалифицированных специалистов по синтезу ЛС, служит весьма благодатной почвой для организации и построения ИСпроект, позволяющих овеществить этот опыт и сделать его доступным для менее квалифицированных специалистов.

Основу построения различных интеллектуальных систем, в том числе и ИСпроект ЦУ, составляют методы искусственного интеллекта. В рамках этого научного направления получены значительные результаты благодаря трудам как отечественных, так и зарубежных ученых. Не претендуя на перечисление всех ученых, внесших весомый вклад в разработку теории и практики интеллектуальных систем, отметим только тех специалистов, работы которых были прямо или косвенно использованы автором в его исследованиях по проблеме построения интеллектуальных систем логического проектирования Т8- согласованных ЦУ. Это И. Братко, В.Н. Вагин, Е.И. Ефимов, Л.Т. Кузин, В.Е. Кузнецов, В.М. Курсйчик, Ж.Л. Лорьер, М. Минский, Н. Нильсон, С. Осуга, Э.В. Попов, Г.С. Поспелов, Д.А. Поспелов, П.Г. Уинстон, Д. Уотермен, X. Уэно, Дж. Эти, А. Эндрю, Р. Эшби и др.

В проведенных автором исследованиях процедуры ТБ- согласования играют необходимую роль одновременно как для собственно ТБ-согласования объектов проектирования, так и для построения соответствующих машин вывода самих ИСпроект. В последнем случае процедуры

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

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

В своем развитии методы технической диагностики ЦУ прошли значительный путь: от традиционных детерминированных методов (большинство из них достаточно хорошо исследованы и изложены в фундаментальных работах P.C. Гольдмана, В.А. Гуляева, В.И. Казначеева, В.В. Карибского, П.П. Пархоменко, А.Н. Скляревича, Е.С. Согомоняна, Н.А. Соловьева, В.Ф. Халчева, Г. Чжена, В.П. Чипулиса, C.B. Яблонского и др.) до компактных вероятностных методов, использующих случайные входные сигналы (в этом направлении наибольшую известность получили работы В. Агравала, М.С. Берштейна, Б.Л. Долинского, Дж. Лоска, К. Паркера, А.М. Романкевича, Дж. Савира, В.Н. Ярмолика и др).

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

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

На защиту выносятся:

1. Потоковый подход к TS- согласованию цифровых вычислительных устройств.

2. Методология высокоуровневого синтеза параллельных проблемно-ориентированных цифровых вычислительных систем на базе потокового подхода к их TS- согласованию.

3. Концептуальная и пользовательская модели интеллектуальных систем логического проектирования операционных элементов комбинационного типа.

4. Методология организации и построения основных компонент интеллектуальных систем логического проектирования цифровых устройств: диалогового процессора, планировщика, базы знаний, базы данных, интерпретатора, ТБ- согласователя и др.

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

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

7. Методы вероятностного логического анализа сложных комбинационных устройств с использованием только внешних выходов объектов анализа.

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

Научная новизна. В диссертационной работе получены следующие основные результаты, характеризующиеся научной новизной:

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

2. Разработан потоковый подход к ТБ- согласованию параллельных проблемно- ориентированных цифровых вычислительных систем, позволяющий выполнить синтез ЦВС, начиная от обычной последовательной граф- схемы алгоритма (ГСА) и заканчивая параллельной Тв- согласованной структурой, реализующей заданную ГСА.

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

4. Разработан специализированный язык представления знаний в области синтеза ОЭКТ на основе компактных линейных деревьев, допускающих в отличие от обычных линейных деревьев такие конструкции как: одиночный и кратный циклы вне линейных деревьев, а также циклы произвольной вложенности внутри линейных деревьев.

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

6. Разработана модель экспертного логического синтезатора, предназначенного для быстрого синтеза ТБ- согласованных ЦВУ с минимальным участием человека.

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

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

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

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

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

Практическая значимость и ценность работы заключается:

• в разработке базовых структурных моделей ОЭКТ, рассчитанных на блочную компоновку микроопераций, что значительно упрощает введение процедуры замены эквивалентных микроопераций одним общим оператором;

• в разработке системы базовых микроопераций ИСпроект, используемой в качестве входного языка ИСпроект ОЭКТ;

• в создании базы знаний, содержащей свыше 300 правил (продукций), отражающих имеющийся опыт синтеза ОЭКТ. Многие из этих правил выкристаллизовывались поколениями разработчиков и прошли проверку временем;

• в разработке конкретной версии экспертного логического синтезатора "ЭЛС", вобравшей в себя предложенные методы организации и построения математического и алгоритмического обеспечения интеллектуальных систем логического проектирования цифровых устройств;

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

Реализация результатов работы. Результаты исследований по разработке методов построения интеллектуальных систем логического проектирования Т8- согласованных цифровых устройств реализованы при выполнении НИР "Разработка теории интеллектуальных систем проектирования высоконадежных и отказоустойчивых мультипроцессорных устройств обработки информации и управления", проводимой на факультете информационных систем и технологий Нижегородского государственного технического университета и финансируемой в рамках единого заказ- наряда (названная тема входит в раздел "Информационные технологии и электроника" по группе "Системы искусственного интеллекта" перечня критических технологий федерального уровня, одобренного правительственной комиссией по научно- технической политике от 21.07.1996 г. №2727п-П8), в программном продукте НИР "Разработка экспертной системы для автоматического функционально-логического проектирования цифровых устройств с применением базовых матричных кристаллов" (х/д Н/075МС, 1991.- 967 е.), а также применяются в учебном процессе при чтении курсов лекций "Цифровые автоматы" и "Основы теории интеллектуальных вычислительных систем" для студентов специальности 22.01- "Электронные вычислительные машины, системы, комплексы и сети" НГТУ.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всесоюз. науч.-техн. конф. "Дальнейшее развитие и внедрение новой техники приемных устройств" (Москва- Горький, 1977); 2- ом Всесоюз. науч.- техн. семинаре "Оптимизация технических систем" (Винница, 1979); науч.- техн. семинаре "Обеспечение надежности и качества систем методами технической диагностики" (Челябинск, 1979); 4- ом Всесоюз. совещании по технической диагностики (Черкассы, 1979); семинаре "Техническая диагностика и эксплуатация вычислительных и управляющих систем" по комплексной проблеме "Теоретическая электротехника, электроника и моделирование" Сектора электроники и моделирования Института электродинамики АН УССР (Киев, 1979, 1982); 5- ом Всесоюз. совещании по статистическим методам в процессах управления (Алма-Ата, 1981); семинаре "Теоретическая кибернетика" Казанского госуниверситета (Казань, 1981); 3- м Всесоюз. симпозиуме "Вероятностные автоматы и их приложения" (Казань, 1983); науч.- техн. конф. "Вероятностные автоматы и их приложения" (Батуми, 1986); 8- й Всесоюз. конф. "Проблемы теоретической кибернетики" (Горький, 1988); Международном форуме информатизации "МФИ- 92" (Н. Новгород, 1992); науч.- техн. конф. факультета радиоэлектроники и технической кибернетики НГТУ (Н. Новгород, 1980, 1996, 1997); науч.- техн. конф. факультета информационных систем и технологий НГТУ (Н. Новгород, 1998).

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

Структура и объем работы. Диссертационная работа состоит из введения, семи глав, заключения, списка литературы из 277 наименований и приложения; содержит 362 машинописные страницы основного текста, включая 80 рисунков и 14 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Введение. Рассматривается актуальность, цель и направление исследований, научная новизна и практическая ценность результатов диссертационной работы, реализация результатов и апробация работы, публикации, объем и структура диссертации.

Первая глава посвящена анализу современного состояния, тенденций и перспектив развития методов проектирования цифровых устройств.

Анализ новых информационных технологий решения задач на ЭВМ (§ 1.1) показывает, что одной из центральных проблем развития и применения средств вычислительной техники в настоящее время является

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

§ 1.2 посвящен вопросам интеллектуализации систем логического проектирования ЦУ. Анализ перспектив развития аппаратного подхода в проектировании ЦВУ и ЦВС показывает, что преимущества этого подхода позволяют отказаться от применения машин только последовательного действия и начать переход к параллельным ЭВМ на пути широкого применения технологии непосредственного "транслирования" алгоритмов в специализированные процессорные модули массовым пользователем. Такой переход осуществим только с помощью организации и построения ИСпроект ЦУ. Традиционные способы построения ЦУ базируются, как правило, на процедурных знаниях теории и практики синтеза и анализа логических схем. С ростом сложности объектов синтеза традиционные алгоритмические методы испытывают серьезные вычислительные трудности. Особенно это касается операционных автоматов, обладающих практически бесконечной памятью. Узким местом здесь является отсутствие развитой, с точки зрения синтеза реальных ЦУ, теории бесконечных автоматов. Вместе с тем замечено, что человек справляется с подобными задачами сравнительно легко. Более того, целыми поколениями разработчиков накоплен и систематизирован значительный по объему опыт синтеза таких объектов. Все это свидетельствует в пользу того, чтобы для синтеза логических схем ЦУ (в первую очередь операционных автоматов) использовать декларативные (описательные) знания высококлассных специалистов- экспертов, отражающие имеющийся опыт логического проектирования подобных объектов. ИСпроект ЦУ должны строиться и развиваться как гибридные экспертные системы, аккумулирующие в себе и декларативные (для синтеза ОА), и процедурные (для синтеза УА) профессиональные знания из области проектирования цифровых устройств.

В § 1.3 отмечается роль методов ТБ- согласования при построении машины вывода ИСпроект ЦУ и необходимость разработки потокового подхода к ТБ- согласованию ЦУ. Машины вывода интеллектуальных систем логического проектирования ЦУ должны строиться на базе методов структурно- временного согласования ЦУ. Для этого необходима разработка теории структурно- временного согласования ЦВУ и ЦВС на основе потокового подхода, позволяющего проводить согласование на

основе простых итеративных преобразований потока в сетях;

В § 1.4 приведен сравнительный анализ методов функционально-логического анализа ЦУ. Отмечается, что наряду с рассматриваемыми задачами синтеза важной проблемой, решаемой в рамках логического проекгирования, является анализ ЦУ. Для ранения задач функционально-логического анализа ЦУ интеллектуальные системы логического проектирования должны опираться не только на детерминированные входные сигналы, но и на случайные с широким применением вероятностных методов принятия решений. Известные методы анализа ЦУ с помощью случайных входных сигналов разработаны не достаточно. Отсутствуют методики построения проверяющих и различающих совокупностей контрольных точек, расчета параметров вероятностного логического анализа комбинационных схем, обеспечивающих при равновероятных входных сигналах обнаружение и поиск неисправностей с вероятностью ошибки, не превышающей наперед заданной величины. Необходима разработка методов вероятностного функционального анализа сложных комбинационных схем со многими выходами по обобщенному параметру, полностью не требующего перебора неисправностей.

Глава 2 посвящена ТБ- согласованию цифровых вычислительных устройств. В качестве объектов ТЯ- согласования рассматриваются ЦВУ, состоящие из двух автоматов: операционного (ОА) и управляющего (УА). ОА- композиция п операционных элементов накапливающего типа (ОЭНТ). В свою очередь каждый ОЭНТ состоит из трех компонент: блочной комбинационной схемы (КС) Ф^ (ОЭКТ), регистра и произвольной КС КС Ф, в зависимости от заданной микрооперации Ут^У) формирует сигналы возбуждения, управляющие переключением элементов памяти, из которых состоит регистр 8,. КС Ч'; вычисляет логические условия X,-. Структура УА, кроме элементов памяти, содержит еще в зависимости от типа УА либо одну КС (КС УА типа Мили), либо две (КСЬ КС2 УА типа Мура). Если считать триггеры ЦВУ заданными и неизменными, то из сказанного следует, что ТЯ- согласованию подлежат блочные КС Ф, и произвольные КС ОА совместно с произвольными комбинационными схемами КС или КС! и КС2 УА.

В § 2.1 показано, что Т8- согласование блочных КС (ОЭКТ) может быть выполнено путем построения и оптимизации простых и расширенных сетевых графиков на основе эффективного потокового алгоритма Форда- Фалкерсона- Келли (ФФК). Блочная КС строится из комбинационных блоков (КБ), каждый из которых реализует определенную микрооперацию типа сложения, сдвига, сравнения и т.п. Функциональная схема (ФС) блочной КС состоит из объектов двух видов: вершин (КБ), обозначаемых кружками, и соединяющих их дуг, обозначаемых стрелками. КБ выполняет некоторую вычислительную

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

Переход от ФС к ее простому сетевому графику (СГ) выполняется в следующей последовательности:

1. Каждый КБ а, связанный с несколькими блоками аь аз, ..., аь дублируется. Причем вершины а- а' соединяются сплошными стрелками, а а'- а.ь а'- а2, ..., а'- ак- пунктирными. Прежние связи по выходу КБ а

удаляются.

2. Удаляются все внешние входы ФС.

3. Все вершины, у которых отсутствуют входные дуги, объединяются в одну, которая служит начальной вершиной сетевого графика.

4. Все внешние выходы ФС замыкаются на дополнительно введенную вершину, которая играет роль конечной вершины сетевого графика.

5. Все вершины сетевого графика нумеруются числами натурального ряда. Номер 1 присваивается начальной вершине. Конечная вершина получает максимальный номер.

Каждая сплошная стрелка простого СГ соответствует вычислительной работе того или иного КБ ФС. Пунктирные же стрелки сетевого графика соответствуют фиктивным работам, имеющим нулевую длительность и стоимость.

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

Дуги расширенного СГ взвешиваются тремя рациональными числами: Су и ср|-, к = 1,т(^), где

э . — э

ц,г + 1 ----- -

а* =

У

,к = 1 4« ,к = 1

,к=2 ................... ,с;-=< с ■„ -с.., УД ц,! ,к =2

с! у,т(1,х)-1 и ,к = т(^)-1 Су>™('>1)-1 -е.. ,. _ „,к = т(1,¡)-1

,к= т(^) 00 ,к = т(^)

а и , - соответственно сложность и задержка некоторой реализации КБ а, совпадающей с £-м узлом аппроксимации, причем

5У,ш00)-1>--'>8о,1> а <•••<<%] •

В приведенных соотношениях сН и ср^ - пропускная способность и

поток к-й дуги, соединяющей вершины 1 и ], соответственно. Заметим, что если |Иа|=1, то с1-, = [ ,су = со, а для фиктивной работы с!^ = 0,Су = со.

ТБ-согласование блочных КС выполняется в три этапа: 1- грубое приближение, 2- уточнение и 3- доводка. Каждый этап реализуется в два приема:

^предварительная оптимизация сетевого графика на основе его расширенной модели с помощью алгоритма ФФК;

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

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

Описанный метод ТБ- согласования ОЭКТ допускает обобщение на случай произвольных КС.

Это обобщение рассматривается в § 2.2, что позволяет организовать ПЧ- согласование как отдельных частей ЦВУ (ОЭНТ, ОА, УА), так и ЦВУ в целом.

Предварительно рассмотрим процедуру распараллеливания П). Пусть имеется последовательное соединение некоторой подсхемы (ПС) а с

другими ПС си, а2, ..., а^. Процедура распараллеливания состоит е дублировании ПС а к+1 либо к раз (в зависимости от того, является ит нет выход ПС а внешним) и переходе к параллельной структуре 6локое а'ь а'г,..., а'к, каждый из которых получается в результате "втягивания" е него блока а. Выходные функции ПС а,, а,г, ..., ак и соответственно а'ь а'2, а'к совпадают.

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

Заметим также, что если после проведения ряда процедур распараллеливания структура всей КС примет вид структуры, в которой отсутствует последовательное соединение блоков, то такую структуру будем называть предельно распараллеленной.

С учетом процедуры П1 алгоритм ТБ- согласования произвольных КС принимает следующий вид:

1. Разбиение КС на максимальные одновыходные ПС.

2. Расчет задержки Т распространения сигнала КС в целом, исходя из самых быстродействующих реализаций (ДНФ- реализаций) каждой ПС.

3. Проверка неравенства Т<Тзад1 где Тзад- наперед заданная величина. Если условие выполняется, то перейти к п.8, в противном случае- к следующему пункту.

4. Проверка достижимости предельного распараллеливания блочной структуры КС (под блоком понимается ПС). Если текущая блочная структура КС предельно распараллелена, то перейти к п.7, в противном случае- к следующему пункту.

5. Выбор ПС а, подлежащей распараллеливанию. Этот выбор можно совершить в следующей последовательности:

a) построить простой сетевой график;

b) определить множество М1р ПС, каждая из которых принадлежит хотя бы одному из критических путей графика;

c) для каждой ПС ае Мкр оценить: (Д8/ДТ)а, если (ДТ)а^0 или (А8)а, если (АТ)а=0, где .АЗ и АТ - модули приращения сложности и задержки КС в целом в предположении, что выполнена процедура II1 распараллеливания для ПС а по сравнению с текущей блочной структурой КС;

с1) выбрать из множества Мьт произвольным образом единственную ПС а, для которой (Д8/ДТ)а=тт, если истинно высказывание ВаеМкр[(АТ)а?40], в противном случае ПС а выбрать из условия (Д8)а=пнп.

Обратим внимание, что в п.5 на всех стадиях используются только ДНФ- реализации всех ПС.

6. Выполнение процедуры II! распараллеливания для ПС а, выбранной I п.5, и безусловный переход к п.2.

7. Выдать сообщение о невозможности обеспечить требуемое зыстродействие и перейти к п.10.

8. Построение для каждой ПС множества реализаций, оптимальных по Тарето.

9. ТБ- согласование текущей блочной структуры КС в соответствии с ш оритмом ТБ- согласования блочных КС.

10.Конец.

Рассмотрены ЦВУ с управляющим автоматом двух типов: Мили и \Дура. Общая комбинационная схема (ОКС), определяющая сложность и Зыстродействие ЦВУ в целом включает в себя следующие комбинационнее схемы: ... ,1РП, КС, КС,, КС2, Фь «Ъ, <К Для ТБ-югласования ОКС применяется модифицированный алгоритм ТБ-;огласования произвольных КС.

В главе 3 предложенный потоковый подход к Т$- согласованию ДВУ распространяется на более сложный класс систем- параллельные 1роблемно- ориентированные ЦВС.

В качестве объектов ТБ- согласования в § 3.1 вводятся в рассмот-х;ние параллельные ЦВС, содержащие три основных компонента: систему гараллельной памяти (СПП), N операционных устройств ОУь ОУ2, ..., ОУм I общий управляющий автомат (ОУА).

Пусть для каждой вершины деС^'Л' последовательной ГСА Г гзвестно множество допустимых реализаций (множество эквивалентных с функциональной точки зрения ОУ) §=1, 2, ..., ((}- множество

шераторных вершин типа сложения, вычитания, умножения и т.п.; .шожество условных вершин). Для эквивалентных вершин, соответствующие им множества Б^ совпадают. Для начальной go и сонечной вершин Яг=0. Обозначим через с- ю реализацию

1ершины g, где с=1, 2, ..., |КВ|, а и соответственно сложность и :реднее время выполнения вершины £ при условии, что используется ОУ, юстроенное по схеме с. Предположим, что все объекты, входящие в .тожество образуют группу устройств, оптимальных по Парето. При (том %1< к&/2< ...< я^вд, а у2> .-•> VgeQ^W.

Рассмотрим последовательную ГСА Г с выделенными линейными участками Ъ,. Пусть входные переменные а^А алгоритма- случайные >елйчины с заданными законами распределения. Тогда статистическое щделирование ГСА Г позволяет определить среднее число Пк повторений го цикла. Это дает возможность привести граф в ГСА Г к щиклическому виду время выполнения которого остается прежним, "раф Оа получается из графа в путем удаления всех дуг, замыкающих щклы. При этом среднее время выполнения всех реализаций г^с каждой

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

6 *ш

вершина g.

Выполнив распараллеливание всех линейных участков Ь последовательной ГСА Г, представленной ациклическим графом Ста.

I

получим ациклическую форму 1а графа Г параллельной ГСА П. Время выполнения алгоритма оценивается по сетевому графику, построенному на

г

основе графа 1а по следующим правилам:

г +

1. Каждая вершина ge 1а с числом исходящих дуг р >2 дублируется. Причем вершины g-g' соединяются сплошными стрелками, а g'-g^, g'-gl, g'-gг пунктирными. Все прежние связи вершины g с другими вершинами ё1, 82, 8/ удаляются.

I

2. Вершине Бое!а в сетевом графике соответствует начальная вершина,

/

а вершине з^е 1а- конечная.

3. Все вершины СГ нумеруются числами натурального ряда. Номер 1

присваивается начальной вершине. Конечная вершина получает

максимальный номер.

Каждая сплошная стрелка СГ соответствует вычислительной

/

работе, совершаемой ОУ, реализующим ту или иную вершину 1рафа 1а. Пунктирные же стрелки сетевого графика соответствуют фиктивным работам, имеющим нулевую длительность и стоимость. Кроме того, нулевую стоимость имеют работы, относящиеся к начальной вершине go и фиктивным вершинам распараллеливания Я; и соединения в; (на сетевом 1рафике эти работы обозначены сплошными стрелками).

г

СГ позволяет интерпретировать граф I а на языке вычислительных работ, совершаемых операционными устройствами при выполнении

г

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

В § 3.2 доказывается ряд теорем, обеспечивающих построение параллельной ГСА с необходимой и достаточной степенью параллельности

(ГСА,«).

Пусть 1а - ациклическая форма графа I предельно распараллеленной граф- схемы алгоритма (ГСА), полученной из последовательной ГСА путем предельного распараллеливания всех линейных участков. Два

оператора а,ЬеМ1 (М; - множество операторов 1-го линейного участка) будем считать совместимыми, если их выполнение на одном ОУ не приводит к увеличению времени выполнения алгоритма, рассчитанному из условия, что каждый оператор выполняется на отдельном ОУ. Множество О; попарно совместимых операторов назовем максимальным (МС-классом), если при добавлении к нему любого оператора из Мь не вошедшего ранее в множество 0,, оно перестает быть попарно совместимым.

Теорема 1. Множество всех вершин ^ , g, , ..., е- } любого маршрута )> eMi , j=Яnт:l, фаФ3 Ь

образует МС- класс.

Здесь Бх - фиктивные операторы распараллеливания и соединения ¡- го линейного участка; 1; - подграф графа 1а (I), которому принадлежат все операторы множества М;.

Систему множеств (31=((2ц, С2и> —» <31.0 назовем покрытием множества М^, если выполнены следующие условия: а) 0ц сМ|, .¡=1,к, б)

__ к

0ц, .)=1,к- множество попарно совместимых операторов, в) . = М;.

Н

Теорема 2. В минимальном покрытии (&=((& 1, С^г, • •■, Qi,k) все множества 1, к максимал1>ны.

Техника отыскания минимального покрытия СЬ связана с построением таблицы покрытий Р;. Строки такой таблицы соответствуют МС-классам множества М; (маршрутам графа 11), а столбцы- операторам суеМ;. На пересечении строки 1 и столбца j ставится метка (единица), если МС-класс, соответствующий ¡- ой строке, покрывает оператор, соответствующий j- ому столбцу. МС- класс \ покрывает оператор _], если й оператор принадлежит \- му МС- классу, т.е. маршрут, соответствующий ¡- му МС-классу, проходит через й оператор.

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

Покрытие К;2, ..., множества операторов М; будем

называть разбиением множества М;, если =0, ^т.

Теорема 3. Минимальное покрытие 0г=(0;,1, 2, •■■, С^.к) становится минимальным разбиением ^=(^1, К12, ••■, Кцк) с тем же значением к, если всякий раз, когда гл С_).га одно из множеств попарно

совместимых операторов, например, Q,m преобразуется по формуле: QI>m \ (QynQu).

В § 3.3 разработаны два метода построения ГСА с необходимой и достаточной степенью параллельности (последовательный и логарифмический), представляющие собой многошаговые процессы, позволяющие, начиная с предельно распараллеленной ГСА, уменьшить степень параллельности до необходимого и достаточного уровня, модифицируя при этом ГСА построенные на предыдущем шаге.

Обозначим через ациклическую форму графа 1НД ГСАИД. Простой сетевой график ГСЛВД строится на основе графа 1адд по правилам построения СГ ГСА П. Расширенный СГ Г'СА,1Д строится на основе простого СГ также, как и в случае построения расширенного СГ для блочной КС. При этом вместо множеств R^ необходимо использовать множества допустимых реализаций Rg.

Проделанная формализация ЦВС в виде простого и расширенного сетевых графиков позволяет воспользоваться потоковым алгоритмом ФФК и определить согласованные требования на длительности тактов тоу , которыми должны обладать ОУ. Требования по тоу. удовлетворяются

путем TS- согласования ОУ.

Глава 4 посвящена логическому проектированию ОЭКТ с позиций экспертных систем.

В § 4.1 описываются базовые структурные модели ОЭКТ, рассчитанные на блочную компоновку микроопераций. С этой целью разработана блочная модель ОЭКТ, в которую введен механизм замены эквивалентных микроопераций одним общим оператором. Критерием о вхождении микрооперации в определенный блок является общность имен выходных слов, а все микрооперации, допускающие замену общим оператором, помечаются звездочкой. Практическая реализация этого механизма замены требует ранее сформированные блоки микроопераций (МОП) разбить на три части В, Z и М. Первая часть (В) включает блоки МОП, реализация которых будет проводиться без замены эквивалентных микроопераций (даже если они гам и есть). Вторая часть (Z) содержит блоки МОП, для которых будет выполнена внутриблочная замена эквивалентных МОП. Третья часть (М) состоит из блоков МОП, для которых будет выполнена межблочная замена эквивалентных микроопераций.

Блочная компоновка МОП, реализуемых ОЭКТ, и введение процедуры замены эквивалентных МОП одним оператором обеспечивает проведение оптимизации ОЭКТ на более высоком (структурном) уровне по сравнению с классическими методами минимизации булевых функций, применяемыми обычно на более низких уровнях.

При проектировании ОЭКТ реальной сложности весьма полезным жазывается принцип проектирования сложных объектов по частям, в соответствии с которым разработана основная модель. В рамках этой «юдоли ОЭКТ состоит из ш узлов, каждый из которых синтезируется по элочной модели.

В § 4.2 предлагается концептуальная модель ИСпроект ОЭКТ, обесточивающая формализацию знаний в области синтеза ОЭКТ с помощью тродукционньгх экспертных систем. Эта модель, изображенная на рис.1, ¡клгочает в себя три основных компоненты: базу данных, базу знаний правила, продукции) и интерпретатор (управляющую структуру).

База знаний представляет собой набор правил типа: ЕСЛИ (Условие) ТО (Действие), а управляющая структура определяет, какое правило должно быть проверено следующим, . (Условие)- это проверка состояния базы данных, а (Действие) определенным образом видоизменяет содержимое базы данных.

Содержательно условная Рис. 1 часть правила включает в себя

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

В § 4.3 концептуальная модель детализируется до уровня пользовательской модели (рис. 2) и проводится анализ основных потоков информации в ИСпроект.

Детализация касается структур данных и языка представления шаний (ЯГО), используемых для формирования и описания базы данных и зазы знаний.

В процессе диалога возникает необходимость иметь двойное представление списка микроопераций, подлежащих реализации: внешнее и знутреннее. Внешнее представление рассчитано на возможный просмотр списка микроопераций пользователем в процессе диалога и потому оно должно иметь форму, ориентированную на человека. Введение другой внутренней) формы представления списка микроопераций обеспечивает >ффективное выполнение последующих работ по проектированию ОЭКТ.

Таким образом, становится необходимым разделить БД1 (в обозначениях рис. 1- это список микроопераций, подлежащих реализации) на две части: БД-1 внешнее представление списка микроопераций и

БД-2 внутреннее представление списка реализации (в обозначениях рис. 2).

микрооперации, подлежащи

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

В нашем случа целесообразно выделит четыре источника знани? Х£\- основной и 1X2, КЗ Е4- дополнительные. Тр] Рис. 2 последних источника по;]

держивают механизм замены МОП. При этом 17,2 обеспечивае мультиплексирование входных сигналов сумматора. В зависимости о типа переноса (последовательный, параллельный, параллельна параллельный и т.д.) ЕЗ обеспечивает формирование логической схем! самого сумматора. НА используется для реализации специально) микрооперации:

<У>-- ПЕРЕНОС ИЗ СТАРШЕГО (Ы- го) РАЗРЯДА, необходимой для наращивания разрядности сумматора.

Все источники знаний построены по единой схеме (с использо ванием правил типа Условие- Действие). Действующая часть всех правш построена на базе компактных линейных деревьев (КЛД).

КЛД оказываются весьма удобным инструментом для компактной хранения знаний о различных реализациях микроопераций, но они малс приспособлены для выполнения общих процедур оптимизации логически? схем. Поэтому вводится в рассмотрение еще одна структура данных каковой является динамическая таблица (ДТ). Эта таблица в дальнейше!у рассматривается как основная структура данных, используемая дт первичного представления КС и выполнения последующих оптимизи рующих процедур.

Структурная таблица (БД2 на рис. 1) может быть реализован; путем введения всего лишь одного правила в основной источник зналиI \Ъ\. Поэтому становится понятным назначение баз данных БДЗ и БД4 не рис. 2. База данных БДЗ включает в себя систему булевых функций в виде линейных деревьев, описывающих поведение ОЭКТ. База данных БД4-это динамическая таблица, выступающая как внутреннее представление проектируемого ОЭКТ на различных стадиях оптимизации и

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

В главе 5 рассматривается функциональное наполнение и принципы реализации основных компонент интеллектуальных систем логического проектирования ТБ- согласованных ЦУ: диалогового процессора (ДП), базы знаний и планировщика.

При построении диалогового процессора (§ 5.1) ИСпроект ЦУ в ориентации на массового конечного пользователя в качестве модели диалога целесообразно использовать регламентированный диалог, основанный на иерархическом меню. Выбор такой формы диалога, при которой запросы потребителя и ответы системы представляются в виде сообщений с заданной структурой, во- первых, не требует от пользователя глубоких знаний предметной области и синтаксиса языка, описывающего эту область, во-вторых, значительно облегчает реализацию ДП.

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

Система базовых микроопераций, описанная на языке функционального микропрограммирования и используемая в качестве входного языка ИСпроект ОЭКТ, и регламентированный диалог на основе меню однозначно позволяют распределить роли между системой (ИСпроект) и пользователем. Система, занимая активную сторону, предоставляя различные меню, будет "вести" пользователя (направлять его работу по формированию задания на проектирование). За пользователем в основном остается лишь начальная конкретизация выбранных им же базовых микроопераций.

В § 5.2 рассмотрен пример подготовки задания на синтез ОЭКТ.

Формализация профессиональных знаний предполагает выделение и оформление знаний в отдельные информационные объекты в виде баз знаний, создание которых требует разработки специализированных языков. В § 5.3 рассматриваются основные конструкции специализиро-

ванного ЯШ, используемого при написании КЛД (вложенные циклы внутри линейного дерева, а также одиночный и двойной циклы вне линейных деревьев).

В основе синтаксиса однолинейного (строчного) описания логических схем (другими словами линейных деревьев) лежит следующая конструкция, описывающая отдельный логический элемент (ЛЭ):

ЗАГ= (ТИПЛЭ /КОЛВХ/ ( ),...,( ) ), где ЗАГ - заголовок дерева (имя выходного сигнала схемы); ТИПЛЭ - тип логического элемента (ТИПЛЭ е { &, !, \ %, V, @}; причем & - И, ! -ИЛИ, 1 - НЕ, % - И-НЕ, V - ИЛИ-НЕ, @ - сложение по mod 2); КОЛВХ -количество входов у ЛЭ (КОЛВХ=1, 2, 3, ...); в последующих круглых скобках, разделенных запятыми, должны содержаться описания входов данного ЛЭ, начинающиеся с символа #- листа дерева ( в качестве таких описаний могут использоваться описания других ЛЭ, с аналогичным синтаксисом); число запятых должно равняться КОЛВХ-1; число открывающих скобок во всей конструкции должно равняться числу закрывающих скобок.

В булевой алгебре для записи формул вида: Y=(Xi[1]+X2[1]) (Xi[2]+X2[2]) ... (Xi[L]+X2[L]) часто используется более компактная форма: l

Y= & (X [k] + X [к]. На языке компактных линейных деревьев сжатая k = I

запись формулы для Y принимает вид: Y=(&/K=l:L/(!/2/(#<Xl>[K]), (#<Х2>[К]))).

Отсюда видно, что для компактного изображения линейных деревьев достаточно расширить возможности атрибута КОЛВХ, допустив употребление вместо целочисленного изображения количества входов ЛЭ линейную конструкцию цикла по некоторой переменной с фиксацией границ изменения этой переменной (в нашем примере, цикл /К=1:1У по переменной К от 1 до L). В ИСпроект развертывание компактного линейного дерева, содержащего любое количество циклов любой вложенности, приводит к копированию соответствующих участков линейного дерева и замене переменной цикла в тех пределах, которые указаны в конструкции цикла. Развернув по К компактное линейное дерево для Y, получим:

Y=(&/L/ (!/2/(#<Х1>[1]), (#<Х2>[1])), (!/2/(#<Х1>[2]), (#<Х2>[2])),

(!/2/(#<Х1>[Ц), (//<Х2>[Ц))). Линейные деревья позволяют описать любую комбинационную схему. Однако, если в схеме имеются ветвления, то длина линейного дерева увеличивается за счет дублирования определенных отрезков дерева.

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

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

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

Таким образом, действующую часть правил базы знаний будем строить по схеме:

* <цикл> <линейное дерево> ; <цикл> <линейное дерево> ;

<цикл> <линейное дерево> *.

Рассмотрим синтаксис конструкции <цикл> сначала по схеме одиночного цикла. Поскольку <цикл> вынесен за пределы линейного дерева, назовем такую конструкцию одиночным циклом вне линейного дерева.

Для присвоения конкретного (единственного) значения переменной цикла используется конструкция <цикл> в виде: / I = < Г > /, где <Г>-некоторое арифметическое выражение, определяющее граничное значение переменной цикла I.

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

Для генерации (создания) нескольких линейных деревьев, отличающихся друг от друга значением переменной цикла I, может быть использована другая конструкция одиночного цикла: /1 = < Г1 > : < Г2 > /, где < Г1 >, < Г2 >- арифметические выражения, определяющие границы изменения I (I = < Г1 >, < Г1 >Н, < Г1 >+-2,..., < Г2 >). Причем, если после вычисления <Г1 >и<Г2> возникнет ситуация, когда <Г1 > > <Г2>, то

линейное дерево, соответствующее данному циклу, игнорируется (не создается вообще).

В цифровой технике часто при организации многоразрядных схем (сумматоров, компараторов и т.п.) прибегают к разбиению схемы на группы. Описание таких схем требует ввести дополнительные соглашения, связанные с обозначением количества групп и количества разрядов в каждой группе. Пусть К (К=1, 2, ...)- количество групп, а ] (С[1]=1, 2, ...)- количество разрядов в I- ой группе.

Нетрудно видеть, что для 1-ой группы номера разрядов лежат в ы I 1

пределах: +1 -I- ]>]С[С>]. Арифметические суммы типа: и

0=1 0=1 0=1

и

+ 1 на языке линейных деревьев могут быть записаны в виде:

0=1

(+/(2=1:1/(# СК])и(+/д=1:И /(#С[д]))+1 соответственно.

Отсюда вытекает необходимость расширения конструкции цикла за счет возможности применения циклов вида: (+/<П>=<Г1>:<Г2>/ (#С[<П>])), где <П> - переменная цикла; <Г1>, <Г2>- по- прежнему левая и правая граница цикла (некоторые арифметические выражения).

При описании схем с групповой организацией возникает необходимость указания номера группы и номера разряда в группе. Эго можно сделать, предусмотрев двойной цикл вне линейного дерева: <цикл по <П1> > <цикл по <П2> > <линейное дерево>, где <П1>, <П2>-переменные цикла.

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

В § 5.4 рассмотрены основные реализации различных микроопераций из списка базовых МОП на основе КЛД. Одна из таких реализаций имеет вид:

4 ЕСЛИ

*/СУММАТ0Р С ГРУППОВЫМ (ПАРАЛЛЕЛЬНО- ПАРАЛЛЕЛЬНЫМ) ПЕРЕНОСОМ (В БАЗИСЕ И, ИЛИ, М2)/* ТО

*/1=1:>1-2/ <$80,7>[1] = ( !/2/(# <$Ш>[1]), (# <$21)>[1]) ); Л=1:К-1/<$8О,б>[1]==(!/А=(+/0=1:1-1/(#О[0]))4-1:(+/0=1:ЩО[0])У

(&/2/(&/2/(#<$Ю>[А]),(//<$20>[А])), •

(&/М=А+1 :(+/(3=1:1/(#0[С>]))/ (#<$8Б,7>[М]))) ); Я=1 :К-1/ <$80,5>[1] = (&/А= (+/()= 1:1-1/(# С[<3]))(1: (+/0=1:1 /(# С[(Д)) /(# <$8Э,7>[А]) );

/1=2:К/ <$SD,4>[I]=( !/2/(&/2/(#<$3D>), (&/A= 1:1-1 /(<$SD,5>[A]))), (!/A= H-l / (&/2/(# <$SD,6>[A]), (&/M= A+1:1-1 / (# <$SD,5>[M])))));

/1=1 :G[1]/ <$SD,1>[I]=(@ /3/( # <$ 1 D> [I]), (# <$2 D> [I]), (!/2/(&/2/

(# <$3D>),(&/A= l:I-l/(# <$SD,7>[A]))),( !/A= 1:1-1/ (&/2/(&/2/(# <$1D>[A1), (# <$2B>[A])), (&/M= A+H-l / (// <$SD,7>[M]))))));

/J=2:KJ /I - ( +/Q= 1 :J-1 / (// G[Q])) + 1: ( ¡7Q- 1J / (# G[Q]))/ <SSD,l>[I]=(@y3/(#<$lD>[l]),(#<$2D>[I]),(!/2/

(!/A=(+/Q=l:J-l/(#G[Q]))+l:I-l/(&/2/(#<$lD>[A]), (#<$2D>[A])),(&/TV1=A+1:I-1/(#<$SD,7>[M])))), (&/2/(# <$SD,4>[J]),(&/R=(+/Q= 1:J-1(# G[Q]))+1:I-1/ (# <$SD,7>[R])))) )*.

Здесь <$SD,7>[I]- условие распространения переноса через 1-й разряд; <$SD,6>[I]- условие заролодения переноса из 1-й группы; <$SD,5>[I]- условие распространения переноса через 1-ю группу; <$SD,4>[I]- перенос в 1-ю группу; <$SD,1>[I]- значение суммы в 1-м разряде.

Первый цикл по I от 1 до N-2 для <SSD,7>[I] обеспечивает построение N-2 двухвходовых логических элементов типа ИЛИ, на выходах которых реализуются условия распространения переноса через каждый из N-2 младших разрядов сумматора.

Второй цикл по I от 1 до К-1 для <$SD,6>[I] служит для построения К-1 подсхем, на выходах которых реализуются условия генерации (зарождения) переноса из младших К-1 групп. Здесь необходимо обратить внимание на внутренний цикл по А. Левая граница этого цикла в качестве терма арифметического выражения содержит арифметическую сумму (+/Q= 1:1-1 / (# G[Q]) )+1, которую целесообразно использовать не только в циклах вне линейных деревьев, но и в самих линейных деревьях в качестве термов определенных арифметических выражений.

Третий цикл по I от 1 до К-1 для <$SD,5>[I] обеспечиваег построение К-1 подсхем, формирующих условия распространения переноса через К-1 младших групп.

Четвертый цикл по I от 2 до К для <$SD,4>[I] предназначен для построения К-1 подсхем, формирующих по параллельной схеме переносы в каждую из групп, начиная со второй.

Предпоследний цикл по 1 от 1 до G[l] для <$SD,1>[I] служит для построения самой младшей группы сумматора, число разрядов которой-G[l].

Последний двойной цикл по J и по I вне линейного дерева для <$SD,1>[I] на основе предыдущих деревьев строит все остальные группы сумматора.

Основные функции планировщика и пакета прикладных программ (ППП на рис. 2) связаны с обработкой проектируемых схем, представленных в виде компактных линейных деревьев и динамических таблиц.

В § 5.5 выделены и формализованы основные этапы обработки проектируемых логических схем, представленных на языке КЛД: конкретизация параметров в задании на проектирование; выбор из базы знаний описаний МОП в виде КЛД в базовых аргументах; распаковка КЛД в базовых аргументах и конкретизация переменных в линейных развернутых деревьях с базовыми аргументами.

Во всех источниках знаний использована единая методология организации правил в компактном (свернутом) виде, поэтому для распаковки этих правил независимо от вида задания можно использовать единую процедуру распаковки правил RAZVOR. Основные преобразования, связанные с работой этой процедуры, имеют вид: освобождение от циклов вне линейных деревьев путем копирования базовых линейных деревьев и соответствующей конкретизацией переменных внешних циклов; удаление внутренних циклов с соответствующей конкретизацией переменных цикла; удаление элементов без входов; преобразование элементов с одним входом (элементы типа И, ИЛИ, М2 преобразуются в проводники, а элементы типа И-НЕ, ИЛИ-НЕ- в инверторы); приведение к соответствию числа входов ЛЭ к их реальному числу. Выполнение последнего пункта может потребовать, в случае появления одновходовых элементов, возврата к предыдущему пункту. Преобразования заканчиваются, когда в линейных деревьях будут отсутствовать, кроме инверторов, элементы с одним входом.

В § 5.6 приводится алгоритм отображения развернутых и конкретизированных линейных деревьев на внутреннее представление логических схем в виде динамических таблиц, с помощью которых выполняется вся последующая обработка. Для этого разработан ряд общих процедур по оптимизации многоуровневых логических схем, представленных в виде динамических таблиц, например, таких как: OBDERZAP- объединение деревьев по именам с запятыми; UDALFRAG- удаление фрагмента логической схемы; UDALIZBELEM- удаление избыточных ЛЭ; OBEDIM-объединение деревьев по именам; CONST- учет константных входов; UKRUPSX- укрупнение ЛЭ схемы; FAKTORSX- факторизация схемы и др.

§ 5.7 содержит описание экспертного логического синтезатора "ЭЛС" (рис. 3) и практики логического проектирования ЦУ на его основе.

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

главное меню

программным кпд у ль

j а-пглл исгуал ¿лая cfctema ПТОПчТИРОЗАНИЯ оэкт

программный мзду ль

иреоьразоьатгль цувеа5ис пользователя

программный модуль

ввод схем. разработанных вне-элс-

ОТ ДРУГИХ САП?

программным мэдуль

СБОРЩИК МОДУЛ ЕЙ ЦУ В ГИПСЛТШЧЕС-КОМ БАЗИСЕ

строграмкйшй мэдупь

rS-СОППАСОВАТЕЛЬ

модули цу в

ЬАЗНСЕ ПОЛЬЗОВАТЕЛЯ

БИБЛИОТЕКА

МОДУЛИ ЦУ в ГИПОТЕШЧ ЕС-ком базисе

БИБЛИОТЕКА

елочные комбинацией-ИЫ В СХЕМЫ

ПРОСТ амьиый мзду ль

МОДИФИКАТОР цу Б БАЗИСЕ ПОЛЬЗОВАТЕЛЯ

СТОГ? АШДЪЙ ыс д у ль

База знаний системы написана на языке компакгных линейных деревьев и состоит примерно из 300 правил (продукций). Компактные линейные деревья в "ЭЛС" версии 2.1 могут содержать один или два внешних цикла и произвольное число внутренних циклов неограниченной вложенности. _

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

БИБЛИОТЕКАРЬ

программный модуль

ВЕРИФИКАТОР ИТОГОВЫХ УСТРОЙСТВ [ РЕЗУЛЬТАТЫ I

программный иэдуль

ГЕНЕРАТОР

выход нэй

документации

! выходной документ i

г другим сапр

Рис.3

щается в библиотеку "ЭЛС" с помощью Общий объем программного продукта версии 2.1 насчитывает более 100 тысяч операторов языка Турбо-Паскаль. Выходная информация о синтезированной логической схеме выдается на языке структурного описания.

"ЭЛС" позволяет выполнять проектирование цифровых устройств в произвольном базисе логических элементов типа И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, Исключающее ИЛИ с учетом заданных коэффициентов объединения по входам и разветвления по выходам. Сложность проектируемых схем уже при объеме ОЗУ в 640 Кбайт может превышать 8000 ЛЭ.

"ЭЛС" поддерживает нисходящую и восходящую стратегии проектирования. Нисходящее (декомпозиционное) проектирование

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

Время синтеза, например, 64-ти разрядного специализированного TS- согласованного АЛУ сложностью в 8635 логических элемента типа 2И, 4И, 8И, 2И-НЕ, 4Й-НЕ, 8И-НЕ, НЕ с коэффициентом разветвления по выходу равным 6 составляет 13 минут на ПК IBM PC Pentium-200.

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

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

В § 6.1 применяются равномерно распределенные СВС. Рассматриваются произвольные ЦУ, реализующие отображения: А,хА2х... хA,aj-h>В,хВ2х... хВ|в|, где А(В)- множество входных (выходных) переменных ГСА, реализуемой ЦУ; Ai( В,)- множество значений переменной а,(Ь,)еА(В); х- декартово произведение; |Х|- мощность множества X. Пусть n/m,)- количество двоичных разрядов, используемых для записи переменной a,(bj). Обозначим через n(m) общее число двоичных переменных, используемых для записи всех входных (выходных) переменных ГСА, т.е. п=п(+п2+ ...+П|А|, т=т1+т2+ ...+Ш|в|.

Поведение таких устройств можно описать с помощью комбинационных схем, имеющих п входов: Хь х2,..., хп и ш выходов: yi у2, ... ,ут и реализующих определенные системы из ш булевых функций, каждая из которых зависит от п переменных.

Считая, что в неисправном состоянии анализируемая КС на любом

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

P{my|5„} й N(my|e0^l' Oj),

= 0,5-(l/2m+1), о? = (l-2'2m)/3-2n+2.

Здесь р{ту|е()}- плотность распределения СВ (ту[ео - матема-

тическое ожидание у;

1 1 1

+ —у2+...н--ут в неисправном техническом

2 4 2

состоянии (ё0 ) устройства).

В § 6.2 применяются нормально распределенные СВС. Доказана Теорема 5. При больших Ь

= 0.5(2га -1), oj = (15.625-103(4m -l)/^h6(l-0))'

1-

1-(

где Ф(х) = (2/^)|е"'Л, И=2п-1- количество тактов в случайной о

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

У - У) •2т~1 + у2 •2га_^+...+ут -2".

В § 6.3 применяются СВС, распределенные по закону Симпсона. Доказана

Теорема 6. При больших п

т-2

^3=0,5(2т-1), (4т-1)

а? =

3 9- 2Ап+1

(23п+2 + 9-22т2 -2П).

В § 6.4 решается задача вероятностного функционального анализа ЦУ с эталонными блоками. Доказана следующая теорема. Теорема 7. При больших п Р{Р^о}*К(Р^5,с2)

43 = i-(i-y)ra,

a2 = [х2 +(1-х)2]п{11-(1-у)т12(1-уГ +(1-у)2п[1-(1-у)т]}-Здесь Pz|i()- вероятность появления единичного сигнала на выходе

z = (у) © У1)v(y2 Ф у2) v... v(ym Ф угп), где Ф- операция сложения по mod2, v- дизъюнкция, а х!,х2,...,хп и у1; у2, ..., у1П- входы и выходы эталонного (заведомо исправного) ЦУ, при условии, что анализируемое устройство неисправно; Р{х; = 1} = Р{х; = 1} = х, V; - вероятности появления единичного сигнала на входах устройств; у- вероятность изменения

отдельной клетки таблицы истинности анализируемого объекта па противоположное значение в неисправном состоянии.

Доказанные теоремы позволяют свести вероятностны й функциональный анализ ЦУ к вероятностному анализу лишь одного-исправного- технического состояния анализируемого объекта.

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

В § 7.1 вводится понятие р- таблицы функций неисправностей (р-ТФН, р- символ вероятности) и рассматривается задача построения проверяющих и различающих совокупностей контрольных точек (КТ). Строки таких таблиц соответствуют техническим состояниям устройства еь I = О, I, ..., а столбцы- выходам логических элементов схемы ц, j = 1,2, ..., Щ (8-множество рассматриваемых неисправностей, 2- множество выходов всех ЛЭ, е0- исправное состояние). На пересечении ¡-и строки и .¡-го столбца проставляется вероятность появления единичного сигнала на выходе ^го ЛЭ при условии, что устройство находится в состоянии еь т.е. р2.|е. =1|е;}. При этом предполагается, что на входах устройства

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

Доказаны следующие теоремы.

Теорема 8. Для любой правильной логической сети С, построенной из логических элементов И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, всегда найдется непустое множество = таких КТ, что любая одиночная

неисправность о4 е О, а также произвольное их сочетание, обнаружимы хотя бы по одному выходу ъ} е .

Теорема 9. Для любой правильной логической сети С, построенной из произвольных логических элементов, всегда найдется непустое множество ^п = {2})п таких КТ, что любая одиночная неисправность о; е О, а также произвольное их сочетание, обнаружимы хотя бы по одному выходу

г е/8 ¿.1 п ■

Теорема 10. Для любой правильной логической сети С, построенной из произвольных логических элементов, всегда найдется множество = , Ър таких КТ, что любые две неисправности од и ога

выходов разных ЛЭ сети различимы хотя бы по одному выходу е .

В теоремах 8-10 О- множество одиночных константных неисправностей входных и/или выходных полюсов ЛЭ, О - множество одиночных константных неисправностей только выходных полюсов ЛЭ (О с О с Б).

§ 7.2 содержит методы расчета основных параметров решающих

правил проверки исправности и локализации неисправностей ЦУ. Решение об исправности проверяемого объекта выносится на основе измерения за Кп тактов частоты рг. единичного сигнала в КТ Zj в соответствии с

решающим правилом: если V}, - рг.|е<)1< е", то объект исправен, если

же |р2.-р2.|е<)|>8"- неисправен (с^1 >0- некоторая малая величина,

задающая допустимое отклонение частоты рг. от вероятности Рг^|е0 )■

Локализация обнаруженной неисправности производится по

значению вектора 2 = , ..., zi ), 6{0,1}, к = 1,|2р|,

|2р|

полученного на основе измерения за тактов частоты р7. во всех КТ г^ е7.р по правилу: ^=0, если |р2. - р2.|ео|< г.? и г>= 1, если |р2. - р^^ г].

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

Расчету основных параметров проверки исправности сложных ЦУ посвящены §§ 7.3 (на основе аналитических методов) и 7.4 (с использованием метода статистического моделирования). Показано, что одновременное введение элемента случайности на множество входных наборов и множество константных неисправностей позволяет в отличие от р- ТФН весьма сжато представить информацию о неисправностях комбинационных схем в виде кривых плотностей распределения р{р^Со}

вероятностей появления единичных сигналов на выходах ц в

неисправном е0 состоянии проверяемых объектов. С использованием аналитических методов вероятностного анализа комбинационных схем (§7.3) и метода статистического моделирования (§ 7.4) разработаны методики получения оценок р{р2^0} плотностей р{р2.|ё0} и расчета на их

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

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

В § 7.5 разработана методика оптимизации распределения случайных входных сигналов. Вероятностный логический анализ КС с гп выходами предлагается проводить по оценке математического ожидания ш 1

величины у = ^ — у4. Проверка исправности производится в соответствии ¡=1 2

с решающим правилом: если |ту - ту)ео( - е> Т0 КС исправна, в противном случае- неисправна, где ту- оценка математического ожидания величины у за N тактов проверки; т^,- математическое ожидание величины у в исправном техническом состоянии КС; с - допустимое отклонение шу от т^^. Распределение случайных входных сигналов во время получения оценки ту не изменяется.

Оптимальному контролирующему вектору р* соответствует максимум по рх функции: Ь'(рх) = тт |шу|е.(рх)— шу|ео(рх)[, где Шу|е (рх)- математическое ожидание величины у при ег ом неисправном техническом состоянии КС и входном векторе рх.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Главным результатом диссертационной работы является разработка теории организации и построения интеллектуальных систем логического проектирования Т8- согласованных цифровых устройств. Основные научные и практические результаты диссертации сводятся к следующему:

1. Предложена сетевая интерпретация блочных и произвольных комбинационных схем на языке вычислительных работ, совершаемых отдельными их компонентами. Разработаны правила построения простых и расширенных сетевых графиков, что дает возможность воспользоваться для ТЗ- согласования подобных объектов эффективным потоковым алгоритмом Форда- Фалкерсона- Келли.

2. Разработаны различные модификации алгоритма ТЯ-согласования произвольных КС, позволяющие с единых позиций проводить Т8- согласование как отдельных частей операционных устройств (операционных элементов комбинационного и накапливающего типов, операционных и управляющих автоматов), так и ОУ в целом с учетом произвольной КС управляющего автомата и блочных КС

операционного автомата, из которых и состоит любое ОУ. При этом эассматриваются оба варианта построения УА: по схеме автоматов типа Мили и типа Мура.

3. Предложена сетевая интерпретация параллельных ГСА на языке вычислительных работ, совершаемых операционными устройствами параллельных проблемно- ориентированных ЦВС при выполнении эператорных и условных вершин ГСА. Разработаны правила построения простых и расширенных сетевых графиков параллельных ГСА, что позволяет применить для оптимизации подобных объектов эффективный потоковый алгоритм Форда- Фалкерсона- Келли. Потоковый подход позволяет выполнить синтез ЦВС, начиная от обычной последовательной ГСА и заканчивая параллельной ТБ- согласованной структурой, реализующей заданную ГСА, что дает возможность предложенный подход рассматривать в качестве методологии высокоуровневого синтеза параллельных проблемно- ориентированных ЦВС.

4. Разработаны базовые структурные модели операционных элементов комбинационного типа, рассчитанные на блочную компоновку микроопераций, реализуемых ОЭКТ, что значительно упрощает введение процедуры замены эквивалентных МОП одним оператором, обеспечивающей проведение оптимизации ОЭКТ на более высоком (структурном) уровне по сравнению с классическими методами минимизации булевых функций, применяемыми обычно на более низких уровнях.

5. Предложена концептуальная и пользовательская модели интеллектуальной системы проектирования ОЭКТ, обеспечивающая формализацию знаний в области синтеза ОЭКТ с помощью правил продукционных систем. Определены условная и действующая часть правил, а также состояние других компонент ИСпроект: базы данных и интерпретатора. Проведен анализ основных потоков информации в ИСпроект.

6. Разработана система базовых микроопераций ИСпроект, описанная на языке функционального микропрограммирования и используемая в качестве входного языка ИСпроект ОЭКТ. Список базовых МОП служит основой для построения диалогового процессора ИСпроект и включает в себя следующие группы микроопераций: присвоения, сдвига, логические, арифметические (типа сложения/вычитания) с одним и двумя операндами, образования прямого, обратного и дополнительного кодов, смешанные (арифметико- логические), сравнения, шифрирования, дешифрирования, мультиплексирования и демультиплексирования. Общее число базовых МОП равно 83, что перекрывает практически весь спектр наиболее употребимых микроопераций.

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

8. Выделены и формализованы основные этапы обработки проектируемых логических схем, представленных на языке компактных линейных деревьев и в виде динамических таблиц, что определяет основные функции планировщика ИСпроект ОЭКТ.

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

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

величины шу|5(1 в неисправном состоянии ё0 устройства с ростом числа п входов асимптотически стремятся к нормальным законам распределения N(111^; О; ). Получены формулы для вычисления математических

ожиданий и дисперсий с2 при случайных входных сигналах с различными законами распределения: равномерном, нормальном, а также законе Симпсона.

11. Показано, что применение плотностей распределения N(111^; с,, ) позволяет резко снизить объем предварительных

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

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

остоянии е0, асимптотически стремится к нормальному закону.

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

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

15. С использованием аналитических методов вероятностного нализа комбинационных схем и метода статистического моделирования шработаны методики получения оценок р{р2^0} плотностей р{р^|е0} и

>асчета на их основе основных параметров вероятностной проверки [справности сложных (с большим числом элементов, входов и т.п.) :омбинационных схем без полного перебора всех неисправностей из аданного множества константных неисправностей, что заметно сокращает >бъем предварительных вычислений, связанных с анализом проверяемых 'стройств.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ

По исследованной проблеме автором опубликовано 40 работ. Ниже шречислены публикации, в которых приведены основные научные >езультаты диссертации.

.. Бажанов Ю.С., Баранов В.Г. О выборе контролирующих векторов и контрольных точек в системах статистического диагноза комбинационных схем.- Рига, 1978.- 17с- Рукопись представлена редколлегией журнала "Автоматика и вычислительная техника" Деп. в ВИНИТИ 13 июня 1978, № 1916- 78. I. Бажанов Ю.С., Баранов В.Г. Оптимизация стохастических систем контроля дискретных устройств // 1У Всесоюз. совещание по технической диагностике. Кн. 1: Тез. докл. Всесоюз. совещ,- Черкассы, 1979.-с. 31-зз:

3. Бажанов Ю.С., Баранов В.Г. Статистический метод контроля сложны? комбинационных схем со многими выходами. - Рига, 1981.- 13 е.-Рукопись представлена редколлегией журнала "Автоматика v. вычислительная техника". Деп. в ВИНИТИ 18 июня 1980, №2446-80.

4. Бажанов Ю.С., Баранов В.Г. О расчете стохастических систем контроля дискретных схем с памятью методом статистического моделирования h Техника средств связи. Серия: Радиоизмерительная техника, 1981, вып. 3(35).-С. 17- 29.

5. Бажанов Ю.С. Проверка исправности сложных дискретных устройств с помощью случайных входных сигналов // Техника средств связи. Серия: Радиоизмерительная техника, 1981, вьш.2 (34). С. 98-104.

6. Бажанов Ю.С. О вероятностном диагностировании дискретных устройств // В межвуз. сб. "Автоматизация научных исследований. Методы проектирования технических и программных средств АСНИ" .Куйбышев: КуАИ, 1986.- С. 32- 36.

7. Бажанов Ю.С., Уваров П.И. Об оптимизации распределения входных сигналов при стохастическом контроле автоматов без памяти // Вероятностные автоматы и их приложения,-Казань: КГУ, 1986.-С. 108-114.

8. Бажанов Ю.С. О вероятностном контроле комбинационных преобразователей информации с помощью нормально распределенных случайных кодов // Электронное моделирование,-1990, т. 12, № 3.- С. 57- 61.

9. Бажанов Ю.С. Стохастический контроль комбинационных устройств с помощью случайных кодов, распределенных по закону Симпсона //В межвуз. сб. "Математическое моделирование в задачах механики и управления",- Волгоград: ВГУ, 1990,- С. 137- 144.

10. Бажанов Ю.С., Мусонов Л.В., Александров А.Н. Экспертный логический синтезатор "ЭЛС" // Международный форум информатизации "МФИ -92": Тез. докл.- М., 1992.- С. 150- 155.

П.Баранов В.Г., Бажанов Ю.С. От традиционных САПР к интеллектуальным системам проектирования (ИСпроекг) цифровых устройств // В межвуз. сб. "Системы обработки информации и управления".- Н. Новгород: НГТУ, 1995.- С. 94- 100.

12. Бажанов Ю.С., Баранов В.Г. Структурные модели операционных элементов в ИСпроект // В межвуз. сб. "Системы обработки информации и управления" .- Н. Новгород: НГТУ, 1995,- С. 101- 106.

13. Бажанов Ю.С. Структурно- временное согласование операционных элементов комбинационного типа // В межвуз. сб. "Моделирование и оптимизация сложных систем ".- Н. Новгород: ВГАВТ, 1996,- Вып. 273, Ч.1.-С.8-22.

14. Бажанов Ю.С., Баранов В.Г. Базовые микрооперации интеллектуальных систем проектирования цифровых автоматов // В межвуз. сб. "Системы обработки информации и управления".- Н.Новгород:

НГТУ, 1997.- С. 75- 80.

5. Бажанов Ю.С. Концептуальная моделз, ИСпроект // В межвуз. сб. "Системы обработки информации и управления",- Н.Новгород: НГТУ,

1997.-С. 71-75.

6. Бажанов Ю.С. Пользовательская модель и анализ основных потоков информации ИСпроект // В межвуз. сб. "Системы обработки информации и управления",- Н. Новгород: НГТУ, 1997.- С. 81- 87.

7. Бажанов Ю.С. Структурно- временное согласование цифровых вычислительных устройств // Вестник ВВО АТН РФ. Серия: Высокие технологии в радиоэлектроники. - 1997, №2(4).- С. 215- 219.

8. Бажанов Ю.С. Язык представления знаний на основе компактных линейных деревьев // В межвуз. сб. "Системы обработки информации и управления ".- Н. Новгород: НГТУ, 1998,- Вып. 3,- С. 42-48.

9. Кондратьев В.В., Бажанов Ю.С. Потоковый подход к структурно-временному согласованию цифровых вычислительных устройств и систем // ДАН РФ, 1998, т. 359, № 5.- С. 604- 606.

0. Бажанов Ю.С. Структурно- временное согласование операционных устройств // В межвуз. сб. "Системы обработки информации и управления ".- Н. Новгород: НГТУ, 1998,- Вып. 3,- С. 35- 42.

1. Бажанов Ю.С. Основы теории структурно- временного согласования цифровых вычислительных устройств и систем.- Н. Новгород: НГТУ,

1998,- 80 с.

2. Bazhanov Ju.S., Kondrat'ev V.V. High level synthesis of parallel problem-oriented ts- coordinated digital computing systems // Computer Science Journal of Moldova, Academy of Science of Moldova Institute of Mathematics, 1998, №2.- P. 171- 204.

Введение.

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

1.1. От традиционной технологии решения задач на ЭВМ к интеллектуальному интерфейсу.

1.2. От традиционных САПР к интеллектуальным системам проектирования цифровых устройств.

1.3. О потоковом подходе к ТБ- согласованию ЦУ при их логическом проектировании с помощью интеллектуальных систем.

1.4. От классических методов проверки функций и аппаратуры к вероятностному функционально- логическому анализу ЦУ.

1.5. Выводы и основные вопросы теории интеллектуальных систем логического проектирования ТБ- согласованных цифровых устройств.

ЧАСТЬ ПЕРВАЯ

СТРУКТУРНО- ВРЕМЕННОЕ СОГЛАСОВАНИЕ ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ И СИСТЕМ

Глава вторая. ТБ- согласование цифровых вычислительных устройств.

2.1. ТБ- согласование операционных элементов комбинационного типа.

2.1.1. Объекты ТБ- согласования.

2.1.2. Постановка задачи.

2.1.3. Сетевой график.

2.1.4. Алгоритм ТБ- согласования ОЭКТ с гипотетическими связями между блоками.

2.1.5. Алгоритм ТБ- согласования ОЭКТ с реальными связями между блоками.

2.1.6. Пример ТБ- согласования ОЭКТ.

2.2. Т8-согласование операционных устройств.

2.2.1. Объекты ТБ- согласования.

2.2.2. ТБ- согласование произвольных комбинационных схем.

2.2.3. Особенности Т8- согласования ОУ с УА типа Мили.

2.2.4. Особенности Т8- согласования ОУ с УА типа Мура.

2.3. Выводы.

Глава третья. 18- согласование параллельных проблемноориентированных цифровых вычислительных систем.

3.1. Параллельные ГС А.

3.1.1. Объекты Т8- согласования.

3.1.2. Последовательная ГСА.

3.1.3. Предельно распараллеленная ГСА.

3.1.4. Время выполнения алгоритма.

3.2. Совместимые операторы и минимальные разбиения.

3.2.1. МС-классы.

3.2.2. Минимальные разбиения операторов.

3.3. Т8-согласование параллельных ЦВС.

3.3.1. ГС А с необходимой и достаточной степенью параллельности.

3.3.2. Алгоритм TS- согласования параллельных ЦВС.

3.4. Выводы.

ЧАСТЬ ВТОРАЯ

ИНТЕЛЛЕКТУАЛИЗАЦИЯ ФУНКЦИОНАЛЬНО- ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ УСТРОЙСТВ

Глава четвертая. Синтез операционных элементов комбинационного типа с позиций экспертных систем.

4.1. Структурные модели операционных элементов в ИСпроект.

4.2. Концептуальная модель ИСпроект.

4.3. Пользовательская модель и анализ основных потоков информации в ИСпроект.

4.4. Выводы.

Глава пятая. Синтез цифровых устройств на базе экспертных логических синтезаторов.

5.1. Система базовых микроопераций ИСпроект.

5.2. Пример подготовки задания на синтез ОЭКТ.

5.3. Язык представления знаний на основе компактных линейных деревьев.

5.4. Источники знаний.

5.5. Обработка проектируемых схем, представленных в виде компактных линейных деревьев.

5.6. Обработка проектируемых схем, представленных в виде динамических таблиц.

5.7. Экспертный логический синтезатор "ЭЛС" и практика логического проектирования цифровых устройств.

5.8. Выводы.

ЧАСТЬ ТРЕТЬЯ

ВЕРОЯТНОСТНЫЙ ФУНКЦИОНАЛЬНО- ЛОГИЧЕСКИЙ АНАЛИЗ ЦИФРОВЫХ УСТРОЙСТВ

Глава шестая. Вероятностный функциональный анализ цифровых устройств.

6.1. Применение равномерно распределенных случайных входных сигналов.

6.2. Применение СВС, распределенных по нормальному закону.

6.3. Применение СВС, распределенных по закону Симпсона.

6.4. Вероятностный функциональный анализ цифровых устройств с эталонными блоками.

6.5. Выводы.

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

7.1. р- ТФН и построение проверяющих и различающих совокупностей контрольных точек.

7.2. Построение решающих правил проверки исправности и локализации неисправностей комбинационных устройств.

7.3. Расчет основных параметров проверки исправности сложных комбинационных устройств на основе аналитических методов их вероятностного анализа.

7.4. Расчет основных параметров проверки исправности сложных комбинационных устройств методом статистического моделирования.

7.5. Оптимизация распределения входных сигналов.

7.6. Выводы.

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

Вопросы структурно- временного согласования (кратко ТБ-согласования) цифровых вычислительных устройств и систем (ЦВУ и ЦВС) получили фундаментальное развитие в работах А.Г. Алексенко, С.И. Баранова, В.М. Глушкова, В.А. Горбатова, Е.А. Дроздова, А.Д. Закревского, У. Квайна, В.Г. Лазарева, О.Б. Лупанова, С.А. Майорова, Р. Миллера, В.А. Мищенко, Дж. Неймана, Д.А. Поспелова, Д. Рота, А. Фридмана, С.В. Яблонского и других российских и зарубежных ученых.

Известные методы Т8- согласования ЦВУ и ЦВС носят, в основном, алгебраический характер, что, как правило, приводит к потере сетевой структуры объектов оптимизации, следствием чего является недостаточная структурированность информации и большие затраты памяти и времени при решении задач указанного типа.

Разработка потокового подхода к Т8- согласованию ЦВУ и ЦВС, основанного на простых итеративных преобразованиях потока в сетях, позволяет устранить эти недостатки.

Автоматический процесс формирования логики работы ТБ-согласованных ЦУ в настоящее время не мыслим без использования интеллектуальных систем проектирования (ИСпроект). Интерес к разработке интеллектуальных систем логического проектирования ЦУ обусловлен тем, что ФЛП является достаточно сложным и трудоемким процессом, остающимся до сих пор слабо алгоритмизированным и носящим эвристический характер, так как большая доля работ по синтезу логических схем ЦУ выполняется не машиной, а человеком.

Огромную роль в процессе поиска хороших логических схем (ЛС) играет опыт. За долгие годы работы многих поколений разработчиков в области ФЛП ЦУ накоплен значительный по объему опыт синтеза ЛС, предназначенных для реализации многих типовых функций. Наличие такого опыта, разбросанного по многочисленным литературным источникам и сосредоточенного в головах высококвалифицированных специалистов по синтезу ЛС, служит весьма благодатной почвой для организации и построения ИСпроект, позволяющих овеществить этот опыт и сделать его доступным для менее квалифицированных специалистов.

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

B.Е. Кузнецов, В.М. Курейчик, Ж.Л. Лорьер, М. Минский, Н. Нильсон,

C. Осуга, Э.В. Попов, Г.С. Поспелов, Д.А. Поспелов, П.Г. Уинстон, Д. Уотермен, X. Уэно, Дж. Элти, А. Эндрю, Р. Эшби и др. Необходимо заметить, что в проведенных автором исследованиях процедуры ТБ-согласования играют необходимую роль одновременно как для собственно TS- согласования объектов проектирования, так и для построения соответствующих машин вывода ИСпроект.

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

В своем развитии методы технической диагностики ЦУ прошли значительный путь: от традиционных детерминированных методов (большинство из них достаточно хорошо исследованы и изложены в фундаментальных работах P.C. Гольдмана, В.А. Гуляева, В.И. Казначеева, В.В. Карибского, П.П. Пархоменко, А.Н. Скляревича, Е.С. Согомоняна, H.A. Соловьева, В.Ф. Халчева, Г. Чжена, В.П. Чипулиса, C.B. Яблонского и др.) до компактных вероятностных методов, использующих случайные входные сигналы (в этом направлении наибольшую известность получили работы В. Агравала, М.С. Берштейна, Б.Л. Долинского, Дж. Лоска, К. Паркера, A.M. Романкевича, Дж. Савира, В.Н. Ярмолика и др).

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

Цель работы. Разработка методов организации и построения интеллектуальных систем логического проектирования Т8- согласованных цифровых устройств.

На защиту выносятся:

1. Потоковый подход к Т8- согласованию цифровых вычислительных устройств.

2. Методология высокоуровневого синтеза параллельных проблемно- ориентированных цифровых вычислительных систем на базе потокового подхода к их Т8- согласованию.

3. Концептуальная и пользовательская модели интеллектуальных систем логического проектирования операционных элементов комбинационного типа.

4. Методология организации и построения основных компонент интеллектуальных систем логического проектирования цифровых устройств: диалогового процессора, планировщика, базы знаний, базы данных, интерпретатора, Т8- согласователя и др.

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

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

-117. Методы вероятностного логического анализа сложных комбинационных устройств с использованием только внешних выходов объектов анализа.

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

Научная новизна. В диссертационной работе получены следующие основные результаты, характеризующиеся научной новизной:

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

2. Разработан потоковый подход к ТБ- согласованию параллельных проблемно- ориентированных цифровых вычислительных систем, позволяющий выполнить синтез ЦВС, начиная от обычной последовательной граф- схемы алгоритма (ГСА) и заканчивая параллельной ТБ- согласованной структурой, реализующей заданную ГСА.

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

4. Разработан специализированный язык представления знаний в области синтеза ОЭКТ на основе компактных линейных деревьев, допускающих в отличие от обычных линейных деревьев такие конструкции как: одиночный и кратный циклы вне линейных деревьев, а также циклы произвольной вложенности внутри линейных деревьев.

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

6. Разработана модель экспертного логического синтезатора, предназначенного для быстрого синтеза Т8- согласованных ЦВУ с минимальным участием человека.

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

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

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

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

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

Практическая значимость и ценность работы заключается:

• в разработке базовых структурных моделей ОЭКТ, рассчитанных на блочную компоновку микроопераций, что значительно упрощает введение процедуры замены эквивалентных микроопераций одним общим оператором;

• в разработке системы базовых микроопераций ИСпроект, используемой в качестве входного языка ИСпроект ОЭКТ;

• в создании базы знаний, содержащей свыше 300 правил (продукций), отражающих имеющийся опыт синтеза ОЭКТ. Многие из этих правил выкристаллизовывались поколениями разработчиков и прошли проверку временем;

• в разработке конкретной версии экспертного логического синтезатора "ЭЛС", вобравшей в себя предложенные методы организации и построения математического и алгоритмического обеспечения интеллектуальных систем логического проектирования цифровых устройств;

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

Реализация результатов работы. Результаты исследований по разработке методов построения интеллектуальных систем логического проектирования ТБ- согласованных цифровых устройств реализованы при выполнении НИР "Разработка теории интеллектуальных систем проектирования высоконадежных и отказоустойчивых мультипроцессорных устройств обработки информации и управления", проводимой на факультете информационных систем и технологий Нижегородского государственного технического университета и финансируемой в рамках единого заказ- наряда (названная тема входит в раздел "Информационные технологии и электроника" по группе "Системы искусственного интеллекта" перечня критических технологий федерального уровня, одобренного правительственной комиссией по научно- технической политике от 21.07.1996 г. №2727п-П8), в программном продукте НИР "Разработка экспертной системы для автоматического функционально-логического проектирования цифровых устройств с применением базовых матричных кристаллов" (х/д Н/075МС, 1991,- 967 е.), а также применяются в учебном процессе при чтении курсов лекций "Цифровые автоматы" и "Основы теории интеллектуальных вычислительных систем" для студентов специальности 22.01- "Электронные вычислительные машины, системы, комплексы и сети" НГТУ.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всесоюз. науч.- техн. конф. "Дальнейшее развитие и внедрение новой техники приемных устройств" (Москва- Горький, 1977); 2- ом Всесоюз. науч,-техн. семинаре "Оптимизация технических систем" (Винница, 1979); науч.- техн. семинаре "Обеспечение надежности и качества систем методами технической диагностики" (Челябинск, 1979); 4- ом Всесоюз. совещании по технической диагностики (Черкассы, 1979); семинаре "Техническая диагностика и эксплуатация вычислительных и управляющих систем" по комплексной проблеме "Теоретическая электротехника, электроника и моделирование" Сектора электроники и моделирования Института электродинамики АН УССР (Киев, 1979, 1982); 5- ом Всесоюз. совещании по статистическим методам в процессах управления (Алма-Ата, 1981); семинаре "Теоретическая кибернетика" Казанского госуниверситета (Казань, 1981); 3- м Всесоюз. симпозиуме "Вероятностные автоматы и их приложения" (Казань, 1983); науч.- техн. конф. "Вероятностные автоматы и их приложения" (Батуми, 1986); 8- й Всесоюз. конф. "Проблемы теоретической кибернетики" (Горький, 1988); Международном форуме информатизации "МФИ- 92" (Н. Новгород, 1992); науч.- техн. конф. факультета радиоэлектроники и технической кибернетики НГТУ (Н. Новгород, 1980, 1996, 1997); науч,-техн. конф. факультета информационных систем и технологий НГТУ (Н. Новгород, 1998).

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

Структура и объем работы. Диссертационная работа состоит из введения, семи глав, заключения, списка литературы из 277 наименований и приложения; содержит 362 машинописные страницы основного

4.4. ВЫВОДЫ

1. Разработаны базовые структурные модели операционных элементов комбинационного типа, рассчитанные на блочную компоновку микроопераций, реализуемых ОЭКТ, что значительно упрощает введение процедуры замены эквивалентных МОП одним оператором, обеспечивающей проведение оптимизации ОЭКТ на более высоком (структурном) уровне по сравнению с классическими методами минимизации булевых функций, применяемыми обычно на более низких уровнях.

2. Предложена концептуальная модель интеллектуальной системы проектирования ОЭКТ, обеспечивающая формализацию знаний в области синтеза ОЭКТ с помощью правил продукционных систем. Содержательно определены условная и действующая часть правил, а также состояние других компонент ИСпроект: базы данных и интерпретатора. Разработана последовательность синтеза ОЭКТ с помощью предложенной модели ИСпроект.

ГЛАВА ПЯТАЯ

СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ НА БАЗЕ ЭКСПЕРТНЫХ ЛОГИЧЕСКИХ СИНТЕЗАТОРОВ

В этой главе рассматриваются функциональное наполнение и принципы реализации основных компонент интеллектуальных систем логического проектирования TS- согласованных ЦУ: диалогового процессора (§§ 5.1, 5.2), базы знаний ((§§ 5.3, 5.4) и планировщика ((§§ 5.5, 5.6). § 5.7 содержит описание экспертного логического синтезатора "ЭЛС" и практики логического проектирования ЦУ на его основе. Эта глава написана по результатам работ [34, 38, 39,45, 49].

5.1. СИСТЕМА БАЗОВЫХ МИКРООПЕРАЦИЙ ИС-ПРОЕКТ

Для функционального описания цифровых устройств в настоящее время имеется достаточно много языковых средств. В качестве примера можно назвать такие языки, как HSL-FX, FDL, Ф, DDL, CDL и др. [109, 124, 149, 155, 224]. Однако при построении интеллектуальных систем проектирования ЦУ в ориентации на массового конечного пользователя в качестве модели диалога целесообразно использовать регламентированный диалог, основанный на иерархическом меню [225].

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

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

Анализ литературы по проектированию ЦУ, а также просмотр систем команд различных микропроцессоров, позволяют выделить 15 различных групп микроопераций типа: присвоения, сдвига, логических, арифметических (типа сложения/вычитания) с одним и двумя операндами, смешанных (арифметико-логических), сравнения, дешифрирования, шифрирования, мультиплексирования и демультиплексирования [12, 13, 77- 83, 97, 106,115-117, 120-122, 126, 130, 135, 151, 154-156, 167170, 192, 193, 196-199, 201, 202, 206-209, 219, 221, 226, 238]. Система базовых микроопераций ИСпроект ЦУ приведена в таблице 5.1. Общее число базовых микроопераций равно 83, что перекрывает практически весь спектр наиболее распространенных микроопераций.

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

Группа микроопераций присвоения. Эта группа содержит единственную микрооперацию (МОП) под номером 1 (см. табл. 5.1). На поведенческом (функциональном) уровне данная МОП означает, что если и = 1, ,е с ли и = 0.

1. Первый источник знаний (IZ1). Первое правило \Ъ\ имеет вид:1 ЕСЛИ1. У>Ш.:=<Х1>[№1]*1. ТОл=ш/ <$гд>1.=(#<х1 >!.)*и служит для реализации 1М- разрядной шины, обеспечивающей передачу двоичной информации от <Х1>№1. к <$2,1>[№1].

2. На рис. 5.3 изображена схема сдвигателя, которая описывается следующим правилом:5 ЕСЛИ1. У>К:1.:=К1(0.<Х1>р^:1])*1. ТО

3. Я=Ш-1/ <$г,1>1.=(#<Х1>1+1.);я=к/ <$гд>1.=(#<о>)*.$гд>К. <$г,1>[ы-1] <$гд>рчг-2] • • • <$г,1>1.

4. Х1>К. <Х1>[М-1] • • • <Х1>[2]1. Рис. 5.3

5. Х1>И. <Х1>[М-1] . . . <Х1>1.1. Рис. 5.4

6. Многоместные одноразрядные логические микрооперации служат для описания отдельных логических элементов различного типа. Например, к- разрядный конъюнктор в \Ъ\ представлен следующим правилом:31 ЕСЛИ

7. У>: =АЖ)(<Х1 >,<Х2>,., <ХК>)* ТО

8. Я=1/ <$2,1>1.=(&/Ь=1 :К/(#<ХЬ>))*. Правила 9,10 источника знаний К1:9 ЕСЛИ1. У>№1.:=<Х1>[Ш]+1*

9. ПАРАЛЛЕЛЬНЫЙ ПЕРЕНОС, В БАЗИСЕ И,НЕ,М2 / ТО

10. Л=1/ <$г,1>1.=(л/1/(#<Х1>1.)); /1=2:Ы/ <$г,1>[1]=(@/2/(#<Х1>[1]),1. К=1:1-1/ (#<Х1>К.)))*;10 ЕСЛИ1. У>Р^1.:=<Х1>№1]+1*

11. СКВОЗНОЙ ПЕРЕНОС, В БАЗИСЕ И,НЕ,М2 /1. ТО

12. Из группы микроопераций образования прямого, обратного и дополнительного кодов выберем МОП 42. Этой микрооперации в Е1 соответствует правило 12:12 ЕСЛИ1. У>Ш.:=1.Л<Х1>[ЪИ.Т]* ТО

13. Л=1 <$гД>1.=(л/1/(#<Х1>1.));1=Ы/ <$2Д>1.=(#<1>)*.

14. Остальные правила источника Ш предназначены для реализации микроопераций дешифрирования, шифрирования, мультиплексирования, демультиплексирования и сравнения.

15. Базовые дешифраторы "1 на 2", "2 на 4" и "3 на 8" реализованы по линейной схеме. Кроме того, в дешифраторах "2 на 4" и "3 на 8" предусмотрены входные буферные каскады на инверторах.

16. На рис. 5.7, 5.8,а-б приведены вентильные эквиваленты правил описания МОП дешифрирования "1 на 2" (правило 51 в 121), "2 на 4" (правило 55 в \ЪХ) и "3 на 8" (правило 59 в К!).11. Рис. 5.7

17. Указанные правила имеют вид: 51 ЕСЛИ

18. У>2АМ-1:0. :=БС(<Х1>[№ 1],<Е>)*1 НА 2" В БАЗИСЕ И,НЕ/1. ТО

19. Л=1/ <$2,1 >1.=(&/2/(А/1 /(#<Х 1 >)),(#<Х2>));1=2/ <$гД>1.=(&/2/(#<Х1>),(#<Х2>))*;55 ЕСЛИ

20. У>2л.чИ:0] :=БС(<Х1>[№ 1],<Е>)*2 НА 4" В БАЗИСЕ ~ И,НЕ/1. Рис. 5.8,а1. ТО1=1:2/ <$г,3>1.=(л/1/(#<Х1>1.));1=1:2/ <$Z,2>1.=(A/1/(#<$Z,3>I.));

21. Я=1/ <$Z,l>1.=(&/3/(#<$Z,3>l.),(#<$Z,3>[2]),(#<X2>));1=2/ <$г,1>1.=(&/3/(#<$г,2>1.),(#<$2,3>[2]),(#<Х2>));1=3/ <$Z,l>1.=(&/3/(#<$Z,3>l.),(#<$Z,2>[2]),(#<X2>));1=4/ <$2,1>И=(&/3/(#<$г,2>1.),(#<$г,2>2.),(#<Х2>))*; 59 ЕСЛИ

22. У>2лМ-1:0. :=БС(<Х1>[№ 1],<Е>)*3 НА 8" В БАЗИСЕ И,НЕ/1. ТО

23. Построение других дешифраторов рассмотрим на примере дешифратора "4 на 16" (правило 63 в Ш:63 ЕСЛИ

24. Вентильный эквивалент этого правила представлен на рис. 5.9. Первые 12 строк данного правила описывают с помощью цикла по I два дешифратора "2 на 4". Последние 2-е строки соответствуют ступени элементов И.