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

Р Г Б ОД РОССИЙСКАЯ АКАДЕМИЯ НАУК './ КI *: Вычислительный центр

На правах рукописи ДЮСЕМБЛЕВ Ануар Ермукаяович

КОРРЕКТНЫЕ МОДЕЛИ СЕГМЕНТАЦИИ ПРОГРАММ

Спвци&лькоста< 05.13.17 - Теоретические основы

ннформатнхн

АВТОРЕФЕРАТ

диссертации на соискание•ученой степени доктора физико-математических наук

Москва, 1994

Работа выполнена в Научном Совете по комплексной проблеме "Кибернетика" Российской Академии Наук.

Научный консультант - академик РАН Журавлев Ю.И. Официальные

оппоненты: - доктор технических наук,

профессор А.Л. Горелик

- доктор физико-математических наук, профессор, академик РАО В. Л. Матросов

- доктор физико-математических наук,член-корреспондент РАЕН

• К.В. Рудаков

Ведущая организация - Научно-исследовательский

институт системных исследова ний РАН

Защита состоится " " 1994 г.на заседании

Специализированного Совета Д 002.32.06 при Вычислительном Центре РАН.

Адрес: 117967, ГСП-1, Москва, ул, Вавилова, 4 0

С диссертацией можно ознакомиться в библиотеке МИ РАН.

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

Ученый секретарь специализированного Совета Д.002.32.06 Кандидат физико-математических

наук __—--------

С.М. Швартин

(ШЦИК ОЕРДЙШ о дигаятлшш

Актуальность тыл*. Как из постна,круг проблем,связанных с оценкой производительности и упраплением вычислительным процессом в ЭВМ, чрезвычайно широк и составляет предмет исследования отдельного научного направления|Д,2], в котором именно программы часто выступпют п качестре пенпннык объектов исследования.

