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

'.¡шшстерство образования Республики Еоларусь Минский радиотехнический институт

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

Янушкевич Светлана Николаевна

РАЗРАБОТКА МЕТОДОВ С: ИТЕРА Ih'iPAJU^'LhUU-KOiiBluiEHijX ¿-СаШСТЙ ДЛЯ i IPflOii?;\ ЗОВА!U1Л БУЛЕВ!« ^МНОГОЗНАЧНЫХ ШШЦШ - !)А ОСНОВЕ Ш1ЕЗА ИСЧПСЛШЭТ

Спецпельность 05.13.05 - элементы и устройства

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

АВТОРЕФЕРАТ

диссертации на соискание учено» степени качдидата технических наук

плнек 19i'c

I -ьота выполнена на кафедре "Вычислительные методц и програаиа-, лклшз" Млпского радиотехнического института

1 ¡.... чиьЛ руководитель; кандидат технических ьоу^,

старшин научный сотрудник Н.Н.ПАЙШЮВ-

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

кандидат ризико-матецатп-ческих наук, доцент ШТ'хиСЛНА С.А.

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

доктор технических наук, профессор,

чл.-корр.АН Республики Еоларусь ЗАКРЕЗС1Ш А.Д.

кандидат технических наук, старший научный сотрудник ШОУС А.И.

Ведуцая организация:

Белорусский гоеударствйпш;П уЬ;и/ерСйтет

Защита состоится 5 ноаоця- 1992 года в М часов на заседании специализированного совета К 05G.05.0I Минского радиотехнического института по адресу: 2;;0027, Минск, ул.П.Еронки, 6.

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

Автореферат разослан

1992 г.

Учений секретарь ■

специализированного совета, . /> /7

кандидат технических наук, доцент ПШ05ШЧ А.П.

0В1{ЛЛ ХЛРЛ1СГЕРШТЙКА. РЛЮТЫ

Обработке, логических данных (ДЦ) занимает одно из центральных несг в современных инфо,ыационннх технологиях: логическом управлении объектами, обработке изображений и распознавании образов, контроле и диагностике цифровых устройств, системах искусственного интеллекта. Специфические особенности .ЬД требуют испольповрнш для их обработки специальных методов, алгоритмов, программ и аппаратных средств. Сдко из главных требований к вычислительным средсизгш обработки ЛД состоит в г он, чтобы они были ориентированы в своей реализации на технология сверхбольших (СШТ) и ультра-больших (ульт^-ЬПС; интегральных схем.

Реализация классических методов обработки ЯД приводит к бинарным программам либо неоднородным по структуре аппаратные средствам. Другими словами, программная и аппаратная реализация, классических методов приводит к уникальным по структуре и организации специализированном вычислительным средства).!, которые часто оказываются неприемлемыми по стоимости, надежности и эксплуатационным характеристикам. Это является одной из причин отставания теоретических результатов в данном направлении от совремешпзс возможностей интегрально;) технологии и потребностей практики.

В связи о винеизложенным актуальной является задача ]взра-ботки новых методов обработки ЛД, для реализации которих требовались бы относительно простые и дешеше технологии, б идеальном случае - возможность использован 1Я готовых СБИС, з том числе - компонентов и устройств из других областей техники. 3 этом плане рядом исследователей изучался вопрос о связи мето-доз цифровой обработки сигналов (ЦОС) и обработки изображений с методами обработки ЛД. Многие аспекты этой идеи удалось Формализовать и доказать правильность основных ее поселок.

Следовательно, конечно!! целью исследований в данном научном направлении являюгел технические решения, ориентированнее в своей реализации либо на создание специализированных СБИС с однородной структурой, в начбольией степени удовлетворяющей требования!.? интегральной технологии, либо на использование готовых специализированных СЬЛС. Вопрос о том, какой из путей является более лредпочг.чтельнш, решается исходя из конкретно!* екчуации и условий. Окажем, для вычисления ряда операторов

логических преобразовании дешевле использовать готоы.:е и широко распрост^анешше, ¿аботпкцпе, как правило, на предельных характеристиках СП1С для вичиеления операторов ДОС, чем проектировать ночую схему. Однако пол массовом спросе предпочтительнее ио:'ет оказаться изготовлен 1С СьлЗ, поскольку для обработки лошяешк данных не всегда требуется такал производительность вычислительных средств, как в ДОС. Кроме того, всегда шлется возможность распараллелить вычисления и тем самым достигнуть заданной производительности при сши-ешш требований к состаьлякцпк снстс-гу компонента!.!.

