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

Белорусский государственный университет ¡шформлтгаа? и радиоэлектроники

УДК 681. 3. 16. 513 : 714. 24

Р Г б и -1

* г "ТЧ '••

Левашенко Виталий Григорьевич

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

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

Минск, 1996.

Работа выполнена на кафедре "Вычислительные методы и программирование Белорусского государственного университета информатики и радиоэлектроники кафедре "Информационных технологий" Белорусского государственног экономического университета.

Защита состоится,21 ноябрч 1996 года в 14 часов на заседании совета по задпгге диссертации Д02.15.01 в Белорусском государственном университете информатики и радиоэлектроники по адресу: 220027, Минск, ул.П.Бровки, 6.

С диссертацией можно ознакомиться в библиотеке Белорусского государственного университета информатики и радиоэлектроники.

Автореферат разослан 21 октября 1996 г.

Ученый секретарь совета по защите диссертаций доктор технических наук,

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

Научный руководитель:

доктор технических наук, профессор, Шмерко В.П.

доктор технических наук, профессор, Ярмолик В.Н.

кандидат технически наук, доцент Супрун В.П.

Оппонирующая организация: Институт технической кибернетики АН РБ

профессор,

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Известны методы синтеза параллельных алгоритмов для реализации логических дифференциальных операторов. Однако класс так называемых направленных логических дифференциальных операторов остался малоисследованным. Их использование позволяет эффективно решать ряд задач анализа дискретных устройств, Например, тестирование схем на т-уровневы\ . элементах. Поэтому, актуальными являются задачи разработки параллельных алгоритмов анализа дискретных устройств на основе направленных логических дифференциальных операторов и аппаратных средств для га реализации, удовлетворяющих требованиям современной технологии СБИС. Эти алгоритмы востребованы в современном логическом проектировании дискретных у стропа в на т-уровневых элементах. Решаемые в работе задачи отвечают современным тенденция» в проектировании и создании устройств, состоящих из бинарных и т-уровневых элементов.

Связь работы с научными программами, темами. Работа выполнена в рамках программы "Информатизация" на 1991-1995 гг. и на период . до 2000 г., утвержденной Постановлением № 444 Совета Министров Республики Беларусь от 27.11.91, а также в рамках научно-исследовательских тем БГУИР "Алгоритмы и высокопроизводительные вычислительные средства в системах технического зрения и искусственного интеллекта" (1992-1995), "Разработка прикладной теории логического дифференциального исчисления" (199Л). "Разработка инструментальных средств прикладной теории логического дифференциального исчисления" (1994), "Разработка технологии применения

z

прикладной, теории логического дифференциального исчисления" (1995), ■ "Разработка методов и алгоритмов обработки /и-значных функции алгебры логики" (1996) и Института Информатики Щецинского технического университета (г.Щецин, Польша) "Methods and Algorithms of Logic Differential Calculus to solve problems of discrete devices synthesis and analysis", а также используется в учебных курсах "Логическое проектирование цифровых устройств", "Логические основы цифровых устройств", "Прикладная математика" ряда университетов. ' _

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

- формально описывается и расширяется класс направленных логических дифференциальных операторов на основе матричного математического аппарата;

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

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

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

Научная новизна полученных результатов состоит в том, что:

- впервые получены параллельные алгоритмы вычисления направленных логических дифференциальных операторов;

- разработаны структурные схемы устройств для реализации полученных алюритмов, оригинальность и новизна которых подтверждена 3 авторскими свидетельствами на изобретения СССР;

- предложена модификация алгоритма тестирования /и-уровневых схем на принципе активизации многомерного пути.

Практическая значимость полученных результатов состоит в том, что они направлены на решение класса актуальных прикладных задач

логического проектирования дискретных устройств на m-уровневых элементах. Наиболее важными для практических приложении являются :

- комплекс программ для экспериментальных исследований на основе направленных логических дифференциальных операторов;

- методики Использования разработанных алгоритмов при тестировании схем на тя-уровневых элементах;

- учебный программный комплекс, ориентированный на. использование в учебных курсах.

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

Основные положения диссертации, выносимые на защиту.

1. Алгоритмы вычисления направленных логических дифференциальных операторов и решения булевых дифференциальных уравнений.

2. Модификация алгоритма тестирования комбинационных схем на ш-уровневых элементах.

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

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

