Введение к работе
Актуальность тыл*. Как известно,круг проблем,связанных с оценкой производительности и управлением вычислительным процессом в ЭВМ, чрезвычайно широк и составляет предмет исследования отдельного научного направленияfl,2j, в котором именно программы часто выступают r качестве пенсійних объектоп исследования.
Одной из интересных задач в теории управления вычислительным процессом в ЭВМ является задача сегментации программ [i ,2J. Первоначально, как правило, под задачей сегментации било принято Понимать задачу разбиения последовательной программы на вэаимнозави-еимыл по управлению и информационно!по данным) части - блоки,секции, сегменты и т.д., в соответствии с. той или иной целью. В страничных системах с виртуальной памятью, учитывая,что в любой момент выполнения программы в осноиноЙ памяти(ОП) находится лишь некоторая часть страниц программы, такой палью может быть :
- минимизация Функционала ерэпнего числа страничных отказов!т.е.
среднего числа обпапюний к страницам программы ,во вспомогательную
память);
минимизация среднего размера ОП, отводимого программе;
минимизация среднего времени выполнения программы;
минимизация фуккпионала ПГОСТШСШ*ВРЕМЯ и лр. Для параллельных систем одна из основных целей при сегментации- ато разбио-
I/ Авен 0.П.,Турин Н.Н.,Коган Я,А. Опенка ігочсства и оптимизация вычислител*ных систем.- М: Hayr'i , І9ТО, -'V'Ac.
II Форрари Д. Опенка прпизропителыюсти вычислительных систем.-М: Мир ,1901, - .'ИЬс.
_4-
ние последовательной программы на части - ветви параллельной программы и сегментирование самих ветвей.
Для систем с виртуальной памятью с определённого времени наряду'с терыином"сегментация" используются термины: переструк-TypHpoBaHHef2j, реорганизация и др. При этом считается, что программа состоит из конечного числа блоков, располагаемых на страницах (сегментах), виртуальной памяти. Под оптимальной сегментацией понимается такое расположение блоков программы по сегментам (страницам), при котором достигается экстремум заданного критерия качества.
В диссертации рассматривается именно такая интерпретация задачи сегментации программ.
Экспериментально было обнаружено[і,2J, что наибольший эффект при сегментации проявляется у программ с так называемым частым ( постоянным) прогоном, например, у трансляторов, больших системных программ и др.
По мере формирования и развития отдельного научного направления - "Оптимизация вычислительных систем" в его рамках
для задачи сегментации сложились ряд методов, которые условно иожно.разделить на три подхода: подход, основанный на синтезе дискретных, аналитических моделей; графовый, а также кластерный подходи, которые позволяют, в основном, получать лишь при-'блйкённыв решения при неизвестной погрешности получаемых решений. Точные решения гарантируются лишь в весьма частных случаях.
Первый подход сводится к синтезу функционала и ограничений, описывающих множество допустимых сегментаций для исходной задачи.' Графовый подход основан .на представлении программ в виде взвешен-
ного, полного неориентированного графа (2]. Кластерный подход основывается на представлении задачи сегментации как задачи, кластерного анализа 2,3,4] , Исходя из этого, первоначально для решения задачи сегментации непосредственно применялись методы дискретной оптимизации, кластерного анализа и теории графов. Позже при синтезе алгоритмов сегментации стали учитывать накопленный экспериментальный материал. Было показаноf 7,2], что как комбинаторная задача, задача сегментации в общем случае, принадлежит классу ІЇР -полных задач и поо*вляет свойства последних в вычислительных экспериментах fl»2 J. Ряд работ были нацелены на то, чтобы учитывать при сегментации локальность программ [5 ] , стратегию замещения [б]и др. Здесь же заметим, что работы по сегментации программ восходят к известным результатам по теоретическому программированию Ляпунова Л.А., Янова Ю.И., Калужнина Л.Л., Карпа Р., Для данной работы основную стиыулирущую роль сыграли результаты
3/ Журавлёв Ю.И. Об алгебраическом подходе к задачей распознавания и классификации. - В сб. Проблемы кибернетики. Вып. 31,1978г.,с.5-08.
4/ MftsiUo. Т., $hiota И., tfcjuehi X., Ohki Т. ОрИтіглЬрАї of projram crjatfiiatic* 8y tfaster uHtiysfs.Pret. IFIP Cc»$ress lS*f, pp. і И-ЗІ6.
5/ rWisew A.\J., bedsotf A. P. Characteristics ef Pre) ram Locatities. Сопіти*, of ACM, /1*y і 3f6 , її U, S'5', PP. 2iS- 2Sf
G/ VtMA/iMj P. VJorlrivj sit; Pasta*/// Present 1EFE Trays, ge-fivare Є**$. Y$-$, //J, 1930, pp. Ії-St.
7/ Гэри'М., Джонсон Д . Вычислительные машины и трудноретаемые задачи. - П.: Мир, 1982.
авторов:
Samamcortky С, V., Сотец*и. 1.^/-Поспелоьа Д.А., Косарева В.Г., benfisi А: Т., Реь/ffteU &.,Ьоь1еТ.,
вп'*л» U К., Феміу P., Hd-fie/d -V.J., QeraU I, BaerJ.L Сол^Ц к. fi., Ьао H, Pv Яйцо!:* Ь.% їегш\Т>., ttasuXy.,
^iidt* H.,M>jucki Y.,0^1^., АвєнаО.И., Когана Я.А. .ГуринлН.Н., Игиатуїценко В.В., Ьальковского Б.А., Касьянова В.И., Arthartl її., Миренкора Н.Н., totopurVo. и др.
Данная работ», является частью исследований, выполненных в рамках темы" Я&аработкд и реализация системи технологий распознавания на основе алгебраических и логических методов" (НИР 836 ) Тема диссертации тесно свяаана с планом госбюджетных работ: "Дискретные н наклассические модели обработки информации и принятие решений"( Тема 1.13.12.6., ИГР 0І8В.026033 ) Цель работы. Основной целью работы является синтез математических моделей сегментации, с помощью которых могут' быть определены точные решения задачи сегментации программ. В диссертации разработаны и исслэдованы:
модели сегментации программ для систем с виртуальной памятью со стратегией V/p (рабочие множество[ б J, рабочий комплек-rf I J)
модели,основанные на применении алгебраической теории{ 3 Jk задаче сегментации программ.
Наличие тьких модвлый позволяет определить условия,при выполнении которых гарантируется построение точных ( -точных) решений задачи сегментации.
Следует отметать, что стратегияУ$ является основным представителем группы алгоритмов обмена с изменяющимся во времени числом активных сегментов программы и служила основной
- ? -
при определении других алгоритмов этой группыyt1IA/,PFF,/rk'lflfh/l5. Накопленный экспериментальный и теоретический материал позволил утвврждатьСсм.Д.ФаррариС 2 ,стр.4153). что"...стратегия рабочего множества является одним из наиболее удачных средств самонастройки, когда-либо использовавшихся в вычислительных системах." Как отмочено в[ 1,стр.194 J размер рабочего множесгвя(комплекта) это показатель качества страничной программы, на зависящий от алгоритма распределения виртуальной памяти. Концепция рабочего множества играет особую роль в теории управления вычислительным процессом и значительное число публикаций посвящены исследованию свойств рабочего множества и его обобщений^ б J. В связи с этим решение задачи сегментации в случае W р стратегии имеет также особый интерес.
Научная новизна. Основные результаты, содержащиеся в диссертации являются новыми. В диссертации предложен и фактически разработан новый подход к решении задачи сегментации программ,основанный на применении плгеОряичеекой теории Журавлева к исходной задаче. Изложение в диссертации результаты в этом направлении можно рассматривать также и как развитие данной теории в прикладном аспекте.
Специально изучен случай У $ стратегии обмена. Для данного случая при весьма общих ограничениях удаётся выписать явный вид функционала задачи сегментации и системы огарничений, задающих множество допустимых сегментаций.
Заметим, что при всём многообразии работ по сегментации, для і/$ стратегии ранее на был известен ни явный вид функционала задачи сегментации, ни явный вид ограничений, задающих множество допустимых сегментаций.
. Найденные автором результаты позволили определить условия, га-
рантирующие построение точных(-точных) решений задачи сегментации.
Практическая ценность.Определяется известным прикладным характером основных постановок и важностью решённых в диссертации прикладных задач.
Реализация. На основе полученных в диссертации результатов могут быть созданы программные модули как составные части пакетов прикладных программ. При наличии соответствующего программного обеспечения, реализующего а.в.о.[б] и алгоритмы дискретной оптимизации, реализация процедур сегментации, разработанных в диссертации, не.представляет принципиальных трудностей.
Апробация. Основные результаты диссертации докладывались на ряде всесоюзных и международных конференций,а также на научных семинарах, в том числе: на научном семинаре лаборатории проблем распознавания ВЦ РАН(1982,1983), на научном семинаре по теории автоматов мех.мата МГУНУ Конференция молодых учёных МГУ,1982), на I Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам, и дискретной оптимизации Алма-Ата, 1981); на Советско-немецком семинаре"Дискретная математика и её приложения в кибернетике "(Алма-Ата,1985); на научном семинаре кафедры математических основ управления ЫФТИ(ноябрь,1984); на международной конференции "Высокопроизводительные вычислительные системи в АНИ"(Алма-Ата,199I), на международной конференции по статистическим наукаы(Рабат,1992), на семинаре отдела проблем распознавания и методов комбинаторного анализа ВЦ РАН(Москва,1994),на. научном семинарвНИИСИ РАШМосква,1994) Публикации. По теме диссертации опубликованы II печатных работ. Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Работа выполнена на 243 страницах машинопечатного текста, содержит 9 рисунков и 8 таблиц.
Список^, литературы включает 186 наименований.
, 8/ Пакет, прикладных програш для решения задач распознавания и классификации.(ПАРК). М: ВЦ АНСССР.,1981г.