Одной из интересных задач в теории управления пичислитель-ным процессом в ЭВМ является задача сегментации программ [I ,2^. Первоначально, как правило, под задачей согменгапии било принято понимать задачу разбиения последовательной программы на вэаимнозави-еимыл по управлению и информационно!по данным) части - блоки,секции, сегменты и т.д., в соответствии с. той или иной целью. В страничных системах с виртуальной памятью, учитывая,что в любой момент выполнения программы в основной памяти(ОГП находится лишь некоторая часть страниц программы, такой кельм может быть :

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

- минимизация среднего размера ОП, отводимого программе;

- минимизация среднего времени выполнения программы;

- минимизация Функционала ПГ0СТШСШ*ВРШ1 и лр. Для параллельных систем одна из основных целей при сегментации- это разбио-

I/ Авен О.И.,Гурин Н.Н.,Коган Я,А. Опенка качества и оптимизация вычислительных систем.- М: Каура , 1УТО, -<?04с.

2/ Форрчри Д. Опенка произвопителыюсти вычислительных систем.-М: Мир ,1901, - .'ИЬс.

ние последовательной программы на части - ветви параллельной программы и сегментирование самих ветвей.

Для систем с виртуальной памятью с определённого времени наряду'с термином"сегмещ,ация" используются термины: переструк-тypнpoвaниef2 реорганизация и др. При этом считается, что программа состоит из конечного числа блоков, располагаемых на страницах (сегментаЬс). виртуальной памяти. Под оптимальной сегментацией понимается такое расположение блоков программы по сегментам (страницам), при котором достигается экстремум заданного критерия качества.

В диссертации рассматривается именно такая интерпретация задачи сегментации программ.

Экспериментально было обнаруженочто наибольший эффект при сегментации проявляется у программ с так назнвавмым частым ( постоянным) прогоном, например, у трансляторов, больших системных программ и др.

; По мере формирования и развития отдельного научного направления - "Оптимизация вычислительных систем" в его рамках

V

•для задачи сегментации сложились ряд методов, которые условно южно, разделить иа три подхода: подход, основанный на синтезе дискретных, аналитических моделей; графовый, а такие кластерный подходи, которые позволяют, в основном, получать лишь приближённые решения при неизвестной погрешности получаемых решений. Точные решения гарантируются лишь в весьма частных случаях.

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

ного, полного неориентированного графа (2J. Кластерный подход основывается на представлении задачи сегментации как задачи, кластерного анализа £2,3,4} , Исходя из этого, первоначально для решения задачи сегментации непосредственно применялись методы дискретной оптимизации, кластерного анализа и теории графов. Позже при синтезе алгоритмов сегментации стали учитывать накопленный экспериментальная материал. Было показаноf 7,2], что как комбинаторная задача, задача сегментации в общем случае, принадлежит классу МР -полных задач и проявляет свойства последних в вычислительных экспериментах [l,2 J. Ряд работ были нацелены на то, чтобы учитывать при сегментации локальность программ [5 J , стратегию замещения [б]и др.Здесь же заметим, что работы по сегментации программ восходят к известным результатам по теоретическому программированию Ляпунова A.A., Янова Ю.И., Калужнина Л.Л., Карпа Р.,

Для данной работы основную стимулирущую роль сыграли результаты

3/ Журавлёв Ю.И. Об алгебраическом подходе к задачам распознавания и классификации. - В сб. Проблемы кибернетики. Вып. 3I,I978r. ,c.5-Ü8.

4/ Mftsu4a. Т., $hiota И., f/cyuehi X., Ohki Т. Optimieabe/S of projram crjtttfiiatic* *(usttr a**fys(s.Pret. IFJP Ccvfress , рр. i и-366. 5/ Maáisov A.Vi., b&iso*/ A.P. Churacterisfici ef Prcjrom hoeatities. Commufi/. cf ACM, i 3fé , 1? H, S 5~, PP- 2SS- 2 3*

6/ Vtwisj P. \Jori<¡A>j sif; Past a.*>tf Prese*f. IEEE Trass. ¿e-fivare У¡S£-6, A>Jt l9SO,f>p.

7/ Гэри'М., Джонсон Д . Вычислительные машины и труднорешаете задачи. - И,: Мир, 1982.

авторов: Denrüiey F. И,, HewíH ¿hurma^A., Kr«t J., %w¡s Jt¡

$ amarncortky С, V., Comí cu. L. ^ Поспелова A.A., Косарева Ю.Г., ßenh-si A.T., В.^ок/гТ,

èrltM и K.t Dé-л/а//vj P., Hd-f¿efd -V.J., QeraU l, ñaerj.l. Сол^Ц a, bao pv farjoéi* b.% ferr»r\T>., ttasuttf.,

¿i;»!* H.,M>juck¡ It.jOhkiT., АвенлО.И., Когана Я.А. «ГуринлН.Н., Игиатущенко В.В., Ьальковского Б. А., Касьянова В.И., Archar/f tl.j Миренкора H.H., ш сиг^С. и др.

Данная работ», является частью исследований, выполненных в рамках tému" ^аарлботка и реализация системы технологий распознавания па основе алгебраических и логических методов" (НИР 836 ) Тема диссертации тесно свяаана с планом госбюджетных работ: "Дискретный н наклясеические модели обработки информации и принятие рвшоиий'Ч Тема I.13.12.6., ИГР Olßü.026033 ) Цель работы. Основной целью работы является синтез математических ыодблей сегментации, с помощью которых могут' быть определены точные решения задачи сегментации программ. В диссертации разработаны и исслэдовани:

- модели сегыантации программ для систем с виртуальной памятью со стратегией V/ $ (рабочбв множество[ 6 ], рабочий комплект[ I ])

- модели»основанные на применении алгебраической теории{ 3 Jk задаче сегментации программ.

Наличие тьких модвлый позволяет определить условия,при выполнении которых, гарантируется построение точных ( £ -точных)

г

решений задачи сегментации.

Следует отметить, что стратегия vi S является основным представителей группы алгоритмов обмена с изменяющимся во времени числом активных сегментов программы и служила основной

при определении других алгоритмов этой группы Накопленный экспериментальный и теоретический материал позволил утвврждатьСсм.Д.ФаррариС 2 ,стр.4153), что"...стратегия рабочего множества является одним из наиболее удачных средств самонастройки, когда-либо использовавшихся в вычислительных системах." Как отмечено в[ 1,стр.194 ] размер рабочего множесгва(комплекта) это показатель качества страничной программы, на зависящий от алгоритма распределения виртуальной памяти. Концепция рабочего множества играет особую роль в теории управления вычислительным процессом и значительное число публикаций посвящены исследованию свойств рабочего множества и его обобщений^ б ]. В связи с этим решение задачи сегментации в случае У $ стратегии имеет также особый интерес. '

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

Специально изучен случай У $ стратегии обмена. Для данного случая при весьма общих ограничениях удаётся выписать явный вид • функционала задачи сегментации и системы огарничений, задающих множество допустимых сегментаций.

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

. Найденные автором результаты позволили определить условия, то-

рацтирующие построение точных (¿-точных) решений задачи сегментации.

Практическая ценность.Определяется известным прикладным характером основных постановок и важностью решённых в диссертации прикладных задач.

>

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

Апробация. Основные результаты диссертации докладывались на ряде всесоюзных и международных конференций,а также на научных семинарах, в том числе: на научном семинаре лаборатории проблем распознавания ВЦ РАН(1982,1983), на научном семинаре по теории автоматов мех.мата МГУИУ Конференция молодых учёных МГУ,1982), на I Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам, и дискретной оптимизаций Алма-Ата, 1981); на Советско-немецком семинаре"Дискретная математика и её приложения в кибернетике "(Алма-Ата,1985); на научном семинаре кафедры математических основ управления №ЕТИ(ноябрь,1984); на международной конференции "Высокопроизводительные вычислительные системы в АНИ"(Алма-Ата,1991), на международной конференции по статистическим наукаы(Рабат, 1992), на семинаре отдела проблем распознавания и методов комбинаторного анализа ВЦ РАН(Москва,1994),«а научном семинареНИИСИ РАЖ Москва,1994) Публикации. По теме диссертации опубликованы II печатных работ. Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Работа выполнена на 243 страницах машинопечатного текста, содержит 9 рисунков и 8 таблиц. Список^, литературы включает 186 наименований.

. 8/ Пакет, прикладных программ для решения задач распознавания и классификации.(ПАРК). М: ВЦ АНСССР.,1981г.

СОДЕРЖАНИЕ РАБОТЫ .

Во введении- даны общие сведения о диссертации.

В первой главе представлен обзор подходов и методов для задачи сегментации программ,при отом рпссмотр»нч как метолм,основанные на классической графовой постановке задачи сегментации, так и методы, предложенные на основе дискретных, аналитических моделей сегментации, а также кластерные методы. Слэдуя1.Я?гп)<^2,стр.5513 а также др. авторам, под сегментацией программы понимается отображение

. V •• в —» з

множества блоков программы В в множество страниц(сегментов)4 » причём при различных отображениях В"-*4 одна и та же строка ссылок на блоки преобразуется в различные строки ссылок На страницы!сегменты).

