Введение к работе
Актуальность работы. Реализация большинства современных информаци-ощгых технологий предполагает использование параллельной обработки ин-формащш. Успешное применение многопроцессорных вычислительных систем (МВС) и, в том числе, распределенных вычислительных систем (РВС) невозможно без создания соответствующего программного обеспечения (ПО). При проектироваїгаи параллельного и распределенного ПО (ПРПО) разработчикам неизбежно приходится решать новые сложные проблемы, связшшые с выбором средств синхронизации, масштабностью распараллеливания и т.д.
В то же время, как отмечает ряд исследователей (В.Е. Котов, А.Б. Барский, Россия; L. Lamport, США и др.), средства разработки ПРПО, полностью базирующиеся на традиционных подходах, заимствованных из опыта разработки традиционного последовательного ПО, малоэффективны.
По мнению многих специалистов по проектированию ПО и ПРПО (В.В. Липаев, А.А. Саркисян, А.А. Штрик и т.д.) перечисленные проблемы еще больше усугубляются в связи с явно недостаточной развитостью теоретических основ разработки ПРПО.
Таким образом, существует необходимость разработки новых подходов к проектированию ПРПО, которые бы позволяли как можно раньше проводить анализ корректности и эффективности создаваемого ПРПО, а также ускорить его разработку, повысить быстродействие и надежность.
Анализ современного состояния проблемы разработки высоконадежного и эффективного ПРПО позволяет сделать вывод о том, что актуальность дашюй темы определяется отсутствием высокоэффективных методов проектирования ПРПО, должного набора инструментальных средств поддержки проектирования ПРПО и отсутствием технологии проектирования ПРПО, опирающейся на такие методы и средства.
Исследования и разработки по теме проводились в соответствии с утвержденными планами НИР Кибернетического центра ТПУ, входили в Государственную НТП «Трансфертные технологии, комплексы и оборудование» (подраздел «Программные системы»).
Прикладные исследования проводились в рамках ряда хоздоговорных НИР, в том числе по теме «Развитие математического обеспечешія сейсморегистри-рующих телеметрических систем» (№ Гос. регистрации 01850022657) т.д., а также по госбюджетной теме «Компьютерный томограф недр».
Исследования по теме «Разработка моделей и методов проектирования программного обеспечения мультипроцессорных вычислительных систем» выполнялись в 1992—1994 гг. по Гранту Миннауки России.
Цель работы и задачи исследований. Целью данной работы является создание технологии проектирования ПРПО, основанной на использовании оригинального аппарата PS-сетей. Для достижения этой цели решаются следующие задачи:
-
Развитие теоретических основ PS-сетей как аппарата моделирования параллельных процессов.
-
Разработка методов, позволяющих использовать аппарат PS-сетей для проектирования ПРПО.
-
Создание инструментальных средств, позволяющих использовать предложенные методы проектирования ПРПО.
Разработанная совокупность правил целенаправленного использования развитой теории и созданных методов и инструментальных средств должна составить совместно с ними технологию проектирования ПРПО.
Для исследования эффективности разработанной технологии также необходимо решить ряд задач проектирования реальных программных систем.
Методы исследований. В работе использованы методы теории множеств, теории параллельных вычислений, теории алгоритмов, теории графов и комбинаторики и теории моделирования.
Научную новизну полученных результатов определяют:
. теоретико-множественное представление аппарата PS-сетей, предназначенного для описания алгоритмов и ПРПО и исследования взаимодействия параллельных процессов;
. теория гпчтерпретаций и протоколов, опирающаяся на ряд теорем и позволяющая формализовать сопоставление моделей с моделируемой системой и устанавливать эквивалентность моделей;
. способ интеграции подсетей, позволяющий уточнять параметры моделей верхних иерархических уровней проектирования параметрами моделей, полученных на шгжележащих иерархических уровнях;
. способы учета и оценки числа процессоров МВС, позволяющие решать задачу оценки количества необходимых для вычислений процессоров при переносе параллельного алгоритма на конкретную МВС, метод размножения дуг для моделирования ПРПО неоднородных МВС и способ уточнения параметров моделей проектируемой системы с помощью полунатурных экспериментов на однопроцессорной ЭВМ;
методология моделирования и анализа алгоритмов, позволяющая строить и анализировать модели (PS-сети) алгоритмов по их стандартным схемам;
. совокупность правил целенаправленного использования разработанных теории, методов и инструментальных средств, составляющая совместно с ними технологию проектирования ПРПО.
Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методы, алгоритмы и инструментальные программные средства составляющие технологию проектирования ПРПО. Инструментальное ПО функционирует на ПЭВМ типа ШМ PC AT. Объем разработанного на языке C++ ПО составляет более 6000 операторов.
Разработанная технология была применена при проектировании и исследовании ряда систем, в частности, при исследовании эффективности проектируемых способов и алгоритмов параллелышх вычислешш для программируемого
матричного процессора (ПМП), разработанного в СКТБ СЭТ г. Краснодар; ис-следовшши эффективности различішх органтаций распределенной обработки данных и при проектировании параллельного режима вычислений подсистемы «Оценка геологических запасов» программной системы «Томограф», внедренной в Нефтеюганском Управлении автоматизации, информатики и связи (г. Нефтеюганск), что подтверждено соответствующим актом о внедрении.
Создагаше щшраммные средства инструментальной системы моделирования параллельных процессов «Parallax» внедрены в учебный процесс на кафедре Автоматизации проектирования Томского шлитехшгческого университета при выполнения цикла лабораторных работ по курсу «Современные архитектуры вычислительных машин, комплексов, систем и сетей» и подготовке магистров, что подтверждено соответствующим актом о внедрении.
Основные положения, выносимые на защиту:
-
Теоретический аппарат PS-сетей является более удобным и эффективным при практическом применении аппаратом для описания и исследования взаимодействия параллельных процессов, чем сети Петри и их расширения.
-
Предложенная теория интерпретаций и протоколов дает возможность аналгоировать результаты моделирования, формализовать сопоставление моделей с моделируемой системой и устанавливать эквивалентность моделей.
-
Разработанные теоретические положения, способы, методы и ішструмен-тальные средства, составляющие технологию проектирования, позволяют проектировать высоконадежное и эффективное ПРПО.
Апробация работы. Основные результаты работы докладывались и обсуждались на Международной конференции «Фундаментальные и прикладные проблемы охраны окружающей среды» (г. Томск, 1995 г.), на II Международной научно-практической конференции «Природные и интеллектуальные ресурсы Сибири» (г. Новосибирск, 1996 г.), на Международной конференции «Всесибирские чтения по математике и механике» (г. Томск, 1997 г.) и на 1 Международном симпозиуме по науке и технологии KoRus'97 (г. Ульсан, Южная Корея, 1997 г.).
Публикации. По результатам исследований опубликовано 9 работ, в том числе 5 статей.
Личный вклад:
-
Основные идеи создшшя формального аппарата PS-сетей принадлежат Н.Г. Маркову и АЛО. Смирнову, однако разработка и научное обоснование теоретико-множественной формулировки определений PS-сетей, их маркировки и правил их функционирования осуществлены лично автором.
-
Постановки рассмотренных в диссертации проблем и задач выполнены совместно с Н.Г. Марковым, при этом математические формулировки задач исследований осуществлены автором.
-
Методы и способы проектироваштя ПРПО разработаны автором.
-
Основные научные результаты, полученные с применением предложенных методов, моделей и подходов, принадлежат автору.
-
Программные средства инструментальной системы моделирования параллельных процессов «Parallax» разработаны автором, за исключение подсистемы обнаружения тупиков, которая создана А.В. Сарайкиным.
-
Постановки задачи исследования эффективности проектируемых способов и алгоритмов параллельных вычислений для программируемого матричного процессора ПМП и задачи исследования эффективности различных организаций распределенной обработки данных осуществлены совместно с Н.Г. Марковым.
-
Постановка задачи проектирования параллельного режима вычислений в подсистеме «Оценка геологических запасов» программной системы «Томограф» осуществлена совместно с СВ. Костюченко.
Результаты решения задач п. 6 и п. 7 получены автором.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 82 наименований и приложения. Объем основного текста диссертации составляет 143 страницы машинописного текста, иллюстрированного 60 рисунками.