Апробация результатов диссертации. Основные результаты работы докладывались и обсуждались на: Всесоюзных туполевскнх чтениях "Актуальные проблемы авиастроения" (Казань, 1990), НТК стран СНГ "Распознавание образов и обработка изображений' (Минск, 1993). юбилейной НТК ММВИУ "Проблемы совершенствования и эксплуатации радиотехнического и радиоэлектронного вооружения и автоматизированных систем управления" (Минск, 1993), НТК БГУИР (Минск, 1993), Международной НТК "Новые информационные технологии в учебном процессе" (Минск, 1994). International Conference on Applications of Computer (Szczecin, Poland, 1994). 17 International Symposium of Students and Young Scientist, (Zielona Gora, Poland, 1995), НТК "Современные проблемы радиотехники, электроники и связи" (Минск. 1995). ПипI International Sientißc Conference on Pattern Recognition and Information Analysis

(Minsk, 1995), Workshop ort Sampllng Theory & Applications (Riga, Latvia, 1995), International Symposium on Methods and Models in Automation and Robotics. (Miedzyzdroje, Poland, 1995), НТК "Автоматизация проектирования дискретных систем" (Минск, 1995), International Conference "Modern Methgods о/Signal processing in evaluatioi), control, and diagnostic systemf (Minsk, 1995) International Conference Computer Methods and Jnverse Problems in Nondestruclive Testing and Diagnostic (Minsk, 1995), 26th International Symposium on Multiple Valued Logic (ISMVL'96, Santiago-de-Compostela, Spaij)), Workshop on 'Design Methodologies for Signal Processing.

. (Zakopane, poland, 1996), а также на научно-технических семинарах кафедры "Вычислительные методы и программирование" БГУИР и НИЛ "Обработка изображений и распознавание образов" того же университета, НИЛ "Новые информационные технологии в экономике и управлении" Белорусского государственного экономического университета и Института Информатики Щецинского технического университета (Польша).

Опубликованность результатов. По теме диссертации опубликовано 32 научных работы, в том числе 5 статен в' периодических журналах, 12 статей в реферированных сборниках трудов конференции, получено 3 авторских свидетельства СССР на изобретение.

Структура и объем диссертационной работы. Рабйта состоит из введения, четырех разделов, заключения, списка используемых источников in 166 наименований, приложения и содержит 155 страниц текста, включающего 37 таблиц, 60 рисунков.

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

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

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

Анализ современных тенденций развития алгоритмов логического дифференциального исчисления позволяет условно выделить два подхода. Первый подход основан на символических преобразованиях логических выражений. В рамках данного подхода наиболее заметны результаты, получение А.Д.Таланцевым (1959), S.Akers (1959), F.Setlere (1959), A.Browti (1969). A.TIiayse и M.Davio (1971), J.Tucker (1977), D.BocIimaini (1981), D.Gfeeu, C.Moraga. Второй подход основан на регулярных матричных преобразования и эффективен в случаях, когда данные представлены в векторной (табличной) форме. Этот подход позволяет использовать не только программную реализацию вычислений в среде типовых пакетов программ'матричной алгебры, но и аппаратную - на однородных и систолических массивах^ Большой вклад в развитие данного подхода внесли А.Д.Закревский (1962), S.Lee (1974), А.М.Морозов (I97S), J.Muzio (1986), В.П.Шмерко (1989) и их научные школы.

Особый класс логических дифференциальных операторов составляют направленные операторы, включающие, направленные логические производные ФАЛ (direct and inverse partial derivatives). Последние определяют условия, при которых изменение значений входных сигналов (возрастание, убывание) приводит к возрастанию пли убыванию значении на выходе схемы. Это . позволяет более детально исследовать структуру и динамику логического объекта. Впервые операторы этого типа исследованы в работах A.Brown (1969). J.Tucker (1977, 1985) и обобщены T.Giuma (1987). Ими получены алгоритмы вычислений, основанные на символических преобразованиях.

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

6 >

Вторая глава содержит основные теоретические результаты работы.

