Информатика занимает важное место среди научных исследований ИАПУ ДВО РАН. Основными направлениями исследований Института в данной области с момента его становления были искусственный интеллект, компьютерная графика, компьютерные сети и базы данных. В последнее время работы по базам данных были приостановлены, но начались работы по высокопроизводительным вычислениям. В настоящей статье дан обзор важнейших результатов, полученных Институтом в этих направлениях.
1. Искусственный интеллект
Работы в области искусственного интеллекта начались в Институте в середине 70-х годов. Были разработаны некоторые модели представления знаний, основы математической теории онтологий и ее приложения, ряд инструментальных и прикладных систем искусственного интеллекта.
Стремление выделить такой класс систем реляционных продукций, свойства которого были бы возможно ближе к свойствам языка исчисления предикатов первого порядка, привело к определению класса систем конфлюентных реляционных продукций [54]. Каждая система этого класса есть неупорядоченное множество предложений языка исчисления предикатов, имеющих форму импликации и удовлетворяющих некоторым ограничениям. Результат вывода в такой системе не зависит от порядка применения правил при выводе. Любая система продукций этого класса как логическая теория непротиворечива, как порождающая модель - монотонна (любое состояние порождающего процесса есть подмножество следующего состояния) и полна (конечное состояние любого порождающего процесса, если оно существует, есть пересечение всех возможных состояний, содержащих начальное состояние, и таких, в которых нет применимых правил). На основе конфлюентных реляционных продукций было предложено несколько версий языка представления знаний [55,75]. В [71] проведено сравнение грамматической и семантической сложности этого языка и алгоритмических языков с учетом реальной практики их использования. Оказалось, что грамматическая сложность средней продукции в 3.4-4.9 раза выше грамматической сложности среднего предложения алгоритмического языка, семантические элементы продукции примерно в 1.5 раза информативнее семантических элементов алгоритмического языка, средний алгоритмический аналог средней продукции в 5.3-7.2 раза сложнее, чем среднее алгоритмическое предложение, откуда можно заключить, что средняя продукция эквивалентна по сложности модулю алгоритмического языка, состоящему из 12-18 предложений, а элементы алгоритмических знаний в среднем в 15 раз проще, чем средние элементы логических знаний. В [55] была предложена схема вывода для таких продукций, основанная на принципе резолюции, а также основанный на этой схеме метод компиляции в совокупность асинхронно вызываемых подпрограмм. В [57] разработаны методы пошаговой оптимизации вывода для систем продукций этого класса. Наконец, обобщением конфлюентных реляционных продукций являются недоопределенные продукции, введенные в [6], вывод в которых состоит в уточнении значений недоопределенных объектов.
Стремление ввести системы, основанные на знаниях, в рамки контекста разработки прикладных программ, когда программе, ее проекту и даже ее спецификации предшествуют математическая постановка задач и разработка методов их решения, привело к созданию математического аппарата, в терминах которого возможна формулировка таких задач и методов. В качестве такого аппарата были предложены системы логических соотношений n-го порядка [74]. В [11-14] исследовано множество решений систем логических соотношений первого порядка. В частности, доказана теорема: для любой системы S логических соотношений первого порядка и любого замкнутого относительно нее множества U существует примитивная система SU логических соотношений такая, что множества решений с носителем U для S и SU совпадают, что позволяет свести проблему изучения множества решений произвольных систем логических соотношений первого порядка к проблеме изучения множества решений примитивных систем. В [5,10] рассматривается использование таких систем в качестве моделей предметных областей. Продолжением этих работ явилась разработка теории необогащенных систем логических соотношений [52] и их использования в качестве математических моделей онтологий предметных областей [50,53], т.е. систем, определяющих смысл понятий предметных областей. На основе этих результатов была предложена новая постановка задачи индуктивного формирования баз знаний экспертных систем [47], ориентированная на тезис Д. Мики.
Поскольку онтологии многократно используются при разработке других информационных ресурсов, необходимо их своевременное оценивание, обнаружение в них дефектов и особенностей их устройства, которые могут свидетельствовать о недоработках, избыточности или нехватке информации в них, а также контроль свойств моделей знаний и онтологий, важных для их сопровождения. Для систематического изучения свойств онтологий разработана универсальная классификация, которая охватывает свойства онтологий разных уровней общности, разных предметных областей и написанных на разных языках [48,68,69]. Она упорядочивает известные из литературы свойства и не ограничивает исследователей в обнаружении новых свойств. Такая классификация положена в основу единого подхода к определению в однозначных терминах свойств онтологий.
Исследование ряда важных предметных областей позволило построить повторно используемые модели их онтологий. В [51,67] была опубликована модель онтологии медицинской диагностики. На основе этих результатов были разработаны базы знаний основных разделов медицинской диагностики [70]. В качестве одного из результатов проекта, совместного с Институтом технических исследований, Токио, Япония, была опубликована онтология "ноу-хау" в области обработки деталей на станках с ЧПУ (обрабатывающих центров) [76]. В [7,9,16] опубликована модель онтологии некоторых разделов физической, органической и аналитической химии в объеме университетского курса. Модель онтологии преобразования программ представлена в работах [8,58]. На основе этой модели онтологии была предложена концепция оптимизирующего компилятора, управляемого базой знаний [59]. Наконец, разработка онтологии пользовательского интерфейса позволила выдвинуть новый, онтологический подход к проектированию, реализации и сопровождению интерфейсов, и его инструментальной поддержке [42].
Приведенные выше теоретические результаты были использованы при создании инструментальных средств, основанных на принципах искусственного интеллекта. На основе теории конфлюентных реляционных продукций были разработаны универсальные оболочки экспертных систем Синап и Репро, а также оптимизированная оболочка Репро [4]. На основе онтологического подхода к проектированию, реализации и сопровождению интерфейсов были разработаны оболочки систем ввода и вывода данных, основанные на онтологиях [43,44]. Для коллективного формирования, редактирования, хранения и обработки информационных ресурсов различных уровней общности (моделей языков, онтологий, баз знаний и данных) была разработана Интернет-система "Многоцелевой банк знаний" и Редактор информации различных уровней общности [49].
Эти же теоретические результаты и инструментальные средства были использованы и при разработке ряда прикладных интеллектуальных систем. Модель онтологии медицинской диагностики была положена в основу экспертной системы медицинской диагностики Консультант-2, разработанной средствами системы Репро [45], которая применялась в дальнем походе на одном из кораблей Тихоокеанского флота. Для решения задач в области химии была разработана концепция и проведено макетирование компьютерного банка знаний в области химии [15]. Для обеспечения возможностей компьютерных экспериментов в области преобразований программ, макетирования оптимизирующих компиляторов и активного обучения студентов методам оптимизации программ была разработана концепция и проведено макетирование компьютерного банка знаний в области преобразований программ [56]. Разработаны также принципы применения онтологического подхода к созданию систем интерактивного доказательства математических теорем [38].
Полученные к настоящему времени результаты определяют направления дальнейших работ. Это исследование схем распараллеливания логических программ; развитие теории онтологий, теоретическое и экспериментальное изучение многоуровневых онтологий и их моделей; разработка методов онтологического анализа предметных областей как на основе вербального представления информации, так и на основе метаонтологий высокого уровня; разработка языков для исследования онтологий; исследование реальных онтологий научных предметных областей и разработка их математических моделей; разработка методов создания систем интерактивного проектирования "нетехнических" объектов (танцев, музыки и т.п.); разработка и экспериментальное исследование методов индуктивного формирования баз знаний в терминах непримитивных онтологий; развитие методов прямого и косвенного редактирования информации различных уровней общности; развитие компьютерных банков знаний в областях медицины, химии, преобразований программ и математики; разработка средств проектирования пользовательских интерфейсов и Интернет-сервисов; разработка теории и приложений интеллектуальных агентов.
2. Компьютерная графика.
Компьютерная графика, как научное направление, заняла свое место в тематике института в середине 70-х и ее развитие на протяжении всего периода было неразрывно связано с приложениями в автоматизации научных исследований, в САПР и в геоинформатике. Универсальная графическая система ДИСГРАФ [23], разработанная и функционирующая вначале на отечественной ЭВМ БЭСМ-6, а затем и на ЭВМ серии ЕС, была одной из первых графических систем в стране. Она активно применялась для интерактивной визуализации во многих задачах, связанных с тематикой ИАПУ и других институтов ДВО РАН, была внедрена в большое число заинтересованных организаций и была также отмечена медалями ВДНХ в 1979 году. Первые прикладные результаты были получены применительно к САПР в судостроении [21]. Позже это направление получило развитие в совместных работах с ДВВИМУ в интересах судостроительных проектных организаций страны [17]. Другим направлением САПР, развиваемым в лаборатории машинной графики в тот период, стала автоматизация картографирования с последующим внедрением результатов в картографическое предприятие (обслуживающее ДВ-регион) в г. Хабаровске и в ЦНИИГАиК ГУГК (г. Москва) [34]. Позже в 90-е годы эти работы трансформировались в разработку актуальных геоинформационных приложений, которые внедрялись и эксплуатировались во многих ведомственных организациях г. Владивостока и Приморского края. К их числу относится инструментальная ГИС АТЛАС, земельный, городской и дорожный кадастры [20,32]. Весомым результатом в плане автоматизации научных исследований в 80-е было и создание системы молекулярной графики [36], которая успешно применялась в научных исследованиях ТИБОХ, ИХ ДВНЦ, в научно-исследовательском центре в г. Пущино и в других научных организациях. В этот же период закладывались и основы распределенных графических систем на двухмашинной конфигурации и на сети ЭВМ [22,29], а немного позже были получены и первые результаты по организации параллельных вычислений на появившейся тогда транспьютерной вычислительной технике [27].
В последнее время усилия лаборатории машинной графики по-прежнему направлены, как на решение актуальных сегодня задач компьютерной графики, так и на создание проблемно-ориентированных приложений, связанных с обработкой графической информации. Одной из таких задач стало развитие воксельной графики, как альтернативы традиционной, реализуемой в распространенных графических программах полигональной графики. Воксельное представление объектов является адекватной моделью для визуализации больших объемов пространственных данных, но требует значительных вычислительных ресурсов. Поэтому усилия разработчиков постоянно направлены на повышение производительности методов обработки графических данных, и, в конечном счете, на повышение эффективности методов рендеринга (формирования растровой формы) изображений. В институте была разработана система воксельной графики для моделирования сложных геометрических сцен и их визуализации [19]. С одной стороны, она позволяет универсальным образом описывать и визуализировать сложные графические объекты и сцены средствами конструктивной геометрии. С другой стороны, она является адекватным инструментом для визуализации объемов, задаваемых скалярными полями. Скалярное поле в этом случае представляется изоповерхностями (фиксированное значение функции-скаляра). При этом была реализована эффективная алгоритмическая база, основанная на применении октантных структур данных, методах трассировки лучей, послойного рендеринга и целого ряда оригинальных оптимизационных решений, направленных на повышение скорости рендеринга [26]. Наряду с алгоритмической оптимизацией были реализованы и возможности ускорения визуализации за счет использования штатных аппаратных средств (видеокарты) и применения параллельных вычислений. Задача организации эффективных параллельных вычислений на многопроцессорной вычислительной системе представляет самостоятельный интерес, и результатом ее решения явилась методика распараллеливания применительно к семейству алгоритмов, входящих в состав системы воксельной графики [18]. На практике эффективность системы была подтверждена несколькими ее тематическими приложениями. Система была адаптирована и применяется для визуализации и анализа скалярных физических полей в океанологии (температура, соленость и др.). Другим адекватным применением является визуализация данных компьютерной томографии. При реализации этого приложения для быстрого формирования изоповерхностей (в данном случае заданный уровень плотности ткани) был применен алгоритм "маркированных кубов", который в сочетании с аппаратным рендерингом обеспечил требуемую в реальной практике интерактивную скорость визуализации. Для оценки универсальности воксельного подхода было реализовано и геоинформационное приложение "пространственная карта города". В этой прикладной программе были совмещены возможности воксельного представления зданий, рельефа, использования растровых карт для нанесения текстуры, применения параллельных вычислений и аппаратного рендеринга. Иллюстрации к работе системы представлены на рис. 1-3.
К визуализации объемов относится также и визуализация векторных полей, которая должна учитывать динамику сцены и требует, соответственно, анимации. Такие возможности также были реализованы на основе известного метода многочастичной анимации (МЧА) [61]. Как и в вышеописанных приложениях, в данном случае возможно объединение воксельной графики и метода МЧА с использованием аппаратного рендеринга. На рис.4 иллюстрируется работа программы применительно к решаемой в институте задаче газовой динамики по взаимодействию ударной волны с источником локального энерговыделения.
В направлении геоинформатики были получены решения двух актуальных прикладных задач, связанных с рельефом местности. В задаче моделирования динамики водостока на рельефе местности была предложена оригинальная математическая модель и вычислительная схема с организацией параллельных вычислений на эксплуатируемой в ВЦ ИАПУ супер-ЭВМ МВС-1000 [24]. Использование цифровой модели рельефа позволило (в отличие от традиционных решений-аналогов) учитывать пространственно-распределенный характер факторов стокообразования. В реализованной программе предусмотрены и возможности анимационной визуализации результатов моделирования. В задаче определения прямой радиовидимости на местности также было предложено эффективное алгоритмическое решение с использованием цифровой модели рельефа [46].
В рамках нового подхода к визуализации [78], активно развиваемого сегодня в компьютерной графике и получившего название IBR (Image Base Rendering), в лаборатории машинной графики были реализованы два эффективных метода рендеринга - метод рельефных текстур применительно к синтетическим воксельным сценам [31] и пленоптический метод генерации новых видов по фотоизображениям [35]. В отличие от традиционного подхода, опирающегося на геометрическую модель сцены и модель освещения, данный подход основывается на использовании смежных растровых изображений при формировании изображения нового вида. Его принципиальным преимуществом является независимость времени формирования нового изображения от геометрической сложности объектов сцены. Фактически, вычислительные трудозатраты определяются только текстурным разрешением используемых базовых изображений. В методе рельефных текстур выполняется построение базовых изображений с сохранением z-буфера, по которым затем формируются изображения промежуточных видов. Метод обеспечивает анимационную скорость визуализации с приемлемым качеством изображений. Пленоптический метод обеспечивает режим "виртуальной прогулки" по протяженной сцене (например, по улицам города). Входной информацией для него являются изображения реальной сцены, которые могут быть получены обычной цифровой фотокамерой. На предварительном этапе из этих изображений строятся "панорамные виды", с помощью которых затем формируются изображения требуемых видов. Каждый панорамный вид объединяет фиксированное множество лучей трассировки, закрашивающих пикселы экрана. Формальное описание всего множества пространственных лучей и определяет понятие пленоптической функции. В итоге процесс формирования нового изображения сводится к выборке требуемого множества лучей для закраски пикселов изображения.
Самостоятельный интерес в компьютерной графике и ее различных приложениях представляет задача реконструкции пространственных сцен. Практическую важность она имеет и в области робототехники при разработке методов компьютерного зрения. Как правило, задача пространственной реконструкции решается сегодня с учетом прикладного контекста и разного рода упрощающих предположений. В лаборатории машинной графики в настоящее время также ведутся исследования в этом направлении в рамках конкретных развиваемых приложений. В частности, получен результат по решению задачи сопоставления/идентификации отрезков на растровых изображениях разных видов пространственной полигональной сцены для случая калиброванных камер. Предложенный метод базируется на использовании корреляционной методики сравнения локальных участков изображений, и трифокальной геометрии, связывающей образы точек и линий на трех смежных изображениях [33]. Метод обеспечивает восстановление пространственных координат наблюдаемых отрезков для последующего построения геометрической модели сцены. В качестве пространственных сцен в данном случае рассматриваются сцены городской обстановки.
Новой областью проблемного приложения современных возможностей компьютерной графики в тематике института стала разработка моделирующего программного комплекса применительно к интересам подводной робототехники. Развиваемый графический моделирующий комплекс (работа выполняется по грантам РФФИ и ДВО РАН в сотрудничестве с ИПМТ ДВО РАН) предназначен для исследования методов управления движением автономного подводного аппарата (АПА) [28]. Предполагается, что комплекс послужит компьютерным тренажером для проверки, исследования и развития новых методов/алгоритмов планирования траекторий и непосредственного управления сложным пространственным движением АПА. Реализация комплекса основывается на принципе виртуальной реальности и имитационном моделировании всех систем АПА. Визуализация движения виртуального аппарата в условиях виртуальной подводной обстановки должна обеспечить наглядное представление об эффективности закладываемого в АПА программно-алгоритмического интеллекта. Наряду с генерацией/визуализацией виртуальной среды при создании комплекса возникает и более сложная задача по реконструкции окружающей обстановки и точной координации аппарата по данным его оптических сенсоров (цифровая видеокамера, фотоаппарат). Методы решения этой задачи составляют часть упомянутого "интеллекта" АПА. Указанная задача, именуемая в литературе как задача "одновременного восстановления структуры и движения" или SLAM (Simultaneous Localization and Mapping) является фундаментальной задачей в робототехнике и компьютерном зрении и требует дальнейшего совершенствования методов ее решения. Известные в мире подходы к ее решению учитываются в работе, проводимой в институте, и на их основе планируется получение новых результатов. На сегодняшний день в плане создания моделирующего комплекса уже получен ряд результатов: разработан блок визуализации, редактор виртуальной среды и характеристик АПА, один алгоритм пространственной реконструкции множества точек объектов среды, предложен метод восстановления реперных точек и уточнения траектории движения АПА на основе применения "фильтра Калмана". Однако эти результаты носят пока незавершенный характер и составляют содержание НИР ближайшей перспективы. На рис. 5 приведена иллюстрация к работе блока визуализации комплекса.
Еще одной важной в научном и практическом плане областью развития и применения новых информационных технологий является обработка спутниковой информации в контексте решения целого спектра прикладных задач, составляющих фундаментальную проблему моделирования динамики атмосферы и океана. Методы обработки графической информации, включая визуализацию, здесь также важны и развиваются с учетом прикладной специфики решаемых задач. Одним из таких методов, разработанным совместными усилиями лаборатории машинной графики, лаборатории моделирования океанических процессов и лаборатории спутникового мониторинга, явился релаксационно-контурный (РК) метода определения поля скоростей течений по спутниковым изображениям [25,30]. На рис. 6 показан пример работы РК-метода. Дальнейшее развитие подхода направлено на определение структуры течений применительно к океану и атмосфере. Развернутое описание проблемы и состояния дел в институте в этом направлении дается в статье Алексанина А.И. в настоящем выпуске.
3. Базы данных
Важным направлением развития информационных технологий в тематике института с самого начала было и создание средств организации и ведения баз данных (БД), поскольку многие прикладные программы, как правило, предполагают обработку больших объемов тематических данных. Особо актуально это для наук о Земле, где накопление наблюдаемых данных осуществляется для больших территорий и на больших интервалах времени. Поэтому уже в начале 80-х в институте была разработана универсальная система управления базами данных (СУБД) ЛОРД, основанная на перспективной концепции реляционного подхода к организации данных [64]. В реализацию системы был заложен ряд оригинальных концептуальных решений, методов, алгоритмов и языковых средств, включая логические модели, многоуровневость, протоколы взаимодействия, средства оптимизированной выборки данных и др., направленные на придание системе универсальности и повышение скорости обработки запросов пользователя. Следует отметить, что наряду с локальным вариантом СУБД также была реализована и распределенная система, функционирующая в вычислительной сети [39]. На базе системы СУБД ЛОРД в сотрудничестве с ТОИ ДВО РАН был создан океанографический банк данных, получивший в дальнейшем развитие и эксплуатируемый в ТОИ до настоящего времени. Одновременно с разработкой СУБД ЛОРД, ориентированной на создание больших БД и требующей больших вычислительных ресурсов, была выполнена и разработка версии реляционной СУБД МИР, предназначенной для организации оперативных БД на малых ЭВМ [65]. Указанная система успешно использовалась для создания судовых банков океанографических данных в морских экспедициях [40].
4. Высокопроизводительные вычисления
Современный этап превращения ИАПУ в центр высокопроизводительных вычислений и телекоммуникаций для Приморского научного центра ДВО РАН начался в 1999 году с организации лаборатории суперкомпьютерных и распределенных вычислительных технологий, превратившуюся со временем в значительное научное подразделение, в котором работают свыше 20 сотрудников (1 доктор наук, 5 кандидатов).
Внутри лаборатории сформировались следующие научные направления: высокопроизводительные научные вычисления, телекоммуникации и сетевые технологии.
По направлению высокопроизводительных вычислений в ИАПУ организован Центр коллективного пользования "Дальневосточный вычислительный ресурс" (ЦКП ДВВР). Центр оснащен многопроцессорными вычислительными комплексами отечественного производства МВС-1000/16, МВС-1000/17 и предоставляет свои услуги научному сообществу для проведения сложных расчетов, связанных с математическим моделированием различных явлений и процессов. Среди этих работ можно отметить определение пространственной структуры сложных биоорганических молекул [77], расчеты аэродинамических сверхзвуковых потоков с энерговыделением [60]. ЦКП ДВВР является базовой платформой для работ по программе №17 Президиума РАН "Параллельные вычисления и многопроцессорные вычислительные системы", ведущихся в ДВО РАН, проекта ДВО РАН "Разработка комплекса алгоритмов и программ параметрического синтеза по критерию надежности" и др. Вычислительные мощности ЦКП ДВВР используются также внешними организациями - членами научно-образовательной сети г. Владивостока, в которую сейчас входят помимо ДВО РАН и крупнейшие университеты - ДВГУ, ДВГТУ, ВГУЭС. В лаборатории ведутся работы по развитию численных методов решения экстремальных задач сложной структуры c использованием параллельных вычислений [37,62,63].
Чрезвычайно важна роль ИАПУ как системообразующего звена в корпоративной вычислительной сети ДВО РАН. Институт представляет собой региональный центр сети RBNet - межведомственной опорной сети, обеспечивающей формирование интегрированного информационного пространства науки и образования Российской Федерации. Под непосредственным сетевым управлением ИАПУ находятся крупнейшие научные учреждения ДВО РАН, сегмент сети Приморского научного центра с более чем 1000 узлами, подключенными в Интернет, в составе этого сегмента функционируют около 50 глобальных информационных серверов, ежедневный трафик в Интернет через маршрутизаторы ИАПУ составляет порядка 40 Гб. В рамках Программы развития информационно-телекоммуникационных ресурсов ДВО РАН ИАПУ является головным исполнителем по Приморскому научному центру, ведет работу по созданию корпоративной вычислительной сети ДВО РАН, включающей стационары и другие отдаленные научные подразделения отделения.
Трудами, в основном, сотрудников лаборатории создана локальная вычислительная сеть ИАПУ, имеющая в настоящее время двухуровневую иерархическую структуру, состоящую из магистрали с пропускной способности до 1Гбит и горизонтальных (этажную) сегментов с пропускная способность до 100 Мбит. Общее число постоянных рабочих мест в сети составляет 208 с резервом около 20 для временных подключений (ноутбуки, системы удаленного доступа, временные подключения внешних пользователей, другие нужды).
5. Информационно-вычислительные сети
Первые работы по исследованию и построению распределенных вычислительных систем на Дальнем Востоке были начаты в нашем институте в начале восьмидесятых годов. Тогда на базе ВЦ института был создан и сдан комиссии Госкомитета по науке и технике в эксплуатацию вычислительный центр коллективного пользования, который был предназначен предоставлять свои ресурсы в режиме удаленного доступа крупным организациям и предприятиям города. Параллельно с этой большой научно-практической работой силами лаборатории системного программирования (рук. к.ф.-м.н. Голенков Е.А.) велись исследования в области информационно-вычислительных сетей, разработки сетевых протоколов и сетевого программного обеспечения [2,3]. В то время в мире еще не существовало единой компьютерной сети типа интернет, и в каждой стране создавались свои собственные корпоративные или национальные сети, архитектура которых подчас была очень далека от архитектуры открытых систем, предложенной Международной организацией стандартов, что в значительной мере затрудняло межсетевое взаимодействие. В нашей стране самым масштабным был проект Академсеть, в котором участвовали ведущие академические и отраслевые институты. Создаваемая сеть была призвана, в первую очередь, объединить вычислительные ресурсы наиболее крупных городов страны и предоставлять их удаленным пользователям. Институт автоматики и процессов управления, так же как и ВЦ ДВО РАН, принимал активное участие в данном проекте, его сотрудники были членами различных рабочих групп координационного комитета Академсети. В институте было разработано сетевое программное обеспечение, которое эксплуатировалось на участке сети, объединявшей две площадки института - в центре города и в академгородке, и которое проходило экспериментальную проверку на глобальном маршруте Владивосток - Москва - Рига - Вена. Разрабатывались планы создания дальневосточной академической подсети.
Практика реализации сетевого программного обеспечения показала неоднозначность трактовки неформальных описаний протоколов, что затрудняло взаимодействие разных коллективов разработчиков. Поэтому в лаборатории системного программирования возникло новое научное направление, связанное с разработкой теоретического аппарата для формализации сетевых протоколов, что позволило бы решить не только проблему однозначности трактовки описаний протоколов, но исследовать их на корректность. В качестве базиса была выбрана теория сетей Петри, которая хорошо подходила для описания параллельных асинхронных систем, каковыми и являются сетевые протоколы. Основным идеологом данного направления стал д.т.н. Анисимов Н.А., которым была разработана теория композициональных сетей Петри, позволившая разделять сложные распределенные системы на отдельные фрагменты, что упрощало проведение верификации протоколов распределённых систем [1]. В практической области был разработан программный продукт PN3Tool, реализующий принципы композиционального построения протоколов при помощи композиции объектов сетей Петри и методы верификации протоколов. В целом по данному научному направлению были защищены одна докторская и пять кандидатских диссертаций.
По мере развития компьютерных сетей актуальность исследования протоколов снизилась, но полученные ранее фундаментальные наработки оказалось возможным использовать для другого важного на сегодняшний день направления - параллельного программирования. Основными проблемами в этой области и по сей день являются: отладка параллельных программ, повторное использование текстов программ, масштабирование в соответствии с доступными ресурсами и эффективность исполнения программ, а также проблема проверки корректности параллельных программ. В этой области выделяются такие направления как теория языков программирования, теория схем программ, и верификация программ на основе различных математических и логических формализмов. Однако, несмотря на длительную историю развития параллельного программирования, ни один из теоретических методов разработки и анализа параллельных программ не дошёл до масштабного практического применения. Совместный анализ предметной области и сетей Петри показал принципиальную возможность применения сетей Петри для решения основных проблем параллельного программирования. Предпосылками этого являются: графическое представление сетей Петри, позволяющее визуализировать поведение параллельных и распределённых систем; композициональная теория построения сложных сетей Петри из более простых составляющих; развитая теоретическая база в области анализа поведения сетей Петри.
На первом этапе исследования применения сетей Петри в области параллельного программирования, в лаборатории решалась задача описания параллельных программ в терминах цветных композициональных сетей Петри. Для этого теория цветных сетей Петри была доработана с целью включения типов данных и выражений императивных языков программирования. Теория композициональных сетей Петри была также доработана с целью определения параметризованных операций композиции над цветными сетями. Также было предложено описание сетей Петри на языке XML, совмещающем математическое описание структуры сети и описание типов данных, выражений и предикатов на языке С++. В терминах разработанного расширения сетей Петри, названного сети Петри для программирования были описаны основные семантические конструкции императивных языков программирования: последовательный участок, ветвление, цикл и вызов функции. Это доказывает, что для параллельных программ, на императивных языках программирования может быть построена спецификация в терминах сетей Петри.
Следующим этапом исследования была попытка использования сетей Петри для программирования непосредственного описания параллельных программ, минуя стадию использования языков программирования. Основной проблемой, решаемой на этом этапе, был поиск метода представления параллельных конструкций сетей Петри в виде последовательных взаимодействующих процессов. В результате была разработана схема трансляции параллельных программ, описанных сетями Петри в исполняемое представление, состоящая из трёх этапов, на первом из которых генерируется внутреннее представление программы, на втором определяется разбиение программы на процессы и на заключительном этапе генерируется исполняемое представление программы.
Для проверки и практической реализации теоретических результатов исследований в 1995 году в лаборатории начал разрабатываться новый программный продукт PN3System, при разработке которого были учтены основные недостатки предыдущей системы: отсутствие модульности в архитектуре системы, ориентация на графический интерфейс, бинарный нерасширяемый язык описания сетей Петри. Поэтому на момент начала разработки новой системы были выработаны концептуальные положения, предусматривающие дальнейшее развитие и возможности её адаптации к изменяющимся аппаратно-техническим условиям:
К концу 2001 года была разработана первая экспериментальная версия программной среды PN3System, состоящая из главного модуля, редактора сетей Петри и набора вызываемых из него независимых подсистем. Для трансляции программ, описанных в терминах сетей Петри, в исполняемое представление были разработаны следующие подсистемы, реализующие схему трансляции: 1) подсистема разбиения сетей Петри на процессы; 2) подсистема сборки процессов, работающая по трём эмпирическим критериям; 3) транслятор последовательных процессов, описанных в терминах сетей Петри в С++ [72].
В ходе работ над экспериментальной версией программной среды PN3System было получено подтверждение применимости сетей Петри для параллельного программирования. Однако также появилось чёткое понимание, что сети Петри в своём математическом представлении затрудняют технологический процесс программирования. Графическое представление программ описанных в терминах сетей Петри очень быстро превышает допустимые для единовременного обозревания размеры, вследствие этого поиск необходимой информации и модификация программы становится более сложной, чем при текстовом представлении программы. Очевидным стало, что для облегчения процесса программирования в терминах сетей Петри необходимо изменить способ описания параллельных программ. Поэтому в поисках нового способа описания параллельных программ было решено перейти к проблемам применения сетей Петри для отладки и проверки корректности параллельных программ.
Проверка корректности последовательных программ сводится к вопросам корректности алгоритма и его реализации, для параллельных программ к этим двум вопросам добавляется также вопрос корректности поведения параллельной программы, так как даже при корректном поведении каждого отдельного последовательного процесса параллельной программы их совместное выполнение может приводить к ошибкам, среди которых самыми сложными являются тупиковые состояния. Поиск тупиковых состояний является достаточно хорошо изученным вопросом для простых сетей Петри. В последние годы в лаборатории исследовался вопрос поиска тупиковых состояний для программ описанных в терминах сетей Петри для программирования. В результате был разработан метод автоматического построения спецификации программ написанных на языке С++ в терминах сетей Петри для программирования. Для полученных моделей программы был опробован метод поиска дедлоков по дереву достижимости упрощённой сети Петри, а также разработан метод анализа корректности параллельных программ, учитывающий влияние данных при взаимодействии процессов [41].
Техника отладки последовательных программ заключается в многократном исполнении программы при одинаковых входных условиях, что приводит к одинаковым условиям возникновения ошибок. Проблема отладки параллельных программ в том, что одновременное выполнение множества процессов параллельной программы приводит к недетерминированности их совместного выполнения и, как следствие, неприменимости традиционных средств отладки последовательных программ. За последние годы в лаборатории исследовались вопросы использования сетей Петри для обеспечения, во-первых, ретроспективного анализа поведения параллельной программы после возникновения ошибок, а во-вторых, обеспечения повторяемости условий возникновения ошибок. В результате был разработан метод отладки параллельных программ, на основе модели параллельной программы в терминах сетей Петри для программирования [66,73]. После построения модели параллельной программы в исходный текст программы добавляется отладочные участки кода, позволяющие: 1) синхронизовать поведение параллельной программы с изображением на модели программы, - т.е. визуализировать поведение параллельной программы; 2) сохранять последовательность событий, для последующего ретроспективного отображения истории выполнения программы; 3) контролировать порядок прохождения контрольных участков при помощи приостановки выполнения внеочередных событий.
Результаты теоретических исследований лаборатории по проблемам отладки и проверки корректности параллельных программ были реализованы в виде следующих подсистем экспериментальной среды разработки PN3System:
Результаты, полученные на предыдущих этапах исследования, определили следующий круг задач, стоящих перед лабораторией. Во-первых, это переход от файлового представления программ к связным спецификациям на основе сетей Петри, позволяющим описывать одновременно и программу, и язык программирования, и среду выполнения программ, и желаемое поведение программы. Связные спецификации позволят реализовать такой технологический процесс программирования, при котором алгоритмы анализа параллельных программ не будут зависеть от исходного языка программирования. А во-вторых, разработка на основе связных спецификаций полного цикла программирования с проверкой корректности программ на каждой стадии программирования.
Литература
Бобков Валерий Александрович
д.т.н., зав.лаб. машинной графики ИАПУ ДВО РАН,
г. Владивосток, ул. Радио, 5,
тел. 313-776, bobkov@iacp.dvo.ru
Голенков Евгений Александрович
к.ф.-м.н., с.н.с., ИАПУ ДВО РАН,
г. Владивосток, ул. Радио, 5,
тел. 310-911, golenkov@iacp.dvo.ru
Клещев Александр Сергеевич
д.ф.-м.н., зав.лаб. представления знаний ИАПУ ДВО РАН,
г. Владивосток, ул. Радио, 5,
тел. 310-424, kleschev@iacp.dvo.ru
Нурминский Евгений Алексеевич
д.ф.-м.н., зав.лаб. суперкомпьютерных вычислительных технологий ИАПУ ДВО РАН,
г. Владивосток, ул. Радио, 5,
тел. 310-404, nurmi@iacp.dvo.ru