Введение к работе
Актуальность темы. Особенностью настоящего этапа
нформацнонной революции является необходимость решения
а практике широкого круга задач с параллелизмом объектов.
анный класс вычислений характерен для таких областей, как :
:ология, сельское и лесное хозяйство, метеорология, гидрология
океанография, картография, биомедицинские приложения,
эиминалистика, промышленно-технические приложения
ггоматизация проектирования, компьютерная фотография,
*
ультипликация и т.д.
Исследование' и проектирование ЭВМ и систем для :шения задач в перечисленных областях проводятся как у нас в
ране, так и за рубежом начиная с 60-х годов. Однако, парк ких ЭВМ и систем по технико-экономическим причинам ироко не использовался. Сегодня задача создания технически зфектнвных и рентабельных СБИС-ЭВМ и систем для решения дач с параллелизмом объектов определена в ведущих странах іра в качестве приоритетной научно-технической проблемы. іализ известных решений в этой области, опыта, юектирования и эксплуатации таких ЭВМ и систем, зультаты исследовательских и опытно-конструкторских работ называют, что использование методологии массивных битовых [числений позволяет наиболее полно учесть особенности временных технологий изготовления СБИС и соответственно іфективно реализовать процессорную платформу, обеспечить спараллеливание вычислений до битового уровня, упростить шепие проблемы межсистемной совместимости. Методология
таких вычислений эффективно реализуема в ЭВМ и системах,
процессорное пространство которых концептуально
организовано в виде итеративно-битовых процессорных структур и сред. Однако, до настоящего времени теоретические положения и инженерно-технические методы реализации таких вычислений в полном объеме не разработаны. 8 связи с этим как в практическом, так и теоретическом аспектах актуальна задача исследования и разработки соответствующих разделов современной дискретной математики, теории формальных языков, алгоритмов и программ, теории цифровых автоматов, if опии вычислительных систем и структур.
Цель диссертационной работы состоит в разработке теории и методов реализации массивных вычислений в итеративно-битовых СБИС-структурах для ЭВМ и систем класса ОКМД.
Для достижения поставленной цели решаются следующие задачи.
-
Исследование особенностей, способов решения прикладных задач, методов организации вычислений, современных концепций и способов построения платформ ЭВМ и систем класса ОКМД.
-
Исследование. и разработка положений теории организации и теории сложности массивных вычислений в итеративно-битовых СБИС-структурах.
-
"Исследование и разработка алгебраических основ проектирования, методов формального синтеза, преобразования и оптимизации алгоритмов для массивных вычислений в .иератпвно-битовых СБИС-структурах.
і. Разработка методологии проектирования и способов технической реализации итеративно-битовых СБИС-структур тли арифметической и логической обработки, поиска и структурных преобразовании .данных, обработки цифровых изображении с использованием техники массивных вычислений и их псслелование.
Методы исследования основаны на использовании ^тематических аппаратов теории множеств, алгебр логики. ісчислення высказываний, теории формальных грамматик и івтоматов, теории графов, теории алгоритмов, теории опознавания образов.
Научная новизна результатов диссертационной работы в іедом заключается в разработке новых разделов теории праллельных вычислений и структур - теории и способов сал;п:шии массивных вычислений в итеративно-битовых ы-шс.мпеч.ных структурах :
:. Предложены и исследованы способы организации ычислений на основе массивных итерационно-разрядных и л сточных операций в итеративно-битовых вычислительных ;рукт\рах и подход для оценки их временной и ространс і венной сложности, позволяющие при реализации ігоритмов массивных вычислений осуществить обоснованный s.6op способа организации вычислительного процесса и ^или) (особа построения СБИС-етрукдуры.
2. Выведен набор аналитических выражений, позволяющих і уровне общего алгоритма решения задачи формально >щолнить оценку временной и пространственной сложности его
реализации в итеративно-битовых СБИОструктурах различной размерности при различных способах организации вычислений, что дает возможность при программной реализации алгоритма осуществить обоснованный выбор типа' ЭВМ или системы и определить оптимальные с точки зрения сложности способы организации вычислений, а при аппаратной реализации алгоритма - обоснованно выбрать способ организации вычислительного пространства.
-
Предложена и исследована алгебраическая система для описания процессов массивных вычислений на основе итерационно-разрядных и клеточных операций в итеративно-битовых вычислительных структурах, являющаяся основой методов формального синтеза и эквивалентных преобразований алгоритмов для массивных вычислений в итеративно-битовых СБИС-структурах.
-
В базисе введенной алгебраической системы определены правила эквивалентных преобразований графических и аналитических представлений алгоритмов массивных вычислений, что позволяет при проектировании, алгоритмов формально выполнять эквивалентные преобразования их аналитических и графических-форм описания.
5. В базисе введенной алгебраической системы предложены
аналитические и графические методы минимизации
аналитических выражений, позволяющие путем формальных
эквивалентных преобразований обеспечить формирование
аналитического описания алгоритма массивных вычислений с
минимальным количеством операций и соответственно
эбеспечить минимальную временную и пространственную сложность его реализации в СБИС-структуре.
-
Предложены правила формального преобразования зыраженнй алгебры логики Буля в выражения введеиноіі шгебраической . системы, что обеспечивает возможность зыполнить формальное преобразование алгебраического шисания. алгоритма в виде булевых выражений в эквивалентное шалитическое описание алгоритма для массивных' вычислений в ітеративно-битовьгх. СБИС-структурах. "
-
Предложена методология синтеза алгоритмов в базисе іведенной. алгебраической ; системы.* и синтезированы іптимальньїе по вычислительной сложности параллельные лгоритмы базовых процедур . предварительной обработки :ифровых изображений, что обеспечивает возможность рограммной реализации алгоритмов с минимальной временной ложностью и возможность формального синтеза СБИС-груктур для их аппаратной реализации.
8. Предложены и исследованы способы технической
еализации итеративно-битовых СБИС-структур-для выполнения
ассивных итерационно-разрядных логических и
зифметических операций, операций структурных
реобразований и поиска данных, операций предварительной
Зработки цифровых изображений,, что позволяет сделать
Зоснованный выбор способа технической . реализации
Іпаратного обеспечения СБИС-ЭВМ или системы
ютветствующей проблемной ориентации.
Практическая ценность работы заключается в. разработке
положений теории и методов реализации массивных
вычислений и СБИС-структур для ЭВМ и систем класса ОКМД. В комплексе полученные результаты обеспечивают возможность формализовать процесс проектирования алгоритмов и структур для массивных вычислений, выбрать оптимальные с точки зрения сложности вычислении объем и разрядность данных, способ организации вычислений, способ технической реализации СБИС-структуры.
Реализация и внедрение. Диссертация является
теоретическим обобщением ряда научно-исследовательских
работ, выполненных автором в Пензенском государственном
университете в соответствии с Координационным планом вузов
в области вычислительной техники. Основные практические и
теоретические результаты получены автором при выполнении
НИР «Исследование и разработка аппаратных средств поддержки
математического обеспечения -ВС ' для решения задач
конструкторского проектирования СВТ» в рамках
правительственной программы «Единая система автоматизации
проектирования электронной вычислительной техники»,
фундаментальной НИР «Разработка теории и исследование
способов реализации параллельных ' процессоров логико-
комбинаторных вычислений» в рамках заказа Минвуза РФ.
Результаты работы в виде моделей, алгоритмов, программных и
аппаратных модулей внедрены и используются в Пензенском
производственном- объединении электронно-вычислительной
'схчпки, НИИ -вычислительной техники (і .Пенза).
Государственном научно-производственном предприятии
"Рубин* (г.Пенза). По результатам исследований предложены
іе.хнпческие решения, защищенные 17 ангорскими
евнлеіедьсгвачи на изобрегенпя и патентами РФ. Разрабокшные
. н диссертационной работе теоретические положения и
пн.кенерно-юхшг'.гскнс методики введены в учебную программу
подготовки студентов по специальности 22.01.00. «ЭВМ,
комплексы, системы и сети» в Пензенском технологическом
институте по кафедре «Вычислительные системы ,и машины»,
Пензенском государственном университете по кафедре
«Вычислительная техника»' и используются на лекционных и практических занятиях, при курсовом и дипломном проектировании.
ЛіфЛчаїшя рабои^. Основные результаты диссертационной работ"].: кжладывллпсь и обсуждались на следующих симпозиумах, семинарах и научно-технических конференциях : 1-ої: Мс.кллнар. научно-практ. конф.«САЛР СВТ'89.»,17-2! апр. 1989г..г. Лепишрад ; М^ждунар. Кош}). «Новые информационные технологии в науке, образовании и бизнесе», Украина, г. Гурзуф, -І-І.- м.н; !li'J2 г..1993г., 1997г. : Междунар. п/т комф.^Техпо.мч ,у\ и системы сбора, обработки и представления информации», г.Рязань .15-18 сентября 1993 г. : Межлународ. науч. техн. конф. ": L'i'.v;"»'м.ц.і-лопіческме и нейронные сет;: и мг-к..;;і". !'''|С : . ^ rfii>/Uiuuei.., 2.-ji,i л I jyiv-iy нар. її/1 конф. xioiibw нткрормацн^''^::-'^ і"е 'по.іоі in! п сис;емы".1996. Пенза : Всесоюзд. спмно муч.' "Проблемы цифрового кодирования и преобразования изображений".18-20 сент. 1980г., г. Тбилиси ; ЇІІ Всесоюзн. шк.
по оптической обработке информации.,11-20 мая 1980г.,-г. Рига; Всесоюзн. конф. " Автоматизированные системы обработки изображений", 9-11 июня 1981г., г. Москва; Регион, конф «Обработка изображений и дистанционные исследования», 1-3 апр.1981г., г. Новосибирск ; Всесоюзн. совещание-семинар «Технические и прикладные вопросы разработки, внедрения и эксплуатации САПР радиоэлектронной аппаратуры»,3-8 сент.1984г.,г.Одесса; Всесоюзнной. научн. техн. конф. «Микропроцессорные системы», г. Челябинск, 1984г. ; Всесоюзн. научн. техн. конф. «Совершенствование устройств памяти информационных компьютерных и робототехнических систем». 23-25 нояб. 1988г., г. Одесса ; IV Всесоюзн. научн. техн. конф. «Системы баз данных и знаний» ,21-23 ноябр. 1989г., г.Калинин, 1989.- С.20-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г., г. Львов.
НА ЗАЩИТУ выносятся новые теоретические и инженерно-технические положения,, в комплексе составляющие решение крупной научно-технической проблемы - создание теории и методов реализации массивных вычислении г> итеративно-битовых СБИС-структурах для ЭВМ и систем класса ОКМД.
і Теоретические основы массивных вычислений в итеративно-битовых СБИС-структурах, включающие способы организации вычислений на базе массивных итерационно-разрядных и клеточных операций и правила аналитической оценки сложности их реализации в итеративно-битовых вычислительных структурах различной размерности.
2. Алгебраические основы проектирования алгоритмов массивных вычислении для итеративно-битовых СБИС-структур , включающие методы их гнал гтическоґо и ^ графического описания, эквивалентных преобразований и минимизации.
-
Методология алгебраического'-. синтеза алгоритмов массивных вычислений в итеративно-битовых СБИС-структурах и синтезированные на ее основе алгоритмы решения задач предварительной обработки цифровых изображений.
-
Методология проектирования и способы технической реализации специализированных и программируемых итеративно-битовых СБИС-структур для массивных арифметических, логических, поисковых операций, структурных преобразований данных и предварительной обработки цифровых изображений.
Публикации. По теме диссертации в научных изданиях, в которых могут быть изложены основные научные результаты докторских диссертаций, опубликовано 64 работа. В том числе 17 авторских свидетельств и патентов на изобретения, 21 статья, моиоірафия, два учебных пособия для специальности 22.01.00. по плану Минвуза РФ и тезисы докладов в трудах Международных, Всесоюзных и Всероссийских научно-технических конференций и симпозиумов.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы и приложения. Объем работы: 339 страниц основного текста, 115 рисунков на 45 страницах, 5 таблиц, список литературы из 300 наименований на 2ft страницах, приложения на 10 страницах. СОДЕРЖАНИЕ РАБОТЫ
