Параллельное программирование

Упражнение 1:

Номер 1

Проанализируйте решающие правила, используемые в "быстрых" эвристических алгоритмах динамического распараллеливания. Какое решающее правило эффективно при деспетчировании однородных вычислительных систем?

Ответ:

(1) из множества тех работ, которые могут быть назначены для выполнения с данного момента времени, назначать наиболее трудоемкую

(2) из множества тех работ, которые могут быть назначены для выполнения с данного момента времени, назначать наименее трудоемкую

(3) из множества тех работ, которые могут быть назначены для выполнения с данного момента времени, назначать в порядке следования

Номер 2

Проанализируйте решающие правила, используемые в "быстрых" эвристических алгоритмах динамического распараллеливания. Какое решающее правило эффективно при деспетчировании неоднородных вычислительных систем?

Ответ:

(1) из тех работ, которые могут быть назначены для выполнения с данного момента времени, в первую очередь назначать самую трудоемкую; назначение производить на тот процессор, который освободился ранее других

(2) из тех работ, которые могут быть назначены для выполнения с данного момента времени, в первую очередь назначать самую трудоемкую; назначение производить на тот процессор, который ранее других закончит ее выполнение

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

Номер 3

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

Ответ:

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

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

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

Упражнение 2:

Номер 1

Распределите поровну пакет программ, заданных условным временем выполнения между тремя процессорами. Определите время загрузки каждого процессора. 2, 8, 16, 3, 5, 8, 12, 12, 10, 2, 8

Ответ:

(1) время загрузки 29, 29, 30 условных единиц

(2) время загрузки 28, 30, 30 условных единиц

(3) время загрузки 29, 30, 29 условных единиц

Номер 2

Распределите поровну пакет программ, заданных условным временем выполнения между тремя процессорами. Определите время загрузки каждого процессора. 6, 4, 3, 5, 8, 5, 4, 7, 8, 3, 5, 6

Ответ:

(1) время загрузки 22, 21, 21 условных единиц

(2) время загрузки 21, 22, 21 условных единиц

(3) время загрузки 21, 20, 22 условных единиц

Номер 3

Распределите поровну пакет программ, заданных условным временем выполнения между тремя процессорами. Определите время загрузки каждого процессора. 1, 2, 2, 8, 5, 8, 6, 2, 3, 4, 7, 3

Ответ:

(1) время загрузки 17, 17, 17 условных единиц

(2) время загрузки 16, 18, 17 условных единиц

(3) время загрузки 17, 16, 18 условных единиц

Упражнение 4:

Номер 1

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

Ответ:

(1)

(2)

(3)

Номер 2

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

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

(1)

(2)

(3)

Упражнение 5:

Номер 1

С помощью диспетчера последовательного назначения распределите работы, заданные графом G, в неоднородной ВС с известным количеством n₁ и n₂ процессоров разной специализации. Представьте временные диаграммы выполнения работ. n₁=1, n₂=2

Ответ:

(1)

T=5

(2)

T=6

(3)

T=6

Номер 2

С помощью диспетчера последовательного назначения распределите работы, заданные графом G, в неоднородной ВС с известным количеством п1 и п2 процессоров разной специализации. Представьте временные диаграммы выполнения работ.n₁=2, n₂=1

Ответ:

(1)

T=4

(2)

T=6

(3)

T=6

Номер 3

С помощью диспетчера последовательного назначения распределите работы, заданные графом G, в неоднородной ВС с известным количеством п1 и п2 процессоров разной специализации. Представьте временные диаграммы выполнения работ.n₁=2, n₂=1

Ответ:

(1)

T=5

(2)

T=6

(3)

T=6

Упражнение 6:

Номер 1

Какие элементы методов точного решения задач распараллеливания и методов "быстрого" диспетчирования целесообразно применять при компоновке "широкой" команды?

Ответ:

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

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

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

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

Номер 2

Какие элементы точного решения задач распараллеливания целесообразно применять при построении диспетчеров для однородных ВС?

Ответ:

(1) статистически доказано, что алгоритм последовательного назначения по приведенному в лекции решающему правилу, работает "быстро" и обеспечивает расписания, в более 90% случаев совпадающие с оптимальными. Поэтому используемое им решающее правило при назначении работ следует считать приоритетным. Как дополнительные критерии, характерные для методов точного решения, справедлив критерий назначения в первую очередь работ, для которых ресурс времени, оставшегося до директивного срока, минимален, а затем – критерий назначения работ, инициирующих максимальный объем

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

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

Номер 3

Какие элементы точного решения задач распараллеливания целесообразно применять при построении диспетчеров для неоднородных ВС?

Ответ:

(1) динамическое планирование работы неоднородных ВС полностью основано на применении точных методов решения задач распараллеливания

(2) диспетчеры для неоднородных ВС используют обобщение решающего правила последовательного назначения, применяемого для однородных ВС

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

Параллельное программирование - тест 10