- •Билет №1
- •1.Составные части и свойства распределенной системы
- •2. Удаленный сервер
- •Билет №2
- •1. Параллелизм в распределенной системе
- •2. Реализация локального сервера
- •Билет №3
- •1. Закон Амдала
- •2. Заместитель/заглушка. Компилятор midl
- •Билет №4
- •1. Ускорение решения задачи в распределенной параллельной системе
- •2. Язык idl
- •Билет №5
- •1. Последовательные операции. Параллельные операции. Число процессоров.
- •2. Назначение данных на узлы распределенной системы. Модель назначения объектов на узлы. Сокращение трафика в каналах передачи данных.
- •Билет №6
- •1. Планирование параллельной распределенной обработки данных.
- •2. Модель назначения объектов на узлы. Частоты запросов к объектам. Длины объектов. Производительность узлов. Производительность каналов передачи данных.
- •Билет №7
- •1. Параллелизм в пространстве и во времени (конвейерный параллелизм)
- •2. Среднее время обработки одного запроса. Минимизация времени
- •Многошаговое планирование на базе asap
- •1 31 6 Типы операций:
- •Билет №8
- •1. Синхронное и асинхронное планирование.
- •2. Время обработки всех запросов к объектам. Загрузка узлов. Загрузка каналов передачи данных.
- •Билет №9
- •1. Планирование при ограничениях на ресурсы, время, достижимость
- •2. Локальный вызов процедуры. Маршалинг Локальный вызов процедуры
- •Маршалинг
- •Билет №10
- •Стратегия планирования asap Алгоритм планирования asap (как можно раньше)
- •2. Серверы в exe.
- •Билет №11
- •1. Стратегия планирования alap
- •2. Включение и агрегирование компонентов
- •Стратегия планирования «Группировка доминирующей последовательности» (Dominant Sequence Clustering - dsc)
- •Билет №12
- •1. Стратегия спискового планирования
- •Регистрация компонента в реестре
- •Билет №13
- •1. Многошаговое планирование
- •2. Функции CoGetClassObject и DllGetClassObject и их использование
- •Билет №14
- •1. Цепочечное планирование
- •2. Интерфейс iClassFactory
- •AБилет №15
- •1. Граф предшествования и граф распараллеленности операций
- •2. Фабрика класса
- •Билет №16
- •1. Свертывание графа распараллеленности операций
- •2. Использование динамической библиотеки. Экспорт функций из библиотеки. Загрузка и выгрузка dll
- •Билет №17
- •1. Синтез последовательно параллельного плана
- •2. Динамическая компоновка. Библиотеки dll. Создание динамической библиотеки
- •Билет №18
- •1. Модель разнородной распределенной системы
- •2. Управление временем жизни компонента. Подсчет ссылок
- •Билет №19
- •1. Сведение планирования к задаче целочисленного линейного программирования
- •2. Запрос интерфейса. Интерфейс iUnknown. Реализация интерфейса
- •1 31 6 Типы операций:
- •Билет №20
- •1. Задача минимизации ресурсов при заданном времени реализации плана
- •2. Таблица виртуальных функций
- •Билет №21
- •1. Целочисленное линейное программирование. Пример. Целевая функция. Система ограничений
- •Многошаговое планирование на базе asap
- •Билет №22
- •1. Планирование выполнения графа задач на узлах распределенной системы с учетом обмена данными
- •2. Теория интерфейсов
- •Неизменность интерфейсов
- •Билет №23
- •1. Граф задач. Назначение задач на процессоры. Обмен данными. План решения задач на каждом процессоре. Планирование выполнения графа задач на узлах распределенной системы с учетом обмена данными
- •Планирование графа задач
- •2. Языки и инструменты программирования распределенной обработки данных.
- •1 31 6 Типы операций:
- •Билет №24
- •1. Стратегии планирования на графе задач. Планирование графа задач
- •2. Процессы и потоки. Многопоточные приложения. Модель многопоточных приложений
- •Билет №25
- •1. Стратегия планирования «Наиболее ранняя задача первая» (Earliest Task First - etf). Стратегия планирования «Наиболее ранняя задача первая» (Earliest Task First - etf)
- •2 . Инкапсуляция. Полиморфизм. Виртуальные функции. Чисто абстрактные базовые классы. Множественное наследование. Инкапсуляция.
- •Полиморфизм и виртуальные функции
- •Чисто абстрактные базовые классы
- •Множественное наследование классов. Компоненты
- •1 31 6 Типы операций:
- •Билет №26
- •1. Стратегия планирования «Зануление дуг» (Edge Zeroing - ez). Стратегия планирования «Зануление дуг» (Edge Zeroing - ez)
- •2. Преимущество использования компонентов. Требования к компонентам. Преимущества использования компонентов
- •Требования к компонентам
- •Билет №27
- •2. Модель компонентных объектов com.
- •1 31 6 Типы операций:
- •Билет №28
- •1. Стратегия планирования «Управление мобильностью» (Mobility Directed - md). Стратегия планирования «Управление мобильностью» (Mobility Directed - md)
- •2. Интерфейс передачи сообщений (Message Passing Interface - mpi). Интерфейс передачи сообщений mpi
- •Постановка проблемы
- •Билет №29
- •1. Граф взаимодействия задач. Граф разнородной сети. Планирование решения задач в разнородной распределенной системе
- •2. Интерфейс OpenMp. Интерфейс OpenMp
- •Билет №30
- •Постановка проблемы
- •Алгоритм а* оптимального назначения задач на процессоры
- •2. Технологический стандарт написания распределённых приложений corba. Технологический стандарт corba
Билет №21
1. Целочисленное линейное программирование. Пример. Целевая функция. Система ограничений
Пусть N={1,…n} - множество планируемых операций.
Бинарное отношение H непосредственного предшествования операций (если (i,j)H, то i непосредственно предшествует j) строится в результате анализа информационных зависимостей между операциями
Отношение H представляется конечным ориентированным графом GH.
Минимальный шаг Si выполнения операции i определяется по плану, генерируемому ASAP.
Максимальный шаг Li выполнения операции i определяется по плану, генерируемому ALAP.
Число используемых в плане процессоров типа k есть bk при k=1,…,TYPES.
Стоимость процессора типа k определяется величиной сk.
Обозначим через xij двоичную переменную, принимающую значение 1 в случае, если операция i выполняется на шаге j, и принимающую значение 0 в случае, если операция i не выполняется на шаге j.
Рассмотрим задачу построения обыкновенного плана, имеющего минимальную стоимость при заданном числе Т шагов управления (time-constrained scheduling). Стоимость выразим суммарной стоимостью используемых планом процессоров всех типов.
Эта задача формулируется в виде следующей задачи целочисленного линейного программирования:
Целевая функция:
Система ограничений:
при 1jT, 1kTYPES,
при 1in,
при (i,j)H.
Ограничение (1) вытекает из того факта, что на каждом шаге число используемых процессоров типа k не должно превышать число bk имеющихся процессоров этого типа.
Ограничение (2) выражает возможность выполнения любой операции ровно на одном шаге управления (обыкновенное планирование).
Ограничение (3) формализует тот факт, что операция j должна выполняться на шаге с номером большим, чем номер шага, на котором выполняется операция i, в случае, если операция i предшествует операции j.
2. Определение интерфейсов в С++
Способность к унифицированной работе с разными компонентами известна как полиморфизм (polymorphism). Открытое (public) наследование от чисто абстрактного базового класса называется наследованием интерфейса (interface inheritance), так как производный класс наследует лишь описания функций. Вместо определения интерфейса как класса можно использовать следующее определение из заголовочного файла objbase.h Microsoft Win32 Software Development Kit (SDK):
#define interface struct
Определение использует ключевое слово struct, а не class. Благодаря этому члены структуры автоматически имеют открытый доступ, так что не требуется ключевое слово public. Чтобы стать настоящими интерфейсами в СOM, интерфейсы должны наследовать стандартный интерфейс IUnknown.
Задача - Привести пример многошагового плана
Многошаговое планирование на базе asap
Тип – планирование на достижимость.
Исходные данные:
Граф непосредственного предшествования операций.
Времена t(i), iN выполнения операций.
Время tstep шага управления .
Результирующие данные:
Шаги управления.
Распределение операций по шагам управления.
Число процессоров каждого типа.
Описание алгоритма:
Планирование выполняется в цикле, начиная с первого шага и кончая последним шагом.
Множество всех операций разбивается в процессе планирования на три подмножества: не спланированных операций, частично спланированных операций, полностью спланированных операций.
Алгоритм начинает работу с введения первого шага управления и размещения на нем операций, не имеющих операций-предшественников. Если время выполнения операции меньше времени шага управления, операция полностью размещается на этом шаге, в противном случае операция является частично спланированной.
Алгоритм завершает работу в случае полного размещения всех операций на введенных шагах управления.
Для каждого шага управления выполняются следующие действия по планированию:
Из множества всех операций выбираются частично спланированные операции, которые полностью или частично размещаются на текущем шаге.
Из множества всех операций выбираются не спланированные операции.
Для каждой из не спланированных операций проверяется, все ли операции-предшественники спланированы на предшествующих шагах управления.
Если да, то операция полностью или частично включается в текущий шаг, в противном случае остается не спланированной.
Рис. 1. Многошаговое планирование ASAP; t(1)= t(3)= t(5)= t(6)= t(8)=1; t(2)= t(4)= t(7)=2; tstep=1; общее время решения задачи 5 единиц (при простом планировании 8 единиц)