Введение к работе
**
Актуальность trmh. Современный этап развитая информационно-измерительных систем различного назначения характеризуется широким применением многопроцессорных и многомашинных вычислительных систем СМВС). как средства повышения производительности при обработке информации. Организация вычислительного процесса в таких системах требует рамания ряда специальных залач планирования параллельных вычислений, в частности, построениэ расписаний выполнения программ в МВС с целью наиболее полного использования возможностей параллельных систем.
Указанное обстоятельство обусловило выбор оаьею2_исошлава= ния диссертации, который может быть охарактеризован: однородные МВС и программный комплекс для распараллеливания последовательных программ.
Интенсивное развитие научных исследований в области планиро
вания параллельный вычислительных процессов производится как в
Направлении создания специальных параллельных языков программиро
вания,- так и в области разработки алгоритмов распараллеливания
как отдельный Фрагментов, так и в целом структурированных прог
рамм. " '
Формальная машинная независимость алгоритмических языков позволяет 'накапливать на этан языках математические знание с последующим их использованием на различных ЭВМ; Это на; пление осуществляется в виде библиотек и пакетов структурированных программ. Однако, программы, реализущие однотипные алгоритмы на различных ЭВМ, обладают не только разными, но и часто несопоставимыми характеристиками. К тому же библиотеки быстро устаревают, а их поддержание на уровне современных достижений требует значительных дополнительных усилий.
Однако, имеется лишь небольыое число библиотек на алгоритмических языках, которые действительно переносятся без ручного изменения на различные ЭЕМ. При этом стоимость разработки лучших
_ 4 -
программных комплексов по зарубежным данным локодит до нескольких дасятісов долларов 'за одну инструкцию языка.
Обсуждаемые проблемы были осознаны более десяти лет назад. Однако, отсутствие обобщенного аппарата автоматического распараллеливания связано с тем, что котя правила выделения независимых црагмантов .в программе сформулировать относительно несложно, задача назначения Фрагментов является комбинаторной и. NP-слошэй. что приводит к неоправданно высокой трудоемкости процедуры распараллеливания и требует больимх затрат машинных'времени и памяти.
Кроме того, реальные программы обладают "недетерминированны-' ми временными характеристиками, вследствие .наличия в. ник логических ветвлений, сиклоа неопределенной дпины, а также конфликтов в. обцей памяти, обусловленный внутренними и внешними прерываниями при прогоне программы в КЗС. При . этой . подавляющее оольиинство современным катодов постооения расписаний предполагает, что время выполнения Фрагментов программы известно точно или использует-скаляв-ше оценки. Применение вероятностный оценок является трудоемким процессом"и-юмет использоваться лишь в редких случаям или при неЗольиом числе фрагментов.
Тем нэ менее, поскольку Формальные правила организации структурированным программ (ограниченное число упразлямаих конструкций и логический связей между н*!ми) существенно проще, то представляется воз.«о>хньи разработать обыле подходы к распараллеливанию таких програші с учетом недетерминированного времени их
ВШОЯИЭНИЯ. ...''.'
Указанное обстоятельство обусловило,выбор шаішеда ticcjejHb
взшія диссертации, который моліегі быть охарактеризован как методы
сштояэлогш) планирования параллельный зучиаіительпь'к процессов
с недетерминированными временными характеристиками, реалиэукщих
. гарантированное распределение при наихудшем сочетании неопреде
ленных Факторов.
Целыо диссертационной работы является создание методологии расчета временный характеристик и анализа степени параллельности структурированный программ с недетерминированным временем решения отдельных Фрагментов с применением теории нечеткий множеств, и разработка комплекса алгоритмов для оптимизации процесса распараллеливания таким програ\ы.
В соответствии с поставленной целью автором решены следующие задачи:
созданы обобщенные методы исследования и анализа структуры программ по нечетким графам с использованием понятия временного определителя:
исследованы принципы выполнен,: л расширенный арифметический-и логический операция с нечеткими числами;
разработан комплекс алгоритмов для минимизации длины расписаний выполнения программ с недетерминированным временем решения;
проведены экспериментальные исследования по оценке качества и трудоемкости, подтверждающие эффективность алгоритмов распараллеливания,
Мйтюлн пегий» ррпршцр. в работе используются методы фундаментального аппарата теории нечетких множеств, теории графов, теории алгоритмов и комбинаторные методы поиска. Разработка алгоритмов осуществлялась на основе объектно-ориентированного поднода* к организации данный и алгоритмов.
н^учн^я нгтизца п^пты заключается в следующем.
-
Разработана обобщенная методика оценки временный характеристик и исследования параллелизма программ с недетерминированным временем ввшолнэния с 'использованием теории нечетких множеств на основе анализа особенностей графовый моделей программ.
-
Разработаны поисковые и эвристические алгоритмы для решения задач планирования параллельных вычислительный процессов на основе Использования теории нечеткий множеств.'
3. Обоснованы критерии назначения операторов на процессоры и предложены способы' уточнения атак критериев на основе нечеткой модели при шнашчйсісом распараллеливании программ с неточно известным врбюкам выполнения.
Ш2ШіШСіша.ііенность работы заключается в применении теоретический положений и выводов диссертации для режиия практический задач планирования параллельный вычислительный процессов и уменьшения ик трудоемкости, а тзкке:
-
Разработка способов быстрой оценки временный, карактерис-i.ir. параллельный'вычислений.
-
Создание библиотеки программ для расширенный ариФметичес-іс:<ч операций с нечеткими числами.
-
Разработка алгоритмического и программного обеспечения для минимизации длины расписаний выполнения программ с неточно известным времена.* выполнения операторов.
Направление исследований по теме диссертации является частью
работ по комплексной инновационной научно-текнической программе
Государственного Комитета РФ по высшему образовании "Создание
комплексов обработки изображений и средств отображения и;форма
ции" (13.223, а та-шэ хоздоговорной НИР 22101 "Разработка лппарат-
но-програмшшк средств обработки j; отображения видеоинформации" с
№Sf "Стрела" і\ Тула.. ' - '
Еаашащцзкшаізіаз_і^^ прикладные
результаты диссертационной работы были внедрены в рамкак комплексной инновационной научно-технической программы Государственного Комитета РФ по высшему образованию 13.22 С1993-1995 г. проект "Создание комплексов обработки изображений и средств отображения информации"), НИР "Разработка аппаратно-программных средств обработки и отображения видеоинформации"- с НИИ "Стрела" г. Тула' С1993-1995 г., коз.дог.тема 22101) и в фонде "Дисплей" С1995 г., коз. дог. тема 15)...
Теогетичзскнэ результата работа вналреян в учебнын курсам "Вычислительный комплэксы, системы и сета" и "Пгязктароеание спеп ЭВМ" на кафеяре ЭВМ Тульского государстЕэнног-о университета.
/Шш&ЗіШН^га&ш. Основные подокания диссертационной работа докладывались на следующий конФерзнцияк и семянерзк. "1. Мэящуна-родная научно-тенничзекая конференция "Htmra иязормзцчошьй тенно-'логин и системы" с Пенза. ПГТУ, 1994 г.). 2. йзздународаая науч-ко-тсяничзскея конфетсниия "Нзпг?рк2на~логйчэс?ая .методы. -п науке, тенникз и экономике" спэнза, 1S95 г.э.- 3. 2-ая кзядунзродная конИйрекция "Распознззйнкэ-95". (Курск, 1993 г. J. 4. 2-ая кэь'яу-нарояная конференция "Алгебрамчэскиэ, вэраятнсстнга, геометричес-х!'э, комбиматорниэ и Фушсшоигльнкз методы в теорій чисел" с ва-ронэя, 1933 г. 3. 5. Научная кшіешіимя "Матанатичэские методы в Ш'.мми" стула. ТулГУ, 1ЭЗЗ г.5. 8. Молодекная нзучно-твнническая конференция "Гагаринские чтения" с г. Москва, MYTH. 1996 г.). 7. Нгучно-прах'лтеская конференция поофгссорско-преподавательского состава ТулГУ с Тула, 1993 г.). з. з-ая Мендун-зрадноя конференция "Современные проблеми теории чисел, и єо прилокепия", с г. Тула, ТГПУ. 1998 г.)
Пуояйїшйц. По результатам исследований опубликовано 10 печатный работ.
КараетшисїШа~пзштн. Лиссертацнонная работа состоит из ввеяения, четырех глав и заключения, изложенный на 120 страницах чаїаіногосного текста, включашего 21 рисунок, 5 таблиц, содержит* список использованной литература из 85 наименования и приложения.