Билет №22

1. Планирование выполнения графа задач на узлах распределенной системы с учетом обмена данными

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

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

Граф задач (Task graph).

Граф задач – это ориентированный ациклический граф G=(V, E), где

V – множество узлов, |V| = v, представляющих задачи, каждая из которых описывается множеством инструкций (операторов), выполняемых последовательно на одном процессоре;

E – множество дуг |E| = e, представляющих передаваемые данные и отношения предшествования между узлами.

Вершина n_i графа метится числом w(n_i), описывающим время решения задачи. Дуга (i,j) графа метится числом c_ij, описывающим время передачи данных от задачи n_i к задаче n_j.

Входным называется узел, не имеющий входящих дуг. Выходным называется узел, не имеющий исходящих дуг.

Задача не может начать выполнение не получив данные от родительских задач.

К оэффициентом «коммуникация/вычисление» (communication-to-computation ratio - CCR) графа задач называется отношение среднего времени передачи данных от одной задачи к другой к среднему времени решения задачи.

Решение задач может происходить параллельно с передачами данных. Время передачи данных между двумя задачи, равное c_ij в исходном графе, принимается равным нулю при назначении задач на один процессор.

Пример графа задач дан на рис.1. Он включает четыре задачи n₁, n₂, n₃, n₄, имеющие время решения 5, 20, 10 и 8 единиц каждая. Время передачи данных между задачами n₁, n₂ составляет 1 единицу, между задачами n₁, n₃ – 20 единиц, между задачами n₂, n₄ – 1 единицу, между задачами n₃, n₄ – 10 единиц. Время реализации графа задач определяется суммарным весом всех узлов и дуг наиболее длинного пути на графе и равно 54. Коэффициент «коммуникация/вычисление» CCR=0.73.

2. Теория интерфейсов

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