автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Модели и методы поиска оптимальных программных реализации простых зацикленных алгоритмов

РОССИЙСКАЯ АКАДЕМИЯ НАУК л „ КАБАРДИНО-БАЛКАРСКИМ НАУЧНЫЙ ЦЕНТР

Г ' ; ОД

2 0 1 - На правах рукописи

Мох'д Гассан Изеддиа Абаза

МОДЕЛИ И МЕТОДУ ПОИСКА ОПТИМАЛЬНЫХ ПРОГРАММНЫХ РЕАЛИЗАЦИЙ ПРОСТЫХ ЗАЦИКЛЕННЫХ АЛГОРИТМОВ

Специальность: 05.13.II -- Математическое и программное обеспечение вычислительных машин, хошлехсов, систем и сетей

АВТОРЕФЕРАТ диссертации на -соискание ученой степени кандидата технических наук

Нальчик -1995

Работа выполнена в Кабардино-Балкарском научном центре , Российской Академии Наук

Научный руководитель : доктор технических наук, профессор В.О.Гроппен

Официальные оппоненты : доктор технических цауж Кузнецов О.П.

кандидат технических наук, старший научный сотрудник Алешин' А.И.

Ведущая организация : Институт автоматизации проектирования РАН

Защита состоится_1995г. в_ часов

на заседании Специализированного совета Д002.68.01 Института проблем управления РАН по адресу: 117806, Москва, Профсоюзная 65.

■ С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан " " _1995г.

Ученый секретарь Специализированного совета кандидат технических наук

Е.В.Юркевич

• -ОВДАЯ ХАРЖГЕВКТИКА РАБОТЫ

Актуе^ьноуть, д>абрть>.. Стремление к созданию универсального программного продукта противоречит концепции создания высококачественных программ, эффективно использующих ресурсы конкретных ЭВМ, а сокращение трудозатрат программиста, связанное с' применением виртуальной памяти, часто приводит к неэффективному использованию последней,., повааащрму время счета. Попытка примирить эти противоречия лежит в основе предлагаемой ниже новой технологам проектирования программ, развитой применительно к программным реализациям простак зацикленных алгоритмов. К последним сводится значительное число зацикленных и квазизацикленных алгоритмов, используемых для решения ряда разнообразных приададный задач с повтаряксщкиса вычислениями: • обработка . радиолокационной информации и данный сейсмозондирований, компьютерная графика,' компьютерный контроль шздугородних переговоров на АТС, вычисления определенных интегралов методом Мэнте-Карло и т.п. Таким образом актуальность проблемы не вызывает сомнений.

Целью диссертационной работу является разработка и исследование матодоа, алгоритмов и программ, предназначенных для поддержки оптимального проектирования программных реализаций простая зацикленных алгоритмов при использовании различных целей оптимизации и разнообразный вычислительных средств.

. Под различными целями оптимизации ниже понимается поиск таких программных реализации вь:меназвшных алгоритмов, которые минимизировали бы время одной итерации при решении заданной проблемы, Либо объем используемой при этом оперативной памяти. В последнем случае время одной итерации может выступать в качестве ограничения, либо еще одного критерия в многокритериальной задаче. Цель» работа являлось также распрострачание развитого подхода на возможно более широкий диапазон вычислительных средств, в том

численна вычислительные системы и комплексы, позволяющие распараллеливание вычислений.

Нзтоды исследования. привлеченные в работе для достижения поставленной цели представляют собой совокупность методов теории графэв, исследования операций,. математического анализа и комбина-' торного программирования. Накопление и обработка экспериментальных данных осуществлялись с использованием методов математической статистики.

Научная новизна работы'связана с углублением и развитием направлений, выделенных в £3,5] применительно к выбранной предметной области. Сужение последней позволило получить ряд нетривиальных результатов, например доказана бессмысленность лексикографического упорядочения критериев применительно к поиску оптимальной реализации простых зацикленных алгоритмов по нескольким критериям, получены аналитический выражения, определяющие опти-. мадьныс размеры вспомогательных массивов для нескольким частных случаев Сглава 3), получено более простое, чем в {3) доказательство теоремы, определяющей шжнда границу числа обращений к внешней памяти в общем случае.

Практическая ценность работы заключается в создании теоретически обоснованной технологии проектирования оптимальных программных средств, реализующих простые зацикленные алгоритмы и средств программной поддержки этой технологии. ' Разработанная технология позволяет сократить время оптимизации программного продукта и, одновременно, повысить качество последнего в соответствии с выбранными критериями. И числу последних относятся время и стоимость решения прикладных задач, объем используемой'при этом оперативной памяти и, для многопроцессорных вычислительных систем, числа используемых процессоров.

