Введение к работе
Актуальность работы. Решение задач, возникающих в таких областях, как обработка изображений, машинное зрение, ядерная физика, структурный анализ, обработка речевых, радиолокационных, сейсмических, метеорологических, медицинских и других данных, требует от современных вычислительных систем (ВС) производительности от 25 млрд. до 1000 трлн. операций/секунду. Однако предельная производительность одного процессора на полупроводниковой элементной базе с фон-неймановской архитектурой не превышает 100 млн. операций/секунду при скалярных вычислениях. Поэтому последовательные системы не позволяют строить перспективные обрабатывающие системы реального времени и необходимо привлечение дополнительных мощностей в виде параллельных вычислительных структур.
Среди ногых подходов к проектированию перспективных ВС следует выделить локальность связей, програ'нмируемость архитектуры и. динамическую реконфигураций ВС, пространственно-временное распределение данных, декомпозицию вычислительных структур и данных, параллельное представление алгоритмов, разработка элементной базы для высокопроизводительных ЭВМ (RISC-процессоры, 'транспьютеры, СБИС на основе арсени-да галлия, ИС с переходами Джозефсона и др.). Однако, значительные достижения в разработке новых подходов к проектированию перспективных систем еще не дали существенных положительных результатов в решении поставленной проблемы. Одна из причин этого заключается в значительной разобщенности областей исследования, почти полном отсутствии общих инструментальных средств и объектов исследование и, как следствие, слабом понимании специалистами одной области проблем, над решением которых работают специалисты других областей. Другой причиной, требующей скорейшего устранения, является отсутствие единых, .доступных для понимания разработчиком и имеющих-возможность эффективного,представления в ЭВМ средств формализованного описания и преобразования параллельных алгоритмов и структур,
Задачи синтеза структур сложных ВС тесно взаимосвязаны и образуют в совокупности сложную проблему, которая в полном объеме не решена и в настоящее время интенсивно разрабатывается многими исследователями Известны'различные подходы к анализу структур сложных ВС. К ним относятся методы декомпозиции, координации и агрегации, методы агрегатив-ного описания'сложных систем, логико-комбинаторный подход, структурный подход, подход, основанный на теории сложности. Усложнение исследуемых систем на современном этапе привело к возникновению и интенсивному развитию системного подхода к проектированию.
Органически вписывается в концепцию системного структурный ПОДХОД, который приобретает еще большее значение на современном этапе проектирования параллельных ВС. В соответствии со структурным подходом к проектированию действия разработчика включа»? следующие этапы:
' - выработка ряда гипотез, касающихся структур подсистем, из которых будет состоять проектируемая ВС;
формирование из полученных подсистем альтернативных структур-кандидатов:
анализ каждой структуры с целью определения характеристик и выбора, окончательной структуры.
В силу NP-слокности задачи синтеза альтернативных вариантов про
ектируемой ВС, автоматизация структурного и параметрического синтезг
является трудно реализуемой лаке с использованием систем.проектирова
ния, реализованных на высокопроизводительных ЭВМ, Поэтому большинств<
из существующих подходов.к решений задачи синтеза носят эвристически!
характер и предусматривают включение в контур машинного прогчтированиі
человека. . ' ' ,
В рамках описаннгас подходов предложено достаточно большое числі методов проектироеания, среди которых мокно выделить следующие: деком . позиция и агрегатирование, формальный синтез, синтез на основе, эвристических приемов, синтез по обобщенной модели. Поиск наилучшего вари анта структуры ВС сопряжен с необходимость» количественной оценки как дой '' структуры, а это в свою очередь требует наличие соответствующи математических теорий и методов. В этом плане особый интерес представ ляют теория структур и теория сложности. Использование данных теори при проектировании позволяет управлять процессом помета и знячительн уменшить сложность решаемых задач.
На основе сделанного анализа иокно заключи', ь, что очень важным актуальным является разработка такого подхода к проектированию струк тур параллельных ВС, который позволял бы:
обобщать результаты, полученные с помощью различных методо исследования отдельных уровней описания модели;
строить простые методы отображение результатов исследования от дельных подсистем на общую модель ВС;
сочетать простоту получения альтернативных вариантов с возмог ностью описания многоуровневых моделей параллельных ВС с различие
„степенью детализации. '
Одним из таких является подход, основанный на тензорных метода) ^Впервые' данный подход систематически изложил американский инжеж _ Г.Крон, который использовал тензорные методы при анализе элёктричесю
яаиин. В дальнейшем тензорные методы развивались как в работах отечественных ученых (в области расчета задач электродинамики - А. В. Гапо-нов-Грехов. В.П. Веников. И.П.Копылов и др., в области исследования экономических систем - А.Е.Петров, в области проектирования баз данных и систем искусственного интеллекта - Л.Т.Кузин, А.Е.Армейский, для построения и анализа -лгоритмоз обработки структур данных интересный подход предложен в работах В.П.Панферова), так и в работах зарубежных ученых (исследование инвариантов - 0. Веблен» исследование сложных систем по частям - X.Хепп, Д.Цуганский, использование тензорных методов для решения задач символьной обработки- Да. Орр).
Вышеизложенное позволяет составить представление о состоянии теории и практики проектирования структур параллельных ВС. Оно сводится к следующему:
в настоящее время отсутствуют теоретические основы проектирования структур параллельных ВС, спектр которых распространяется от волновых и матричных процессоров с локальнш..и связями до протоколов управления сложными ВС:
разработка теоретических основ проектирования параллельных вычислительных структур и создание на их основе соответствующих инструментальных средств, доступных широкому кругу разработчиков, является ванной народнохозяйственной задачей.
Цель работа: разработка теоретических основ, и построение доступ
ных широкому кругу разработчиков'инструментальных средств.проектирова
ния параллельных ВС, основанных на тензорном исчислении сетевых моде
лей. "''.
В соответствии с доставленной целью основными 'задачами работы яв
ляются: . ' '
обоснование выбора сетевых моделей для формализованного описания и тензорного подхода к проектированию структур параллельных ВС;
формулировка задачи проектирования структур параллельных ВС в терминах тензорного исчисления сетевых моделей;
- разработка нового формализма для исследования сетевых моделей, основанного на теории структур; '
разработка подхода к анализу и синтезу сетевых моделей, основанных на тензорном исчислении;
разработка способов формирования базы данных и базы знаний для представления сетевых моделей структур параллельных ВС в интеллектуальных системах автоматизированного проектирования; построение алгоритмов разработанных методов; ,
. -» практическая реализация разработанных теоретических результатов, построение экспериментального образца интеллек-уальной системы автоматизированного проектирования и внедрение полученных результатов.
Методы исследования базируются на вновь разработанном подходе, основанном на тензорном исчислении сетевых моделей. В осноьу данного подхода положены теория графов, теория сложности, теория структур, теория сетей Петри, тензорный анализ. При экспериментальных исследованиях использовались методы теории систем, моделирование.
Достоверность результатов подтверждена математическими выводами, моделированием на ЭВМ. промышленной проверкой разработанных средств.
Научная новизна и теоретическая значимость. Разработаны теоретические основы тензорного исчисления сетевых моделей структур параллельных ВС. включающие:
- обоснование эффективности использования тензорного подхода и
сетевого представления моделей структур параллельных ВС;
- формулировку задачи проектиров'ания структур параллельных ВС в
, терминах тензорного исчисления сетевых моделей:
доказательство ряда утверждений, позволяющих сформулировать алгоритмы поиска изоморфных сетевых моделей;
разработку нового формализма - структуры сетей Петри (СП) - для исследования сетевых моделей;
разработку нового подхода к анализу и синтезу СП-структур, основанного на тензорной методологии;
построение алгоритмов, реализующих разработанные методы в рамках интеллектуальной системы автоматизированного проектирования.
Основные положения, выносимые на зашиту, заключаются в следующем.
1. На основе обобщения существующего опыта и проведенных исследований разработаны теоретические основы тензорного исчисления сетевых моделей структур параллельных ВС. В рамках теоретических основ:
сформулирована задача проектирования структур параллельных ВС в терминах тензорного исчисления сете"ых моделей;
разработаны оригинальные методы и языковые Средства формализованного описа"ия сетевых моделей структур ВС;
разработан новый ф.рмализм для исследования сетевых моделей -структуры гетей Петри;
доказаны теоремы, позволяющп построить эффективные алгоритмы генерации сетевых моделей ЕС;
- разработана методология анализа и синтеза СП-структур, основанная на тензорном исчислении.
2. На основе предложенных методов разработаны организация, структура и алгоритмы интеллектуальной системы автоматизированного проектирования структур параллельных ВС.
Реализация и внедрение результатов работы. На основе полученных теоретических результатов разработаны: методика анализа и синтеза структур параллельных ВС: средства описания сетевых моделей структур ВС; организация, структура базы знаний и базы данных, алгоритмы интеллектуальной системы проектирования структур параллельных ВС. Первая версия системы проектирования сдана в Государственный фонд алгоритмов и программ (регистрационный номер П008080 от 14.02.85 г.).
Научные и практические результаты диссертации внедрены на следующих предприятиях: Пензенское НПО "Рубин" (г.-Пенза). РосНИИ ИС (г.Москва), Государственный НИИ моделирования и интеллектуализации сложных систем (г. Санкт-Петербург), НИИ моделирования и вычислительного эксперимента при Ивановском энергетическом университете (г. Иваново). В!.эдрение результатов диссертационной работы в промышленности обеспечило экономический, технический и социальный эффект, подтвержденный актами о внедрении и использовании результатов работы.
Научные и практические результаты диссертационной работы использованы в учебном процессе Пензенского государственного технического университета. Пензенского технологического института. Московского государственного института электроники и математики (технического университета) . Материалы работы были использованы при постановке таких курсов как: "Прикладная математика", "Инструментальные средства проектирования микропроцессорных систем", "Моделирование". Внедрение результатов диссертационной работы в учебный процесс подтверждается соответствующими актами.
Аппобания работы. Основные результаты диссертационной работы докладывались, обсуждались и были одобрены на. Всесоюзном семинаре "Автоматизация проектирования в радиоэлектронике и вычислительной технике" (Москва, МДНГП, 1984), Третьей Всесоюзной конференции "Перспективы и опыт внедрения статистических методов в АСУ ТП" (Тула, 1987), Пятой Всесоюзной конференции "КОМПАК-87" (Рига, 1987), Всесоюзной конференции "Проектирование внешних запоминающих устройств на подвижных носителях" (Пенза, 1988), Всесоюзной конференции "Повышение эффектавности средств обработки информации на базе математического и машинного моде-
лирования" (Тамбов, 1989), Международном симпозиуме "INF0-89" (Минск, 1989), Второй Всесоюзной конференции "Микропроцессорные системы автоматики" (Новосибирск, 1990), Всесоюзном семинаре "Информатика в технологии приборостроения"(Москва, 1990), Всесоюзной конференции "Моделирование, проектирование и производство систем ВЗУ ЭВМ" (Пенза, 1990). Первом Всесоюзном школе-семинаре "Современное состояние теории и разработки программного обеспечения СУ'с ЭВМ" (Самарканд, 1990), Второй Всесоюзной конференции "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1991). Всесоюзном семинаре "Интеллектуальные средства диагностировали». РЭА" (Ленинград, 1991), Всесоюзной конференции "Математическое и машинное моделирование" (Воронен. 1991), Всесоюзном семинар*- "Новые ин-. Формационные технологии в планировании, управлении и в производстве" (Москва, 1991), конференции "Информационные технологии и системы. Технологические задачи механики сплошных сред" (Воронён. 1992). конференции с международным участием "Микросистема-ЭЗ" (Москва. 1Г93), Всесоюзных и Международных школах-семинарах (Крымская область, 1984-94 гг.).
Публикации по работе. По теме диссертации опубликованы 62 печатные работы, из которых 36 в соавторстве.
Структура диссертации. Основное содержание диссертационной работы изложено на 298 страницах машинописного текста, иллюстрированного 156 рисуьками. Диссертация состоит из 6 глав, введения, заключения, списка использованной литературы (362 наименования) и 10 приложений