Хорошо известно, что сегментация является эффективным средством, улучшающим внутренние свойства программ!например, такими как локальность^ 5]) и даёт наиболее ощутимые результаты для программ с частым прогоном.

В Диссертации считается, что программа состоит из И -блоков ,¿1 ,..., ¿п располагаемых на р сегментах!страницах) Д» » Л »•••» ^ виртуальной памяти (Рис.1);при этом считается ,.,что ни длины блоков , ни длины сегментов V; , у4 ,..., Ур не изменяются во время выполнения программы, а сама программа на любой свой прогон затрачивает конечное время. Кроме того, для лкбэЙ рассматриваемой в диссертации задачи предполагается, что существует исходная сегментация Е0 (программы, сети, словаря), при которой вычислительный процесс функционирует в рабочем режиме.

; Если но V, =,. .с УР имеем обычную последовательность страниц. Другими словами, в работе использована организация вирту-• альной памяти незначительно отличающаяся от стандартной страничной организации. Будем считать также, что калдый блок программы входит в состав лишь одного сегмента програшы(усдови© А), а суммарная длина блоков, содержащихся на одном сегменте не должна превышать длины этого сегмента!условие Б).

Здесь же отмечается,что в основном в известных моделях сегментации оптимизация программ происходит за счёт учёта внутри-страничных ссылок. Ссылки между различными сегментами!страницами), входящими в резидентное множество Их( Ь) '(т.е. те страницы программы,которые в текущий момент"6 находятся в ОШ .рассматриваются в этих моделях как ссылки, приводящие к етраничным(сегментным) откялям. При этом п недостаточной степени при сегментации учиты-мется стрнтогпя замещения страниц.

Во вгорой главе диссертации ( в § I ) для стандартного вычислительного процесса^ 2 ^формулируется основная и вспомогательная задачи. В качестве основной задачи взята задача минимизации за счёт изменения исходной структуры программы Математического ожидания числа сэгмзнтных(страничных) отказов в одном прогоне программы. Иначе говоря, если чэрзэ Р*(х,т ) обозначить функционал основной задачи, где хб £ -матрица, описывающая структуру программы, а X - параметр, отражающий зависимость функционала Рс(х,Т ) от стратегии замещения{. например, для стратегии - это размер окна), тогда зафиксировав г, основную задачу запишем в виде

*нл/р'(х,т ) . (0.1)

Хег£

Содержательно каждой матрице /€<? соответствует структура программы, при которой возможна экcплyatlu^ия программы в нормальном режиме,

В качестве вспомогательной задачи взята задача минимизации среднего числа страничных(сегментных) отказов по¿>1 прогонам программы за счёт изменения её структуры. Обозначим через

Р'"(х, I ) функционал вспомогательной задачи и запишем её в виде

Р'Ь)(х,г ) ; ' (1.1)

х« <;

здесь также считается, что Т -фиксировано.

В параграфе I введены понятия нормального и Л -представления функционала основной и вспомогательной задачи, где Л"(и} . набор / вспомогательных переменных. В частности для

нормального представления А =$,м тогда нормальное представление лигаь от переу.пнчх матрицн х. Если же Л то Л-пред-

ставление ФункционалаР" зависит лишь от переменных набора Л. ,но в этом случае каждой матрице хе <г соответствует свой набор значений переменных,входящих в Л , Для записи Л--представления используется обозначение £с(х ), где ,а2 ,... ,а,, ), а^»0, 1=1,2,...,^ .

Пусть -некоторое Л -представление функционала Р"

при условии, что возмущениям подвергаются компоненты набора в. в § I, следуя Леонтьеву В.К. , введены понятия радиуса устойчи- -Еосги, радиуса ¿-устойчивости и устойчивости по функционалу для задачи (0.1). В частности, § I главы содержит также совокупность определений, отражающих характер преобразований, которым подвергается функционал основной и вспомогательной задачи.

В § 2 главы, используя специфические особенности стратегии замещения К/(рабочее множество, рабочий комплект), удаётся записать явный вид функционала основной и вспомогательной задачи для данного случая. При этом законы распределения случайных величин считаются неизвестными, предполагается лишь, что они существуют, а ограничения касаются лишь их самых общих свойств. Источником случайностей здесь является множество данных программы. Природа этого множества не уточняется, но на практике обычно предполагается, что.то подмножество реальных данных, с которым работает программа, не слишком часто изменяется. Невыполнение этого предположения влечёт рвгмеитирование программы заново.

Итак, пусть ^={1,.,1-т(ц,)}-"Рабочее множество" блоков[2 ) программы в виртуальный моментI ,т.е. те блоки, на которые происходили ссылки на интервалеС^Т, 1). Далее будем называть это множество контрольным состоянием(к.с.) программы в момент t и объединим в запись <}, все те контрольные сос.тояния(при различных 1), которые отличаются друг от друга лишь порядком следования блоков. Множество всех контрольных состояний программы обозначим через а через £ . обозначим случайную величину содержательно рапную

числу обращений к блоку i при выполнении k.c.<j, за один прогон программы. Пусть f^. = для всех <{eQ и

1=1,2,..., И . Чероэ îJ,, обозначим контрольное состояние, условно соответствующее пустому множеству и будем считать, что Q . Обозначим через t = • 'W' как 0f5"4H0

скмвол математического ожидания).

Элементы множества <? могут быть определены по строкам ссылок на блоки в результате энсперимзктов с программой1,2 J с различными исходными данными; при этом нэ требуется менять структуру программы. Иными словами, контрольные состояния программы- это её структурные инварианты.

