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

белорусский государственный университет информатики и

радиоэлектроники

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

ЗайнеБа Елена Николаевна

методы и алгоритмы обработки многозначных данных на линейных систолических процессорах

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Минск 1994

/

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

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

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

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

Защита состоится

доктор технических наук, профессор, академик Международной Академии Информатизации , действительный член IEE 1ШЕРК0 В.П.

доктор технических наук, профессор, чл.-корр. Академии наук Республики Беларусь ЗАКРЕВСКИй А.Д.

кандидат технических наук, старший научный сотрудник ПАРАМОНОВ H.H.

Белорусский государственный университет

1994 года в 14 часов на заседании специализированного совета К 056.05.01 Белорусского государственного университета информатики и радио -электроники по адресу: 220027, Минск, ул.П.Бровки, 6.

С диссертацией можно ознакомиться в библиотеке института Автореферат разослан /¡^февраля_199 4 года

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

ПАШКЕВИЧ А.П.

общая характеристика работу

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

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

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

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

Настоящая работа базируется на этой методологии и рвшэвт с вв

помощью рад актуальных задач, связанных с обработкой МД на вы- . сокопроизводительных вычислительных структурах. Полученные в диссертации результаты ссности&шшгся с достижениями ведущих научных международных центров в данном, напрвлении, публикуемы- , ыи в основном в трудах ыеадународного симпозиума п//г*ек/гсг*ёо-■ па? За/п/х>2(</<п м ¿о^с ", проводимого на протя-

жении более двух десятилетий.

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

В рамках выбранного направления исследований (обработки МД> в работе: '

- расширяется класс форм описания МД и исследуются способа их конструированияI

- обобщаются методы логического.дифференциального исчисления для данных зкачности р т ( р - простое)

- синтезируются вычислительные устройства систолического типа для обработки МД.

ЦЕЛЬ РАБОТУ состоит в разработке методов.и алгоритмов обработки МД, ориентированных в своей реализации на систолические массивы линейного типа и удовлетворяющие основным требованиям технологии СБИС.

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

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

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

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

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

МЕТОДЫ ИССЛЕДОВАНИЙ. В диссертационной работе использованы метода алгебра логики, теории, цифровых автоматов й бинарных динамических систем, элементы методов математического моделирования, дискретной математики и цифровой обработки сигналов. Для эксперементальной проверки результатов использовались метода моделирования на ЭВМ.

НАУЧНАЯ НОВИЗНА РАБОТЫ заключается в том, что предложено новое решение актуальной научно-технической задачи- обработки МД на высокопроизводительных вычислительных устройствах, а именно:

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

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

3. Разработана методика использования средств» реализующих дискретное ортогональное преобразование, для синтеза форм представления МД, что в ряде случаев позволяет использовать готовые и высокоэффективные средства для решения задач обработки МД.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОМ состоит в том, что предложено использовать в инженерной практике теоретически обоснованные и апробированные новые методы и алгоритмы аналитического описания МД. Эти алгоритмы ориентированы в своей реализации на технологию СБИС я ультра-ШС. Наибольшую ценность составляют:

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

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

~ У- ■

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.-Работа выполнена в рамках республиканской программы "Информатика" по постановлению СМ БССР от 16.11.88 №327 (ГВЦ 92-3097, "93-3052, 93-8028), а также программы "Информатизация" на-1991-1995г.г. и на период до 2000 года, утвержденной -постановлением СМ РБ от 27.II.9Ir, М444 и в рамках, договоров о научно-техническом сотрудничества и госбюджетных тем Белорусского государственного университета информатики и радиоэлектроники. С 1989 года результаты работы используются в учебном процессе Белорусского государственного университета информатики и радиоэлектроники в курсах "Основы дискретной математики" и "Прикладная математика" для студентов специальности "Электронные вычислительные машины".

АПРОБАЦИЯ НАУЧНЫХ РЕЗУЛЬТАТОВ. Основные результаты диссертационной работы докладывались и обсуждались на всесоюзной конференции "Метода и микроэлектронные средства цифрового преобразования и обработки сигналов" СРига, 1986), втором всесоюзном совещании "Конвейерные вычислительные системы" (Киев, 1988), всесоюзном семинаре "Системы цифровой обработки сигналов" (Ленинград, 1988), республиканской конференции молодых ученых и специалистов "Применение информатики и вычислительной техники при решении народно-хозяйственных задач" (Минск, 1909), межреспубликанской научно-технической конференции "Актуальные проблемы фундаментальных наук"С Москва, 1989), всесоюзной научно-технической конференции "Цифровая обработка сигналов в системах связи и управления" (Суздаль, 1989), 25-й юбилейной военной научно-технической конференции МВВИУ "Проблемы совершенствования и эксплуатации радиотехнического и радиоэлектронного вооружения и автоматизированных систем управления" (Минск, 1993)»'научно-технической конференции стран СНГ. "Распознование образов и обработка изображений" (Минск, 1993), а также научно-технических семинарах кафедры "Вычислительные методы и программирование" Белорусского государственного университета информатики и радиоэлектроники (Минск, 1993).

