автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Теория и методы реализации массивных вычислений в итеративно-битовых СБИС-структурах

* С - ' 3 1

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

К51ЯЗЫ(ОГ. Владилиф Сергеевич

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

\>ПС I к Я Л Л о ¡¡ость 05.13.1.3. — «Вычислительные машины, комплексы, системы и сети»

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

АВТО РЕФЕРАТ

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

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

ПЕНЗА 1998

Работа выполнена ,на кафедре «Вычислительная техника» Пензенского государственного университета.

Научный консультант: заслуженный деятель науки и техники РФ, доктор технических наук, профессор Вашкевич Н. П.

Официальные оппоненты: доктор технических наук, профессор Жданов В. С.; доктор технических наук, профессор Песошин В. А.; доктор технических наук, профессор Титов В. С.

Ведущая организация: Государственное научно-производственное предприятие «Рубин».

Защита диссертации состоится РШ^ 1 ПОЯ г.,

в /V часов, на заседании диссертационного совета Д 063.18.02 Пензенского государственного университета по адресу: г. Пенза, ул. Красная, 40.

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

Автореферат разослан (Ю-МТЛо&З- 1998 г.

Ученый секретарь /

диссертационного совета^.. у Б. Д. Шашков

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

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

ггоматизация проектирования, компьютерная фотография,

«

ультипликация и т.д.

Исследование' и проектирование ЭВМ и систем для :шения задач в перечисленных областях проводятся как у нас в

ране, так и за рубежом начиная с 60-х годов. Однако, парк ких ЭВМ и систем по технико-экономическим причинам ироко не использовался. Сегодня задача создания технически зфективных и рентабельных СБИС-ЭВМ и систем для решения дач с параллелизмом объектов определена в ведущих странах 1ра в качестве приоритетной научно-технической проблемы, гализ известных решений в этой области, опыта, юектирования и эксплуатации таких ЭВМ и систем, зультаты исследовательских и опытно-конструкторских работ называют, что использование методологии массивных битовых [числений позволяет наиболее полно учесть особенности временных технологий изготовления СБИС и соответственно |фективно реализовать процессорную платформу, обеспечить спараллеливание вычислений до битового уровня, упростить шение проблемы межсистемной совместимости. Методология

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

Цель диссертационной работы состоит в разработке теории и методов реализации массивных вычислений в итеративно-битовых СБИС-структурах для ЭВМ и систем класса ОКМД.

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

1. Исследование особенностей, способов решения прикладных задач, методов организации вычислений, современных концепций и способов построения платформ ЭВМ и систем класса ОКМД.

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

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

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

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

Научная новизна результатов диссертационной работы в [.едом заключается п разработке новых разделов -теории ¡драллельных вычислений и структур - теории и способов са:пп:шип массивных вычислений в итеративно-битовых ьмис.ипетышх структурах :

!. Предложены и исследованы способы органи кщмн счислений на основе массивных итерационно-разрядных и леточных операций в итеративно-битовых вычислительных ;рукт\рах и подход для оценки их временной и ространс!венной сложности, позволяющие при реализации тгоритмов массивных вычислений осуществить обоснованный •лбор способа организации вычислительного процесса и (.или! ¡особа построения СБИС-струкдуры.

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

реализации в итеративно-битовых СБИОструктурах различной размерности при различных способах организации вычислений, что дает возможность при программной реализации алгоритма осуществить обоснованный выбор типа' ЭВМ или системы и определить оптимальные с точки зрения сложности способы организации вычислений, а при аппаратной реализации алгоритма - обоснованно выбрать способ организации вычислительного пространства.

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

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

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

обеспечить минимальную временную и пространственную сложность его реализации в СБИС-структуре.

6. Предложены правила формального преобразования зыраженпй алгебры логики Буля в выражения введенной шгебраическон . системы, что обеспечивает возможность зыполнить формальное преобразование алгебраического шисания. алгоритма в виде булевых выражений в эквивалентное шалитическое описание алгоритма для массивных' вычислений в-1теративно-битовых. СБИС-структурах. "

7. Предложена методология синтеза алгоритмов в базисе :веденной. алгебраической ; системы . * и синтезированы ■птимальные по вь1числительной сложности параллельные лгоритмы базовых процедур . предварительной обработки :ифровых изображений, что обеспечивает возможность рофаммной реализации алгоритмов с минимальной временно]"! ложностью и возможность формального синтеза СБИС-груктур для их аппаратной реализации.

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

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

Реализация и внедрение. Диссертация является теоретическим обобщением ■ ряда научно-исследовательских работ, выполненных автором в Пензенском государственном университете в соответствии с Координационным планом вузов в области вычислительной техники. Основные практические и теоретические результаты получены автором при выполнении НИР «Исследование и разработка аппаратных средств поддержки математического обеспечения -ВС ' для решения задач конструкторского проектирования СВТ» в рамках правительственной программы «Единая система автоматизации проектирования электронной вычислительной техники», фундаментальной НИР «Разработка теории и исследование способов реализации параллельных ' процессоров логико-комбинаторных вычислений» в рамках заказа Минвуза РФ. Результаты работы в виде моделей, алгоритмов, программных и аппаратных модулей внедрены и используются в Пензенском производственном- объединении электронно-вычислительной техники, НИИ • вычислительной техники (I .Пенза).

Государственном научно-производственном предприятии

"Рубин* fr.Пенза). По результатам исследований предложены

i н пчсские решения, защищенные 17 авторскими

■-•виде i ел ьс ними на изобретении и патентами РФ. Разрабокшные

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

пн.кенерно-'.ехмм'.-екпе методики введены в учебную программу

подготовки студентов по специальности 22.01.00. «ЭВМ,

\

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

Aiipoóaiiijя работ!:. Основные результаты диссертационном paóott.: кжладывллпсь и обсуждались на следующих симпозиумах, семинарах и научно-технических конференциях : I -оГ: Между нар. научно-практ. конф.«САЛР CBTS9.», 17-21 аир. IOS1)!..!". Ленишрад ; М^ждунар. Конф. «Новые информационные технологии в науке, образовании и бизнесе», Украина, г. Гурзуф, -М.- \!,H¡ !1¡'J2 г.. 1093г., 1997г. : Междунар. и/т комф.«< Техно..'»! >п и системы сбора, обработки и представления информации», г.Рязань .15-18 сентября 1993 г. : Международ, науч. техн. конф. " : i_1 :í.íí• *io[ iHiecKH'j и нейронные сет;: и мс-:'■"1 : . 1 2-ал Л i wíviy пар. ii/i конф. üoüuw информации.

го'полем пи и сис»емы".!9%. Пенза ; Bceco:o;v¡. симно i,¡ум.. "Проблемы цифрового кодирон: пия и преобразования изображений".18-20 сент. 1980г., г. Тбилиси ; III Всесоюзн. шк.

по оптической обработке информации.,11-20 мая 1980г.,-г. Рига; Всесоюзн. конф. " Автоматизированные системы обработки изображений", 9-11 июня 1981г., г. Москва; Регион, конф «Обработка изображений и дистанционные исследования», 1-3 апр.1981г., г. Новосибирск ; Всесоюзн. совещание-семинар «Технические и прикладные вопросы разработки, внедрения и эксплуатации САПР радиоэлектронной аппаратуры»,3-8 сент.1984г.,г.Одесса; Всесоюзнной. научн. техн. конф. «Микропроцессорные системы», г. Челябинск, 1984г. ; Всесоюзн. научн. техн. конф. «Совершенствование устройств памяти информационных компьютерных и робототехнических систем». 23-25 нояб. 1988г., г. Одесса ; IV Всесоюзн. научн. техн. конф. «Системы баз данных и знаний» ,21-23 ноябр. 1989г., г.Калинин, 1989.- C.2Q-21 ; IX Всесоюзн. научн. техн. конф. «Планирование й автоматизация эксперимента в научных исследованиях» • ,25-27 сент. 1989г.,г.Москва; VII Всесоюзн. школе-семинаре «Распараллеливание обработки информации» ,9-14 окт. 1989г., г. Львов ; Всесоюзн, научн. техн. семинаре «Распределенная обработка информации» , 1-9 июля 1989г., г. Улан-Удэ ; Всесоюзн. научн. техн. семинаре «Распределенная обработка информации» , 19-25 авг. 1991г., г. Горно-Алтайск ; Всесоюзн. научн. техн. конф. "Новые информационные технологии в науке, образовании и бизнесе", 1992-1993г.г., Воронеж ; Всеросс. научн. техн. конф. «Распознавание образов и * анализ изображений: новые . информационные технологии», • Ульяновск, 1995г.; Всеросс. научн. техн.конф. «Интеллектуальные САПР», сент. 1992г., 1994г.,1995г., 1996г., 1997г, г. Геленджик ;

Всеросс. научи, техн. конф. «Непрерывная и смежные логики в информатике, экономике и социологии» ,30-31 окт., 1997г., г.Пенза ; Всесоюзн. научи, техн. совещание семинар молодых ученых и специалистов «Разработка и оптимизация САПР и ГАП изделий электронной техники на базе высокопроизводительных мини - и микро- ЭВМ» , 11-19 еент. 1989г., г. Воронеж ;Всесоюзн. научн. техн. совещание-семинаре «Технические и прикладные вопросы разработки, внедрения и; эксплуатации САПР радиоэлектронной аппаратуры», 3-8 сент. 1984,г., Одесса ; Всесоюзн. шк.-семин. «Опыт ' разработки и - применения приборноттехнологических САПР» 23-28 февр. 1991г., г. Львов.

На ЗАЩИТУ выносятся новые теоретические и инженерно-технические положения,, в

. л

комплексе составляющие решение крупной научно-технической проблемы - создание теории и методов реализации массивных вычислении г> итеративно-битовых СБИС-структурах для ЭВМ и систем класса ОКМД.

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

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

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

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

Публикации. По теме диссертации в научных изданиях, в которых могут быть изложены основные научные результаты докторских диссертаций, опубликовано 64 работа. В том числе 17 авторских свидетельств'"и патентов на изобретения, 21 статья, монетрафия, два учебных пособия для специальности 22.01.00. по плану Мщшуза РФ и тезисы докладов в трудах Международных, Всесоюзных и Всероссийских научно-технических конференций и симпозиумов.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы и приложения. Объем работы: 339 страниц основного текста, 115 рисунков на 45 страницах, 5 таблиц, список литературы из 300 наименований на 2& страницах, приложения на 10 страницах.

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

По введении обоснована актуальность темы диссертации, определена цель исследования, сформулированы научная

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

В первой главе проведен комплексный анализ способов решения прикладных задач, методов организации вычислений, современных концепций построения ЭВМ и систем класса ОКМД и особенностей их организации. Показано, что область применения специализированных ЭВМ и систем с полной аппаратной реализацией вычислений ограничиваемся задачами с

практически отработанными решениями. ЭВМ и системы на

*

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

• Комплексный анализ современных решений в области ЭВМ I систем класса ОКМД, опыта их проектирования и жеплуатации, " результаты исследовательских и опытно-сонструкторских работ показывают, что наиболее эффективной [вляется концепция массивных вычислений с командно-юммутационным тйпом управления. Такой подход позволяет [аиболее полно учесть особенности, технологии - изготовления "БИС, реализовать технически просто процессорную платформу,

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

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

Алгоритмические решения ' задач нечисленного типа в основном используют операции целочисленного ■ сложения и вычитания, практически отсутствуют арифметические операцин

г плавающей точкой. При этом, обрабатываемые структуры

данных как правило являются связанными, доступ к их

элементам осуществляется с использованием указателей, в

качестве указателей обычно используется небольшое количество

юкальных скалярных переменных; индексация массивов

фименяется редко. Наиболее часто выполняются такие

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

слассифнкацни и идентификации - групп данных.

Базовыми операциями первого * уровня при решении

1

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

Повышение эффективности вычислений можно обеспечить

а счет адекватной организации вычислительной среды для

ыполнения операции мерного уровня. При этом эффективно

спользование методологии массивных битовых вычислении. ' f

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

технической проблемой является разработка теории и методов реализации массивных вычислений в итеративно-битовых СБИС-структурах для ЭВМ и систем класса ОКМД.

Во второй главе разрабатываются й исследуются способы организации массивных вычислений в одномерных, двумерных и трехмерных вычислительных структурах с общим управлением. Выполняется оценка сложности вычислений в процессорных структурах с топологией связей типа «ближайший сосед». Исследуемые структуры являются массивами битовых процессорных элементов (ПЭ) с индивидуальными битовыми модулями ОЗУ. ПЭ связаны между собой битовыми каналами приема-передачи данных через коммутационные элементы. Для оценки сложности вычислений в таких структурах используются понятия временной и пространственной сложности. Под временной сложностью вычисления ( TIME ( М, N )) понимается число шагов вычислений М над цепочкой данных X до останова М. Под пространственной сложностью вычисления ( SPACE (M,N)) понимается число функциональных модулей структуры, необходимых при вычислениях М на цепочке данных X до останова • М. Пространственная сложность и временная сложность оцениваются функциями вида :

• TIME ( M,N )=Max (TIME (М, X):|X| = N) и

' . SPACE (М , N )= Max (SPACE (М , X) : | X | = N ).

.»Организация вычислений рассматривается в многомерных итеративно-битовых процессорна пространствах из D элементов при. различных способах размещения N-элементных структур М-

разрядных данных для класса А-вычислений и юшсса К-вычислений. . . .

Ллясс А-вычислений характеризует операции первого уровня численных задач. При таких вычислениях выполняется набор из Р итерационно-разрядных операций. .Причем, каждая операция выполняется для каждого данного, порядок обработки данных произвольный, операции обработки данных являются и1 епанионно-независимымп,• при вычислениях значение каждого ¡-го разряда данного зависит от значения его (И)-га разряда.

Класс К-вычислений характеризует операция задач нечисленной.обработки. Каждая операция является клеточной, итерационно-разрядной операцией : значение .¡-го разряда Ь-го элемента данных зависит от значения его собственного (.¡-1 )-го разряда и (_ ,¡-1 )-ых разрядов элементов его окрестности. Каждая операция вычислении является пространственно-инвариантной, итерационно-независимой и применяется для каждого данного структуры, порядок обработки данных произвольный.

Показано, что временная и пространственная сложность вычислений в итеративно-битовых СБИС-структурах при А- и д-вычислениях определяется выражениями, приведенными в таблицах 1-6. , где : . • •

?.} - разрядность элемента данных, N - количество /цишых. О - количество модулей вычислительной структуры, ОТ1МК -класс временной сложности вычислений, Б8РАСЕ - класс пространственной сложности вычислений, Р - общее количество

исполняемых операций, а - количество элементов окрестности при выполнении клеточной операции.

Таблица 1

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

разрялло-параллелыше вычисления ЭТ1МЕ (( 2 (М+1) МЫ/Т)) Р ) ОБРАСЕ ( М N + 2 О )

разрядпо-последовательные вычисления ОТ1МЕ ( 3 М N Р / Б ) 05РАСЕ ( М N + 2 Р )

разрядно-параллелъные конвейерные вычисления при плотной упаковке элементов ОТ1МЕ ((4МЫ / Э+4 (0-1))Р ) ЭБРАСЕ (МЫ тБ ( Б+ 1))

разрядно-яараллельные конвейерные вычисления при разряженной упаковке элементов БТ1МЕ ( 4 М N ) ОБРАСЕ(МЫО+2Б)

разрядно-последовательные конвейерные вычисления при плотной упаковке элементов ЭТ1МЕ (( 3 МЫ Д>+3(0-1)) Р ) ЮБРАСЕ ( М N + Б ( О + 1 ) ^

разрядно-последовательные конвейерные вычисления при . разряженной упаковке элементов БТШЕ ( 3 М N Р) В5РАСЕ(МЫБ + 2Б )

Полученные аналитические выражения для оценки сложности вычислений кроме прямой оценки временной и 1>росфлнсгиешгой сложности реализации вычислительного процесса позволяют определить такие практически нужные чаракгсристики , как : число процессоров вычислительного (Ч^кп ранета. способ организации данных и вычислений,

18

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

Таблица 2

НиСОЬЫ организации массншю- пос."ндов мгльных вычислений временная и пространственная сложность одномерных К-вычислений

разрядно-параллельные . ТУПМЕ (ГПМ-Н)я+?) М N Р / О ) П5Г,\СЕ ( М N г )

разрялно-последовательные вычисления БТ1МЕ (( 2 а + 1 ) М N Р / Б ) Б5РАСЕ ( М N + 2 Б )

разрядно-параллельные конвейерные вычисления при плотной упаковш данных ОТ1МЕ ((3 (а -1)+4 М ) N Р/Б ) ББРАСЕ ( 2 Б + М N Э )

разрядно- параллельные конвейерные вычисления при разряженной упаковке данных БТШЕ (( 3 (а-1)т4М)^Р/Б+ + Р ( Б - 1 ) / М ) ОБ РАСЕ ( Б ( Б + 1 ) + М N )

разрялно-последовательные конвейерные вычисления при плотной упаковке данных . БТШЕ ((3 М N /Б+3 (Б-!)) а Р ) ББРАСЕ ( М N а +Б ( Б + 1 ) )

пазрядно-послеловятельнь.; конвейерные вычисления при разряженной упаковки данных БТШЕ (3 М N аР) ББРАСЕ ( М N а Б + 2 Б )

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

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

Таблица 3

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

раз|зядно-послсдовательные ортогонально-конвейерные вычисления БТ1МЕ ( ( 2 М+4 М N / 0 ) Р ) ББРАСЕ ( М N Б + 2 Б 2 )

разрядно-параллельные • ортогонально-конвейерные вычисления БТШЕ ( 4 М + 5 М N / Б ) ЪбРАСЕ ( М N Б +2 В'2 )

ортогонально-конвейерные диагональные вьгчисдения ЭТШЕ ((6Б + 4М N / Б - 4 ) Р ) ОБ РАСЕ ( М N В + В 2 + Б1)

разрядно-последовательные вычисления БТ1МЕ ( 4 М N ?/ В1) ЦБ РАСЕ ( М N + 2 Б2 )

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

разрядно-параллельные вычисления БТШЕ (2 ( М + 1) МЫ Р/Б2) ББРАСЕ ( М N + 2 О2)

разрядно-параллельные диагональные вычисления ШШЕ (2 ( М+1)(М^02+0.5(0-1)Р) ОБРАСЕ ( М N Б + 2 Б2 )

разрядно-последовательные диагональные вычисления ОТ1МЕ (4Р(М^Р2+ 0.5 (Б - 1 )) ОБРАСЕ ( М N 0 + 2 Б2 )

рззрЯдно-последоЕательные диагонально-конвейерные вычисления ОТШЕ ( 4 Р ( М N / О 2 +0.5 (Б-! )) ББРАСЕ ( М N Б + 2 Б2 )

| СПОСОБЫ ОРГАНИЗАЦИИ - ■ ' - " '..... " ' м ХССПШЮ-НОСЛЕДОВЛГЕЛЬНЫХ ; вычислений , временная и пространственная сложность ДВУМЕРНЫХ К-ВМЧИСЛЕПИЙ

ра ¡рядно-последовательные орюгональко-конвейерные вычисления ОТЬМЕ <( 2 М + 4 N1 N / О) а Р ) ОБРАСЕ ( М N О +2 О 2 )

разрядно-параллельные ортогонально-конвейерные вычисления ОТ1МЕ ; (( 4 М а + 5 М№ / О ) Р ) 05РАСЕ ( М N о"+2 О 2 ) ■ 1

ортогонально-конвейерные диагональные вычислений . 0Т1МЕ •(( 6Э+4М N / Э - 4 )а Р ) ОБ РАСЕ ( М N 0+ Э 2 + О3 )

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

разрядно-последовательные вычисления ОТ1МЕ ( 2 ( а + 1 ) М N Р /О2) ОБ РАСЕ (МН+202)

разрядно-параллельные вычисления ШШЕ ((2 а М+а+1) MNP/ О2) 05РАСЕ ( М N + 2 Б2)

разрядно-параллельные диагональные вычисления. 0Т1МЕ (Р (2аМ+а+1) (МН/02+0.5(0-. 1)) ^ ОЗРАСЕ ( М N О + 2 О2)

разрядно-последовательные диагональные вычислений 0Т1МЕ ( 2 Р (а+1) ( МЫ/О 2+ 0.5 ф-15) ОБРАСЕ (-М N Б + 2 Б2 )

разрядно-последовательные диагонально-конвейерные вычисления БТ1МЕ ( 2Р (а+1) ( МЫ/ 02+0.5 (Э-1))) 05РАСЕ |М N О +2 Р2)

способы организации массивно. поспедовательных вычислений временная и пространственная сложность трехмерных А-ВЫЧИСЛЕНИЙ

разрядно-последовательные ортогонально-конвейерные вычисления ЭТ1МЕ (( 2 М + 4 М N / о2) Р ) ББРАСЕ ( М N Б 2+2 Б 3)

разрядно-параллельные ортогонально-конвейерные ■ вычислений ОТ1МЕ (4 М + 5 М N / Б - ) ББРАСЕ ( М N Б 2+2 О 3)

ортогонально-конвейерные диагональные вычисления БТШЕ ( (4 М N / ГЯ + 60 -4) Р) ББРАСЕ (N1 N Б2 +0 3+Б4 )

способы организации массивно-параллельных вычислений вгеменная и пространственная сложность трехмерных А-ВЫЧИСЛЕНИЙ

разрядно-последорательные вычисления ШЧМЕ ( 4 М N Р/Б3) ББРАСЕ ( М N Б + 2 О3)

разрялно-параллельные вычисления ШШЕ (.2 ( М + 1 ) М N Р / В3) ББРАСЕ ( М N О + 2 О3 )

разрядио-параллельные диагональные вычислений БТ1МЕ ( ( М + 1 ) (2М>}/В3 +(0-1)) Р ) ББРАСЕ (МЫ Б2+ 2 Б3)

разрядно-последовательные диагональные вычисления ■ БТШЕ ( ( 4 М N /Б3 +2(0-1)) Р ) ОБ РАСЕ ( М N Б2 + 2 Б3)

разрядно-последовательные диагонально-конвейерные шч'лсленпя БТШЕ ( ( 4 М N / Б 3 +2(В-1)) Р ) ББРАСЕ ( М N Бг + 2 Б3 )

) способы организации | млссишго- 1 последовательных ; вычислений ' "" ВРЕМЕННАЯ и пространственная сложность трехмерных К-вычасмЕ.чий

( разрядно-]юследоватедьные | ортогонально-конвейерные | вычисления DTIM Е (а (2 М + 4 М N / D2 ) Р) I DSPACE( М N D2+2 D 3 ) |

разрядно-параллельные ортогонально-конвейерные вычисления DTIME ((*4*Ма+ 5М Nai/ D2) Р) DSPACE ( М N D 2 + 2 D 3)

ортогонально-конвейерные диагональные вычисления DTIME ( а ( 4MN / D 2+6 - 4 )Р) DSPACE (MND+D2 + D3)

способы организации МЛССИВНО-ПАРАЛЛЕТЬНЫХ ВЫЧИСЛЕНИЙ временная и пространственная сложность трехмерных К-ВЫЧИСЛЕНИЙ . .

разрядно-последовательные вычисления DTIME ( 2 ( а + I ) м N Р / D3 ) DSPACE ( М N D + 2 D3)

разрядно-параллельные вычисления DTIME (( 2а M+a+l)MN Р / D3 ) DSPACE (MND + 2D3) .

разрядно-параллельные диагональные вычисления DTIME (Р (2aM+a+l)( MN/D3+0.5(D-l)) DSPACE ( М N D2+2 D3)

разрядно-последовательные диагональные вычисления DTIME ( (a+l)(2MN/D 3+(D-l )) P ) DSPACE ( M N D2+ 2D3)

разрядно-последовательные диагонально-конвейерные вычисления • DTIME (( я+l) (2MN/D 3+D-1) i' 1 DSPACE ( MND3 + 2 W) ! ■ . . I

Вычислительное пространство интерпретируется Евклидовой плоскостью с дискретизирующей решеткой размерностью ( а к к1.4

элементов.» метрикой Мура* <11 < 1 ^ > ='! Ч"- 1 + I Л - j г Ь Каждому элементу данных сопоставлена пара целых чисел (У)' координат Евклидовой плоскости. Значения данных определены на множестве {0,1 }к . Множество А=. {а у} элементов такой ■плоскости образует пространство с метрикой с!) (1 , ), где а; ] е А представим булевым вектором длинной к: а ¡л = а' ¡о , а 21^ ,-а3 у , а4 ¡^ ... ак у. Множество А принимается в качестве области определения 5-алгебры, а сигнатуру составляет следующий набор операций.

Определение 1. Б-операцией ориентированного сдвига 0 ^ ( А ) называется операция массовой перестановки элементов множества А = { аау }, 1=1,2,...,п , j=l,2>...,m, а = 1 , 2-,..., к в метрическом пространстве на N позиций без изменения их значений.

Операции 8-сдвига на «х» позиций "вправо" , "влево" "вверх" и "вниз" по координатной оси ОХ и ОУ далее соответственно обозначаются как : (А), Ц(А), \УХ (А), Ых( А). Определение 2. 8-операцией инверсии называется операция массовой замены значений элементов множества А на их дополнения без изменения местоположения в метрическом пространстве и обозначается. С =.А , где А = { а, ^ } ; 1 = 1.....П , ') = 1,..., ш.

Определение 3. Б-Операцией дизъюнкции называется операция массового логического сложения однопозиционных элементов двух множеств А = { а 1й В = { Ь ¡ ] }, \ - = 1,2,...,п , ,] = .1,2,..,,т без изменения их местоположения в метрическом

. пространстве: С = A v В . где С = { с ¡ j } , i= l,2,...,n ;

j = l,2,...,m ; с ¡ j = a ¡j _v b ,j. .

Определение 4. Б-оиерлннсн конъюнкции называется операции массового логического умножения олиопозишгонных элементов двух множеств А = { a ¡j } и В' = { b ¡ j }, i = 1.2,...,л , i = 1.2,.. .m oes и ¡менеипя их местоположения в метрическом пространстве. С = А&В , где ■ "

С Í с .. I . i— ¡ ,2.. ,i i _ , / гп с •: = i . i к ^ ■ Для исследуемой области приложений использованы также понятия функций тестирования, пространственной 1 и 0. Определение 5. S-функцией дизъюнктивного тестирования "Р ( А ) называется операция вычисления булевой функции от ( п х ш ) переменных на множестве А = { a ¡} }, i= 1,2,,..,п , j - I.2....,;n вида:- Г ( А ,) = а'и v a2u v ....v akmn = V ( а ). Определение "6. S-функнией конъюнктивного тестирования Т0 ( А ) называется операция вычисления булевой функции от

( n \ m ) переменных на множестве А= { a ¡j } , i = 1,2.....n .

j = i,2,...,m вида: T* ( А ) = a'u & а2,, & ... & akmn =& ( a k,j) . Определение. 7. Множество А называется логической -S-едитшеп (1 s ) , если ( А )=[, и логическим S-нулем (0 ^ }, если ~Г'(Л )=Ü.

Введены табличнйя и аналитическая формы представления

Функций. ПОНЯТИЯ ДИЗЪЮНКТИВНЫХ И КОНЪЮНКТИВНЫХ S-'iepMün, ранга термов, конъюнктивных и дизъюнктивных форм. Разработаны правила взаимных преобразований табличных :: шалишческих представлений функций. Исследованы свойства элементарных S-функций и методом совершенной индукции

Т4 ( (? N ( А V А)) Т4 ( 1 О N ( А "V А))

Ту (1 О N ( А V А ))

Ту (1 О м ( А & А ) )

= 0;

= 0;

= 1;

= 1.

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

1. свойства истинности Т*(С>Ы(А&А)) = 0;

(<3 м' ( А V А )) =1 ; ■Р'СОм (А & А')) = 0 ; Т'М 1 <э к ( А & А )) = 1 ; Следствия

■I* (0 N (А V А (1 О к ( А V А)) = Т&(10М(А & А > ) ;

( 0 м ( А V А ) ) <3 N ( А & А ) ) = 0 .

2. свойства идемпотентности

0 N (В)&(3 N (В )= о N ( В ) ; О Ы (А) V 0 N (А)=(? N (А).

3. свойство ориентированного сдвига

<3 к(НЬ(С> к «О с ( ((А))...)=0о (А) & н; (1®)&н; (1 5),

где Б =Ы-Ь+К-1+С...- И , (2 N. Н;....- операции сдвига.

Следствия

<Ь=о(А)= А; А .«^м-в(А);

(А))=\%м(А) & (1 8).

^ (1м (А))-К^м£А)&Ьм О 5);

( А)) = А & Ык (1 ^;

4. свойства ассоциативности

СЫ(НМ (Бк (А)))= ( Нм ( сы ( ( А ))) =.... (( <3Ы ( 5К ( Нм ( А ))); Оы(А) У(Нм(В)у5к(С)) = ( ОК(А)УНм(В)) V ( С ); СЫ(А)&(Нм(В)&5к(С))=(С>ы( А ) &Нм ( В )) & ( С ).

5. свойства ¡¡'единицы ( ) и б-нуля( о5)

О*- 15 ;

о 5 V = ^ ;

N 1 Б ) = о 5 при М = ш ; Ь ы С1 5 ) = 0 5 при N = п ; Ок.(А )у 0 N С А ) = ^ ; О N ( А ) & о N ( А ) Т= 0 ;

<Ь(А) V <3 ц ( А ) * 1« <Зи(А)&1Б = (Зк(А) ^ м ( 1 5 ) = 0 5 прим = ш Як П Б ) = О55 при N = п Т ^ (О N (13))=1 при Ы* п (Н * гп ) Т^ (0 м ( ] £ ) =0 при N *0 •

Q N ( 1s") * ls ; Qn(A)vOS = A; T v (Q N ( 0 s ) ) = 0; 0S& ls = OS; Q N ( A ) V IS = 1S ; ~ls = OS;

Следствия

~ 14

о - — i ^ :

Ts = ()S 0s ¿.¡s = 0s

OS v ]S =]S ;

1 s ) = 1 ; . - • - • Тл( 1S) = 1 ;

T1(Qn(0s)=0; Q n ( Os ) = Os ;

Q N ( A ) & Os = OS ; Qn(A-) & Ôn(A) = 0; (0 N ( 1 s ) ) = 1 ( 0 N < Â ) ) & ] ( Q N ( A ) ). свойств SPACE-едипицы и SPACE-нуля

Л \ - 1'»,

A & îs = A ;

A V A = 1S ;

A & A = Os.

Qn(A) v hn,(B)=HN(B ) v Qn ( A ).

On < A » л !s - Q N ( Л ) ; On ( A ) v Q N í A ) = ON (A) vO^= Qn (A); A Os = 0 ; A - v Оь = A

6. свойство ko m mua гпп1ю ctji

• Qn ( A )&HN(B)=HN(B )&Qn (A ) ;

7. свойство дистрибутивности Qn ( A V В ) = Qn ( A ) v QN ( В ) ; Qn ( A & В ) = Qn ( A ) & QN ( В ) ;

Q N (A) v SN (B & C)=(Q N (A) v S n ( В )) & (Q N ( A ) v S N ( С )) ; Qn (A) & S n (B v С )= Q N (A ) & S n ( В ) v Q N (A ) & S N ( С ) ; Q N (A) v(S m (B ) & H к (C))=(Q n (A) v S m (В)) к (Q N (A) v H K(C)) ; Q n (A)&(S M(B)v Hk (С)) =Q N (A) &S M(B)v Q N ( A ) & H K ( С ) . s. свойства поглощения . ( Q n (A) & Q N (B))v Q n (b )= Q n ( в ) ( Q N l A) V Q N (B)) &Q N (B) = Q N ( В ) ( Q m (A) v Q n ( A ))&Q N (B)= Q n ( В ) ; N.n(A) = Wn(A); . 9. Законы ji: Моргана

M. Q к ( A & В ) = QN(Â)vQN(B) V ] Q N ( 1 s y ; ' ! Q N ( A X' B) =0 N ( Л ) A; Q N ■ В ) v Q N ( i & ) i (Q i I s ) / = > <. Q N 1 A i ) Л: 1 ( Q N ( A ) ) ;

] (0 N ( 0 s 1 ) = :

L.N(A) = RN(A); WN(NM,(A))=\Vn.m (A ) W.n(A) = Nn(A); R.f. ( A) = Ln (A).

Ом.( А) = 10 N (А) & О N (15); 1 (А) = О N ( А ] )).

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

Исследованы свойства коммутативности, ассоциативности, дистрибутивности, идемпотентности и определены правила взаимного преобразования элементарных функций Б - алгебр : сложения по модулю 2, импликации, стрелки Шеффера и Пирса. В частности, БРАСЕ-функция сложения по модулю 2 ( © ) имеет вид : *

ООц (А) © Нм (В)=<& (А)&Н м ( В ) у.рц ( А) & Н м ( В ) = = «Зм (А ) V Н м ( В ) ).&( СЫ ( А ) V Н м ( В )) , где с-, ] = {((^ ( )еНм(Ь'|] )),-..,м ( Ь^-))} = = ( ) & Н „ с Б^ ) V С}* ( а*,-, ) & Н м ) . Для данной функций справедливы следующие свойства :

1. А е А = 0 5 ; А © А = 1 А =А 0 1 Б ; С?» ( А © А ) * 1 5 ;

2. <2М ( А ) © ( А) = 0 5 ; 0,\ ( А ) = Ом ( А © 1 й );

3. СЫ ( А V В ) = ( А ) © ( В ) © ( А & В ) ;

4 0Ч: ( А А В ) = о- ( А е В ) е Ом ( А V В ) ;

5 (. А ) 14 --- А ; ( А 1?. О * ) •-= А ;

(-. Ох ( А V В ) - (А ) е Оц ( В ) Э ( А ) & (8) ;' .. 7. -<Эм ( А&( В © С)) = 0к(А)&0'м1 В © С).

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

выражений алгебры Буля, в эквивалентные выражения Б-алгебрьт. Для этого требуется выполнить позиционирование и размещение переменных, логических функций в метрическом пространстве Б-алгебры и преобразовать представления, логических функций в представления функции Б-плгсбрм логики. Определение [¡'.-ременных функций можно выполнить в метрическом пространстве . ¿-алгебры либо как ч^м.'нтпк сдпогс пс:?;сстьа-г.;'.г>\..с»г;а п„|,пи, .шии разишь набор переменных на группы и определи) ь каждую группу как множество-аргумент Б-фуикпии. В зависимости от способа метрического определения переменных сформулированы правила формирования представлений функций Б-алгебры из: функций алгебры логики.

Разработаны аналитический и графический методы минимизации функций Б-алгебры и модификация метода минимизации Квайна в приложении к функциям Б-алгебры. Это обеспечивает возможность оптимизации временной сложности алгоритмов '• массивных вычислений путем минимизации их аналитических описаний в базисе Б-алгебры. . :

Полученные теоретические и практические результаты в прикладном аспекте образуют алгебраическую основу методов проектирования и оптимизации массивно-параллельных алгоритмов для решения прикладных задач и методов структурно-функционального проектирования аппаратного обеспечения терзчивн-.--би штдч с.■.¡■их-онн.ьг-. О КМ Л СЫ'/ ЭВМ и систс/.

Методология формального синтеза алгоритмов в базисе Б-ал^ебры .для итеративно-битовых процессорных пространств исйользована для конструирования массивно-параллельного алгоритма поиска максимального числа в массиве из N положительных целых М-разрядных чисел. Временная сложность реализаци»: полученного алгоритма при реализации в итеративно-битовом процессорном пространстве составила значение БТ1МЕ ( 4 М N Р / Б 2 ).

В четвертой главе « Алгебраический синтез и оптимизация массивно-параллельных алгоритмов нечисленной обработки изображений для итеративно-битовых вычислительных пространств» на примере задач предварительной обработки цифровых изображений разрабатывается методологии алгебраического синтеза и временной оптимизации массивно-параллельных алгоритмов в базисе Б- алгебры для итеративно-битовых гиперпроцессорных пространств синхронных ОКМЦ ЭВМ и систем.

Реальное А изображение представляется массивом цифровых кодов его волновых характеристик М(А) — { а j; 1 =1,2,...,п ; j = 1,2,...,т }, ( п х ш ) - размерность дискретизирующей решетки. Подмножество

Р( аи ) = {ам>з ,ан.и,ам_, ,аи+'1 } е М (А) • . является окрестностью фон-Неймана, а .

С (аи) ау_1 ,а^+1,а^и.ьаМг^1,ан-11Н,аИ1,+1} 6 М(А) -

окрестностью Мура. Данные типы окрестностей использованы при синтезе аналитических г.редставлений алгоритмов обработки изображений в базисе операции Б-алгебры. В качестве

иллюстрации использованного подхода ниже приводится ряд. таких аналитических описаний алгоритмов.

Процедура порогового преобразования цифровых многоуровневых

гпопрлжегпгп

1. М ^ -1 (I +1) = М к * 1 ( I ) V м к ^ 1( I ) ;

Т'"1 1 (I +П = Ч I) V Тк+ Ч I ) • :. М - ( I I ^МК-'П) М Ак ( 0 & Дк ( I IV А к( I ) Л: Д *( 1 У) ;

Тк( I +1)=тк+4 I )& АЧ I )& дк( г МК+Ч 1 I ).

} \.<| К -1 1 ММ») ^.(ДК-1/ | А К-) Д « К-1/ * ) } '

ук-1 (1+1)=тк( [ ) &дк-1 ц ) & дк-!( [ ) v М" (1 )& Тк( I ) . М к (4+1) =.М к"' (I (А*"2 Й) & Д К"2Й) V Ак"2а)& Л к"20)) ;

М^ЧО&Т^Ч I ) .

М°(1+1)=.М1(1)Л(А°й)& с )У А°( I) & д0(О); Т°(1-г1>=Т!(Г)&А'°(1 Л: л 5 (т) V Мгч г > &ТЧ I ) .

С 1 ( ! +1) = М 0 ( I ) V Г1' ( ! ) .

м кн(1-1)=м Ч i ) v ( г ) ;

