Билет №11

1. Стратегия планирования alap

Алгоритм планирования ALAP (как можно позже)

Тип – планирование на достижимость.

Исходные данные: 1) Граф непосредственного предшествования операций.

Результирующие данные:

1. Шаги управления.

2. Распределение операций по шагам управления

3. Число процессоров каждого типа.

Описание алгоритма:

1. Планирование выполняется в цикле, начиная с последнего шага и кончая первым шагом.

2. Алгоритм начинает работу с введения последнего шага управления и размещения на нем операций, не имеющих операций-последователей.

3. Алгоритм завершает работу в случае назначения всех операций на шаги управления.

4. Для каждого шага управления выполняются следующие действия по планированию:

4. Из множества всех операций выбираются не спланированные операции.

5. Для каждой из них проверяется, все ли операции-последователи спланированы на последующих шагах управления.

6. Если да, то операция включается в текущий шаг, в противном случае остается не спланированной.

2. Включение и агрегирование компонентов

Включение и агрегирование — это приемы программирования, в которых один компонент использует другой. Я называю эти два компонента внешним (outer component) и внутренним (inner component) соответственно. Внешний компонент или агрегирует, или включает в себя внутренний.

Включение в СОМ похоже на включение в С++. Однако, как и все в СОМ, включение выполняется на уровне интерфейсов. Внешний компонент содержит указатели на интерфейсы внутреннего. Внешний компонент — просто клиент внутреннего компонента. Используя интерфейсы последнего, он реализует свои собственные интерфейсы (рис. 1). Внешний компонент может также реализовывать заново интерфейс, поддерживаемый внутренним, передавая последнему вызовы этого интерфейса. Внешний компонент может специализировать этот интерфейс, добавляя свой код перед вызовом внутреннего компонента и после этого (рис. 2).

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

Задача - Привести пример плана для графа задач на нескольких процессорах.