ПУБЛИКАЦИИ. По теме диссертации опубликовано I? работ, в том числе: I монография, 2 статьи в периодической печати, 6 авторских свидетельств на изобретения.

СТРУКТУРА И"ОБЪЕМ РАБОТЫ. Работа состоит из введения, четырех разделов, заключения, списка литературы и приложения, содержит 122 страницы основного текста, 33 таблицы, 54 рисунка и 134 наименования в списке литературы.

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

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

В первом разделе анализируется состояние и тенденции развития теории, методов, средств обработки ЫД, формулируются цели и задачи работы. Отмечается, что в рамках проблемы отображения задач обработки МД в архитектуру высокопроизводительных вычислительных устройств на СБИС, следует выделить два направления. Первое направление представляет собой обобщение методов классической булевой алгебры и основано на символических преобразованиях полиномиальной алгебры. В рамках второго направления разрабатываются методы обработки МД на основе матричных преобразований. Именно результаты, относящиеся ко второму направлению, позволяют решить проблему отображения задач обработки МД в архитектуру устройств на СБИС при максимальном использовании возможностей интегральной технологии. В последний годы данной проблеме посвящены работы А.Д. Закревского, В.А. Склярова, В.А. Вальковского, С.Г. Седухина, Ю.С. Каневского, В.Г. Лазарева, П.И. Соболевского. Следовательно для успешного решения задачи отображения методов обработки МД в архитектуры высокопроизводительных устройств эти методы должны быть основаны на матричных процедурах. Однако пока для известных методов многозначной логики не получены матричные аналоги ("за редким исключением). С другой стороны, решение проблемы разработки, высокопроизводительных средств обработки МД сдерживается отсуствием многоуровневой элементной базы. Поэтому в настоящее время исследователи ограничиваются моделями многоуровневых элементов на двоичной элементной базе.

Несмотря на многочисленные трудности, исследования в данном направлении стимулируются практической потребностью и перспективами повышения степени интеграции вычислительной техники. В первом разделе кратко излагаются результаты, полученные В.А. Горбатовым, H.H. Айзенбергом и В.Г. Лабунцом по методам описания ЫД. Отмечается, что синтезированные формы не удовлетворяют требованиям архитек^ры высокопроизводительных средств на CHIC, что является центральной задачей настоящей работы. Известны результаты зарубежных ученых (К.Мораго, Д.Грина, Дж.Музио.), которые предложили оригинальные методы синтеза форм представления МД на систолических структурах.. Работы В.П.Шмерко обобщают накопленный опыт и предоставляют методологию синтеза форм представления МД

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

Во втором разделе излагается единый подход к синтезу форм представления МД и алгоритмы его реализации. Главный результат исследований состоит в том, что расширены классы арифметических и логических форм представления МД* получены новые аналитические конструкции, причем известные формы представления МД являются их частными случаями. Вместе с этим, необходимо отметить, что для логических форд описания МД получено расширение класса аа счет обобщения известных форм для значности р"1 (р -прос?ое>. Ценность полученных: результатов состоит в том, что представляется возможным установить более гибкую связь с соответствие) между формальным представлением задачи и возможностями аппаратно-программцшссредств (память, разрядность, тип арифметики).

Предлагается развитие ранее предложенной классификации форм представления МД (рисД). Все формы подразделяются на два класса: логические Ш и арифметические (Я) . Каждый класс, включает два подкласса» функциональные (П, Щ) и неполиномиальные ОVI, ЩУ формы. Классы различаются типом использу-, емой арифметики , а подклассы - структурой формы. В зависимости от типа используемой арифметики поля, формы представления МД

Сормн представления многозначных данных

А 1

Логические (1) Арифметические (Я)

1 - 1

Функциональные (П) Неполиномиальные №) Ьункциональ-ные СРЮ Неполиномиальные (Ш)