Всегда ли ш..:но получить такс.; результат, т.е. отобразить задачу в С1 ИС с однородной архитектурой, <рункц«окирую:це£ на принципах параллелизма и конвейеризации V Ца отот вопрос пока нет окончательного ответа, но известны решения широкого спектра задач обраоотки Лд.

Центральным этапов всех известных методов синтеза высокопроизводительных вычислительных средств для обработки лыл-отзя формализация в матричной (£огме решаемо ¡'. задач л (в данной диссертации - класса операторов. логического дц^еренциальпого исчислен.¡л). Если этот этап реализован, то далее «оаю воспользоваться известной методологией синтеза параллельно-конвейерных устройств, получаемых в результате отображения операционного графа решения задачи в архитектуру устройства.

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

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

Для достижения поставленной цели решаются следующие задачи:

- разработка теоретических основ матричных преобразований ЛД методами логического д1ОДР.ренцйального исчисления;

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

- разработка на эсой теоретическо/, основе методов синтеза вычислительных.устройств параллельно-конвейерного типа для обработки ад, удовлетворяю, у« требования),1 технологии СЕЛО и ультра-ЫС;

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

йегодя исследог.'-н:ги. Совокупность исподьзовзши.: в диссертационной раооте средств исследовании основывается на теории функции алгебры логики, теории цифровых автоматов и бинарных динамических систем; использочены также методы математического моделирования, диагностики цш;ров;!Х устройств, истода организации вкчцсленлй на систолических иассшзах. Перечисленные средства исследований подчеркиваются широким применением методов дискретной математики,, цифровой обработки сигналов и матричной алгебры. Методами экспериментальной проверки результатов явилось моделирование на ЗВЛ.

Научная новизна работы-заключается в решении актуально!'! научно-технической задачи отображения класса операторов обработки ДЦ з архитектуру вычислительных средств на СКИС и ульт-ра-ЬИС.

I.Получены матричное аналоги класса операторов логического дифференциального исчисления, предложен общий подход наставления класса операторов в матричной форме. Это позволило Епер-вле синтезировать операционные графи вычислительных алгоритмов, удовлетворяющие требованиям различных архитектур на СГИС и принципам сисголичесно!'! обработки данных.

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

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