Контрольное состояние и матрица х(. Gr с учётом

условий (А),(Б) порождают однозначно рабочее множество R ( <{. ,х), кадцый сегмент которого содержит, по крайней мере, один блок, входящий в к.с. ^ , кроме того в множество jÇ ( iJ. ,х) входят

л

и некоторые другие блоки. Обозначим через R(îJ,x) множество блоков, входящих в сегмпнты R( ^,х).Следует заметить, что вообще говоря любое рабочее множество W (i , t ) является рабочим множеством вида к ( <{, ,х).

Итак, пусть )- это Л -представление функционала

F" основной задачи, тогда для модели вычислительного процосса [2 ]имеет место следующий результат, который является по существу основным результатом данной главы.

Теорема 2.1. Пусть на любой свой прогон при W7? стратегии обмена программа затрачивает конечное время, а любая матрица

FQ

основной задачи существует нормальное представление

где ■ ¿^(х) функция:

л

fo, если блок i входит в множество Я( ц ,х), цф^..

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

Способ вычисления функции £Хх) дан в §§2,3 главы при условии, что матрица х£(? удовлетворяет условиям (А),(Б). В частности в § 3 описан более удобный, чем в § 2 способ вычисления _функции ^(х) через элементы матрицы x=(xit )р<п»(

-h если блок входит в состав сегмента и х71 =0, в противном случае )а именно

г0, если x'ti>хг;, > I, .....im

J-L Isf

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

Множество матриц £ описывается в § 2 главы; в описании Q участвует также функция Н., (х)-характеристическая функция

рабочего множества £( ^,х). Учитывая способ вычисления функции . (¡^(х) и способ вычисления функции Н^Сх):

если^Т^х^» (I- ^(х))* I , + ^

у*)-.'

* 1 О, в противном случае

это даёт возможность вь)числять размер рабочего множества £ ,х)

(обозначим его через [1( ^ ,х )])по простой формуле р

п 1

При известной матрице хе£ для вычисления ^.х)} фактически достаточно иметь информацию о контрольном состоянии ф. и длинах сегментов X» •

Для функционала вспомогательной задачи имеет место аналогичное представление, а именно

^ _Д и

- ¿2иг*<(х) Ф • »•*>

где Е^ - среднее число обращений за к прогонов к блоку £ при выполнении к.с. ( , ¿=1,2,...,'» ).

Представление (1.2) функционала Р' является явным представлением функционала

, содержит нелинейные слагаемые и в общем случае неизвестные величины ( , £»1»2»...,.»» ). Выражение (1.4) напротив содержит величины Е^' , которые могут быть вычислены по результатам к экспериментов с программой. Здесь возникает вопрос: существуют ли условия, при которых оптимальное решение задачи (1.1) с функционалом (1.4) будет приемлемым решением задачи (0.1) с функционалом (1.2)?

Выражения (1.2) и (1.4) для функционалов основной и вспомогательной задачи несколько неудобны для того, чтобы дать содержательный ответ на поставленный вопрос. .

Особенности рассматриваемой в данной главе задачи позволяют вместо выражения (1.2) записать линейное по вспомогательным переменным Л-представление функционала Г' , а именно

* гс

-ЕС

«'«1

здесь булева переменная, значение которой равно

• значению функции ^-(х) при фиксированной матрице х , причём каждой матрица х 6 соответствует свой набор значений булевых переменных о)^¿'=1,2,..., ). Замена осуществля-• .ется за счёт введения в ограничения дополнительных 2.-|01П квадратичных соотношений.

Та же схема рассуждений позволяет записать и линейное Л-представление функционала Р вспомогательной задачи (1.1).

В-§ 3 главы показано, что при весьма общих ограничениях на исходную информацию оптимальное решение вспомогательной задачи (1.1) является приемлемым решением основной задачи (0.1), при этой число прогонов программы к должно быть обратно пропорционально квадрату радиуса устойчивости задачи (0.1). Данный факт имеет лишь теорэтичаркий интер®с, поскольку в ■'выражение для радиуса устойчивости входят неизвестные величины ^(г 0 ,1=1,2,...,« ). В. главе У на основе полученных в данной глава результатов приводятся условия более приемлемые с практической точки зрения,при выполнении которых опти-. ыальное решение вспомогательной задачи будет приемлемым ре' шанием (в сшоле заданной точности л надёжности)основной задачи. ' Глава НТ поешцена нэкогорым задачам,непоерздетвенно связанным с исходной задачйй(задачей сегментации) .точнее говоря тем, которые'пвляатся её пряшми обобщениями.

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

программы можот находиться лишь один сегмент(страница) программы.

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

Итак, пусть сеть состоит из м+1 узлов ,>» ,У",

информационно связанных друг с другом. Среди этих узлов выделен один вспомогательный узел У , называемый центром, который формирует информационное поле сети в любой момент сеанса перо-дачи информации от одного из исходных узлов , "V]! ,..,,% к одному из узлов, также входящих в множество ,т^ ,...,Т*

В узлах ,..., ТГ„ . передаваемая информация подвергает-

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

Следует отметить, что в любой момент t сеанса стоимость передачи информации внутри информационного поля равна нули, а передача информации к узлу, на содержащемуся внутри информационного поля происходит через узелУ(центр) и стоимость такой передачи равна "I". Пусть далее каждому узлу приписан вес.

Рассмотрим вопрос формирования информационного поля t ) для фиксированной информации в произвольный момент t сеанса. Пусть узлы сети Т4 ,Уг покрываются конечным числом

множеств М ,М1,...,Мг такими, что