Реализация результатов работы. Научные и практические результаты диссертационной .работы использованы при разработке программного обеспечения П.О. "Телемеханика" для динамического оператив-

ного размещения данных в памяти 1^совмеспг1мых ПЭВМ на основе накапливаемой статистики обраа^ния.

Апробация, работы. Основные результаты" работы докладывались на международной конференции по дистанционному образованию (Москва, 1994), Мэвдунайодной научно-технической конференции по новым информационным технологиям в образовании (1994, Владикавказ), на семинарах Севе ро-Осетинского Центра новых информационный технологий (1992-1993 г.г..Владикавказ) и кафедры Автоматизации обработки информации Северо-Кавказского государственного текнологического униьерситета (1993-1994 г.г. .Владикавказ).

Публикации: по результатам выполненных исследований опубликовано' 2 печатные работа.

Структура к сб-ъем лиссертаиии: диссертация состоит из введения, четырех глаз, заключения и приложений, изложенных на 103 страницах машинописного текста. Слисок . литературы содержит 48 наименований.

СОДЕРЖАЖЕ Р/БОТЫ

Вр„£9£Л£НШ1 обосновьвается актуальность темы, указана цель работы, описаны используемые методы исследования, приведены сведения о практической и научной ценности полученных результатов и апробации работа. Посда описания структуры диссертации, во введении приводятся обозначения, определения и допущения, Являющиеся общими во веек четырех главах работы.

■В первой главе приводятся содержательные и формальные постановки решаемых в диссертации задач, их свойства и описания общих подходов, используемых при их реыекии. Показана возможность сведения задачи оптимальной программной реализации простого зацикленного алгоритма к поиску на полном бисвязном взвешенном орграфе такого контура, число дуг которого било бн минимально, а сук-

- л

ма минимального веса принадлежацей этому контуру дуги и аналогичной дуги с максимальным весом не превысила бы объема оперативной памяти, выпеченной для нреяения программный единиц V,: г

р ^ пъигь г<*,)1иЫ1;

> . Ш) к ' * '

I"

4 <1?

^Л(Сг) ч

где: АСО - множество простых контуров графа б(Х,1!);

а £ АСО - к-й контур мнозшства АС б); к " и(а-,) -г- множество дуг контура а £ А(0".

•4 4

(уХи(а^) - дуга С "из множества иСа^);

2(а,3 - булевская переменная, принимающая значение, равное

единице, если контур а, входит в оптимальное решение и нулю к.

в противном случае.

Физически целевая функция соответствует минимизации числа обращения к. внешним носителям программы и подпрограммы, рабо-такадх в оверлейном режиме. Аналогично формируется задача минимизации среднего числа обра^ний к внешним носителям' при условии,

/

что для кеширования 1-го массива пользователя, размещенного на внесник носителях, объем которого равен VI, используется 1-ый блек кэширования с объемом Уд:

Г

р ЯЛАМ, _ __

2- ¿=< Ыс

ъЦ пит (УЦ-- Ы*);

Й, * ^ ;

»' - 4

¿-1

(2)

<- >

гдэ \'2 - объем оперативной памяти, ввделенной под блоки кеширова-

Р1 _ вероятность обращения-к 1-у массиву пользователя за фиксированный промежуток времени. Поскольку единицы.измерения обеих целевых функций совпадают, совместное рекёние визелриведеннык задач мокко заменить . решениам одной задачи, ■ объединяющей огргяичэкия первый двух при условии, что:

а) целевая Функция новой задачи ¡-»Р^Рг;

5) объем свободной оперативно:"! памяти Очевидно, что новая задача относится к задачам смешанного программирования, причэм в первой главе доказана. модальность этой задачи. Это позволило предложить для се рекения два различных алгоритма: в основе одного из ник лежит интерполяция и дихотомия, а другого - полиномиальная аналитическая аппроксимация и использование методов матеыатйческого анализа для поиска зкстре-

Последний параграф первой главы посвящэн многокритериальной оптимизации.: возможность постановки задачи оптимизации с несколькими несоизмеримыми целевь-ми функциями (например единовременная минимизация времени счета и объема используемой оперативной

ния.

^ума.

памяти) делает актуальным поиск оптимума по Пзрето.

Вторая, глава посвящена подробному анализу эффективности различных методов решения первой из приведенных выше задач. Поиск решения при этом осуществляется в два этапа. На первом на заданном бисеязном орграфе выделяются все контуры, а на втором этапе на множестве контуров выбирается один, удовлетворяющий ограничения« и обладающий минимальным числом дуг.