ТК+ 4 1) = ТК+ Ч I ) V Т>-+ 1 (I) . МК(Т-И)=МК+1 (Ак£д*У Ак&..5К); Т к < I +1)=ТК"Ч1)& А к (I )& Д кй)у Мк+1(0 )..

М ,;->(И-!)=М Ч I ) (Ак"] (О&ДК-ЧОУ А к-'(1 ).&, дк-' (0) ;

т1-1и+1)=т,;(0& Ак-1(г)&дк-Ч1)у м*(1)&тчо.

М к"' (А к"2Л.Д*-:\' А к"2 & Л"2) ; Ак-2(0& дк-2(0 V мк-ЧО&Т^Ч г) .

'.: - -1: --.'.¡м;1, ЛЧЛ '■' < : I ¿ч- л( { I \ А Ч I ! л

тп у £ ~ л/. » .. т о» . ч,. " • г

К-1 К-2

К+3.

Множества М, Т , С формируются при выполнении данной процедуры, Я - множество-указатель элементов изображения относительно заданного порога. Процедура логической фильтрации изолированных точек А(1+1) = А([)&(ЯцА(1) )уЬ,(А(1) )УЫ((А(1))У

V \У,(А(0 >УЯ,(>У',(А(1.)))-УЬ ,(А(1) ))У vN|(Ll(A(t)))vW,(R1(A(tШ). Процедура логической фильтрации штриховых линий .

; А (1+1 )=А ( I ) & ( Я !(А( I)) V Ь !(А( I))') & (Ы ,(А( I »V ,(А( 1)))& ,& (Я,(А( I )))У I.,(Ы ,(А( I ))) & (Ы !(Ь!(А( I )))у W,( Я |( А( I))).' Процедура логичекой фильтрации разрывов и пустот

А( 1+1) = А( I) V Я, (А( I ))& Ь, (А( I)) V Ы, (А( I ))&\У, (А( I)) V V (ЯК\У,(А(1 )))&(!,,(Ы, (А( I )))У 1(А( I) ))&(Ы , (Я ,(А( I))).

Связное подмножество : Б = { в 1 : е X } информационных элементов множества М (А ) называется утонченным изображением М (А ) ( скелетом изображения ), если 8 является связным подмножеством и каждый элемент в у е Б является элементом элементарной линии. ] Процедура утончения бинарного изображения

1. С (1+1) = Я,(15) V N,(15);

2. АЧ I +1) - А'( I )&(Ц( А( I )) V W1( А( I)) V Я[(А( I ))у

V К'|(Л (I)) V С( I) ).

3. А2"( I +1) = А'( I) &(Ь!( А'( 1))У№|( А1(1))УЯ1(А'(1))У

V N. ( А '(I) ) УС( I)).

к+1 Ак+1( г+1 ) = АК( I) & ( Ь]( Ак( 1) ) V \У|( Ак( I )) V •V Я,( А к (I)) V N 1 (Ак( I) )УС (I )).

Процедура расширения бинарных изображений

А(1+1) =А(1) V (Я,(А(Г)))У ( Ь х ( А( I) ))у( Ы, (А(1)))у V ( XV , ( А( г))) V (.Я , (И , ( А( I))) V ( Ь, ( N , ( А(Ч ))) V

V (Я , ^ , (А (I))) У(Ь , ( А( I ) )) ,

Связное подмножество в = { g ; ^ е X } информационных элементов множества М (А ) называется элементарной линией изображения М (А ), если каждый элемент в находится в'отношении'непосредственной связности хотя бы с-одним фоновым ' элементом из М (А ) и отношении непосредственной связности ( с* ) с элементами из Г. . причем: линия называется горизонтальной, если § ^ ® б ¡+! ^ и 2 м ® о ¡-1 • ' линия называется вертикальной, если £ 0 § ^ ^ и е ^ ® § ^ .¡, ; линия называется право-диагональной, если § ^ <8>-ё 1 -1 и ё ® ё м о+-ь ; линия называется лево-диагональной, если Б^ ® б |-1 .1 ,и§ ^ ® б ¡+1^ + 1-Процедуры разложения изображений на единичные линии

а) процедура выделения элементарных горизонтальных линий :

0(1+1) = А (I ) & ( Я! ( А( I) ) V Ь ! ( А (I )) ) ;

б) процедура выделения элементарных вертикальных линий :

V (1+1 ) = А (I) & ( N ! ( А( I) ) V \¥ ! ( А (I )) ) ;

в) процедура выделения элементарных право-диагональных, линий : ) = АО)&-(N,( мАОПу у>у', (ц,(А(И )));

г) процедура выделения элементарных лево-диагональных линий: Б1- (I +1) = А (*') & ( N ! ( Я, (А( г) )) у № , ( ц (А( I) )) ).

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

1.узел начата горизонтальной линии -

и »•' ( I -ч ).= А ( I ) & Я , ( 1А < I ) )■•& Ь , ( А ( I ) ).

2. узел начала вертикальной линии -

Ъ "М!+1)^А(1) & \\' , (1ч ( 1 )) Л; ( N ,( Л ( 1)1.

3. узел начала прачо-дпагон;->л:»иой лт»:»: -

г г' ¡1 - а (' ; ) А; к ( ! V,' , ('А ( I 'ц ; л:{ к ц -. -А ¡' ; г.!.

4.|узел начала лево-диагональной линии -

р «ад ( 1+1) = а ( t ) ¿с ( N , ( R, ( а ( t ))) & L , ( W , (1а ( t )) ).

5. рел окончания горизонтальной линии -

р t+l) = А ( t ) & R1 ( А ( t » & l 1 (1а ( t )). .6. узел окончания вертикальной линии -

UKB(t+I)=A(t)& \u 1 ( А ( t )) ) '& N 1 (Та ( t )).

7. узел окончания право-диагональной линии -

|U (t+l)- А ( t )& W , ( R, ( A ( t )) ) & L , ( N |(1A ( t )) ). .

8. узел окончания лево-диагональной линии -

U ( t+l) = А ( t ) & W , ( L, ( A ( t ))) ) & R , ( N , (TA ( t )) ).

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

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

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

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

34

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

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

Получены новые технические решения.

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

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

Новизна перечисленных технических решений подтверждена авторскими свидетельствами и патентами на изобретения и заключается в использовании идеологии ГШС-процессоров, применении методологии битовых ¿тссивных вычислений, новых способах реализации процессорных элементов и структур.

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

перепрограммирования.

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

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

Основные результаты работы

В диссертационной „ работе решена крупная научно-техническая проблема - разработана теория и методы реализации массивных вычислений в итеративно-битовых СБИС-структурах.

1 Разработаны теоретические основы массивных сычислений, включающие способы организации вычислений и правила аналитической оценки сложности их реализации в итеративно-битовых СБИС-структурах различной размерности, что позволяет : при проектировании алгоритмов и их программных решизаций для существующих ЭВМ и систем класса ОКМД обеспечить их временную оптимизацию за счет выбора способа организации вычислений при известных параметрах вычислительного пространства ; при создании нового проекта ЭВМ или системы класса ОКМД на уровне архитектурного проектирования определить оптимальные относительно временной и пространственной сложности способы организации

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

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

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

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

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

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

5. Предложены методология проектирования и способы

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

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

1. Knyaz'kov V.S. An Assotiative Cellular VLSI Processor for Paralled Processing by Raster Image: the concept and Applied Computations // Pattern Recognition and Image Analysis, Vol.6, № 2, .1996, pp.401-402.

2. Knyaz'kov V.S., Volchenskaya T.V. Maximally Parallel Algorithms for Raster Image Processing by Cellular VLSI Processors // Pattern Recognition and Image Analysis, Vol.6, № 2, 1996, pp.403-404.

3. V.S.KnyazAkov, V.V.Moshechkov. A Homogéneos Computational Environment for Raster.//Pattern Recognition and Image .Analysis vol.6 N 2. 1996, pp.405.

4. Пат. 1573456 G06 F 7/00 Ячейка однородной структуры. / Князьков B.C. Волченская Т.В. , октябрь 1993 г.

5. Патент ..№ 1663609, G06 F 7/00 Многофункциональная ячейка однородной структуры /Волченская Т.В., Князьков B.C. и др., октябрь 1993 г.

6. A.C. ' 1314332 G06F7/00 Коммутатор. / Князьков B.C.) .. Волченская Т.В., БИ 20, 1987 г.

7. A.C. 1335975 G06F7/0Û.. Ячейка однородной структуры./ Князьков B.C. и др., БИ № 33, 1987 г.

8. A.C. 1363232 G06F15/20 Устройство для перебора сочетании размешен!»! и перестановок. / Князьков B.C., Солчслская. Т.В. БИ № 48, 1987 г. •

9. А С. ! 363239 GQ6FIJ/2G Устройство для генерирования перестановок и сочетаний./ Князьков B.C., и др.,БИ 3Vï 48, 1987г.

10.А.С. 1372322 G06F7/00. Ячейка однородной структуры./ Князьков B.C. и др., БИ № 5, 1988 г.

Д1.А.С. 1411729 G06F 7/00 Ячейка, трассирующей сети./ Князьков B.C. и др.. БИ Ш 27, 1988 г.

12.А.С. 1411789 G06K 9/00. Логическая ячейка для распознающей матрицы. /' Князьков B.C. и др., БИ № 27. 1988 г.

13.А.С. 1418695 G06F7/00. Ячейка однородной структуры./ Князьков B.C. и др., БИ № 31, 1988 г.

14.А.С. 1501035 G06F7/Ö0. Ячейка однородной структуры./ Князьков B.C. и др., БИ № 30, 1989 г. •

15. A.C. 1513471 G06F15/20. Ячейка однородной вычислительной среды./ Князьков B.C. и др., БИ № 37, 1989 г.

16.А.С. ' 1573456 G06F7/00. Ячейка однородной структуры / Князьков B.C., Волченская Т.В.,БИ № 23, 1990 г.

17.А.С. 1663609 G06F7/Û0. Многофункциональная ячсПка однооояной структур!.)./ Князьков B.C. и др., БИ jNfe 5, ¡99!

18.А.С. 1665368 G06F7/00. Многофункциональный логически;! модуль / Князьков B.C., Волченская Т.В.,БИ .Ni 27, 1991 г.

19}А.с. 1835549 G06F7/00. Логическая ячейка для распознающей матрицы. / Князьков B.C. и др. - Бюлл. изобр. N 31, 1993 г.

20.^.С. 947911 G06C19/00 Одноразрядное стековое ЗУ./ Князьков B.C., и др., БИ № 28, 1982 г.

21.Князьков В, С. Организация ассоциативных вычислительных структур и процессов логической обработки штриховых изображений. / Автореф. на соиск. уч. ст. канд. техн. наук.- Л.: ЛЭ^И, 1982,-16с.

22.Князьков B.C. , Волченская Т. В . Способы построения конвейерных вычислительных структур с управлением коммутации потоков данных. Деп. рук. , ВИНИТИ, N 5581В9Д от 31. 10.90, Минвуз РСФСР Пенза, П.ПИ, 1990, 10 с.

23.Князьков В. С. Аппаратное обеспечение конвейерных вычислительных систем. Пенза, 1992, -79с.

24.Князьков В. ' С. , Бикгашев Р. А. Параллельные вычислительные системы с ОКМД архитектурой. Пенза, РИО Пензенского политехнического ин - та, 1991, уч. пособие, 51 с.

25.Князьков В. С. , Волченская Т. В. Быстродействующие процессоры на базе однородных сред. // В кн.: Распараллеливание обработки информации : Тез. докл. VII Всесоюз. шк. семинара 914 окг. 1989 года, Львов; 1989, с. 24.

26. Князьков В. С. , Волченская Т. В. Интеллектуальный мультипроцессор для САПР ЭВА : концепция, принципы построения // САПР92. Новые информационные технологии в науке, образований и бизнесе : Тез. докл. Межд. конф. 4-13 мая, Гурзуф. - Воронеж, 1992.- С. 26-27.

27.Князьков В. С. , Волченская Т. В. Классификация средств обработки данных. . Деп. рук. , ВИНИТИ, N 8873В88 от 21. 12. 88, Минвуз РСФСР Пенза, Пензенский политехнический ин-т, 19S8, 24с. .

28.Князьков В. С. , Волченская, Т. В. Конвейерная вычислительная среда с программируемой структурой//В кн.: Распределенная обработка информации : /Тез. докл. Всесоюзного семинара Распределенная обработка информации, август, 19У1, .Горно - Алтайск. Новосибирск, 1991,13 с.

29.Князьков B.C. Ассоциативный СБИС-процессор массивно-клеточных вычислений : архитектура и прикладные алгоритмы.// Известия ТРТУ №3,1996,С.121-122.

30.Князьков B.C. Временная и пространственная сложност! , реализации клеточно-массивных вычислений в итеративно-битовых вычислительных средах с многомерной организацией.//Материалы 2-ой Междунар. н.т. конф. "Новые информационные технологии и системы",ч.1, 1996, Пенза, С. 106-108.

31.Князьков B.C. Общая оценка" сложности реализации

массивно-клеточных вычислений в итерационно-битовых вычислительных структурах с многомерной, организацией. //Известия ТРТУ, N 3, 1997, с.218.

32.Князьков B.C. Ассоциативно - клеточный СБИС - процессор параллельной обработки растровых изображений // Материя.™ Вееросс. Конф. «Распознавание образов и анализ изображен!,-:: иоьыс информационные технологии*.-Ульяновск, 1995 г. -C.113- 115.

3&.Князьков B.C. Ассоциативный СБИС - процессор массивно -кйеточных вычислений : архитектура и прикладные алгоритмы // ИЬвестия ТРТУ,№ 3, 1996 г., Таганрог: материалы Всероссийской научи, техн. конф. « Интеллектуальные САПР-95», сент. 1995 г., г. Геленджик.-Таганрог, 1996, С.121-122.

34. Князьков B.C. базовые схемы и сложность массивных вычислений в одномерных итеративно-битовых процессорных средах // Материалы Всеросс. научи, техн. конф. «Непрерывная и смежные логики в информатике, экономике и социологии» 3031 окт., 1997 г., г.Пенза.- Пенза, С.54-56.

35.Князьков B.C. Базовые, схемы и сложность размещения данных в двумерных итеративно-битовых процессорных средах при массивных параллельных вычислениях // Материалы Всеросс. научн. техн. конф. «Непрерывная и смежные логики в информатике, экономике и социологии» 30-31 окг., 1997 i., г.Пенза.- Пенза, С.60-62.

36.Князьков B.C. Базовые схемы и сложность размещения данных в одномерных итеративно-битовых процессорных средах при массивных параллельных вычислениях // Материалы Всеросс. научн. техн. конф. «Непрерывная и смежные логики в информатике, экономике и социологии» 30-31 окт., 1997 г., I.Пенза,- Пенза, С.56-58.

37. Князьков B.C. Временная и пространственная сложность реализации клеточно - массивных вычислений в итеративно-битовых вычислительных средах с многомерной организацией // Тез. докл. II Междунар. Научн. техн. конф. «Новые

информационные технологии н системы» 23-25 окт. 1996 г., г.Пенза.-Пенза, 1996, C.106-10S.

38.Князьков B.C. Лвумерные итеративно-битовые процессоры: временная и пространственная сложность последовательно-массивных итерационно-разрядных вычислении //Материалы 2 •

ои Между! :ар. и/т конф. "Новые информационные течнолскл. и сцасмы,4.1,1990, Пенза, C.lUb-109. ?9.}C!li3LI:OC B.C. П^йооиомомцни

комбинаюрной обработки данных: концепция и принципы технической реализации // Труды Международ, науч. техн. конф. "Непрерывнологические ц нейронные сети и модели". -Ульяновск, 1995 г. - С. 38-39.

40.Князьков B.C. Обработка многоуровневых представлений

символьно - графических изображений // Известия ЛЗТИ. »ь;п. 29i. 1981 г.,- Ленингр-и. С.29-33'.

-Я.Князьков B.C. Общая опенка сложности реализации массивно клеточных вычислений ь итерационно - битовых вычислительных структурах'- с многомерной организацией ,'. Материмы Всеросс. лаучн. техн. конф. «Интеллектуальные САПР-96» течат Вып.., Известия ТР7У..^З, ¡997 - Таганро;. ilK'7. С.2К-.

42.Князьков B.C. Одномерные итеративно-битовые процессоры: опенки временной и ппостплигтие»»««.-'. • г""-;-.—

• Г.. л.. ■ ■ ■ —............ .. окт. Il'vt>

г.Мсчз:.:. - Пеня:. }°%.С.МJ-Mo.

4$. Князьков B.C. Организация и сложность массивно -конвейерных итерационно - разрядных вычислений в одномерных вычислительных структурах // Материалы Всеросс. научн. техн. конф. «Интеллектуальные САПР-96» темах. .Вып., Известия ТРТУ, №3, 1997 г., - Таганрог, 1997, C.I96.

44.Князьков B.C. .Лараллельные алгоритмы предварительной обработки бинарных изображений // в кн. «Вычислительные пррцессы и структуры»,ЛИАН, вып. 154., 1982г.- Ленинград,

С.134-138. :

\ - '

45.Князьков B.C. Сложность "массивно - параллельных

вычислений в двумерных итеративно-битовых средах // Материалы Всеросс. научн. техн. конф. «Непрерывная и смежные логики в информатике, экономике и социологии» 30-31 ■ окг., 1997 г., г.Пенза.- Пенза, С.58-60.

46.Князьков B.C., Волченская Т.В. Память с распределенной логикой для нечисленной обработки данных // Совершенствование устройств памяти ' информационных компьютерных и робототехнических систем: тез. докл. Всесоюзн. научн. техн. конф. 23-25 нояб. 1988 г., г. Одесса.-М., Радио, и связь, 1988 г. , С.23-24.

47.Князьков B.C., Волченская Т.В. Классификация средств обработки данных / Пензенский ПИ.-Минвуз РСФСР, Пенза,1988,- 24с,- /Рук. деп. в ВИНИТИ №8873-"В88 от 21.12.1988/. . •

48.Князьков B.C., Бикташев P.A. Архитектура параллельных вычислительных систем.-Пенза, 1993.-с..166.

49.Князьков B.C., Волченская Т.В. Архитектура комбинаторно-векторных процессоров для решения конструкторско-технологических задач в САПР: Тез. докл. В сб. "Новые информационные технологии в науке, образовании и бизнесе".-Воронеж, 1993. С.36. ..

50.Князьков B.C., Волченская Т.В. Быстродействующие процессоры на базе однородных сред // Распараллеливание обработки информации: тез. докл.VII Всесрюзн. шк.-семинара 914 окт. 1989 г., гЛьвов.- Львов,1989.- С.116.

51.Князьков B.C., Волченская Т.В. Комбинаторно-векторные процессоры для САПР: архитектура и прикладные алгоритмы: •Тез. докл. в сб. тез. докл. Междунар. научн.конф."Технологии и системы сбора, обработки и представления информации".-Рязань.-1993.-С.11-12.

52.Князьков B.C., Волченская Т.В. Комбинаторно-векторные процессоры: архитектура и прикладные алгоритмы // Интеллектуальные САПР : межведомст. темат. научн. сб. -выпуск 4 , г. Таганрог. - 1994 г., с . 131-132.

53.Князьков B.C., Волченская Т.В. Конвейерная вычислительная среда с программируемой структурой // Распределенная обработка информации: тез. докл. Всесоюзн. семинара 19-25 авг, 1991 г., г.Горно-Алтайск.- Новосибирск,1991.- С.13.

54.Князьков B.C., Волченская Т.В. Конвейерная обработка данных в структурах с потоковым управлением // Распределенная обработка информации: тез. докл. Ill регионального семинара 1-9 июля 1989г., г.Улан-Удэ.-Новосибирск, 19S9.-C.i3.

5?.Князьков B.C., Волченская Т.В. Матричный спецпроцессор artp САПР с функционально - распределенной обработкой данных // Опыт разработки и применения приборно-тефюлогических САПР: тез. докл. Всесоюзн. шк.-семцнара 23-28 февр. 1991 г., г.Льво1).- Львов, 1991.- С. 40-41.

56.Князьков B.C., Вгиченская Т.В. Однородная вычислительная среда для обработки видеоданных ,// Планирование и автоматизация эксперимента в научных исследованиях: тез. докл. IX;Всесоюзн. конф. 25-27 сент. 1989 г., г. Москва.- М., 1989.-С.1'09. •

57.Князьков B.C., Волченская Т.В. Организация вычислительных структур для выполнения квазиматричных преобразований

. булевых матриц // В кн.»Проектирование и применение , микропроцессорных систем управления».-М.,МИЭТ, 1984 г, С. 17-22.

58.Князьков B.C., Волченская Т.В. Основные типы параллельных архитектур средств обработки данных // Распараллеливание обработки информации: тез. докл.УН Всесоюзн. шк.-семинара 914 окт. 1989 г., г.Львов.- Львов, 1989,- С.24.

59.Князьков В. С. Вычислительная сложность и базовые схемы массивно-разрядных вычислений в многомерных пшерпронессорпых средах //IT+SE 98. Новые информационные ¡ечподопш в науке, образовании, телекоммуникации и бизнесе: Тез. докл. Межд. конф. 15-24 мая «Новые информационные технологии в науке, образовании, телекоммуникации и бизнесе», Украина,Крым, г. Ялта- Гурзуф, 1998.- С. 109-112.

60.Князьков B.C., Волченская Т.В. Предельно-параллельная СБИС - матрица для обработки бинарных цифровых изображений. // Труды Международ, науч. техн. конф-"Непрерывнологические и нейронные сети и модели". i .Ульяновск. 1995 г. -С. 36-37.

6] Князьков В С , Волченская Т.В. Предельно-параллельные алгоритмы обработки растровых гпображеппГ: длл ллсычныч СЬИС прол'юоро» // Материалы -Всеросс. Конф.

«Распознавание образов и анализ изобра жениишовьи-информационные технологии».- г.Ульяновск J 995 г.- С.116- ¡18.

62.Князьков B.C., Волченская Т.В. Спепиааизированный' процессор обработки цифровых изображений:тёз. докл. Всесоюзн. семинара 5-7 септ. 1989 ь, г.Москва.-М., 19S9.-C.66.

63.Князьков B.C., Волченская Т.В. Способы построения конвейерных вычислительных структур с управлением коммутацией потоков данных / Пензенский ПИ.-Минвуз РСФСР, Пенза.1990,- Юс,- /Рук. деп. в ВИНИТИ №5581-В90 от 31.10 1990/

64.Князьков B.C.. Организация и сложность массивно-конвейерных итерационно-разрядных вычислений в одномерных вычислительных структурах.//Известия ТРТУ, N 3,1997,-с. 1997.

о

'О -

I Президиум ВАК России

(рег.теттис от

присуллл ученую ето::ленъ ДСлчТО.

1..... Л"..........................'........................•

; V .

АК ?о-

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕНЫЙ УНИВЕРСИТЕТ

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

КНЯЗЬКОВ

Владимир Сергеевич

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

Специальность - 05.13.13. -«Вычислительные машины, комплексы, системы и сети» Специальность - 05.13.05. -«Элементы и устройства вычислительной техники и

систем управления»

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

Пенза 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ............................................................................................................................................6

ГЛАВА 1.

МАССИВНЫЕ ВЫЧИСЛЕНИЯ : СОВРЕМЕННЫЕ МЕТОДЫ РЕАЛИЗАЦИИ, ОСОБЕННОСТИ ПРИКЛАДНЫХ ЗАДАЧ И ПУТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ

1.1. Современные подходы и способы построения ЭВМ и систем

для массивных вычислений............................................................................19

1.2. Способы организации и особенности архитектуры ЭВМ и систем

для массивных вычислений............................................................................27

1.3. Классы задач и особенности их реализации.................................................38

1.4. Основные проблемы, направления исследований и выводы........................43

ГЛАВА 2.

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

2.1. Основные понятия и определения...................................................................47

2.2. Сложность и особенности размещения данных в итеративно-битовых процессорных структурах при массивных вычислениях..............................53

2.2.1. Векторные схемы размещения данных...........................................................54

2.2.2. Матричные схемы размещения данных..........................................................59

2.3. Способы организации и сложность массивных вычислений

в одномерных итеративно-битовых процессорных структурах......................68

2.3.1. Массивно-последовательные разрядно-параллельные вычисления.............69

2.3.2. Массивно-последовательные разрядно-последовательные

вычисления........................................................................................................75

2.3.3. Массивно-последовательные разрядно-параллельные конвейерные вычисления........................................................................................................81

2.3.4. Массивно-последовательные разрядно-последовательные ковейерные вычисления.........................................................................................................85

2.4. Способы организации и сложность массивных вычислений в

двумерных итеративно-битовых процессорных структурах..........................91

2.4.1. Массивно-последовательные разрядно-последовательные ортогонально-конвейерные вычисления..........................................................92

2.4.2. Массивно-последовательные разрядно-параллельные ортогонально-конвейерные вычисления.................................................................................96

2.4.3. Массивно-последовательные ортогонально-конвейерные диагональные вычисления...............................................................................104

2.4.4. Массивно-параллельные разрядно-последовательные

вычисления........................................................................................................108

2.4.5. Массивно-параллельные разрядно-параллельные вычисления...................113

2.4.6. Массивно-параллельные разрядно-параллельные

диагональные вычисления............................................................................120

2.4.7. Массивно-параллельные разрядно-последовательные

диагональные вычисления...............................................................................122

2.4.8. Массивно-параллельные диагонально-конвейерные вычисления...............123

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

2.6. Основные результаты и выводы......................................................................133

ГЛАВА 3.

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

3.1. Основные положения и определения..........................................................137

3.2. Основные свойства элементарных функций S-алгебры.............................141

3.3. Представления S -функций............................................................................151

3.3.1. Табличное представление функций S -алгебры логики...............................151

3.3.2. Аналитическое представление функций S -алгебры логики.......................152

3.4. Методы преобразования S - функций..........................................................156

3.4.1. Преобразование аналитических представлений функций Булевой алгебры в представления S-функций...........................................................156

3.4.2. Минимизация функций S-алгебры логики..................................................161

3.5. Алгебраический метод синтеза алгоритмов массивных вычислений........168

3.6. Основные результаты и выводы..................................................................174

ГЛАВА 4.

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

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

4.2. Методы и алгебраический синтез массивных алгоритмов фильтрации цифровых изображений в базисе операций S-алгебры........182

4.2.1. Синтез алгоритмов пороговой фильтрации цифровых изображений........185

4.2.2. Синтез алгоритмов логической фильтрации искажений в бинарных изображениях................................................................................191

4.3. Методы и алгебраический синтез массивных алгоритмов структурных преобразований бинарных изображений в базисе операций S-алгебры........................................................................................................198

4.4. Методы и алгебраический синтез массивных алгоритмов препарирования бинарных изображений в базисе операций S-алгебры.............................................................................................................203

4.5. Методы и алгебраический синтез алгоритмов цифровой обработки многоуровневых изображений в базисе операций

S-алгебры......................................................................................................211

4.5.1. Синтез алгоритмов усредненной фильтрации многоуровневых изображений...................................................................................................212

4.5.2. Синтез алгоритмов расширения многоуровневых изображений...............216

4.5.3. Синтез алгоритмов выделения структурных элементов многоуровневых изображений...................................................................................................221

4.6. Основные результаты и выводы.................................................................225

ГЛАВА 5.

ИТЕРАТИВНО-БИТОВЫЕ СБИС-ПРОЦЕССОРЫ МАССИВНЫХ ВЫЧИСЛЕНИЙ : МАТЕМАТИЧЕСКИЕ ОСНОВЫ И СПОСОБЫ ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ......................228

5.1. Итеративно-битовые СБИС-процессоры цифровой обработки, изображений.

...........................................................................................................231

5.2. Итеративно-битовые СБИС-процессоры логических вычислений.............252

5.3. Итеративно-битовые СБИС-процессоры преобразования структур

данных...................................................................................................................280

5.4. Итеративно-битовые процессоры арифметической обработки данных......301

5.5. Основные результаты и выводы...................................................................329

ЗАКЛЮЧЕНИЕ.......................................................................................................................................331

СПИСОК ЛИТЕРАТУРЫ...................................................................................................340

ПРИЛОЖЕНИЯ.......................................................................................................................................365

ВВЕДЕНИЕ

Сегодня во всех сферах деятельности человека идет интенсивное внедрение компьютерных технологий автоматизированной обработки разнообразной информации. Особенностью настоящего этапа информационной революции является несоответствие технико-экономических характеристик действующего парка ЭВМ и систем современным требованиям пользователей к информационно-вычислительным ресурсам. В связи с этим актуальна задача создания нового поколения высокопроизводительных ЭВМ и систем как индивидуального, так и общего пользования с приемлемыми технико-экономическими показателями. Данное направление работ сегодня относится к стратегическим направлениям научно-технической политики ведущих стран мира и интенсивно развивается ведущими производителями компьютерной техники. В данном классе систем активизированы исследовательские и опытно-конструкторские работы в ведущих научных центрах и корпорациях: Стэндфордском, Калифорнийском, Колумбийском университетах, Массачусетском технологическом институте, корпорациях TRASTECH ( Англия ), TELMAT ( Франция ), SUN ( США ), NEC (Япония).

Динамика развития рынка информационно-вычислительных услуг показывает, что уже сегодня более чем 50% его объема относится к задачам, при решении которых требуется пространственно-инвариантная обработка крупных массивов высокоструктурированных данных. По технико-экономическим показателям такие задачи наиболее эффективно решаются в классе ОКМД ЭВМ и систем. Сфера применения ОКМД ЭВМ и систем уже сегодня весьма обширна и включает такие области, как: геология; сельское и лесное хозяйство; метеорология; гидрология и океанография; картография; экология; биомедицинские приложения;

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

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

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

Работы в области ЭВМ и систем класса ОКМД проводятся с начала 60-х годов как отечественными, так и зарубежными специалистами. Значительный вклад в развитие этой области вычислительной техники внесли работы научных школ под руководством Балашова Е.П., Брика В.А., Барского В.А., Вальковского В.А., Виленкина С.Я., Варшавского В.И., Глушкова В.М.„ Головкина Б.А., Головко В.А., Грицык В.В., Евреинова Э.В., Карцева М.А. , Котова В.Е., Каляева A.B., Левина В.К., Марчука Г.И., Медведева И.Л., Прангвишвили И.В., Пузанкова Д.В., Смолова В.Б., Самофалова К.Г., Хетагурова Я.А., Adams S., Brown N.G., Broomhead D.S., Delves L.M., Hard T.G., Hant C.D., Lee C.G., Manuel T., Fuller S.H. , Rohrbacher D.L., Rosenfeld A., Stephenson M., Slotnick D.L., Shooman W., Thurber K.J. и многих других. Несмотря на достаточно длинный период исследований в области математического и аппаратного обеспечения ЭВМ и систем класса ОКМД целый ряд вопросов не нашли своего решения и до настоящего времени. Это связано с тем, что ранее разрабатываемые методы вычислений и способы их технической реализации прежде всего ориентировались на особенности и ограничения существующей микроэлектронной базы и практически реализуемые типы аппаратных пространств. Соответственно неисследованными остались те из проблем, решение которых в практическом аспекте ранее было невозможным. В связи с этим актуальны как теоретические, так и инженерно-технические проблемы эффективной организации новых поколений ЭВМ и систем класса ОКМД, ориентированные на базис современных СБИС-технологий. Анализ показывает,

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

Цель диссертационной работы состоит в разработке теории и методов реализации массивных вычислений в итеративно-битовых СБИС-структурах для ЭВМ и систем класса ОКМД. Для достижения поставленной цели решаются следующие задачи.

1. Исследование особенностей, способов решения прикладных задач, методов организации вычислений, современных концепций и способов построения платформ ЭВМ и систем класса ОКМД.

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

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

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

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

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

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

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

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

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

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

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

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

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

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