I. {у;, г, ..... у*} . О М;

2. Л MJ , I*}

3. Суммарный вес узлов, входящих в произвольное множество ^ не превосходит веса й^ этого множества , j =1,2,... .

Естественно называть множества ,...,Мг сегментами, а всю совокупность этих множеств сегментацией сети . В данной части диссертации рассматриваются только те из них, которые удовлетворяю^ 1)-(3). Информационное поле ± ) сети в виртуальный момент £ сеанса обработки информации может формироваться например, по следующему правилу: в Иг( + ) входят лишь те сегменты из М1,М1,...,М1 , которые входят в рабочее множество V/ ( т , Ь ) сегментов сети, в виртуальный момент . (Рис.2)

Задача состоит в том, чтобы минимизировать среднюю стоимость передачи информации за счёт удачного покрытия узлов "/¡» множествами ,... при условиях( 1)-(3).

Если информационное пол« 1?с( t ) сети формируется по правилу рабочего множества, то для этого случая по аналогии с главой 2 может быть записан в явном виде функционал средней стоимости передачи информации. Соответственно определяются- и условия, гарантирующие, что оптимальное решение вспомогательной задачи будаг приемлемым решением основной задачи.

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

В § 3 главы рассмотрена задача сегментации блоков программы при нефиксированном числе сегментов (р^и) в случав стратегии рабочего множества, при этом сегменты составляются из целого числа блоков программы* Существенным ограничением здесь является лишь размер рабочего множества, который не должен превы-. шать здесь значения некоторой константы. Считаем также, что выполнено условие <А) (каждый блок программы входит в состав лишь одного сегмента).

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

Следует заметить, что практически все основные результаты, полученныо в глав» I и параграфах 1,3 главы II базируются на специфических особенностях стратегии Возникает'вопрос, какие именно внутренние свойства стратегии ^ ^ обеспечивают эти результаты. Ответ на данный вопрос дан в параграфе 2 главы

и сформулирован в виде свойств резидентных множеств, порождаемых стратегией.

Глава четыре посвящена определению условий.гарантирующих построение точных решений задачи сегментации, на основе кластерного [2,4,9} и алгебраического подходов (3J .

Применение алгебраической теории Еуравлёва [3J к задаче сегментации программ позволяет построить модели, с помощью которых даётся положительный ответ на вопрос о существовании таких условий, а результаты автора, изложенные в данной главе, можно рассматривать как развитие алгебраической теории также и в прикладном аспекте.

Прежде всего, здесь следует отметить, что непосредственное

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

В связи с этим возникает задача синтеза корректных моделей [3} на основе кластерного подхода [93 к исходной задаче.

Следуя этой цели, в главо 1У привлечён для решения задачи сегментации алгебраический подход[3J . Применение алгебраического подхода для задач распознавания и классификации, как известно, первоначально предполагает применение алгоритмов из исходного множества (например а.в.о. или flp.[3j ) к задаче распознавания, объекты в которой - суть точки классического признакового пространства. В задаче сегментации отсутстйует классическое описание исходных объектов, что существенно затрудняет непосредственное применение алгебраического подхода к задаче сегментации и в данном случае требует специальной адаптации метода опорных подмножеств [I0.9J .

Б диссертации рассмотрены лишь теоретические аспекты применении алгебраического подхода,основанного на использовании метода

9/ lyp-'iг-;:*в D.H.,Гнусов Р. Об одном способе уточнения таксономии при nevenu распознавших методов типа голосования.ЖВМ и МФ.т.П, , !f 5.1971.

10/ ллртг.-гг Г.И. ,!"амилон U.M. ,Туляганов U.E. Алгоритмы вычисления гцгч!.-,ч: и гх применений,- Т. 1974, -П9с.

опорных подмножеств к задаче сегментации.

Основной трудностью здесь является содержательная интерпретация параметров алгоритмов вычисления оценок(а.в.о.) [Ю ]. Из анализа содержательной постановки исходной задача следует, что для построения функции близости нужно использовать матрицу близости 1=( , где число взаимных ссылок

мезду блоками ^ и , но определение системы опорных множеств вызывает серьёзные затруднения, поскольку при классическом случае такие множества строятся как специальные подмножества множества признаков. Отсутствие классического признакового пространства затрудняет.например, применение здесь опорных ■ множеств тестового типа.

Для задания опорных множеств и их весов в § 4 использовано понятие, ограниченных локальных интервалов (В1*1), введённых С 5 ]при исследовании свойства локальности программ. Это позволяет .во-первых, рассматривать взаимодействие пар блоков

, ив по всей трассе данных в целой {I )), а по некоторой системе множеств Л , используя п отом случае последовательность матриц ¿1 , ^ )} , (О £ Л , Во-вторых, описав некоторую обдую схему, не зависящую от конкретной стратегии, мояшо также через систему множеств Л учесть в каядом отдельном случае влияние выбранной стратегии замощения страниц, если в качоство элементов взять резидентные множества, появившиеся по мера выполнения программы.

СлодуяС 5 ограниченный локальный интервал (ВII) -это пара (А4 ,Ц ), где -множество активности программы, а 1, -время жизни множества . ■

Заметим, что существуют две возможности применения а.в.о. для задачи сегментации. Первая возможность- нопосрадственное

применение с учётом того, что для реальных программ имеется исходная сегментация Е, блоков программы по страницамС сегментам) виртуальной памяти. В втом случае формально считаем, что Ее найдена с помощью некоторого кластерного алгоритма А* . Последующее применение алгоритма распознавания А^а.в.о.), следуя Г 9 |даёт новый кластерный алгоритм « Ай ) с лучшим

качеством разбиения. Считаем тогда Ев начальным приближением для А, .В случае необходимости к множеству блоков, образующих Ее ,

можно применить алгоритм Ак ,т.е. один из известных для . задачи сегментации кластерных алгоритмов [4,2 1,а ужо затом, следуя процессу Г 9 ], как уточняющий алгоритм применить А^ . Как видно, в любом из этих случаев имеет место суперпозиция алгоритмов кластерного А« и распознающего А^ .

Вторая возможность состоит в том, что на первом шаго процедуры сегментации за каждым сегментом закрепляется по крайней мере по одному блоку программы (обучающая выборка на данном шаге). Остальные блоки образуют рабочую выборку, которая сегментируется итеративно, следуя^Ю}.