Для реализации первого этапа анализировались два подхода:

а) выделение всех контуров последовательным возведением матрицы в степень;

б) обход всех замкнуты* пугея на графе ветвящейся процедурой, подробно описанной Вз матери.

Оба алгоритма были программно реализованы (язык программирования - Паскаль, использовалась ШЧ-совместимая ЭВМ 1386, размер ОЗУ - 2 Кб, объем четкого диска 60 Ш, операционная система ЬБ DOS, версия 6.0.) и оттестированы. Для малых размерностей более зййктивнш явился первый подход, для задач реальный размерностей - второй.

Второй этап поиска так*® связан с двумя возможностями. Первая - это глобальный перебор, а вторая - использование алгоритма поиска кратчайших путей на взвешенных графах. Эффективность последней процедуры очевидна, что подтверздается приводимыми в главе 2 примерами. Сочетание наиболее эффективных применительно к задаче заданной размерности процедур каждого этапа позволяет получить эффективный алгоритм минимизации числа обращений к внешней памяти в коде одной итерации зацикленного алгоритма. Во второй главе показано, что, если цедыо оптимизации является минимизация обгема используемой оперативкой памяти, то вышеназванная процедура является одним из шагов, реваицих эту задачу.

Снииениа обгема перебора при поиске решения многокритериальной задачи оптимальной декомпозиции зацикленного алгоритма

• достигается двояко; одним из способов является лексикаграфическое упорядочение критериев, а вторым - их взвешивание. В последнем случае задача сводится к однокритериальиой, ' поэтому наибольший 'интерес представляет предыдущая, для решения которой во второй главе предлагается разновидность методов типа ветвей и границ. Особенностью этой модификации метода ветвей и границ является то, что каждой вершине дерева ветвлений отвечает не одна оценка, а вектор оценок, каедая из который соответствует "своему" функционалу цели.

Третья главд посвящена поиску оптимальной стратегии размена- . ния данным в иерархической памя-Ы ЭВМ. Приводятся содержательные и Формальные постановки задач такого рода, последовательность рассмотрения шд&лей срр^тБетствует росту их адекватности. Исследование свойств шс-тоенных моделей дает возможность доказать три теоремы, две изчкоторыи позволяют б ряде случаев определить аналитически нижнюю границу значения целевой функции задачи (2), а третья - оптимальный вектор переменных:

Теорема 3.3. Оценке снизу оптимального значения целевой функции задачи (2) при условии, чтоУ^Ц^Ц^' , отвечают следуювде значения вектора переменных:

Чг/^нГ

V < £ \ £ И : М~~н сз)

' 4 Лт/^ч

Приводимое в диссертации доказательство отличается от дока-'■ зательстьа аналогичной теоремы, приводимого в £3).

Нз основании доказанных теорем в работе предлагаются два алгоритма решения задачи (2), первый из которых базируется на переборе целочисленных значений вектора переменных в окрестностях точки, определяемой ацэажениеы СЗ), а & основе второго лежит т- ' тод тапа-'ветвей и границ. Описание этих процедур приводится ниже.

Алгоритм

Шаг 0. Величине И присваивается значение, равное + .

Шаг 1. На основании СЗ) иивтея вектор переменных задачи (2).

Шаг 2. Если на множестве индексов переменных I есть подмножество I'«21 такое, что Уг Ш<1; Уф то перейти к следующему шагу, нет - к шагу 7.

Шаг 3. Всем переменным, индексы которых принадлежат подмножеству Ге I, присваивается значение» равное единице.

Шаг 4. 1*14 1'.

Шаг 5. Уг Уг -111.

Шаг 6. Если 1= & или то леррйта к шагу 25, в противном случае - к шагу 7.

Шаг ?. Если на множестве индексов I есть подмножество Г 'е! такое, что:

их х Ча то перейти к шагу 8,

нет - к шагу 12.

В1аг 8. Всем переменным, индексы которых составляют I", присваивается значение, равное величине соответствующего массива, размешенного во внешен памяти: , У/се.1", - VI:

Шаг 9. I - 1\Г\

Шаг ю. Уг - \'г - XI Ш..

¿с-1"

Шаг 11. Если {!{• Уй - 0, то перейти к шагу 25, а противном случае - к шагу 1.

Шаг 12. Если~( I I * 1, то: • -

а) 01 - Уг, 1€1:

б) перейти к вагу 25, в противном случае - к шагу 13.

51'аг 13. Всем переменным, индексы которых соответствует- полученному множеству I,-присваиваются значения, равные их целочисленным ним-им границам.

Шаг 14. Организуется целочисленный массив булевых переменных О, содержания | К компонент, которш эануляотся.

Шаг 15. 1X1Ш - 1Х|1|)" + 1.