4. Разработана мег^.чикп нспольаовпии* средств ЦЭС (коррел;*-

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

П,. мл.-ческая цонпосгь ..абоуц. Совокупность полученных результатов расплелог теоретические основы построении алгоритмических, ирог^-ашшх и апш^-атных средств, ^еалпзуш,::/. обработку ДЦ» На-мьздьцую практическую эи&чшосуь пиеют следующие результаты работы:

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

- шиенерние методики диагностик'-! комбинационных cxe;.i па бинарных и многоуровневых элементах, методика предварительной обх-^аботки бинарных изображений;

- установленнал'формально связь методов логического дифференциального ночислешш и ЦОС (корреляции, свертки, спектра), что позволяет использовать готовые технические решения на СШС и пакеты прикладных програш для решения нового класса задач.

Реализация результатов, работы. Работа выполнена в райках республиканской програмиы "Информатика" по постановлению СМ БССР К? 227 от 16.II.86, Ш!Р и ОКР, выполненных НИЦ :?Ш по постановлению СМ СССР от 16.06.87 675 - 155 и приказу Мннродио» 1рома СССР от 22.07.£7 № 4Ь0, ряда программ, утвержденных рас-поря;.;ен1ШИ Директивных органов, а такие в рамках договоров о научно-техническом- сотрудничестве и госбюджетных тон ЫРГИ, С 1989 года результаты работы используются в учебном процессе МРТИ в курсах "Основы дискретной иата.атики" и "Прикладная математика". Результаты изложены в двух частях учебного пособил "Ь^улево дифференциальное исчисление в вычислительной технике".

Апробация ,аботц. Основные результаты работы докладывались и обсугдались на всесоюзных, республиканских совещаниях, конференции и сенинарах, в той числе: на всесоюзной конференции "Конвейерные вычислительные систем"(Киев, 1988), "Цифровая обработка сигналов в систолах связи и управления"(Суздаль,1969), "Математические метода распознавай1 ш образов"(Р.чга,1989), "Методы и микроолоктронные средства цифрового преобразования и обработки скгналов"(Р1»га, ISB9)."Логические метода построения однородных и систолических структур"(Москва, Р..88), на респуб-

ликанской конференции молодых ученых и специалистов "Применение информатики н вычислительной техники при решонин народнохозяйственных задач" (Минск, ТЛЬ9), на 1-й всесоюзной конференции "Однороднее вычислительные среды и систолические структуры" ( Львов, МО), на всесоюзном семинаре "Системы цифровой обработки сигналов" (Ленинград, ИЬс) .

Публикации. По теме диссертации опубликовано 34 работы, в том числе I книга (справочное пособие), 6 статей в периодической печати (в том числе одна - в международном /урчало), 14 авторских свидетельств и положительных решений Б'гШ государственно;! патентной экспертиз1'! но заявкам на изобретения, учсбн.«е пособия Минского радиотехнического института.

Структура и объен ,лботи. Работа состоит из введения, четырех разделов, заключения, списка литературы и Приложения, содержит 148 страниц основного текста, 07 таблиц , 39 рисунков и список литературы из 121 наименований.

КРАТКОЕ СОДЕРЖАНИЙ РЛиО'Ш

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

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

Показано, что данная щюодема и решение б ее рамках задачи носят ломнлексний характер, затягивая основополагаюц-ю теоретические посылки ряда прикладных: направлений алгебры логики с одной сторона и принц шы построения вычислительных средств с другой. Суть ее состоит в существенной отставании меходов обработки ЛД от возможностей современно!'! интегральной технологии. Б последние годы данной прошеие посвящены работ З&кревского А.Д., Баранова С.И., Склярова В.&., Седухина С.Г.. Критически оцениваются результаты одного из направлений - логического ■ дифференциального и интегрального исчисления, скопированного в работах Акерса С., Селлереа , 'Гейза З&кревского А.Д., Еохманна Д. и Постхофа X. атл результаты не ориентированы на возможности технологии СБИС. Существенный вклад в этом плане внесли работы [Сухарева Г.А. и Шерко В.П. с участие;/, соискателя, в ког.х>рих разработаны теоретические основа логического дифференциального исчисления на основе матричного аппарата. Это позволило синтезировать операционные■гра^ы алгоритмов, имеющих прямое отображение в архитектуру высокопроизводительных вычислительных устройств. В работе излагается суть данных результатов,

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

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

- определении тан называемой арифметической формы булевой производной,

- определении логической производной функции многозначной

алгебры логики через ее разложение в рад Тейлора;

- определении арифметической ,рор-.м логической производной многозначной ф[!укции через ее разложение в арифметический ряд Тейлора.

Формальное определение производных логической функции из ее разложения в рад Тейлора и его ноцк/.пящии является, на наш взгляд, единственным корректив! подходом. Следует отметить, что приведенные определения произкодн:« отличаются от известных, полученных исходу! из целесообразности реиения прикладных задач, в частности, диагностики,отличные Друг от друга определения дани в работах Х.Лу и С.Лк, [укма Т. и Тапна :,!., Музко Д. и. Ут'неп М . Приводи»,¡не в диссертационной ¿аботе результаты позволяют преодолеть ряд затруднений, связанных с некодокткнн определении.) и использованием логических Производных многозна-ш:сх дикций.

Отот подход позволяет расширить представления о формах логических производите. Вводится понятие арифметической (¿о^мы зулово'А производной, которая является аналогом направленной руленой производной, но вычисляется с помодью целочисленное. ;ри['г:еп:ки.

Суть идеи состоит в следующем. Известный метод дискретных >рто тональных прообразована*; (ДОН) логических функций, разра-югиншй В.П.Шмерко, позволяет синтезировать любые полинокиа- • :ьные форм» булевых и многозначных 'ДОШфГ;. Ряды Тейлора дол-:ни дать аналогичной результат, однако липь в том случае, если проделена производная логической функции. Исходя из этого, орлально определяется эта производная.

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

орма К (д) логической Функции / (Х)«(0,к-1) п переменных г,,х2 .....ЛГ/, , XI е. (О,к -у, определяется как разлол.е-пе ч ло1 пческнн ряд Тейлора в точке се(0,кп-1)

1<.;сь сАс,...сг? I! ^■/••¿п " к-нчкое предиавленне чисел

и у соответственно;

и,- ^ н-

(х;

1Д- ^ (шс1 «О.¿V ^ о,

- с/-платное циклическое отрицание переменной X/ ; Л?И)>нр-1) - коэффициенты разложения.

При с-0 и к=2 из разложения (I) получается полином ;.:егалкина а при с-0 и к-лростом - известная логическая полиномиальная скорма к-значноП функции алгебра логики. Очевидно, что при с>О из (I) можно получить различные полиномиальные ?/Ормы, отличающиеся друг от друга характером ихоздения переменных. Всего существует к" полиномиальных форм. С другой стороны, их мо:шо получить посредством ортогонального преобразования вектора значений 1 функции У("Х) .

(с) Рс = V X {даос/ к) , (2)

где Ккл - квадратам матрица размерности к х к ортогонального преобразования, Рс - вектор коэффициентов полинома РС(Х). Исходя из этого, могут быть получены коэффициенты//''"'', которые, с другой стороны, являются значениями логической нролззодной порядка Т функции ^(Х) (3"- количество ненулевых разрядов в к-ичном представлении параметра ,

Следующая теорема отвечает на вопрос о вычислительных аспектах логической производной (3).

Теорема, логическая производная порядкатп£п логической функции ¿{Х)е(0,х -1)значности к. п переменных X,, зг» ,, ЭГ4-б(0,к-р, с ^Т/г , к -простое, вычисляется зал итераций

где матрица З^1 формируется по специальным правилам ( не приводятся из-за громоздскости выражений.). При к=2 выражения (3) и (4^ являются известными булевыми производными порядка т .

Следствие. Логическая производная к-значной логической функции / (х) по частной переменней с ^--крашьы циклическим отрицанием шеет ви^ц ^

- ¿' К(к-7,- ^ ^) (ты1 к), (б

с

где ГС(к-Т;,р) является (к-7,-,р;-м элементом матриц.I ДОН в конъюнктивном базисе К,,.

Л

Изменение типа арифметики (от модулярной! к целочисленной) в в выражении (I) позволяет по данной схе;.:е определить новкй тип производной логической функции - аршметичес^ю производную. Она отлшастся от (4)'тем, что при вычислениях используется обычная арифметика целых чисел, и имеет свойства направленной производной. Дадим ее определенна.

Арифметическая производная к-значной логической функции по переменной ЯГ,- с 7* - кратным циклическим отрицанием имеет вид _ 1

где КГк-Ч/", р) язшнвтея (к- 7,-, р) -у элементом матрицы ДОЛ в конъгонктнэнои арифметическом Оазисе К^:

В табл.1 приведена логические и арифметические производные трехзначной (¡уннции ¿(х, , ,.., Хп ) .

Таблица I

Логическая производная з Арифметическая производная

I д/М п ,, л +2//Х,,..,хп)(т<1 з) -2,..,-*}>>» "4у/' ЗГ/ ,.., ЭГ/ ,.. ,2л))

2 ,.., ¿у ,.. , • •, ^ ... =2 (-3^/ЗЪ, +4 у^сг,,.., ., .ах)-

О третьем разделе диссертации излагаются результаты по разработке и нсслсдовш.ии алгоритмических моделей и структур сис-то.-л'ческнк процессоров для реализации матричных операторов логического д;зА; еренцпального исчисления, Эти исследования подчинены г^г.вной цеда - но только реализовать на СЬпО, по и пепо^ьзогать игвестнь-е и хо^юшо апробированные в ЦОС структуры для рею;ига ¡исмиленьых зад;л.

0:vic.uaoTüji, что в настоящее upoiui предложены методики форыаль-ii-.л'о ut оинтпрованш систолически процесс-о^лв. Среди 1»аах иотодик j 1-1 л логически; данных наиболее приемлемы меюдакн, иреддол.гнные ¿едухпн.лы С.Г., Каиелсшш U.A., Косьанчукоы B.d., Диходсдои H.A., Соболевсх-н П.И. В соответствии с ат.и.т; методиками необходимо получить систему ptucy¿рентных соо1-ношеш|/;, характеризуются локально стыа сиязеп' вычислении, построить структурную схему алгоритма и получшъ отображение в фо^ые реаетчатого ориентированного графа,к пате.,1 получить иис:::естьо решена!'; путе.и пространственного Проециро-шлш» yvoro Графа по одному ;.з i.;no;.:eсгаа допустимых реаюпл:.. За-рершыций отап синтеза состоит а шкЗорв огшилильного проекта,

D настоящей ¿аботе использована иоди-д.шсиБ<я данной схеыи cwi-таза, приподнимая к масснаа« линейного типа. Тииой подход обусловлен теи, что при больших размерностях задач практически ¿еалпзуе-ш-ш на современном этапе развития интегральной технологии оказываются систолические структуры линейного типа, функцлонадодю на принципах параллельно-хкише^ерноК обрабо-гки. Tu:.: самым задача синтеза при ыыбранной архитектуре сводится к разработке зычислитель-ной ячейка (ВЛ) и запоминаюцеи ячейки (351).

-ьунрция систолического процессора для реализации матрично-век-торной операции определяв«я в виде

у ~-х% . (6)

гдеХи У - велюры входных и выходных данных, Л ~ матрица преобразования. Если матрица Л ©авторизуется, т.е. представляется а виде произведения слабозаполненкых матриц,

Л. - Л4"Л,

то выражение (6) преобразуется и виду

Y =Ai1) Л<г)...Л(тг0Х . (7)

Тогда для реализации процедуры (7) используется линейная структура из т ВЯ, соединенных с ЗЛ, и ксиздая ВЛ реализует итерацию

Зс"-А»-"5'*>> (б)

Соотношение (7) при соответствующих матрицах интерпре-

тировать как оператор вычисления М-кратной булевой производной, логической производной, ■ . быстрого преобразования Фурье (Effi<). На рис.1 приведена структура систолического процессора линейного тша, состоящего из ТП ВЛ и ЗЯ, схемотехнические решения кото-р;я определяются характером преобразования (8).

Р.1С.1.

Далее ¿иса.:а ¿решаются принципы построения дрзьовидио-сел'ешх снС'х-ол!1чос!<лх процессоАл>з для вычисления булевых дн^ереициадоп, про наводи« по ьскг'Орам не^екеишх и по ¿унлцан. Приводите.:. технические характеристики процессоров такого кшь.

Для и-крц'пюй логической производной к-пш-.чыой пункции (4) предлнгатся дин способа вычислений на систолических структурах, выполняются оценд.1 ^ихныческих рьшетш. Один из глюесбоа сепооан па вычислении циклической коррекции - типового оператора ЦОС, дли которого риз работа! .и и изготовлены систолические структуры, Теы санки достигается пагтий для тактика результат - использование имеи^пхсл высокопроизводительных и хорошо инробированьых технических средств для реызплц спзщц.ьчесхих задач обработки ДД. Зишейний систолически!', процессор дм ьичпсленин И-нратной логической производной (4) , построенный но принципу процессора для циклической корреляции, содержит /7? блоков по к 31,т блоков по к , ЗЛо. Ка.дпй блок ВЛ выполняет ьтерацию вида

к) ,

Структура / -го блока ,¿=1/77, приведена на рис.2.

I-й олок ЭНг

вю.г

а^т

Э1

тц

л*

_JZ

Структура p-{; B,l в блоке (р~1,к) t'-го блока приведена на рис.З, а ЗЯ^ и ЭПр содер.глт рсгистрн типа PIK) и обеенечьвавд хранение оле-мен тов матр-.щ преобразования н Hpoi.'e:;yro>raux результатов. Аналогично оргг.ш куются начисления на ДШ>-про)(оссоре, по результата'« которых - .»зикторпм Рс (2) строятся векторы значен Iii логических производных.

В табл.2 приведены оценки технических и прогонных характеристик систолического процессора для вп-числения логических производных

порядка ТЛ , построенного двумя способами: первый - на основе структуры для реализации циклической корреляции, второй - на ос-ново структуры для реализации ДП-Т>.

Таблица 2

Количество блоков в процессоре

Количество блоков ВЛ

оЛт

3^2 в блоке

Количество тактов

- начальной загрузки (торнокенин), з

- стационарной работы, cj,e

- общее при обработке

векторов л , Ц. в Эффективность использования оборудования,

и Я»

Значение характеристики

Процессор 1-го типа Процессор ::-го типа

тп п

к К

Кп(1-к'т) кп

К* (qti-*-™) К" ЦП)-«™ к» IX"(<1*1 )-1) H"(%trh1

Относительно выбора элементной базы отмечается, что алгоритмы логаческой обработки аффективно реализуются на выпускаемой в СНГ однородной вычислительной среде ОВД Н 1841 В5 I, что подтверждено экспериментально.

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

13 четвертом разделе работа излагаются методики решения прикладных задач из области пычислителыгой техники и обработки ЛД. Эти методик!! оснопанп на методах логического дпф>реац..адьного исчислении и гIpeдlI0JIaгй]0т использование технических средств в виде систолических процессоров.

Вначале излагается методика рошешы задачи диагностики комбинационных схем на двоичных олылсытах. Строятся модели ошибок типа "инверсия", "константа 0","константа I" и синтезируются диагностические тести на основе матричных операторов булевых Производных. Эта .методика, в отличие от известных, предложенных в работах Ли, Селлерса, Тейза, характеризуется системностью и цельностью, что достигается за счет использования всех оне*лторов булевых производных в единой матричной интерпретации и, что важно подчеркнуть, предполагают аппаратную поддержку на сне.ал^чес-ких процессорах. Далее ¡¡слученные результаты раэв^пзаютоя на основе использования арифметических производных, обладающих свойством направленности и вичнеляшлих в обичной арифметике.

В данном раздело выполнено обобщение методов построения диагностических тостов на основе логических производных для комбинационных схем на многоуровневых элементах. Строятся модели ошибок типа "константа р" л "з^краттюе циклическое отрицание". Так, например, набор /г,...>~Ьп перемен/тх , ^г 1. > являет-тестом для обнаружения неисправности типа "двухкратное циклическое отрицание" для схемы на трехуровневых элементах (для I -го входа X; схеш), если выполняется условие

(з/д) , ни) \ „ / д?м п д//х) и « 2.

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

При решении логического управления в дцскгршм системах

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

Наконец, рассматривается прикладная задача обработки о'инарнкх и ииогоградациошш изображений, задашик дгумерыымп матрицами, которая решатся ira основе использования обобщенных операторов логического дифференциального исчисления - параметрических:. К данному классу относятся оператора параметрической булево.: производной, интеграла, минимума, максимума, матричные процедуры вычисления i;0':Tip!ï>: вводятся в работах, написанных с участие« соискателя. В разделе приводятся таблиц::, где даны простешиь операторы обработки изображений, а такие более слоглше процедур (формирование контуров, удаление зерлп;стых ¡¡¡умов, дефектов на изображениях). Отмечается, что все процедуры реализуются на литейных систолических структурах. Результата исследовании доведены до уровня технических решений, защищенных авторскими сойдете льет вами на изобретения, а тше.е исследовалась реализация предлагаемое алгоритмов на ОПС H 1841 3i' I. Эффективность изложенного подхода состоит с возможности существенно (на порядок и выше) увеличить производительность систем и удовлетворить требованиям реализации на БИС и CL®.

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

Таким образом, создана я теоретически обоснованы необходимее предпосылки для широкого пр;менешш разработанных методоз ы Б'^шслительнык средстг- обработки ДЦ и логических вычислен гл.

£3

ЗАКШЛЕШ1Е

Главный результат диссертационной работы состоит в разработав методов синтеза высокопроизводительных вычислительных устройств ь виде систолических процессоров для реализации класса операторов логического дифференциального исчисления -одного из современных и перспективных направлении прикладной теории алгебры логики, В работе решена основная'задача синтеза - получены м&темых'ичеаше и алгоритмические модели класса операторов, имеюирех пряное отображение в архитектуру параллельно-конвейерных вычислительных устройств. Тем сим.ш результаты работы позволяют преодолеть затруднения в разработке технически средств на СЬИС и ульт^-а-КС для реализации указанных методов обработки ЛД и за счет конвейеризации и распараллеливания достичь практически предельных для современного уровня развития интегральной технологии характеристик.

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

1.1. Впервые получены матричные аналоги класса операторов логического дифференциального исчисления.

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

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

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

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

исчислении реализуются на двух указанных тинах архитектур.

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

2.3.Предложено использовать типовые средства ЦОС в виде процессоров свертки и корреляции для вычисления логических производных. Практически;! эффект выражается совокупность» таких факторов, как исключение необходилости создания уникальных вычислительных средств, унификация и стандартизация изделий.

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

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

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

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

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

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

3.4. Разработана методика и средст-г-. аппаратное: подчерки для предварительной обработки бинарных изображений с помощью

операторов булева дифференциального исчисления. Синтезированные алгоритма нашли применение в вичиолигельной системе обработки изображений с сопроцессор-ом на Оаэс однородно!) вычислительной среда Н 1641 Б2 I. Основной сффо,-т состоит в распар ьл;:ели-вании вычислительного процесса и .повелении коси лма пснрль-эования операционного ресурса.

Оснсшнее содержание диссертации о траке но в следующих работах:

1. ¡Сухарев Г.А., Шмерко В.П., Янушкевич С.Н. Техника параллельной обработки бинарных данных на СБИС: Справочное пособие. - 1«н. ¡Вышэйшая школа, 1991. - 2,io 0.

2. Систолические процессоры для логической обработки многозначных данных. В кн.: Кухарев Т.А., Щыерко D.ÍI., Эгйцева E.H. Алгоритмы и систолические процессоры для обработки многозначных данных. - Глава 4. -Мн.: Паука и техника, 19.;0, -

С.157- 252.

3. Ьулево дифференциальное исчисление в вычислительной техника. Учебное пособие, 4.1. Матричный аппарат булева дифференциал льного исчисления. -Мн.: tiP'Jll, 19^0.

4. Ц/лево дифференциальное исчисление в вычислительной технике Учебное пособий. 4.2. Методы булева дифференциального исчисления в решении прикладньи задач. - йн.: МРШ, 1992.

5. Шыерко В.П., Янушкевич С.Н. Алгоритмы булева дифференциального исчисления для систолических процессоров // Кибернетика. íüL„0, К" 3. С. 141 - I5S,

6. Шыерко В.П., Кузьмицкий Д.В., Янушкевич С.Н. Алгоритмы реали-

зации дифференциальных операторов вычисления ниничумо'1 и максимумов систеш булевых функций, заданной в арифметико-логических формах// Автоматика и вычислительная техника.-Мн.:Вышэйшая школа, IS88. Bun.I?. C.I0Z - 105.

7. Зайцева E.H., Янушкевич С.Н., Шыерко В.П. Обобщение булева

дифференцирования и интегрирования на функции многозначной логики //.Автоматика и вычислительная техника.- Мн.: Вы-шэйшл икола. 19&У. вип.18. G.II6 - IZZ,

8. Левашенко В.Г., Янушкевич С.Н., Шмерко В.П. Матричный метод решен 1-й булевых дифференциальных уравнений на основе дисрет-ного преобразования Фу^ье // Автоматика и вычислительная техника.- Ни.: Вышэйшая школа, 1УС0. Ban.19. С.118 - 124.

9. Нолодиева И,Л., Янушкевич С.Н., Левашенко Б.Г. Методы решения булевых дифференциальных уравнений на древовидно-сетевой структуре // Автоматика и вычислительная техника. - Мн. ¡ Вышэйшая школа. 1991. B¿0.2O, С.102- 105.

10. Зайцева E.H., Шмерко В.П., Янушкевич С.Н. Синтез конвейерных процессоров для логического дифференцирования и интегриро-

вания функции многозначной логики 1 Конвейерные вычисли ..ель-ные системы. Тезисы докл. всесоюзного совещания. - Кяев, IS6Ü. с 149,150.'

11. Ыиарко В.П., Янушкевич С.Н. Конвейерные процессор ijli< с' изменяемым базисом для синтеза новых форм представления булеш« ФункциД. Там кв. С. 1-16, 1-19.

12. Кухарев Г.А., Шмерко В.П., Янушкевич С.Н. Алгоритмы многомерного логического дифференцирования булевых данных и их реализация на систолических структурах/ В кн.: логические методы построения однородных и систолических структур. Труды 1-го всесоюзного семинара. - М.: IP&B. C.II2 - 115.

13. Шмерко В.П., Лнушкевич C.Ü., Колодиева И.Л. Логическая' обработка двумерных массивов бинарных данных на систолических процессорах / Методы и микроэлектронные Средства цифрового преобразования и обработки сигналов. Тезисы докл. всесоюзной конференции. - Рига. 19&У. T.I. С.ЗсО - 262.

14. Кузьмпцкии Д.В., Шмерко В.И., Янушкевич С.Н. Архитекгур- . ные принципы организации логической обработки двумерных

• массивов бынарных данных на магнитооптических туанспаран-тах/ Математические методы распознг.Еания образов. - Тезисы докл. -1-й всесоюзно)! конференции. - Рига. 19ü'j. С. 109 - ИГ.

15. ^узьилцкий д.З., Шмерко D.H., Лиулжевич С.И. Контроль и диагностика компонентов цифровой радиоприемной аппаратуры на основе булева дифференциального исчисления/ Цифровая обработка сигналов в системах связи и управления. - Тезисы доги. 1-й всесоюзной конференции. - Суздаль. I9cD. С.1X9.

IG. Колодиева И.Л., Янушкевич С.П. Матричные алгоритмы вычисления булевых дифференциалов п ях реализация на ССИС/ Тезисы докл. респ.конференции молодых учеких н специалистов "Применение информатики н вычислительно!'» техники при решении народнохозяйственных задач". - Мн.; I9CC. С.319.

17. Кузьшцкиц Д.В.,. Шмеуко В.П,, Янушкезнч С.Н. Алго^ыда логической обработки бинарных изобретет:,'; на однородно'1

■ вычислительной среде// Лспользоват.-ё вычислительной техники для обработки сигналов.- Pna: Рш;. техн.ун-т. Kj.O.C.5-11.

18, Антокенко Б.М., Колодиева ПЛ., Янушкев.'Ч С.Н. Слотояичео-кие процессоры дач вычисления ло»*ических производных многозначных (¿ункцкй / Однородные вычислительные срод i « систолические структуры/ Тезисы докл. Г-н всесоюзной коьфе-

ренции.- Львов. 1990. С.102 - 103.

19. A.C. №1793 <СССР)M.¡Сл.в Об Р 15/34. Устройство для вычисления булевых произведши/ Дашенков ü.M., Кузьиицкий

Д.В., Тупивов В.Д., Шиерно В.П., Янушкевич С.Н.// Шлле-тень изобретений и открытий. - 1980. н-1 19.

20. A.C. 1532946 (СССР) Ы.Кл.8 Об F 15/332, 7/00. Устройство для преобразования булевых .функций / Дашенков В.М., Куэь-ыицкий Д.Б., Емерко В.П., Янушкевич С.Н.// Бюллетень иэобт-ретений и открытий. 19оУ. 46,

21. A.C. 1511591 (СССР) М.Кл.8 Об Р 7/00, 15/31. Устройство для логического дифференцирования булевых функций/ Янушкевич С.Н., Зайцева E.H., ¡(ухарев Г.А., Шмерко ВЛ1.//Бюллетень изобретений и открптиЧ. 19^0. Ь- 5. .

22. A.C. I31I592 ССССР) М.Ка.в 06 F 7/00, 15/31. Устройство для логического дифференцирован,« и интегрирования булевых функций/ Янушкоапч С.К., Зайцева E.H., Цухарев P.A., Uiwep-ко В.П.// Бюллетень изобретений и открытий. ЮСО. е-' 5.

23. A.C. IöüCÜJ.S (СССР) ¡Л.Кл.6 03 F 15/32. Устройство для дн-ф;еренцированш логнчеокихф}Нкций/ Дашенков В.М., Зайцева E.H., Тупиков В.Д., Шыерко В.П., Янушкевич С.Н.// Бюллетень изобретений и открытий. 1990. S! 19.

24. A.C.Io6I79I (СССР) M.ICi.ti Об F 15/332. Устройство для решения Нулевых дифференциальных уравнений/ Девашенко В.Г., Нухарев Г.А., Шмерко В.П., Янушкевич С.Н.// Бюллетень изобретений и открытий. 1991. 25.

25. A.C. I167050 (СССР) Ы.Ил.8 Об Р 7/04. Модуль для логических преобразований булевых функций / Янушкевич С.Н., Морозова A.A., Кухарев Г.А., Шмерко В.П.// Бюллетень изобретений и открытий. IS9I. № 28.

26. A.C. I6864G0 (СССР) М.Кл.6 06 F 15/353. Устройство для вычисления шпликант / Бондарь Я.Н., Дуброва Е.В., Н1ыерко В. П., Янушкевич С.Н.// Бюллетень изобретений и открытий. 1991.

39.

27. Положит.решение по заявке V- 4748448/24 М.Кл.8 Об Р 7/00, 15/31 от II.I0.b9. Модуль для вычисления логических производных/ Антоненко В.М., Зайцева E.H., И&ержо В.П.,

Янушкевич С.Н.

28. Положит.решение по заявке К? 4771326/24 от 18.12.69. М.ГСл.

6 06 Р 7/00, 7/04. Устройство для вычисления булевых дифференциалов/ Колодиева И.Л., Парамонова H.H., Шиерко В.П.,

Януикевпч С.Н.

29. Полоязи.ретение по заявке Ь- 4603549/24 от 19.03.Ш. И.'Лн. Q 06 F 15/33 2. Устройство для решения булевых дифференциальных уравнений/ Янушкевич С.Н., Левашонко В.Г., Ларамо-нов Н.Н., Шморко B.1I.

30. Положит.решение по заявке Ь- -Ш7049&/2-1 от 31.01/.;?.. М.Кл. 0 Об Р 7/00. Устройство для вычисления логических производных многозначных данных / Днгоненко В.М., Шмерко В. П., Янушкевич С.Н.

31. Положит.решение по заявке. 4-ЮЗ:5.77/24 от 2&.0G.9I .М.Кл. 6 00 F 7/00. Устрог.стзо для распознавай .я та линейность булевих пункции / Гоыдарь И.Н., ^уэьмицкии Д.В., iljifpKO В. П., Янушкевич С.Н.

32. Отчет HiBJ ГРУ 57643 "исследование основных направлений разработки и применения малогабаритных устройств оптическэ-считивания информации с первичных докумвктоз для пр.о сес-сиональных персональных оВЛ". HEI ЭВМ. 1809. Научный руководитель Парамонов Н.Н.

33. Y&nushkovich S.N., Shaerko V.P., Kuaaitgky D.T. Algorithma of Binary Image Prooaasing on a linear Systolio Ргооезаога/ First International Conference on Xaforne.tlou Technologies for Image Analyeia and Pattern Recognition. Lviv, USSR.1990.

34. Shmerko V.P., lamishkevich S.N. Binary Image Irocasoing by Boolean Differential Calculus Operators and its Realization on Linear 8ystolic Arrays// Pattarn Recognition and Image Analysis. 1991.Ho.4. pp.406- 422.