В §4 глагы на основе|3,9,10,Дописана модель ШТ а.в.о. для сегментации блоков , I» по сегментам Д,

При этом считаем, что ни длины блоков £, & ,...,^ ни длины V, сегментов не изменяются во время выполнения

программы. Задаётся:

I) система опорных множеств Д -{•»>) ; пусть { А^]-совокупность множеств активности программы, тогда в качествебудем использовать множества активности Д^ € { А^,т.в. Л С. ;

2) функция близости В£ (£., ); пусть ^ , -блоки, и) -опорное множество", ^ t¿j )-число взаимных ссылок между блоками ^ и ¿у в течение интервала жизни множества*^ ;

О <е ¿1; тогда В 1,(4» ^ ) определяй так:

I, если Ти ( к , ) > £ • г,у

О в противном случае. Можно также определить В1, ( ^ ) по-другому:

Л. если 4« ^ )->?■/-<*

. в1(М/)=

1^0 в противном случав; целое из-^О, мах1,уО .

3) параметры - веса и оценки распознающих операторов Вес р ( о).) опорного множества и) зададим как функцию от - времени жизни множества ь) и длин сегментов <•'», <-2 ,..., , составляющих и) , а именно:

р(и) ) = ь/

= Ч, +V

Т^ - время жизни сегмента^, Т^ - длина сегмента ^ = 1,2,...,|и| . Вес блока ^ определим:

( )/ , • 7=1,2....,/, .

Близость между блоками , ^ по множеству и! зададим так:

§ = ги( 4 , $ )/( г (,7^ )+ г(, £ ))

(если ,7(§) + I (, ^ =0, то полагаем Ду = <</ , ))

или

____^ ( . 4 , ^о,

II/ Куравлёв С.И. Корректные алгебры над множествами некорректных •(эвристических) алгоритмов.-Кибернетики3,197(3г.

Где t ( êi ,1 ij ) - суммарное число взаимных ссылон мэжду блоками êi и не êj .

Пусть блоки ^ , iljt ,... .¿^входят в сегмент , тогда оценку Рх ( êi ) блока ^ ва сегмент зададим так:

где x4e(0,l} ..•

4) решащее правило. В данной главе в качестве решающего

# '

правила взято корректное решающее правило С из [ 3,11J :

! I, если rLj > оtj

. c'(Z>» IIAjll, лчп.°> 0СЛИ *

0СЛИ c«j £ VLj ± c9j

Используя универсальность схемы а.в.о. и принципов, заложенных при их построении[з,10], в диссертации обсувдалась концептуальная возможность применения а.в.о. для задачи сегментации программ. В связи с этим интересно заметить, что применение для данной задачи некоторых других распознающих процедур, например типа "Кора" со сходными с а.в.о. параметрами, здесь затруднительно.

Следует заметить, что если длины сегментов одинаковы, то имеем обычнун последовательность страниц ^,...,,5*, .

Касаясь п.1) описания модели

Ж,

отметим, что множества активности могут быть определены по результатам экспе-

риментов с программой с различными данными^ 1,2,5,6 ]. В качестве опорных мнояеств , учитывая иерархию локальных интервалов, можно взять те АА £. f А^, которые в совокупности образуют базу множества |l,2,...,w} (cM.fi* ^ В качество элементов О £ Л могут быть, взяты также' резидентные множества из[4 ].

Наряду с моделью ШГо алгоритмов вычисления оценок в § 4 , описана^',более общая модель а.в.о., отличающаяся от

способом вычисления оценки блока за сегмент а именно:

1\а ) = + х«Гг'(<).

где х» , х{ £ {-1,0,1] ,

(г ( 7/; , г ( ¿1, ))/ £ ),

ВЛ ( ¿1 , ё} >= I - В$ (/;, § ), .4,... Л}*

Предполагается, что в модели параметры х^ , а

также параметры. Ц-I ?1t Рг , ру могут сво-

бодно варьироваться в заданных для них пределах. В качестве рэ-тающего правила взято корректное решающее правило С. Следуя [з,И3 , вводя соответствующие операции на ЭТГ .нетрудно задать , алгебру алгоритмов

порождаемую моделью а.в.о.и корректным решающим правилом С* .

В § 5 рассмотрена модель а.в.о. - обозначим её через-которая получается,если в модели

ш формально положить

=1 ( 1,], =1,2.....и ), х; -х, , - х0 '

( 1=1,2,...,т ),х,, х,б(0,1], а функцию близости определить так: [1, если ^ , ¿') ,

^ в противном случав;

здесь 0 4 £ £ I .

Итак, пусть блоки , £ ,..., каким-либо образом разбиты на непересекающиеся сегменты ..т.е. задана начальная сегментация Е,. Будем следовать также понятиям и обозначениям из£ I ,3 ]. Пусть Л - база множества [1,2,...,/п) ; ?•=<!„ ,Х*> -задача, в которой Xй , ,... } , е шад -алгебра алгоритмов, порождаемая моделью???^ и корректным решающим правилом С* . Итак, пусть Х"« Д 1 в 5 5 введено

