Билет №6

1. Планирование параллельной распределенной обработки данных.

2. Модель назначения объектов на узлы. Частоты запросов к объектам. Длины объектов. Производительность узлов. Производительность каналов передачи данных.

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

Пусть N={1,…,n} — множество узлов, M={1,…,m} — множество объектов. Длины объектов опишем множеством L={l₁,…,l_m}. Эти длины определяют размеры памяти, необходимые для размещения объектов на узлах.

Пусть Q={q_ij|iN, jM} — множество запросов к объектам, принимаемых или генерируемых на узлах. Частоты появления запросов опишем множеством F={f_ij|iN, jM}, где f_ij — число запросов q_ij к объекту j с узла i в течение времени наблюдения Time_Period. Общее число запросов, поступивших за Time_Period, обозначим через (F). В ответ на запрос пересылается либо весь объект длиной l_j, либо его часть длиной send(l_j).

Узлы распределенной системы характеризуются параметрами. Пусть S={s₁,…s_n} — множество объемов памяти на узлах. Для того чтобы все объекты могли быть размещены, суммарный объем памяти (S) должен превышать суммарную длину объектов (L). Собственные времена обработки запросов на узлах опишем множеством R={r_ij|iN, jM}. Величина 1/r_ij есть число запросов к объекту j, обрабатываемых узлом i за единицу времени. Узлы различной производительности обрабатывают запросы к одному объекту за различное время.

Если запрос к объекту j принят или сгенерирован на узле k, но обрабатывается узлом i, данные об объекте длиной send(l_j) составляют часть потока в канале (i,k) передачи данных. От того, на каких узлах размещаются объекты, зависят размеры потоков в каналах передачи данных. Временную задержку передачи единицы данных в канале (i,k) обозначим через c_ik. Множество C={c_ik | i,kN} описывает задержки во всех каналах передачи данных. Если узлы i, k не связаны каналом передачи данных, c_ik=. Производительность канала (i,k) определяется величиной 1/c_ik.

Распределенная информационно-вычислительная система характеризуется двумя основными временными параметрами: средним временем T_request обработки одного запроса к объекту и временем T_total обработки всех запросов. Каждый из этих параметров складывается из двух составляющих T_processing+T_waiting, где T_processing — время непосредственной обработки (пересылки) на узле (канале связи); T_waiting — общее время ожидания, обусловленное случайным характером процесса поступления и обработки запросов. Внимание сфокусируем на первой составляющей.

Обозначим через X={x_ij|x_ij{0,1}, iN, jM} матрицу назначения объектов на узлы. Если x_ij=1, объект j размещается на узле i, в противном случае не размещается. Число объектов, размещенных на узле i, определяется выражением

n^a = , (1)

а емкость памяти, занимаемая объектами на узле i, определяется выражением

S^a_i= . (2)

Время обработки запроса к объекту j, поступившего с узла i и обрабатываемого узлом k, можно описать с достаточной степенью точности выражением f_ij * (r_kj+c_ik*l_j)*x_kj. Поскольку при размещении объектов без репликаций все запросы к объекту j обрабатываются на одном узле, среднее время обработки запроса по всем узлам, всем объектам и всем запросам зависит от матрицы назначения X и оценивается выражением:

T_request(X)= . (3)

Время T_total обработки всех запросов оценим через максимальную временную загрузку всех узлов и каналов. Загрузка узла kN определяется выражением

LoadNode_k(X)= , (4)

в то время как максимальная загрузка узла выражением

LoadNode_max(X)= . (5)

Загрузка канала (i,k) оценивается в виде

LoadChannel_ik(X)= , (6)

в то время как максимальная загрузка канала в виде

LoadChannel_max(X)= . (7)

Тогда время обработки всех запросов определяется выражением

T_total(X)= . (8)

Рис. 1. Иллюстративный пример модели назначения объектов на узлы; число узлов n=3, число объектов m=10; время в R и C измерено в миллисекундах; время в векторе загрузки узлов Lnd и матрице загрузки каналов Lch выражено в секундах; значением функции send(l_j) является l_j; среднее время обработки запроса T_request=7,3 мс; время обработки всех запросов T_total=2,19 с; средняя загрузка узла 74,3%; средняя загрузка канала 51,2%

Назначение объектов на узлы является корректным, если время обработки всех запросов не превышает ширину диапазона времени, на котором измерены частоты появления запросов, другими словами, если выполняется отношение

T_total(X) ≤ Time_Period. (9)

Относительная загрузка узлов оценивается как

LoadNdRel_k =(LoadNode_k(X) / T_total(X))*100%, для kN (10)

а относительная загрузка каналов оценивается как

LoadNdRel_ik=(LoadChannel_ik (X)/T_total(X))*100%, для i,kN (11)

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

Задача - Дать пример виртуальной функции на языке С++.

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

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

Спецификация функции в базовом классе как virtual вызываем позднее связывание (так называемое связывание во время выполнения). Если функция виртуальная в базовом классе, она виртуальная также во всех производных классах. Позднее связывание имеет место только при использовании адреса объекта базового класса, в котором функция объявляется.

class Animal

{

public:

char *Title; //кличка животного

Animal(char *t) {Title=t;} //простой конструктор

virtual void speak(void); //чистая виртуальная функция

};

//класс лягушка

class Frog: public Animal

{

public:

Frog(char *Title): Animal(Title) { };

virtual void speak(void) { cout<<Title<<" говорит "<<"'ква-ква'"<<endl; };

};