Введение к работе
Актуальность исследования. Функционально- логическое проектирование (ФЛП) является начальным этапом в разработке цифровых устройств (ЦУ) и поэтому во многом определяет все их свойства. Одним из основных свойств ЦУ является согласованность по сложности и быстродействию всех частей и элементов для выполнения общей для них задачи с минимальными аппаратурными затратами за время, не превышающее наперед заданной величины.
Вопросы структурно- временного согласования (кратко TS-согласования) цифровых вычислительных устройств и систем (ЦВУ и ЦВС) получили фундаментальное развитие в работах А.Г. Алексенко, СИ. Баранова, В.М. Глушкова, В.А. Горбатова, Е.А. Дроздова, А.Д. Закревского, У. Квайна, В.Г. Лазарева, О.Б. Лупанова, С.А. Майорова, Р. Миллера, В.А. Мищенко, Дж. Неймана, Д.А. Поспелова, Д. Рота, А. Фридмана, СВ. Яблонского и других российских и зарубежных ученых.
Высказывание о необходимости структурно- временного согласования ЦВУ и ЦВС восходит еще к Дж. Фон Нейману, отмечавшему в своей теории организации сложных автоматов, "... что одним из решающих свойств вычислительных машин является равновесие: равновесие между быстродействием отдельных частей, баланс между быстродействием одной части и размерами других частей".
Однако до сих пор применительно к ЦВУ и ЦВС TS- согласование нередко проводится на основе опыта и интуиции разработчика обычно методом проб и ошибок либо делается попытка использования общих методов математического программирования, например, методов линейного программирования, которые, к сожалению, не отражают межблочные связи, а потому изначально приводят к потере сетевого характера рассматриваемых объектов оптимизации, что делает их в итоге недостаточно эффективными.
В то же время для оптимизации сетевых задач более естественным было бы использование потокового подхода, позволяющего проводить оптимизацию на основе простых итеративных преобразований потока в сетях.
При разработке сложных многоблочных и многоразрядных ЦВУ и ЦВС с помощью современных систем проектирования, особенно интеллектуальных, необходим систематический метод TS- согласования, отслеживающий топологию устройства, допускающий эффективную программную реализацию и обеспечивающий баланс отдельных частей ЦВУ и ЦВС, при котором каждая часть обладает достаточными сложностью и быстродействием (но не более того), чтобы выполнить
возложенные на систему вычисления с минимальными аппаратурными затратами за время, не превышающее наперед заданной величины.
Все это приводит к необходимости разработки основ теории структурно- временного согласования цифровых вычислительных устройств и систем на основе потокового подхода. Потоковый подход позволяет резко сократить затраты памяти и время счета, что обеспечивает решение сетевых задач гораздо большей размерности, чем задачи линейного программирования общего вида.
Автоматический процесс формирования логики работы TS-согласованных ЦУ в настоящее время не мыслим без использования интеллектуальных систем проектирования (ИСпроект). Интерес к разработке интеллектуальных систем логического проектирования ЦУ обусловлен тем, что ФЛП является достаточно сложным и трудоемким процессом, остающимся до сих пор слабо алгоритмизированным и носящим эвристический характер, так как большая доля работ по синтезу логических схем ЦУ выполняется не машиной, а человеком.
Огромную роль в процессе поиска хороших логических схем (ЛС) играет опыт. За долгие годы работы многих поколений разработчиков в области ФЛП ЦУ накоплен значительный по объему опыт синтеза ЛС, предназначенных для реализации многих типовых функций. Наличие такого опыта, разбросанного по многочисленным литературным источникам и сосредоточенного в головах высококвалифицированных специалистов по синтезу ЛС, служит весьма благодатной почвой для организации и построения ИСпроект, позволяющих овеществить этот опыт и сделать его доступным для менее квалифицированных специалистов.
Основу построения различных интеллектуальных систем, в том числе и ИСпроект ЦУ, составляют методы искусственного интеллекта. В рамках этого научного направления получены значительные результаты благодаря трудам как отечественных, так и зарубежных ученых. Не претендуя на перечисление всех ученых, внесших весомый вклад в разработку теории и практики интеллектуальных систем, отметим только тех специалистов, работы которых были прямо или косвенно использованы автором в его исследованиях по проблеме построения интеллектуальных систем логического проектирования TS- согласованных ЦУ. Это И. Братко, В.Н. Вагин, Е.И. Ефимов, Л.Т. Кузин, В.Е. Кузнецов, В.М. Курейчик, Ж.Л. Лорьер, М. Минский, Н. Нильсон, С. Осуга, Э.В. Попов, Г.С. Поспелов, Д.А. Поспелов, П.Г. Уинстон, Д. Уотермен, X. Уэно, Дж. Элти, А. Эндрю, Р. Эшби и др.
В проведенных автором исследованиях процедуры TS- согласования играют необходимую роль одновременно как для собственно TS-согласования объектов проектирования, так и для построения соответствующих машин вывода самих ИСпроект. В последнем случае процедуры
TS- согласования по сути дела реализуют режим плавающей системы приоритетов, когда приоритетность правил базы знаний ИСпроект ЦУ не фиксируется заранее, как это обычно делается в известных интеллектуальных системах, а определяется по результатам структурно-временного согласования объекта проектирования и поэтому может изменяться.
Кроме задач синтеза, решаемых на этапе функционально-логического проектирования, важной проблемой является анализ цифровых устройств. Основными задачами анализа ЦУ, получившими наибольшее распространение, являются проверка исправности, работоспособности, правильности функционирования, а также поиск неисправностей. Решением этих задач занимается такая научная дисциплина, как техническая диагностика.
В своем развитии методы технической диагностики ЦУ прошли значительный путь: от традиционных детерминированных методов (большинство из них достаточно хорошо исследованы и изложены в фундаментальных работах Р.С. Гольдмана, В.А. Гуляева, В.И. Казначеева, В.В. Карибского, П.П. Пархоменко, А.Н. Скляревича, Е.С. Согомоняна, Н.А. Соловьева, В.Ф. Халчева, Г. Чжена, В.П. Чипулиса, СВ. Яблонского и др.) до компактных вероятностных методов, использующих случайные входные сигналы (в этом направлении наибольшую известность получили работы В. Агравала, М.С. Берштейна, Б.Л. Долинского, Дж. Лоска, К. Паркера, А.М. Романкевича, Дж. Савира, В.Н. Ярмолика и др).
Однако, вопросы применения случайных входных сигналов (СВС) для вероятностного функционально- логического анализа разработаны и исследованы недостаточно. Отсутствуют эффективные методы расчета параметров систем вероятностного функционального (только по внешним вход/выходам) анализа сложных ЦУ, находящихся под воздействием СВС с различными законами распределения. Необходима разработка экономичных методов вероятностного логического (с использованием логической схемы) анализа, обеспечивающих обнаружение и поиск с помощью СВС неисправностей с наперед заданными качественными характеристиками.
Цель работы. Разработка методов организации и построения интеллектуальных систем логического проектирования TS- согласованных цифровых устройств.
На защиту выносятся:
-
Потоковый подход к TS- согласованию цифровых вычислительных устройств.
-
Методология высокоуровневого синтеза параллельных проблемно-ориентированных цифровых вычислительных систем на базе потокового подхода к их TS- согласованию.
-
Концептуальная и пользовательская модели интеллектуальных систем логического проектирования операционных элементов комбинационного типа.
-
Методология организации и построения основных компонент интеллектуальных систем логического проектирования цифровых устройств: диалогового процессора, планировщика, базы знаний, базы данных, интерпретатора, TS- согласователя и др.
-
Методы вероятностного функционального анализа сложных цифровых устройств со многими выходами, полностью не требующих перебора неисправностей.
-
Теоремы существования проверяющих и различающих совокупностей контрольных точек и методика расчета основных параметров вероятностного логического анализа, обеспечивающих обнаружение и поиск константных неисправностей с любыми наперед заданными качественными характеристиками- вероятностями ложного срабатывания, необнаружения неисправности и неправильной ее локализации.
-
Методы вероятностного логического анализа сложных комбинационных устройств с использованием только внешних выходов объектов анализа.
Методы исследования. Теоретическая и методологическая части работы базируются на методах и моделях искусственного интеллекта, теории потоков в сетях, принципах организации и построения цифровых вычислительных машин, теории структурного программирования, математическом аппарате технической кибернетики (теории конечных автоматов, булевой алгебры, теории графов, сетевых графиках, теории вероятностей и математической статистики), а также на моделях, методах и алгоритмах автоматизированного проектирования цифровых устройств и их технической диагностики.
Научная новизна. В диссертационной работе получены следующие основные результаты, характеризующиеся научной новизной:
-
Разработаны основы математического аппарата структурно-временного согласования цифровых вычислительных устройств, позволяющего с единых позиций проводить TS- согласование как отдельных частей ЦВУ (операционных; элементов комбинационного и накапливающего типов, операционных и управляющих автоматов), так и ЦВУ в целом.
-
Разработан потоковый подход к TS- согласованию параллельных проблемно- ориентированных цифровых вычислительных систем, позволяющий выполнить синтез ЦВС, начиная от обычной последовательной граф- схемы алгоритма (ГСА) и заканчивая параллельной TS- согласованной структурой, реализующей заданную ГСА.
-
Предложены концептуальная и пользовательская модели интеллектуальных систем логического проектирования TS- согласованных операционных элементов комбинационного типа (ОЭКТ), обеспечивающие формализацию знаний в области их синтеза с помощью правил продукционных экспертных систем.
-
Разработан специализированный язык представления знаний в области синтеза ОЭКТ на основе компактных линейных деревьев, допускающих в отличие от обычных линейных деревьев такие конструкции как: одиночный и кратный циклы вне линейных деревьев, а также циклы произвольной вложенности внутри линейных деревьев.
-
Выделены и формализованы основные этапы обработки проектируемых логических схем, представленных на языке компактных линейных деревьев и в виде динамических таблиц.
-
Разработана модель экспертного логического синтезатора, предназначенного для быстрого синтеза TS- согласованных ЦВУ с минимальным участием человека.
-
Разработан метод вероятностного функционального анализа сложных многовыходных цифровых устройств по обобщенному параметру, полностью не требующий перебора неисправностей. В качестве входных воздействий при этом используются случайные сигналы, распределенные по равномерному и нормальному закону, а также по закону Симпсона.
-
Разработан быстрый метод расчета параметров вероятностного функционального анализа цифровых устройств с эталонными блоками, также полностью не требующий перебора неисправностей.
-
Сформулированы и доказаны теоремы существования проверяющих и различающих совокупностей контрольных точек, обеспечивающих при равновероятных случайных входных сигналах соответственно обнаружение одиночных и кратных константных неисправностей и поиск одиночных константных неисправностей комбинационных устройств.
-
Разработана методика расчета основных параметров вероятностного логического анализа ЦУ, обеспечивающих с использованием проверяющих и различающих совокупностей контрольных точек выполнение любых наперед заданных качественных характеристик обнаружения и поиска- вероятностей ложного срабатывания, необнаружения неисправности и неправильной локализации неисправности.
-
В предположении с/г/чайного характера неисправностей на основе методов восстановления неизвестных плотностей распределения в рамках константной модели неисправностей разработаны эффективные методы расчета параметров вероятностного логического анализа сложных комбинационных устройств.
Практическая значимость и ценность работы заключается.
в разработке базовых структурных моделей ОЭКТ, рассчитанных на блочную компоновку микроопераций, что значительно упрощает введение процедуры замены эквивалентных микроопераций одним общим оператором;
в разработке системы базовых микроопераций ИСпроект, используемой в качестве входного языка ИСпроект ОЭКТ;
в создании базы знаний, содержащей свыше 300 правил (продукций), отражающих имеющийся опыт синтеза ОЭКТ. Многие из этих правил выкристаллизовывались поколениями разработчиков и прошли проверку временем;
в разработке конкретной версии экспертного логического синтезатора "ЭЛС", вобравшей в себя предложенные методы организации и построения математического и алгоритмического обеспечения интсллекгуальных систем логического проектирования цифровых устройств;
в разработке методик, алгоритмов и программ построения проверяющих совокупностей контрольных точек и восстановления неизвестных плотностей распределения вероятностей единичных выходных сигналов, обеспечивающих вероятностный анализ цифровых устройств реальной сложности.
Реализация результатов работы. Результаты исследований по разработке методов построения интеллектуальных систем логического проектирования TS- согласованных цифровых устройств реализованы при выполнении НИР "Разработка теории интеллектуальных систем проектирования высоконадежных и отказоустойчивых мультипроцессорных устройств обработки информации и управления", проводимой на факультете информационных систем и технологий Нижегородского государственного технического университета и финансируемой в рамках единого заказ- наряда (названная тема входит в раздел "Информационные технологии и электроника" по группе "Системы искусственного интеллекта" перечня критических технологий федерального уровня, одобренного правительственной комиссией по научно- технической политике от 21.07.1996 г. №2727п-П8), в программном продукте НИР "Разработка экспертной системы для автоматического функционально-логического проектирования цифровых устройств с применением базовых матричных кристаллов" (х/д Н/075МС, 1991.- 967 с), а также применяются в учебном процессе при чтении курсов лекций "Цифровые автоматы" и "Основы теории интеллектуальных вычислительных систем" для студентов специальности 22.01- "Электронные вычислительные машины, системы, комплексы и сети" НГТУ.
8 . - '
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всесоюз. науч.-техн. конф. "Дальнейшее развитие и внедрение новой техники приемных устройств" (Москва- Горький, 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 таблиц.