Определение I. Пусть 2 ■= < Г,, Х*> -задача сегментации, Начальная информация 1.называется Л-существенной для £' , если для всякой пары блоков 4 , £" из ХН найдутся блоках (Ш,Г> и множество шеЛ такие, что ¿', 4 ).

Определение 2. Задача сегментации 2 = ¿£,ХЙ;> называется Л -регулярной, если:

1)

2) . У-1.2....."> ,

3) для всякой пары блоков £ , 4 из ХИ , для всякого выполнено: .

4) Г„ явяляотся-Л- существенной для ? •= <: /,,х">.

С учётом[1 ,3 }в § 5 главы доказана основная для Главы 1У

Теорема.I. Алгебра алгоритмов штл порождаемая'моделью ТИ^ 1 корректна над множеством Л -регулярных задач.

Пусть £ - задача сегментации, а Л. - база мно-

и'егтг.а (1,2 , Ь'сли задача ¿г является -регулярной,

то ;шгко указать модель а.е.о., а именно , что алгебра

алГ|'}'1:т!■!'.">I* ] содержит корректней для 2 алгоритм.

Заметим, что условия (3),(4) определения Л- регулярной ' задачи имеют ясную содержательную интерпретацию.

Следует заметить также, что полученный основной результат нетрудно применить к классической, графовой постановка зццачи сегментации. Для этого случая требуется в качестве JL взять базуJ2, = {fl| ,{2} ....{f^} и если исходная задача

j? являатся Л0- регулярной , то в алгебре {WÇ(J0,x0tXi > Для задачи £ может быть построен

корректный алгоритм в стандартном виде £ И] .

Полученный осноеной результат главы позволяет исследовать подробно ряд различных вариантов определения функции близости, что и сделано в § 5 и § 6 главы.

В § 5 главы доказана корректность алгебрц SifW^i» порождаемой моделью ,t ,i,p,(f )' операторов вычисления оценок (о.в.о.), функция близости в которой связана с матрицей близости 1 =( ) через величину мах и , ) '.] (uiél). Желание на этом пути показать корректность алгебры Щ. , порождаемой моделью о.в.о., в которой функция близости учитывает влияние каждого сегмента ua U) в отдельности , приводит р . следующему её описанию :

пусть и)&Л и сО »( к4, lclt.,. ,кцл ),

i , ê' )- число взаимных ссылок между блоками é", в течении интервала жизни сегмента k^ , "ÎT =1,2,..., M £=( <S1 ,¿1 £м)-вектор ророговых параметров: 0 i ¿±1 «ax£v,

"t=I,2,..., m . Определим функцию близости между блоками и /j по опорному множеству со £ Л следующим образом

&,если U^L-hj-I^Ji

<It6)

О, если хотя бы одно из неравенств нарушено

Б соответствия с новой моделью о.в.о. в § б по аналогии с § 5 введено понятие Л - детерминированной задачи и доказана корректность алгебры зит-}, поровдаемой моделью с функцией близости (1.6) над множеством Л -детерминированных задач сегментации.

Еще раз отметим, что хотя а.в.о. и сам метод опорных подшокеств использовался при решении значительного числа приклад,ньгх задач, но в большинстве работ предполагалось, что исходные объекты - суть точки и -мерного признакового пространства. Содержание данной главы показывает, что сфера применения а.в.о. и алгебраической теории [ 3]. существенно шира.чем её традиционное понимание.

В главе 5 на основе результатов, полученных в главе Ц рассмотрена задача определения условий , выполнение которых гарантирует, что оптимальное решение хк вспомогательной задачи (1.1) является ¿ -оптиыальнымСприемлемым) решением основной задачи (0.1) в смысле оценки

Р {|^(х',г ) - Р'(кк ,-г )!<£}> I - % _ (1.7)

гдй . х* -оптимальное решение задачи (0.1) , £>0, ^>£(0,1). Эти условия, в первую очередь, связаны с ограничениями'на случайные величины ( ¡- =1,2,..., П ) и с

оценкой числа прогонов программы , при которых достигается, оценка (1.7) ,

В параграфах 1,2 соответственно для ^ $ стратегии исследованы независимая и марковская модели поведения программ

]. Обоснованием результатов отих исследований является устойчивость оптимальных ресений задачи (0.1). Показано, что число прогоноз программы является функцией радиуса'устойчивости

( ¿-устойчивости) задачи (O.I). При этом первый случай т.е. , случай зависимости величины к от радиуса устойчивости J>0 зада- • _ чи (0.1) имеет лишь теоретический интерес поскольку в выражение для j>„ входят, в общем случае,неизвестные величины

i=I,2,...,и ). Второй случай, т.е. случай зависимости оценки для k. от величины радиуса ¿ - устойчивости более приемлем с практической точки зрения, поскольку вычисление радиуса ¿-устойчивости задачи (0.1) не представляет сложности.

В связи с изложенным в диссертации подходом для решения задачи сегментации в случав У $ стратегии в данной главе приводится описание процедуры Q для решения вспомогательной задачи (I.I), в которой пpeдnoлáгaeтcя использовать в качестве составной части известные методы дискретного программирования; В качестве входных данных здесь также использутся строки ссы,лон -на блоки, полученные в различных прогонах программы с различными данными.

