Эвристический подход к решению задачи сегментации программ

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

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

Напомним, что под задачей сегментации обычно принято понимать задачу разбиения последовательной программы на взаимозависимые по управлению и информационной части (блоки, секции, сегменты и. т. д) в соответствии с той или иной целью[2.]. Задача сегментации определяется как задача разбиение программы на части по страницам виртуальной памяти. Проблема заключается в том, что при размещении программы по сегментам виртуальной памяти каждый элемент программы получает свой адрес. Операционная система выделяет каждой программе некоторый участок основной памяти. Причем объем выделенной памяти меньше чем сама программа. По мере выполнения программы в памяти находятся копии страниц программ. Обмен между вспомогательной памятью и основной осуществляется целыми страницами, во время обмена центральный процессор переключается на выполнение команд другого сегмента, если во время выполнения программы происходит ссылка на сегмент программы, которая отсутствует в основной памяти, то происходит страничное прерывание. Выполнение программы прерывается. Из-за программ, в которые генерируют избыточное число страничных прерывании. При снижается производительность самой вычислительной системы. Как известно существуют различные подходы разрешение проблемы избыточной генерации числа страничных отказов. Алгоритмы основанные на понятии рабочего множества сегментов предложенные Питером Деннингом обеспечивают уменьшение числа страничных отказов. Если имеется структура программы т.е. программа состоит из  некоторого числа блоков, то за счет переструктурирования программы можно улучшить поведение и локальность самой программы. В связи с этим интересен математический подход к решению задачи сегментации в классической графовой постановке. Идея графового подхода заключается в представлении программы в виде полного взвешенного графа. Вершинам этого графа соответствует блоки программ, ребрам - передачи управления или информации между блоками программы. Вес вершины определяет размер блока программы, а вес ребра число передач управления или информации между блоками. Задача состоит в разбиении вершин на множества так чтобы сумммарный вес вершин попавших   в   одно   множество   не   превосходил   веса   множества   т.е.   страницы. А суммарный вес ребер между разбитыми множествам вершин был бы минимален. На основе графового определение задачи сегментации была построена модель задачи сегментации дающию возможность испольовать методы кластерного анализа. Принципиальную возможность применение кластерного алгоритма обосновано в работе [2]. Приведем формальную постановку задачи.

  

 

 

Литература

 

  1. Журавлев Ю.И.     Корректные    алгебры    над    множествами    некорректных (эвристических) алгоритмов // Проблемы кибернетики. Вып.2. 1978.С. 35-42.
  2. Дюсембаев А.Е.    Математические     модели    сегментации    программ.    -М.: Физматлит, 2001. 207с.
Год: 2012
Город: Алматы