3659 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ПРОЕКТИРОВАНИЯ ЭВС

Лабораторная работа № 1

 

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

НА БАЗЕ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

ВВЕДЕНИЕ

 

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

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

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

На  рис. 1 показана многопроцессорная  система управления технологическим процессом с общим полем внешней памяти.

 

 

 

 

 

 

 

 

 

Рис. 1

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

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

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

I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

I. I. Модель вычислительного процесса. Постановка задачи

Имеется множество А={ , i=} задач, и известны средние времена i решения каждой из задач аi А, а также возможное раннее время  выполнения  и возможное позднее время  выполнения .

Под  будем понимать момент времени, раньше которого не может быть начато выполнение задачи .

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

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

 

Для решения каждой задачи требуется информационный массив данных . Тогда ij – переменная, принимающая значение I в том случае, если возможно одновременное обращение к массивам , и значение 0 в противном случае.

Допустим, что известно среднее время tn потерь для случая, когда произошло одновременное обращение к  , и эти два массива расположены в одной секции ОЗУ. Предположим, что одновременное обращение происходит всякий раз, когда  ij=I. Тогда общее время t, необходимое для получения информации из ОЗУ,

 

где  - время, затрачиваемое собственно на обращение к ОЗУ без учета потерь на ожидание;

 

Условие оптимального размещения информации в секциях ОЗУ можно записать в виде

(1)

При очевидных ограничениях вида

 

где - объем массива ;  - объем секции памяти.

Построим на множестве А={, i= } граф  у которого вершины  соединены ребром, если  ij=I, и не смежны в противном случае. Тогда данная задача может быть сформулирована как следующая задача на графе. Произвести разбиение графа G на m подграфов (по числу m секций ОЗУ) так, чтобы:

1) сумма ребер всех подграфов была минимальной;

2) сумма объемов  (весов вершин графа G), вошедших в некоторый подграф (секцию ОЗУ), не превышала объема этой секции.

 

I. 2. Определение вероятностей совместного решения задач

Описанные в I.I модель и постановка задачи достаточно просты и в ряде случаев вполне приемлемы. Однако для большинства практических случаев предложение, что задачи, для которых   ij=I, всякий раз решаются параллельно, слишком грубо. Здесь желательно ввести вероятности, с которыми задачи могут решаться параллельно. Удобнее всего это сделать, введя вместо ij=(0, I) переменные , принимающие значения в интервале [0, I].

Для определения  воспользуемся следующей методикой. Пусть для двух задач и   известны  причем <.

Положим ;  ,  равными соответственно среднему времени реализации задач и ; ; .

Примем  за начало отсчета. Пусть y – время начала решения задачи ui, х – задачи uj. Ситуация, когда задачи  и  решаются в конце интервала  и , изображена на рис. 2.

 

Рис. 2

 

Интервалы изменения x и y определяются следующими соотношениями:

(2)

 

(3)

Пересечение времен решения задач возможно при следующих условиях:

;                                                   (4)

.                                                        (5)

Соотношения (2) – (5) можно записать в следующем виде:

 

 

 

(6)

 

.

Каждое из неравенств (6) определяет некоторую полуплоскость Так, неравенство  определяет верхнюю полуплоскость, а неравенство  - полуплоскость, лежащую по одну сторону прямой .

Подробные построения для всех  приведены на рис. 3.

 

 

Рис. 3

 

Множество точек прямоугольника ОАВС означает всевозможные значения из множества  и , а множество точек заштрихованной фигуры есть множество только тех значений , для которых пересекаются времена  и  решения задач  и . Тогда , где  - площадь заштрихованной фигуры,  - площадь прямоугольника ОАВС. Нетрудно заметить, что в общем случае  нельзя выразить одним аналитическим выражением, так как в зависимости от соотношения  и  будут получаться различные геометрические фигуры.

I. 3. Алгоритм рационального размещения информации в секционированной памяти

Введем следующие обозначения:

А={, i=} – множество задач, составляющих вычислительный процесс;

G(A) – взвешенный граф, у которого две вершины , соединены ребром , если задачи  ,  могут выполняться параллельно;  - цена, приписываемая ребру  и характеризующая объективную возможность параллельного выполнения задач , . Элементы  заданы в виде матрицы . Отметим, что  связаны с  следующим соотношением:

(7)

где k – некоторый положительный коэффициент, приводящий  к  целому числу ;

- множество секций памяти ();

- объем секции ;

- объем массива , необходимый для реализации задачи .

Множество допустимых по объему отображений А в М определяет множество Q вариантов распределения информации в секционированном ОЗУ. Основным показателем качества того или иного варианта   является число конфликтных ситуаций (точнее, ожидаемое число) в системе.

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

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

.

Из этого выражения следует, что задача максимизации суммарной стоимости  внешних связей эквивалентна задаче минимизации суммарной стоимости  внутренних связей.

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

1. Из всего множества задач А={, i=} произвольно выбирается одна задача , которая образует  группу. При этом -я группа является некоторой моделью секции памяти объемом .

2. Имеется наилучшая “задача  –  кандидат” , которая помещается в ту же -ю группу. Наилучшей  “задачей  –  кандидатом” является задача, которая менее чем, другие задачи связана с группой   с позиции весов  дуг . Если этому условию удовлетворяет более чем одна “задача  –  кандидат”, то делается произвольный выбор. Затем ищется следующая “задача  –  кандидат”.

3. Процесс объединения “задач  –  кандидатов” в группу  продолжается до тех пор, пока суммарный объем  задач в группе не будет удовлетворять следующему соотношению:

,

где  - множество задач -й группы;  - объем последней наилучшей “задачи  –  кандидата” .

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

4. Выбирается любая задача  и повторяются процедуры пунктов I,2,3.

Таким образом, происходит размещение всего множества задач по кубам (секциям) памяти.