Равнонаправленная и разнонаправленная логические производные булевой ФАЛ /(А|,Х2,...,хл) в векторно-матричной форме вычисляются по формулам : дХ/д+х, = (Р«-°> -Х) • (/£•'> -X), ОХ/сХх/ = (Р<!'°> -X) • (Р«:" X). (I)

' Здесь - вектор значений ФАЛ (столбец таблицы истинности)

матрица дифференцирования Р^" по 1-й переменной с параметром /•;((), 11 формируется по правилу :

-12м ® р2(/> ® ъ'-к р2(/)=[ фх0) фх 1) ] « | ,

где ¡2/-1 и Ь«-/ - единичные магрицы размерности 2'чх2м и 2""'х2',~' соответственно, символом ® обозначена операция кронекеровского Произведения матриц. Операционные графы параллельного алгоритма вычисления направленных логических производных булевой ФАЛ п переменных

(л=3) на основе соотношения (I) приведены на рис.1 (символы □ и О обозначают соответственно операции отрицания и конъюнкции). Эгот алгоритм позволяет выполнит ь анализ устройств на бинарных элементах, основанный на определении условий, при которых изменение входных сигналов происходит в одном или разном направлении с направлением изменения выходного сигнала.

Далее приводится параллельный алгоритм решения булевых

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

йХ/,%*) V,'

X)

Рис.1

дХ/д.х,- Уэ

—

л

Приводится обобщение соотношения (1) для функций т-значной лотки. Направленная логическая производная по частной переменной х,- функции т-значной логики, заданной вектором значений X, отражает факт изменения значения функции с у на к при изменении значения переменной г,- с п до Ь. и в векторно-матрнчной форме определяется в виде

дХ{/-+к)/дх,(а->Ь) = • (Р^/'-фПХ)) . (2)

В (2) <|),(Х) (.5 ={/,£}) является векторным литералом: ф5(Х)=|ф5(л<0)).•.ч>1(-^т',",')1т-Матрта дифференцирования Р^'," по переменной г, с параметром формируется по правил)':

т-1

р1':" = Мт/-1 ® в МтЛ-1, Рт("= [фх0)фх1).-ф/т-1)]»

где Мт/'-1 и М„л-/ - диагональные матрицы размерности т1

I .

соответственно, Операционные

ех{]-+к>

у,""

вМ

♦П к 1

-О/ —5#>~|

■»п * -^-»ъ-»'

♦а /

содержащие на гл_авной диагонали значение (н/-1). графы, алгортма вычисления направленной логической производной У/0'" = гХ(/->к)/дх,(П->\) т-значной (т=3) ФАЛ и переменных (п=2) приведены на рис.2.

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

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

В третьей главе излагаются вопросы применения разработанных алгоритмов вычисления направленных логических производных т-значных ФАЛ при тестировании комбинационных схем на /л-уровневых элементах.

Предложен алгоритм, основанный на использовании понятия направления (ориенташш) Б-кубов для т-уровневых элементов (ОП-кубов). Это является модификацией алгоритма активизации многомерного пути Я^рШтап и

Излагается методика использования предложенного алгоритма. На примерах показаны такие его новые качества, как независимость от базиса элементов и их значности т; возможность обнаружения неисправностей, характерных для различных технологий.

и т

ч

Например, требуется построить тест для неисправностей "константа 3" и "сдвиг 2->3" на полюсе 8 комбинационной схемы на 4-х уровневых элементах (рис.3).

хг

Эти неисправности заключаются в изменении сигнала уровня логической 2 на уровень логической 3 (02,3).

Определим элементы, находящиеся

щ

Рис.3.

на путях транспортировки изменения Dj-,3 на выход схемы (путь I: элемент T^(X)=(X|VX2)+J (mod 4) и компаратор comp; путь 2: элементы И, /|(X)=(x"|/Yvi) + l (mod А), ИЛИ и компаратор). Сформируем DD-кубы для этих элементов (табл.1). Активизируем путь транспортировки изменения Dj-,3 от полюса 8 (табл.2).

_ Та б л иц а I

Функция и ее отличная от нуля направленная логическая производная DD-куб

Входные полюса Выход

№)=тт(х 1, хг> , X=|ü000 0111 0)22 0123] Оз., 3 d2j

¿X(2->3)/exi(2-»3) = 10003 0003 0003 00031

rtX)=max(xt, xi), Х=|0123 1J23 2223 3333) D3.» 2 D3.2

dX(3->2)/fti|(3-»0) = 10030 0030 0030 00301

Л(Х)=(*1/и2)+1 (mod 4), Х=|1111 1222 1233 12301 D2.,i 3