* 1

В поле (а) 3 расширении поля еР(рт) .- 18У В поле действительных чисел (с) В поле комплексных чисел (с*?

Тип ар и фм в ти к и Рис. I

делятся на два типа в райках каждого подкласса. Заметим, что в прикладной теории алгебры логики известны лишь Форш подклассов Р1 и РА . Остальные формы представления получены в данной работе.

Приведенная классификация является основой для разработки методики выбора класса, подкласса и типа формы исходя из требований к форме представления МД. Например, если значность МД Г может принимать любое значение, то форма принадлежит классу А. Если вычислительные средства обеспечивают обработку комплексных чисел, то это позволяет сузить область поиска формы до га-па Л^-я'. Далее поиск ведется по более детальным критериям (количество ненулевых компонент в форма, характер зависимости переменных). Тем самым осуществляется "привязка" аналитической конструкции к возможностям и ограничениям вычислительных средств.

Суть подхода к синтезу форм представления МД состоит в следующем» МД значности ? ^ размерности ^ = еп интерпретируются как вектор значений X (столбец таблицы истинности) много-з'начной функции алгебры логики ( ФАЯ) значности е и ^ переменных Т,,Хп (Ху'й?7/ , J* /,/>) , Вектор значений X посредством дискретного ортогонального преобразования (ДОЙ ) преобразуется к вектору С , элементы которого являются коэффициентами искомой аналитической конструкции ( формы представления МД)(рис.2). В общем виде арифметико-логическую форму можно записать следующим образом:

Сй>-1Ёсф{(Л,Ъ.....яь>, (1)

Вектор значений

ДШ

Xе"

ха) —►

Коэффициенты формы

Обратное

7--

¿(с)

ес<)

1

Форма

представления ВД

Рис.2 . - 7~

где /{X/, л») - арифметико-логическое выражение, определяемое базисом ДОП. Способы конструирования функции Х„) составляют центральную идею синтеза разнообразных форм представления МД,

Б табл.1 приведены формы представления функций дизъюнкции Х1 КЗ} = утхкг(■Я, ¥>), где Лу (X) - обобщенная характеристическая функция: (х) -0, если Ых и , если /=.г ' $

'./ = О,? -I. В табл.1 приведены лишь некоторые из форм представления МД, синтезируемые в рамках предлагаемого подхода. Многообразие аналитических конструкций определяется функциональными зависимостями переменных в пределах каждого типа форм. Эта зависимость переменных определяется элементарными функциями (инверсией, степенной функцией, дизъюнкцией с константой и т.д.; и может быть одинаковой или различной для всех переменных. Например, для разложения в .ряд Рида-Маллера трехзначной ФАЛ (г =3) двух переменных (п =2)

Таблица I

Класс формы 1одкяасс и тип формы Знач-ность Форма представления многозначной ФАЛ /ДО

П-а 3 Ш)*Хг *2т,Хг '¿п*^ (мое/3)

п-в А у 2хМ г//?<оле^Га))

М-а 5 ¿СК)-- X, (Св/ (х.) +е„ (¿г)»*2х2ге„(х,) Стос? 3)

М-6 А ¿Ш=Х, (&,(*,) ' Ра (X,) 'Х^р^ст,)* *Р2/(х,)) С8роле

РЛ-с 3

т-е 3 //(Х)*('А)(4Х, ^2(2Саг &,)-<?,г (X,))'Т,гР,2 (X,»

А А/М J