Шаг 16. Переменная 3 пробегает целочисленные значения от )I{ до единицы с шагом -1. При каждом фиксированном значении 4 проверяется содержимое З-ой ячейки массива 0: если IX ,3-1) *2, то содержимое .1-ой ячейки зануляетея, а величина 1X1-1) увеличивается на единицу. Если в результате все элементы массива Р оказались нулевыми, то перейти к шагу 25, в противном случае - к следуэдшу шагу. Шаг 17. V 4г., Ы^~ (Ы^)

II/

Шаг 18. Если Ни то перейти к вагу 19, в противном

случае - к шагу 15,

Шаг 19. Вычисляется значение целевой функции И

Шаг 20. Если 1 < Р, то перейти к и-агу 21, в противном случае - к шагу 23.

Шаг 21. Величине Г присвоить значение 2, полученное на шаге 19

последней итерации, э Шаг 22. Печап Р и вектора и. Шаг 23, У^ Цн - Ук - 1ХЮ. Шаг 24. Перейти к шагу 15.

; Шаг 25. • Конец алгоритма. Последний веданный на печать вектор и содержит оптимальные компоненты.

Конечность алгоритма и оптимальность решения очевидны: при каждом повторении шагов 15+24 значение целевой функции не ухудшается, причем верхняя граница числа этих шагов равна 2Ч(.

К недостаткам алгоритма 1 можно отнести сравнительно большой объем перебора и отсутствие учета целочислзнности числа обрада-

ний к внешней памяти,-что приводит к возможности получения не целочисленного значения величины р. Последнее, однако, можно отнести к недостаткам модели .(2), модификация которой, учитывался ие-лочисленность числа обращений к внешней памяти, имеет вид:

я = пиль & / е*Сйел, + ¿-1 1 и с

Н (4)

* «И; :

V.

Пойск решения задачи С4) предлагается- осуществлять методом типа ветвей и границ, обладавшим следуодэй спецификой."

а) стратегия движения го дереву ветвлений соответствует фронтальному спуску по дереву;"

б) "поиск прекращается, если выбранной вершине отвечает пустое подмножество новых вспомогательных массивов, размеры которых совладают -с размерами соответствующих массивов пользователя на внешних носителях.

При этом используются следующие обозначения и определения:

IX хч) - путь из корневой вершины дерева ветвлений в вершину хч: I - множество индексов массивов пользователя;-Кхч) - множество индексов вершн, принадлежащих пути

Поддерево дерева ветвлений называется минимальным, если его

множество вершин состоит только из вершины - источника и вершин -стоков. " .

Алгоритн 2.

Шар i. Взкорду R присваивается значение, равное +««= . filar 2. Корневой вершиной дерева ветвлений является вершина xs, которой отвечает пустое множество индексов массивов l(xs). Eter 3. На множестве висячих вершин построенной части дерева ветвлений выбирается вершина xq с наименьшей оценкой. На первой итерации q=s. Шаг 4. Генерируются еершны минимального поддерева с корнем в xc¡, висячие верникм которого отвечает индексам массивов, не принадлежащим ьможеству Kxq). Шаг 5. Каящой висячей вершине х, построенного на шаге 4 поддерева

я

стадится в соответствие подмноящстео ГСх ) » Гч(х^). Шаг 6. На множестве массивов I'(xd) решается задача С2), значение целевой функции которой является оценкой, отвечающей вершине ул. Эта процедура повторяется для всех гисячии вершин пострознкого дерева. При ;том следует учитывать, что в (2) величина V2 уменьшается на ■ величину, равную суммарному объему массивов пользователя, помещенных в оперативную память. Если полученная разность, оказывается отрицательной, то значение соответствуют оценки принимается равным ■+"«». Перейти к иагу 3. Шаг ?. Конец алгоритма. Индекса вериин, отвечающие множеству ICxq), определяет массивы пользователя, присутствующие в оперативной памяти полностью. Размеры вспомогательных массивов определяются решением задачи С2), условия которой определяется ВерШИКОЙ 5íq.

С учетом специфики дерева &етвлений верхняя граница числа

однако верхняя граница числа единовременно хранимых в памяти сценок не превышает величины (Н+1)!

Поскольку реализация обеих процедур связана с существенными затратами ресурсов ЭВМ, в следующей главе рассмотрены вопросы распараллеливания вычислений.

