Введение к работе
Актуальность проблемы. Под дискретным автоматом здесь подразумевается система логического управления, или-управляющая система со свойствами конечных абстрактного и структурного автоматов, понимаемых в том широком смысле, который допускает в схеме автомата элементы с управляемой проводимостью, двунаправленные каналы передачи информации, отождествление выходных полюсов компонент и многозначность структурного алфавита, присущие современным большим (БИС) и сверхбольшим (СБИС) интегральным микросхемам. В автомате на полурешетках каждая переменная принимает значения в некоторой конечной верхней полурешетке, т. е. в частично упорядоченном множестве, в котором любые два элемента имеют точную верхнюю грань, называемую суммой этих элементов, и которое вместе с математическими действиями, "моделирующими структурные операции в автомате, образует полурешеточно упорядоченную алгебру. Имеются по меньшей мере три свидетельства актуальности теории дискретных автоматов на полурешетках.
Во-первых, математический аппарат классических функциональных систем (алгебры логики, многозначной логики, теории автоматов) , будучи удобным языком для адекватного описания статического (при фиксированном входном состоянии) поведения дискретного устройства, к сожалению, недостаточен для адекватного описания динамического (вызываемого асинхронным изменением компонент входного состояния) поведения устройства. Этот недостаток преодолевается в функциональных системах на полурешетках,' каковыми являются полу-ре шеточно упорядоченные алгебры. В описании динамического поведения дискретного автомата средствами такой алгебры отношение.порядка в последней интерпретируется как отношение сравнения состояний в автомате по степени их неопределенности, обязанной явленкв состязаний, которые возникают между компонентами состояния в процессе их асинхронного изменения, а сумма состояний в полурешзтке моделирует это изменение как промежуточное (переходное) состояние. Далее, в функциональных системах с частично определенными функциями, такими, как частичные функции конечно-значной логики , частичные автоматы, частично-рекурсивные функции и т.п., неопределенность значения переменной (аргумента, функции) трактуется обычно одним способом - как любое из всех возможных определенных вначений этой переменной. В приложениях к дискретным автоматам, в особенности на базе БИС, такая трактовка ведет нередко к снижению
- г -точности используемых моделей со всеми вытекающими отсюда неприятными последствиями: в синтезе затрудняются формализация исходных функций и их декомпозиция, в анализе - теряется необходимая информация. Этот недостаток математического аппарата можно преодолеть, если в область значений каждой переменной ввести разные значения неопределенности, где каждое .значение неопределенности трактуется как любое из некоторых определенных значений. Подобное размножение неопределенности означает фактически расширение области значений переменной до верхней полурешетки подмножеств множества определенных значений.
Наконец, важнейшими характеристиками любой математической модели, чем в сущности и служит дискретный автомат, являются ее адекватность и степень точности. В случае дискретных моделей первая понимается как безошибочность в том смысле, что результат адекватного моделирования всегда содержит в себе истинное значение моделируемой величины, а вторая - vssty степень неопределенности этого результата /1,2/. Аппарат теории полурешеток и полуреше-точно упорядоченных алгебр позволяет формализовать эти понятия, если принять, что в адекватной модели оперируют с наибольшими элементами смежных классов основной полурешетки по некоторой конгруэнции, которая, собственно, и представляет собой степень точности этой модели. В рамках этого аппарата удается формализовать также понятие физической реализуемости функций дискретного автомата,' выразив его в понятии квазимонотонности, определяемой как реализуемость монотонной функцией, которая, в свою очередь, выражается через отношение порядка в основной полурешетке.
Актуальность теории дискретных автоматов на полурешетгах подтверждается включением исследований по ней в 1981-1990 гг. в Координационные планы работ АН СССР (по проблеме "Кибернетика"), МВиССО СССР (по программе "Микропроцессоры и микро-ЭВМ"). МВиССО РС<КР (по программе САПР), стран-членов СЭВ (но теме 25.01KJ и в 1S92-1995 гг. в Программу "Университеты России" (по направлениям " аундамеигальные проблемы математики и механики" и "Математическое моделирование").
Целью работы является создание математической теории дискретных автоматов на полурешетках для решения задач логического проектирования дискретных динамических систем логического управления, в том числе на базе БИС и СБИС и микросхемах промышленных серий. Достижение этой цели предполагает развитие в соответствую-
- з -щем направлении теории полурешеток и полурешеточно упорядоченных алгебр, разработку основ теории функциональных систем и конечных автоматов на полурешетках, создание подходяще'й дискретной математической модели БИС на транзисторном и вентильном уровнях абстракции, разработку методов их проектирования, включая абстрактный и логический синтез с заданным динамическим поведением, логический анализ и адекватное моделирование с заданной точностью, эквивалентные преобразования и минимизацию форм представления, функциональную и структурную декомпозицию, а также проверку разработанных математических аппарата, модели и методов на реальных объектах и задачах проектирования.
Методы исследования представляют собой сочетания методов дискретной математики (комбинаторного анализа, многозначной логики, теории автоматов, теории синтеза управляющих систем) и общей алгебры (теории полурешеток и полурешеточно упорядоченных алгебр) .
Научная новизна. Принципиально новым здесь является то обстоятельство, что рассматриваемые автоматы функционально описываются в терминах переменных, определенных не, как обычно, на абстрактных множествах, но на конечных верхних полурешетках.
В теории это позволило, во-первых, формализовать такие поня- \ тия как адекватная модель, динамическое поведение и физическая реализуемость дискретного автомата и сделать утвервдения о них доказательными, во-вторых, традиционные задачи (эквивалентных преобразований, минимизации, декомповиции, кодирования, анализа, синтеза) поставить и решить в новой, более общей постановке, отражающей динамику поведения автомата и отвечающей требованиям его физической реализуемости, и в-третьих, должным образом развить необходимый математический аппарат теории полурешеток и полурешеточно упорядоченных алгебр, в том числе получив ряд новых результатов в этой области.
В приложениях же к логическому моделированию БИС это позволило расширить, класс регистрируемых состояний узлов схемы за счет так называемых динамических состояний разной степени неопределенности, представленных подмножествами статических состояний, указав тем самым фактически новую возможность для повышения точности и разрешающей способности дискретиьж моделей.
Кроме того, принципиально новым в представленной здесь переключательной модели БИС на транзисторно-вентильном уровне абс-
- 4 -тракции является то обстоятельство, что в ней, в отличие от известных теперь моделей (Дж-МЗейес, R.E.Bryant, F. J. Ramming и др.), во-первых, возможные статические состояния узла схемы не постулируются изначально как нечто данное извне и моделирующее значение и силу сигнала в узле, но представляются тем, чем последние в сущности и определяются,- наборами проводимостей схемы . от полюсов источника питания до этого узла и, во-вторых, любая компонента БИС (диод, резистор, транзистор, логический вентиль и т.п.) представляется изначально не как элемент для преобразования сигнала - функциональный элемент, но в соответствии с ее физическими основами как элемент с управляемыми проводимостями - переключательный элемент, вследствие чего моделирование схемы сводится к вычислению не значения и силы сигнала в ее узле, но именно проводимостей схемы до узла от полюсов источника питания, в том числе через входы схемы. Этим достигается одновременно и однородность модели, обеспечивающая единообразие, в моделировании схем из разнородных элементов - транзисторов, резисторов, вентилей, ключей и др., и ее адекватность схемам, выполненным по самым разным технологиям, чего не скажешь про другие модели.
Практическая значимость. Полученные в диссертации результаты могут служить теоретической основой для разработки практических алгоритмов логического проектирования и моделирования, в том числе адекватно с разной степенью точности и неопределенности, динамического поведения дискретных управляющих устройств и их современной элементной базы - БИС и СБИС на транзисторном, вентильном и конечно-автоматном уровнях представления. В развитие отдельных положений и идей диссертационной работы под руководством автора выполнены и успешно защищены пять кандидатских диссертаций, четыре из которых имеют указанную практическую направленность. Данное в диссертации решение задачи структурной декомпозиции - покрытия схем свободными модулями распространяется на системы модулей, которые серийно выпускаются отечественной промышленностью.
Реализация результатов работы. Основные элементы теории дискретных автоматов на полурещетках реализованы в промышленных системах функционально-логического проектирования матричных КМОП ВИС в ОКЕ при КПП Новосибирский завод полупроводниковых приборов, где на большом производственном опыте (спроектировано несколько десятков реальных ЫК и СБИС) подтверждена эффективность этой теории, ее адекватность как проектируемым объектам, так и задачам проек-
-5.-тирования, включая моделирование,* анализ, синтез, тестирование. Теория дискретных автоматов на полурешетках составляет также математическую основу подсистемы проектирования цифровых сверхскоростных интегральных микросхем на арсениде галлия в Томском НИИШ1 Программы логического синтеза, использующие ее математический аппарат, работают в САПР РЭА, реализуемых на БИС, в ЦКБ "Алмаз" (г. Москва). Методами декомпозиции, развитыми в диссертации, в ОКБ РА при Томском РТЗ спроектирована цифровая ячейка для сложного комплекса аппаратуры, прошедшая необходимые испытания и выпускаемая серийно. Наконец, в Томском госуниверситеге на факультетах радиофизическом и прикладной математики и кибернетики результаты диссертации используются в ряде курсов лекций по дисциплинам специализаций "Математическая электроника" и "Математическое обеспечение САПР электронной техники", а в Томском институте АСУ и радиоэлектроники - в учебно-исследовательской САПР ЛОГИКА-Т.
Апробация работы. Основные результаты диссертации докладывались на XI Международном конгрессе ИФАК в 1990 г. в Таллинне, на четырех международных конференциях (по основам теории вычислений в 1987 г. в Казани, САПР СВТ-89 в 1989 г. в Ленинграде, по алгебре в 1989г. в Новосибирске и в 1991 г. в Барнауле), на международном совещании стран - членов СЭВ по теории автоматов и ее при- t ложениям в 1983г. в Таллинне, на'IV Международном семинаре по дискретной математике в 1993 г. в Москве, на VIII Всесоюзной конференции по проблемам теоретической кибернетики в 1988 г. в Горьком, на 1 Всесоюзном совещании по автоматизации проектирования интегральных схем в 1978 г. в Киеве, на XI Всесоюзном совещании по проблемам управления в 1989 г. в Ташкенте, на Всесоюзных школах-семинарах им. U А. Гаврилова по теорий дискретных автоматов (в 198211 г. в Миассе,' в 1983 г. в Киеве) и по ЕС ЭВМ (в 1987 г. в Тбилиси, в 1989 г. в Киеве), на многочисленных-научных семинарах в ИК АН Украины, ИТК АН Беларуси, ИПУ РАН, НИИШ, МГУ, КГУ, ТГУ. СФТИ.
Структура и объем диссертации. Диссертация представляет собой опубликованную монографию /21/ и приложение. Монография состоит из введения и восьми глав, ее объем - 14.25 леч. л., библиография - 9S наименований; объем приложения - 12 стр.