Кроме того, следуя подходу, изложенному в §§ 4,6 Гл,1У,т.е. подходу, основанному на применении а.в.о. к задача сегментации . в данной главе приводится также описание процедуры 'ABO,С. При этой предполагается после соответствующей перекодировки входных данных использовать некоторые стандартные подпрограммы (например, ' пакета ПАРК t 8 } ), реализующие а.в.о. £ 3,п]' .

ЗАКЛЮЧЕНИЕ

В диссертации предложен и разработан новый подход к решению задачи сегментации программ, основанный на применении к исходной задаче алгебраической теории Журавлёва[3} •

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

- отразить при сегментации свойство локальности программ. Для этого предлагается пси определении опорных множеств (л)С Л использовать понятие ограниченных локальных интервалов (ВЬ1д ), понятие введённое Ыа/Нхо*/ V/. и Ва^золУ Л.Р. для исследования феномена локальности программ.

На данной основе

- описаны модели Шд , , Ъ^Г,! операторов типа вычисления оценок для реашшя задачи свгнонтации программ.

Содержательная интерпретация параыотров а.и.о. для задачи сегментации программ позволила

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

может быть построен корректный алгоритм, т.е. алгоритм, дающий точное решение задачи сегментации;

- описать множество Л-регулярных задач сегментации;

- показать корректность алгебры ШЩ}, порождаемой моделью

щ о.и.о. над множеством Л-регулярных задач. Данный результат, . в своя очередь, позволил рассмотреть другой вариант определения

определения функции близости при сегментации и показать

- корректность алгебры над множеством Л -детерминированных задач.

Полученные в диссертации результаты можно считать развитием алгебраической теории £зЗ также и в прикладном аспекте. Важно, что это исследование затронуло случай неклассического описания исходных объектов, что в свою очередь раздвигает рамки применимости как метода опорных подмножеств, так и самой алгебраической теории и показывает, что сфера применимости а.в,о. и алгебраической теории [з] существенно шире, чем её традиционное понимание.

Специально изучен случай стратегии замещения Для данного случая при достаточно общих ограничениях найдец явный вид функционала задачи сегментации и системы ограничений, задающих множество допустимых сегментаций. Точнее говоря, найден явный вид функционала основной и явный вид функционала вспомогательной задачи; ■

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

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

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

При наличии соответствующего программного обеспечения для а.в.о. (например, пакет ПАРК) программная реализация алгоритмов сегментации, построенных на основе разработанных в диссертации моделей, не представляет принципиальных сложностей.

В заключение автор выражает глубокую благодарность своему научному консультанту академику Куравлёву Юрию Ивановичу за постоянную поддержку работы н советы, позволившие значительно улучшить её содержание4

Автор глубоко признателен всем сотрудникам отдела проблем распознавания и методов комбинаторного анализа ВЦ РАН и.лаборатории "кибернетические методы в информатике" Научного Совета

9 И

по комплексной проблеме Кибернетика за поддержку данной работы. Автор искренне признателен А.Л.Сахарову, обратившего внимание автора на задачу компоновки программ.

Основные результаты диссертации опубликованы в следующих

работах

х

I. Дюсембаев A.E. О корректности алгебранчеокиз замыканий распознающих алгоритмов типа "тестовых".-НВМ и L3,t.22, » 6, 1982, с,1491-1499. ;

2* Дасембаов А.Е. Об одном подхода к задаче сегментации программ.-ДАН РАН, т.329,В б, с.712-714.

3* Du-semCwv A.t. Correct ñodsPs «/ Afyerithras -for Program btymeAatittf, l»t.J. Paiter/j ñeccjtfliio// W Jnajc Analysis.

ITS A , vrj , tfS , Í393 ,j>f>.iS?-304 ,'

4. Dustnifaev A.e. Statist ¡CAÍ modeh optmizdisM с/ systems olrirtuat menu ry *¡tt sMqy. С 0 M PS TA T ê1! t I¿st. Symp. t i JSv .

5. Дюсембаев A.E. Переструктурирование програет в ЭВМ о виртуальной памятью. Сб. трудов ХУШ Всесоюзной околы по автоматизации научных исследований, АНН 84, Вып.2,1986,0.141-145.

6. Дюсембаев А.Е. Об аналитическом виде функционала задачи сегментации. Тезисы докладов Мездународцой конференции "Висо-

.копроизводительные многопроцессорнхш систекн". ИЛУ РАН и №."! АН РК, Алма-Ата,1991, с.45.

7. Дюсембаев А.Е. Синтез оптимальной структур» программ для енс- . тем с У S стратегией обмена,- Ц ¡ , ВЦ РАН,1994,-52с. .

8. Дюсембаев А.Е. Полныа замыкания операторов внчпсления оценок над дискретными задачами распознавания. I Всессазноо совещание ' по статистическому и днекратному анализу нопиоловой информации, экспертным оценкам н дискретной оптимизации. Тезисы док- , ладов., М-А,1981,с.355-35б.

9. Дюсембаев А.Е. Синтез корректных алгоритмов в замыканиях распознающих алгоритмов с представителышми наборами и системами опорных множеств.-ЖВМ и М&,т.23,1> 6,1983,0.1487-1496.

10.Дюсембаев А.Е. Условия оптимальной сегментации программ.-В сб.Распознавание,классификация и прогноз. Ежегодник РАН, Вып.5,1994,РАН,с.

II.Дюсембаев А.Е. Условия разрэпямости операторного уравнения для задачи сегментации программ о началышмн операторами типа вычисления оценок. ВЦ РАН,1994,-21 с.