Гла$а 4 посвя1цена вопросам оптимизации параллельных реализаций простых зацикленных алгоритмов. Рассматривается ситуация, когда поиск решения исходной задачи можно заменить параллельным решением нескольких задач, для каждой из которых используется тот х® алгоритм, что и для исходной. Примерами могут служить задачи , обработки изображений, поиска 'информации в запросно-поисковых системах, базирующихся на распределенные базы данных, либо системы компьютерного контроля абонентов на междугородный АТС. В этих случаях исходная .задача разбиваетяс на ряд подзадач, решение каждой из которых может осуществляться параллельно с другими, и независимо от них в локальной вычислительной сети С ЛВС) или на многопроцессорном вычислительном комплексе (№К>. При этом обнаруживается, что распараллеливание вычисления влечет за собой возможность изменения целевой функции: если-минимизация времени, рассмотренная в предыдущих трех главах, однозначно определяет минимизацию стоимости решения задачи, то & параллельных вычислениях это не так.: сохранение времени ревения за счет распараллеливания вычислений может привести к росту стоимости решения исходной задачи.

Таким образом распараллеливание вычислений приводит к различным критериям: минимизаций стоимости решения задачи, минимизации стоимости используемого оборудования при условии, что время одной итерации-ке превышает заданной величины Т и минимизаци греке ни одной итерации при ограничениях на стоимость используамого оборудования и однократное ревение поставленной задачи. В диссертации показано, что минимизация стоимости решения последней баз

'/чета ограничений может быть, сведена к. решению квадратного либо кубического уравнения, что зависит от степени детализации используемой модели. Таким образом удалось _ получить аналитические выражения, определяющие число организуемых параллельных процессов 2. Более того, показано, что наличие ограничений сверху и снизу на величину 2 не существенно усложняет задачу: обозначая целую часть- корней выиеназванних уравнения 0, максимальное допустимое число параллельных процессоров - Р, а стоимость организации вычислений (3 параллельными процессорами С0), получим:

если 0 * Р;

2 - 0, если 0 *-Р и°<С0+13 ><=¿(0):

а + 1. если <2 < Р И«*С(МЭ < <*сс0);

1, если 0 < 1.

Анализ различных многокритериальных моделей распараллеливания циклических алгоритмов позволил выделить класс задач, для которых поиск решения может быть существенно упрошен:

Теорема 4.2. Если в многокритериальной модели распараллеливания простого зацикленного алгоритма критерии лексикографически упорядочены, то оптимальное решение зависит только от доминируютго критерия.

Иными словами теорема 4.2. позволяет свести поиск решения многокритериальной'задачи в выценазванкой предметной области, к "поиску решения традиционной оптимизационной згэдачи с одной целевой функцией. ' •

.Заключение содержит шесть пунктов, определяющих полученные в диссертации результаты. • ! •• .

Основный итогом работы является разработка основ технологии проектирования оптимальных программных реализаций простых зацик- , ленных алгоритмов и программных средств поддержи этой технологии.

В рамках этой технологии:

1. Разработаны обшие принципы проектирования оптимальных програм-иык реализаций простых зацикланкых алгоритмов по различным критериям, в том числе многокритериальные.

2. Исследованы различные стратегии декомпозиции простых зацикленных алгоритмов, являющейся имманентной компонентов облей стратегии и определена их эффективность.

31 Построены формальные модели разделения данных в памяти ЭВМ и алгоритмы поиска решения на этих моделях. В ряде случаев удалось получить аналитические, решения.

4. Проведен анализ многокритериальной оптимизации вышеназванных алгоритмов и выделены условия, когда оптимизация такого рода имеет сиысл.

5. Созданы и исследованы модели аффективной реализации простых зацикленных алгоритмов в многопроцессорных вычислительных комплексах. Получены аналитические выражения, позволяющие определить оптимальное число задействованных процессоров и оценить эффективность такого распараллеливания.

6. Разработаны пакеты программ, облегчающие реализации? предложенной технологии.

1

В Приложении приведены тексты программ на языке Паскаль для IBM-совместимых ЭВМ, обеспечивающих программную поддержку наиболее трудоемких" процедур предложенной выше технологии проектирования программного обеспечения в среде MS DCS, версия 6.0.

- is'

Опубликованные работы по теме диссертации

1. i-bchd Abasa. Computer aided system of optimal data distribution. Тез.- докладов Международной научно-технической конференции "Новые информационные технологии е образовании". Владикавказ, 1994 г., с. 29.

2. V.O. Grcppen, M.G. Abasa. Intelligent databases for computer jaeraorv optimal control usage for programing study period shortening. Processings of the first international Conference on Distance Education in Russia, Moscow, 5-8 July, 1984. p.288-300-