Га)*/*>х*./а>а-, (то&.З)

¿=о

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

'Г'гЛ .^Ът/./Чг, '/"Ым-г/^/"* <

¡•о

где функциональные зависимости для первой и второй переменной соответственно имеют вид: (яг, и .

Использование ДОП в качестве инструмента синтеза позволяет на практике воспользоваться типовыми программными и аппаратными средствами ДСП. Принципы их построения изложены в работах Г.А.Кухарева, Ю.С.Каневского, А.А.Петровского. Технические средства для реализации ДОП характеризуются однородностью, параллелизмом, конвейеризацией вычислительного процесса, а также ориентацией на современную СБИС-технологию.

В работах В.Д.Малюгина показаног что система из /»■» булевых функций может быть представлена в виде одного аналитического выражения.- Этот подход остается справедливым и для многозначных ФАЛ. Для этого.систему МД необходимо преобразовать к вектору значений системы' МД , который вычисляется путем умножения матрицы значений системы на весовой вектор:

%:ТЮ; 7* Г г""'... г' (2)

По вектору значений конструируется форма описания систе-

мы МД посредством ДОП. Восстановление системы МД по вектору значений Хъ осуществляется путем представления каждого элемента вектора значений в -ичной системе счисления.

Выбор той или. мной форш обусловлен конкретной задачей. Однако, наиболее часто требуется найти форму представления МД о минимальным заданным числом коэффициентов. Другими словами, вектор коэффициентов должен иметь заданное, число отличных от нуля элементов. В работе предложены три подхода к решению этой задачи. Первый связан с представлением исходных данных в двумерном виде (в виде матрицы значений размерности , * = = I, п -I). Затем эта матрица обрабатывается как система Щ и полученная форма имеет (¿^п) коэффициентов. Заметим, что при одномерном представлении форма имеет коэффициентов.

Второй подход основан на формировании линейной форлы описания системы многозначных ФАЛ, из которых одна функция задана. Искомая форма формируется по стратегии удаления нелинейных (при произведении нескольких переменных) коэффициентов в аналитическом описании МД. И, наконец, в соответствии, с третьим подходом, из множества арифметических и логических форм выбирается форма с наименьшим числом коэффициентов. В табл.2 приведены результаты представления трехзначной ФАЛ двух переменных с вектором значений Т » [000011112]т рассмотренными способами.

*■ . Таблица 2

Способы формирования формы описания

Полиномиальные формы описания , ?= [ООООШШТ

Без применения специальных методов

Двумерное представление МД

Линейная форма описания системы МД

Выбор формы о наименьшим. числом коэффициентов из класса известных форм

(тос/з)

ШХ'АХ-гт, '/мж -^г^гг/'/^ъ -

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

гя)ъ¿v,..., я,) (3)

где © - операция сравнения значений функции /(X) на наборе переменных • х* • * Тг,..., аг„ , а значения х,-и я} определяются характером изменения переменной -у, . Это могут быть функции циклического отрицания, инверсии и т.д. Нулевые элементы логической производной С3) позволяют опре-

{(г</,1>

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

Автором работы предложен специальный тип процедур логического дифференциального исчисления - параметрические логические • производные для систем МД. Последние рассматриваются в системе координат X и У . Изменение значений системы МД относительно координат .X и У определяется как логическая сумма текущего и последующего значения системы по соответствующей координате. Для этих операторов получена процедура восстановления -логические параметрические интегралы. Такие свойства логичес-. ких параметрических производных и интегралов как восстановление, мультиплицирование и выделение характерных лризнакой исходных данных позволяет использовать их при обработке изображений.

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

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

Например, показано, что для вычисления коэффициентов формы представления МД могут быть использованы известные систолические массивы для реализации ДОП (рис.ЗК Этот процессор содержит ВЯ двух типов - непосредственно ВЯ и запомйПаодие ячейки' (ЗЯ), пред-

х"}

Х">

е&Ц

Рг

39

О

Рг

Чин

X

3*

Рис.З

назначенные дая хранения промежуточных результатов. В / -ю с' = = о,. г"-1) ВЯ, содержащую два регистра (Рг>, умножитель (Умн и сумматор СДГ) , последовательно подаются элементы строки матрипн ДОП. На вход устройства - элементы вектора значений МД. Поток данных в '-и ВЯ организован таким образом, что на входа умножителя одновременно поступают *-й (< = 0, г" -I) элемент МД и «т/д/Д-й элемент матрицы ДШ» а сумматор обеспечивает формирование окончательного результата значения /-го с1/> коэффициента формы представления МД. <Н, состоящая из регистра СРг) и коммутатора (К), обеспечивает передачу промежуточного результата через коммутатор в ВЯ и окончательного - на выход устройс-

В том случае, когда непрерывный ввод элементов матрицы. ДШ невозможен, для вычисления коэффициентов формы представления МД используется систолический процессор, приведенный на рис.4. Этот процессор содержит ячейки типа ВЯ, ЗЯ (ЗЯ^) и дополнительную 31 (Ш2>. В у-й ЭЯ2 осуществляется хранение у-Й строки матрицы Д0П в блоке памяти {БП) типа ИБО. Причем во второй блок памяти параллельно с процессом вычисления записывается j ~я строка матрицы ДШ другого базиса. Такая структура Ж2 позволяет организовать непрерывное вычисление коэффициентов различных форм представления МД.

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

тва.

л?//

зяг зя}

11 И

вя вя

11 и

ц ЗЯ,

¿Яг

п

вЯ

п

а)

ЗЯ,

т

п'-о

Рис.4

Для восстановления исходных МЛ, заданных в виде разложения Рида-Маллера, арифметической полиномиальной формы представления, модификаций этих форм предлагается вычислительная структура, приведенная на рис.5. Функционирование этого процессора основано на структурировании данной формы по схеме Горнера:

¿(М=¿г ..

где

j'0.г-t,

)/£, £г*„)*...'Х„ '

Таким образом, исходная форма преобразуется к системе вложенных полиномов, каждый из которых зависит от одной переменной, а его коэффициенты являются значениями полиномов, зависящими от последующей переменной. На вход устройства последовательно поступают коэффициенты полиномиальной формы, начиная с С-го. На вход (л -¿>-й ВЯ подается значение переменной . На выходе устройства формируется значение многозначной ФАЛ, соответствующее набору переменных, заданному на входах. ВЯ.

В табл.3 приведены характеристики систолических процессоров для обработки МД.

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

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

Таблица 3

Характеристика систолического массива Для вычисления формы описания МД Для восстановления МД, заданных в виде 4

Число ячеек Г" П

Число тактов начальной заг-

рузки иг"''

Число тактов в установившем-

ся режиме. г "С/?-/)

Число тактов торможения

Общее число тактов работы (л-*)

Число тактов до начала выда-

чи первого результата + (0-2) ■

Эффективность использования

оборудования </*

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

Рассматривается методика решения задачи диагностики комбинационных схем на многоуровневых элементах. Синтезируются диагностические тесты на основе матричных операторов модифицированных логических производных. Далее этот подход развивается для решения задач диагностики с использованием арифметических форм описания МД, Так, значения многозначной ФАЛ, со-ответствупцие изменениям входных переменных ЯГе- (¿ =1,П) , интерпретируются как переменные ^ (/' = 2, л +1) арифметической форш описания МД

а переменная этой формы рассматривается как текущее зна-

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

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

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

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

ЗШ1ШЕНИЕ

Главный результат диссертационной работы состоит- в разработке единого подхода к синтезу форм представления МД и операторов логического дифференциального исчисления многозначных ФАД на основе матричных процедур. Эта теоретическая основа обеспечила синтез методой и алгоритмов обработки МД, удовлетворяющих требованиям архитектуры систолических массивов линейного типа, ориентированных в своей реализации на современную технологию СБИС. '

I. Разработаны теоретические основы методов синтеза форм представления МД и логического дифференциального исчисления многозначных ФАЛ, имеющих прямое отображение в архитектуру высокопроизводительных систолических массивов:

1.1. Предложен подход к синтезу форм описания МД, в рамках которого получено расширение класса форм за счет синтеза новы* и обобщения известных.

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

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

2. Разработаны алгоритмы и технические решения в виде систолических массивов линейного типа для обработки МД:

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

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

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

3. Разработаны методики решения прикладных задач на основе методов обработки МД и посредством аппаратной поддержки на систолических' процессорах:

3.1. Предложена эффективная методика диагностики схем на многоуровневых элементах, основанная на аналитическом описании, многозначных ФАЛ и их логическом дифференцировании.

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

3.3. Развита методика решения систем логических уравнений

с многозначными переменными посредством матричных процедур| ДШ, которая использована в задачах целочисленного программирования.

3.4. Впервые получены модели многоуровневых элементов в виде линейных систолических массивов.

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

1. Кухарев Г.А., Шмерко В.Г1., Зайцева E.H. Алгоритмы и систолические процессоры для обработки многозначных данных. - Мн.г Наука и техника, 1990. 296с.

2. Шмерко В.П., Янушкевич С.Н., Зайцева E.H. Обобщение булева дифференцирования и интегрирования на функции многозначной логики // Автоматика и вычислительная техника. - mh.s Вы-шэйшая школа, вып.18. С.116-122.

3. Антоненко В.М., Зайцева E.H.,'Шмерко В.П. Арифметико-логические модели многозначных данных // Автоматика и вычислительная техника. - Мн.: Вшзйшая школа, вып. 19, 1990. С. 112—118.

4. Шмерко В.П., Малюгин В.Д., Зайцева E.H. Принципы синтеза и организации однородных структур для полиномиального преобразования булевых функций / Методы й микроэлектронные средства цифрового преобразования и обработки сигналов. -Тез. докл. всесоюзной конференции. — Рига, 1986. С.42-45.

5. Шмерко В.П., Малюгин В.Д., Зайцева E.H. Преобразование полиномиальных форм функций ft. ^значной логики методами цифровой обработки сигналов. Там же. С.54-59.

6. Зайцева E.H. Алгоритмы формирования арифметико-логических форм функций многозначной логики / В кн.: Материалы I сту-денчиской конференции по физико-математическим наукам, радиоэлектронике и вычислительной технике. -!.1н., 1987. С.16.

7. Шмерко В.П., Зайцева E.H., Янушкевич С.Н. Синтез конвейерных процессоров для логического дифференцирования и интегрирования функций многозначной логики / Конвейерные вычислительные системы. Тез. докл. всесоюзного совещания. - Киев, 1988. С.149-150.

8. Антоненко В.М., Зайцева E.H., Кривицкий A.B. Дискретное преобразование Фурье для синтеза форм представления многозначных функций / Актуальные проблемы фундаментальных наук. Тез. докл. межреспубликанской научно-технической'конференции. -!.!., 1989. С.27.

9. Антоненко В.М., Зайцева E.H. Систолические процессоры для синтеза новых форм представления многозначных логических данных / Применение информатики и вычислительной техники при

решенне народно-хоаяйотвенншс вадач. Тез. докл. республиканской конференции молодых ученых и специалистов. - Мн., 1989. С.41-42. ,

10. Антоненко В.М., Зайцева E.H., Шмерко B.1I. Аналитические формы представления целочисленных отсчётов сигнала на основе быстрого преобразования Фурье / Цифровая обработка сигналов в системах связи и управления. Тез. докл. научно-технической конференции. - Суздаль, 1989. С.34-36.,

11. Зайцева E.H., Мысовских С.А. Моделирование.многоуровневого элемента для видеопроцессора / Распознавание образов и анализ изображений. Tea. докл. научно-технической конференции стран СНГ. - Мн., 1993. С.Н6-П9.

12. A.C. 154Г591 /СССР/ м.кл. G 06 3? 7/00, 15/32. Устройство для Логического .дифференцирования булевых функций / Янушкевич С.Н., Зайцева E.H., Кухарев Г.А., Шмерко В.П. // Бюллетень изобретений и открытий, 1990, Ж>.

13. А..С. I541592 /СССР/ М.Кл. G 06 F 7/00, 15/32. Устройство для логического дифференцирования й интегрирования булевых функций / Янушкевич С.Н., Зайцева Ё.Н., Кухарев Г.А., Шмерко В.П. // Бюллетень изобретений и открытий, 1990,

14. A.C. 1666365 /СССР/ М.Кл. G 06 Р 15/32. Устройство для дифференцирования логических функций / Дашенкой В.М., Зайцева E.H., Тупиков В.Д., Шмерко В.П., Янушкевич С.Н. // Бюллетень изобретений и открытий, 1990, №19.

15. A.C. 1656549./СССР/ М.Кл. & 06 Г 7/00. Устройство для вычисления логических производных многозначных данных / Зайцева Jä*H.i КривВДкий A.B.,. Кухарев Г.А, , Шмерко В.П. // Бюллетень изобретений и открытий, 1991, №22.

16. A.C. 1670690 /СССР/ М.Кл. G 06 I'15/31, 7/00. Устройство для вычисления логических производных многозначных данных / Антоненко В.М., Зайцева E.H., Кухарев Г.А., Шмерко В.П. // Бюллетень изобретений и открытий, 1991, №30.

17. A.C. I7306I7 /СССР/ М.Кл, & 06 F 7/04. Модуль для вычисления логических производных / Антоненко В.М., Зайцева E.H., Шмерко В.П., Янушкевич С.Н. // Бшлетень изобретений и открытий, 1992, J46.

- 1.8 -

Зайцева Елена Николаевна

метода И АЛГОРИТМЫ ОБРАБОТКИ МНОГОЗНАЧНЫХ ДАННЫХ на ЛИНЕЙНЫХ СИСТОЛИЧЕСКИХ ПРОЦЕССОРАХ

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

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

Подписано в печать 3.02.94г. Формат 60x84 1/16 Объем 1,0 усл.печ.л. 1,0 уч.-взд.л. Тираж 90 экз. Заказ 54