0X(3-»O)/(V|(2-»3) = 10003 0003 0003 0003|

Л(Х)=»(х|У«)+1 (mod 4), X=[1230 2230 3330 00001 D> ,1 U, * D., ,o

cX(3-+0)/ÖX|(2-*3) = 13330 3330 3330 3330|

co/np(xi,x2), X=|1222 0122 0012 00011 Dj ,o D| .3

ßX(l-»3)AX*i(3-»0),*2(3->2)) 13000 3000 3000 30001

Литерал - 2-V , X = (22201

* В табл. и далее символом Uj отпечено множество значений (0, 1,2).

Tu б л и ц и 2.

Элемент Номер полюса в комбинационной схеме

I 2 3 4 5 ft 7 8 9 10 и 12 n '

D 3 D? л D? л

E 3 Di,, DT ,„

F 2 D, Di.,

С и, D? л Ом

О Di .о Di. 5 D,

A и 0

В ц

Тест' U« и из 3 3 2 из П,.з О,.* D l ,) »1 D} г »1 1

' В табл. символом 112з отмечены значения из множества {I1 1, 2, 3), а симполоч Ч^ значения из множества {0, 1).

Тест для обнаружения неисправности "сдвиг 2->3" имеет вид: и2( и и( 3 2 2.

Для аппаратной поддержки этапа формирования ПО-кубов предложена структура однородного типа на т-уровневых элементах (рис.4 М,- (/=1.....п) -

Вит] X

модуль вычисления направленной го*т.<*. ' логической производной по /-Й переменной, О,- - модуль формирования по этой производной БО-кубов).

Проведены исследования затрат памяти при хранении ОИ-кубов в ПЗУ и даются рекомендашш по их применению.

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

В четвертой главе предстаачены средства аппаратной и программной поддержки разработанных алгоритмов,. Предложены структуры устройства однородного типа для вычисления направленны* логических производных ФАЛ и систолических устройств для решения булевых дифференциальных \ равнении. Новизна и оригинальность этих структур подтверждена 3 авторскими свидетельствами на изобретения.

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

На

рис.5 представлена Такт

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

производных ет-значных ФАЛ и включающего п модулей (модуль содержит управляющую (УЯ), вычислительную (ВЯ) и запоминающую (ЗЯ) ячейки). Схема ('-й ВЯ приведена на рис.6.

выход

УЯ

I

УЯ

УЯ

ВЯ

п

ЗЯ

ВЯ

п

ЗЯ

Тикт.

ест?

пя

п

ЗЯ

Инфор. выгоды гХ(/-»/г)/сх/(а-*Ь) Рис.5

♦

Для решения булевых

дифференциальных уравнений, с п переменными, предлагаются

структуры устройств матричного (рис.7) Н линейного (рис.8) типов.

Каждая линейка ВЯ в устройстве на рис.7 и ВЯ в . устройстве на рис.8 решает одно их уравнений системы, к которой сводится решение булева дифференциального уравнения. Работу ВЯ

а'кк

СрШИ-ЮМ

Вад X!

¡-Я

нчаиса (1!Я г)

Второй

&ИЖ

4

* '\|>ммуилтф iK.-M.Ur И

-V

Рис.6.

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

Тактль$од_

1 УЯ - з УЯ УЯ

1 ВЯ I ВЯ 2" ВЯ

1Ьфчшицш<и

У.

. , { [ 1 { 1ДЯ П 4 *1 ™ I

Информационные выходы

Рис.7.

Тикт вьш* Упрюк*)

к Л

Пршнч*.

Ргу.НЛШПМ

УЯ 1

VII

!амп имя) Ьнр иылгя)

' При шах решения

И

«я 1

СЯ

СЯ

Инфнрмацишмы* кк1к1ы

Рис.Ь.

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

В главе представлены инженерные приемы и методики программной реализации полученных алгоритмов вычисления логических дифференциальных операторов в среде типового пакета программ матротной алгебры Ма<1аЬ 4.02. Эш приемы и методики использовались при создании программ для экспериментальных исследований, на основе которых разработан учебный программный комплекс логической обработки данных. Данный комплекс позволяет: (я) реализовать алгоритмы логического дифференциального исчисления ФАЛ и арифметической логики; (б) моделировать комбинационные

схемы на основе т-уровневых элементов; (в) строить тесты для обнаружения неиспрЛвностей в этих схемах.

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

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

выводы

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

' Главный результат диссертационной работы состоит в разработке параллельных алгоритмов вычисления направленный логических дифференциальных ' операторов булевых и т-значных ФАЛ и методик их использования при тестировании комбинационных схем на т-уровневых элементах.

По результатам работы можно сделать следующие выводы.

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

2. Расширен класс и получена матричная интерпретация логических дифферецциа.гы1ых операторов, а именно:

2.1. Впервые формально определена направленная логическая производная по вектору переменных т-значной ФАЛ ;

2.2. Разработаны матричные аналоги направленных логических производных и дифференциалов булевых и т-значных ФАЛ ;

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

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

3.1. Направленные логические дифференциальные операторы реализуются и виде регулярных и параллельных алгоритмоь ;

3.2. Решение класса булевых дифференциальных уравнений сводится к ортогональным преобразованиям ;

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

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

4.1. Применение в алгоритме Спиллмана и Су предложенных ГЮ-кубои потолило обобщить его для комбинационных схем на т-уровневых элементах в различных функциональных базисных системах

4.2. Формально доказано, что предлагаемая модификация алгоритма Спиллмана и Су, позволяет добиться новых функциональных возможностей, а именно: обнаружения типовых неисправностей, возникающих при создании СБИС на основе современных технологий. Корректность этого вывода подтверждена экспериментально на классе; типовых комбинационных схем

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

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

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

- разработаны оригинальные технические решения: однородная структура для вычисления направленных дифференциальных операторов т-значных ФАЛ; однородная структура на основе несвязанных линейных систолический массивов и линейный систолический массив для решения булевых дифференцихльных уравнении.

6. Результаты настоящей работы соискатель в целом оценивает как завершенный цикл научных исследований, результаты которых создан/ основу для решения ряда

■ качественно новых актуальных задач, среди которых к числу важнейших относится

- в области теории многозначных ФАЛ - установления связей направленных и логических (ненаправленных) дифференциальных операторов, решение логических дифференциальных уравнений, методы обработки неполностью определенных ФАЛ;

- в области прикладных исследований - адаптация разработанного алгоритма тестирования к конкретным технологиям создания дискретных устройств на т-уровневых элементах и системам логического проектирования;

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

По результатам исследований опубликовано 32 работы, из них 5'статен н научных журналах и сборниках научных статей, 3 авторских свидетельства на изобретение СССР, 12 полных текстов рецензируемых докладов на конференциях и симпозиумах, 5 технических отчетов.

СПИСОК ОСНОВНЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Левашенко В.Г., Шмерко В.П, Янушкевич С.Н. Решение булевых дифференциальных уравнений на систолических массивах // Кибернетика и системный анализ, АН Украины. ~ 1996, №1. - С.36-54.

2. Левашенко В.Г., Шмерко В.Г1, Янушкевич С.Н. Параллельные алгоритмы вычисления направленных логических производных многозначных ФАЛ // Кибернетика и системный анализ, АН Украины, (принята к публикации н 19%i).

3. Slimerko V., Yanushkevich S., Levashenko V., Bondar I. Tecluiiques оГ Computing Logical Derivatives for MVL-fimctions // IEEE Proc. of 26th Int. Symp. on Multivalued Logic (ISMVL'96). - Santiago de Compostela, Spain, 1996. - P.267-272.

4. Янушкевич С.Н, Левашенко В.Г., Шмерко В.П. Матричный алгоритм решения булевых дифференциальных уравнений на основе дискретного преобразования Фурье // Автоматика и вычислительная техника. Вып. 19. -Мн.: Вышэйшая школа. - 1990. - С.79-83.

5. Колодиева И.Л., Янушкевич С.Н, Левашенко В.Г. Методы решения булевых дифференциальных уравнений на древовидно-сетевой структуре // Автоматика и вычислительная техника. Вып. 20. - Мн.: Вышэйшая школа. -1991. - С.102-105.

6. Левашенко В.Г., Мусиенко Н.Э. Методы решения булевых дифференциальных уравнений на линейной систолической структуре // Автоматика и вычислительная техника. Вып. 22. - Мн.: Вышэйшая школа. - 1994. - С.116-122.

. 7. Levashenko V.G., Zaitseva E.N. Detection of Faults in Video-Processors with the Use of the Arithmetical Polynomial Forms. // Proc. of the Third Int. Conference on Pattern Recognition and Information Analysis (PRIA'95). - Minsk, Belarus, 1995. -Vol.3. - P. 161-165.

8. Levashenko V.O., Yanushkevich S.N., Zaitseva E.N. Synthesis of Parallel Algorithms to Compute Derivatives of MVL-functions. // Proc. of Workshop on Sampling Theory & Applications (SampTA'95). - Riga, Latvia, 1995. - P.319-322.

9. Slimerko V., Yanushkevich S., Levashenko V., Zaitseva E. Test Generation For Multi-Valued Logic Networks By Logic Derivatives // Pmc. of Worbhop on Design Methodologies for Signal Processing. - Zakopane, Poland, 1996. - P.51-57.

• lO.Kaczmarek A., Levashenko V., Majka E., Yanushkevich S. Method To Solve Boolean Differential Equations on Systolic Arrays // Proc. of the Int. Conf. on Applications of Computer System (ACS'94). - Szczecin, Poland, 1944. - P.39-47.

11.Levashenko V., Yanushkevich S., Majka E., Wojciechowski D. Neural Algorithm and Structure to Solve Boolean Differential Equations Logic Control Systems // 2nd Int. Symp. on Methods and Models in Automation and Robotics (MMAR'95). -Miedzyzdroje, Poland, 1995. - P.763-767.

12.Levashenko V.G., Zaitseva E.N. Detection of Faults in MVL-circuits with use ot the Arithilïetical Polynomial Forms of Reed-Muller expansion // Proc. of Int. Conference on Computer Methods and Inverse Problems in Nondestructive Testing and Diagnostic (CMNDT'95). - Minsk, Belarus, 1995. - P.256-261.

13.Левашенко В.Г. Синтез тестов для выявления неисправностей в схемах на многоуровневых элементах // Современные методы обработки сигналов сигналов в системах измерения, контроля диагностики и управления. Часть 2. Мат.докл.НТК. - Минск, Республика Беларусь, 1995. - С. 143-148.

Н.Левашенко В.Г., Янушкевич С.Н. Исследование алгоритмов лотческою дифференциального исчисления на типовом пакете MATLAB // Новые информационные технологии в учебном процессе. Тез. докл. межд. на)чно-мспи конф. - Минск, Республика Беларусь, 1994. - С.122-124.

15.Zaitseva Е., Levashenko V. Modeling Mulliple-Logic Circuits Use Package ol Matrix Algebra // Proc. of the 17 Int. Symposium of Students and Young Scientists. -Zielona Gora, Poland, 1995. - P.163-167.

16.Wojciechowski D., Frankowski K., Liewaszenko W. Uzycie pakieln MatL.ib u wykladach ze Stucznej inteligencji Ц Proc. of the 17 Int. Symposium of Students am! Young Scientists. - Zielona Gora, Poland, 1995. - P. 159-162 (In Polish).

17. Levashenko V., Yanushkevich S. Matrix Algorithms of Computing Partial Derivative» of MVL functions. Ц Proc. of the 17th Inl. Symposium of Students and Young Scientists, Zielona Gora, Poland, 1995, - P.163-167.

18.Левашенко В.Г. Алгоритмы диагностики видеопроцессоров на основе многоуровневых элементов с помощью направленных логических производных // Распознавание образов и обработка изображении. Тез.докл.НТК стран СНГ. - Минск, Республика Беларусь, 1993. - С.119-121.

19.Левашенко В.Г., Янушкевич С.Н. Решение булевых дифференциальных уравнений на нейронных структурах // Современные проблемы радиотехники, электропики и связи. Тез. докл. НТК. - Минск, Республика Беларуси, 1995. -С.381-382.

20.3айцева Е.Н., Левашенко В.Г., Янушкевич С.Н. Моделирование алгоритмов дискретного ортогонального преобразования в среде типовою пакета программ матричной алгебры // Современные проблемы радиотехники, иектро-ники и свят. Тез. докл. НТК. - Минск, Республика Беларусь, 1995. - С.378-380.

21.Зайцева E.H., Левашенко В.Г. Технологии моделирования многоуровневых элементов // Автоматизация проектирования дискретных систем. Тез. докл. НТК. - Минск, Республика Беларусь, 1995. - СЗЗ.

22.A.c. 1661791 СССР МКИ3 G 06 F 15/332. Модуль для решения булевых дифференциальных уравнений / Кухарев Г.А, Левашенко В.Г, Янушкевич С.Н, Шмерко В.П (СССР). -№ 4719275/24; Заявлено 14.07.89; Опубл. 07.07.91, Бюл. № 25. - 8 с.

23. A.c. 1732785 СССР МКИ3 О 06 F 7/00. Устройство для решения булевых дифференциальных уравнений / Янушкевич С.Н., Левашенко В.Г., Парамонов Н.Н, Шмерко В.П. (СССР). - № 4803549/24; Заявлено 19.03.90; Опубл. 08.01.92, Бюл. Ns 25. - 10 с.

24.A.c. 1803908 СССР МКИ3 G 06 F 7/04. Модуль для вычисления булевых функций / Янушкевич С.Н., Левашенко В.Г., Морозова A.A., Шмерко В.П. (СССР). -Ма 4757265/24; Заявлено 09.11.89; Опубл. 23.03.93, Бюл. № 11. - 16 с.

' 25.Разработка прикладной теории логического дифференциального исчисления: Отчет НИР/ Белорусский государственный университет информатики и радиоэлектроники (БГУИР); Рук. работы ' Янушкевич С.Н.; № ГР 199-41-086. - Минск, 1993. - 215 с.

26.Разработка инструментальных средств прикладной теории логического дифференциального исчисления: Отчет НИР/ Белорусский государственный университет информатики и радиоэлектроники (БГУИР); Рук. работы Янушкевич С.Н.; № ГР 199-43-363. -Минск, 1994. - 106с.

27.Алгоритмы и высокопроизводительные вычислительные средства в системах технического зрения и искусственного интеллекта: Отчет НИР/ Белорусский Государственный Университет Информатики и Радиоэлектроники (БГУИР); Рук. работы Шмерко В.П.; № ГР 199-43-364. - Минск, 1995. - 90 с.

28. Разработка технологии применения прикладной теории логическиого дифференциального исчисления: Отчет НИР/ Белорусский Государственный Университет Информатики и Радиоэлектроники (БГУИР); Рук. работы Шмерко В.П.; № ГР 199-51-339. - Минск, 1995. - 110 с

РЭЗЮМЭ Левашэнка Вггалш Рыгоравш ПАРАЛЕЛЬНЫЯ АЛГАРЫТМЫ АНАЛ13А ДЫСКРЭТНЫХ УСТРОЙСТВ ПА

АСНОВЕ НАК1РАВАНЫХ ЛАГ1ЧНЫХ ВЫТВОРНЫХ I IX АГ1АРАТНА-ПРАГРАМНАЯ РЭдЛПАЦЫЯ

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

Мэта дысертацыпнай работы складасцца у распрацоуцы паралельныя ' алгарытмау класа лапчных дыферэнцыяльных аператарау. сродкау апаратнай падтрымю гэтых алгарытмау 1 ¡х выкпрыстоуванне пры рашлнп задач аналва дыскрэтных устройств на //г-узроуневых элементах.

У рабоце распрацаваны I рэалЬаваны у выглядзе регулярных аперацыйных графау паралельныя алгарытмы: (а) вышчэння наираваных лапчных вытворных 1 диферэнцыялау булевых функций алгебры логш; (б) рашэння булевых дь1ферэнцыяльных урауненняу; (в) вышчэння наыраваных лапчных дыферэнцыяльных аператарау функций мнагазначнан лопм. Цэнтральная ¡дэя, пакладзеная у аснову алгарытмау, заключаецца у пераходзе ад езмн.шчны* пераутварэнняу у рамках законау алгебры лопю к регулярным вектарна-матрычным пераутварэнням. Тэта дазваляе скарыстаць пры ¡х рэолший тыпавыя пакеты праграм матрычнай алгебры 1 ажышшвщь апарагную падтрымку на рэгулярных структурах, напрыклад, аднародных I астал1чных мастах. Прынодзяциа схематэхшчныя рашэнш, арыентаваныя на сучасную тэхналопю ЗВ1С.

Паказана, што намраваныя лап'чныя дыферэнцмяльныя эператары з'яуляюцца эфектыуным ¡нструментам анализ дыскрэтных устройств на т-узроуневых элементах. Прапанаваны мадыфкаваны алгарытм тэсшравання камбшацыйных схем на /л-узроуневых элементах з выкарыстаннем прынпыпа актыунаап мнагамернага шляху. Прапанаваны алгарытм валодае такЫ новым! якасцяМ1, як незалежнасць ад бамса I значнасщ /и-узроуневых элементау, магчымаспю абнаружваць няспраунасш, характэрныя для разных тэхналопй.

Рэзультаты работы прызначаны для выкарыстання у лапчным праектааанн! устройств на т-узроуневых элементах.