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

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

Номер 1

Обсудите достоинства и недостатки способов организации параллельных вычислительных процессов. Каковы достоинства и недостатки централизованного диспетчирования?

Ответ:

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

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

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

Номер 2

Обсудите достоинства и недостатки способов организации параллельных вычислительных процессов. Каковы достоинства и недостатки децентрализованного диспетчирования?

Ответ:

(1) достоинства: самостоятельное планирование "своей" загрузки процессорами обеспечивает высокую живучесть системы, обладающей виртуальным ресурсом и функционирующей в многоканальном и многоциклическом режиме. Недостатки: отсутствие учета состояния всей ВС порождает проблемы восстановления и переназначения невыполненных (вследствие отказов) работ, невозможность применения методов оптимизации совокупного выполнения работ с учетом синхронизации, затруднение контроля правильности вычислительного процесса и необходимости перехода на резерв

(2) достоинства: самостоятельное планирование "своей" загрузки процессорами обеспечивает высокую живучесть системы, обладающей виртуальным ресурсом и функционирующей в многоканальном и многоциклическом режиме, возможность динамической перекомплектации при обеспечении высокой надежности. Недостатки: отсутствие учета состояния всей ВС порождает проблемы восстановления и переназначения невыполненных (вследствие отказов) работ, невозможность применения методов оптимизации совокупного выполнения работ с учетом синхронизации, затруднение контроля правильности вычислительного процесса

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

Номер 3

Обсудите достоинства и недостатки способов организации параллельных вычислительных процессов. Как практически (в ВК семейства "Эльбрус") сочетаются принципы централизованного и децентрализованного диспетчирования?

Ответ:

(1) вычислительный процесс в сложной управляющей системе, функционирующей в режиме реального времени, использует централизованное диспетчирование. Управление вычислительным процессом внутри ВС производится на основе децентрализованного диспетчирования при общей очереди "к процессору" и при виртуальном вычислительном ресурсе

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

(3) вычислительный процесс в сложной управляющей системе, функционирующей в режиме реального времени, использует централизованное диспетчирование. Управление вычислительным процессом внутри ВС производится на основе исключения из ОС средств децентрализованного диспетчирования и заменой их процедурами централизованного диспетчирования. Это позволяет резко снизить накладные расходы на организацию управления

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

Номер 1

ВС содержит 2 процессора. Задачи в реальном времени решаются в циклах длительности δ и 2δ. δ=10 условным единицам времени. Учитывая накладные расходы на управление в одну условную единицу, а также используя принцип мультипрограммирования при решении задач различного относительного приоритета, составьте план загрузки процессоров по графам, отображающим упорядоченность и время выполнения работ в циклах двух длительностей. Рассчитайте коэффициенты загрузки k₁ и k₂ каждого процессора

Ответ:

(1) k₁=0,8, k₂=0,85

(2) k₁=0,9, k₂=0,8

(3) k₁=0,84, k₂=0,8

Номер 2

ВС содержит 2 процессора. Задачи в реальном времени решаются в циклах длительности δ и 2δ. δ = 10 условным единицам времени. Учитывая накладные расходы на управление в одну условную единицу, а также используя принцип мультипрограммирования при решении задач различного относительного приоритета, составьте план загрузки процессоров по графам, отображающим упорядоченность и время выполнения работ в циклах двух длительностей. Рассчитайте коэффициенты загрузки  k₁ и k₂ каждого процессора

Ответ:

(1) k₁=0,7, k₂=0,9

(2) k₁=0,75, k₂=0,85

(3) k₁=0,8, k₂=0,9

Номер 3

ВС содержит 2 процессора. Задачи в реальном времени решаются в циклах длительности δ и 2δ. δ=10 условным единицам времени. Учитывая накладные расходы на управление в одну условную единицу, а также используя принцип мультипрограммирования при решении задач различного относительного приоритета, составьте план загрузки процессоров по графам, отображающим упорядоченность и время выполнения работ в циклах двух длительностей. Рассчитайте коэффициенты загрузки k₁ и k₂ каждого процессора

Ответ:

(1) k₁=0,85, k₂=0,75

(2) k₁=0,95, k₂=0,8

(3) k₁=0,85, k₂=0,85

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

Номер 1

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G₁, задачи второго этапа - графом G₂. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности 2δс меньшим приоритетом решаются фоновые задачи, отображенные графом G₃.



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

Ответ:

(1)

(2)

(3)

Номер 2

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G₁, задачи второго этапа - графом G₂. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности 2δс меньшим приоритетом решаются фоновые задачи, отображенные графом G₃. 



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

Ответ:

(1)

(2)

(3) расписание не укладывается во временной режим

Номер 3

Обслуживание управляемого объекта производится в два этапа. Задачи первого этапа отображаются графом G₁, задачи второго этапа - графом G₂. Длительность цикла составляет δ=10условных единиц времени. В цикле длительности 2δс меньшим приоритетом решаются фоновые задачи, отображенные графом G₃. 



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

Ответ:

(1)

(2)

(3)

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

Номер 1

Представьте применение простейших операций над семафорами для синхронизации частичной упорядоченности работ. Сколько семафоров потребуется?

Ответ:

(1) 5 семафоров

(2) 4 семафора

(3) 3 семафора

Номер 2

Представьте применение простейших операций над семафорами для синхронизации частичной упорядоченности работ. Сколько семафоров потребуется?

Ответ:

(1) 4 семафора

(2) 6 семафоров

(3) 5 семафоров

Номер 3

Представьте применение простейших операций над семафорами для синхронизации частичной упорядоченности работ. Сколько семафоров потребуется?

Ответ:

(1) 6 семафоров

(2) 10 семафоров

(3) 5 семафоров

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

Номер 1

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

Ответ:

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

(2) задержка на 3 такта; схема применима всегда при наличии этапа экстраполяции результатов

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

Номер 2

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

Ответ:

(1) метод полностью воспроизводит идею "data flow", т.к. явно использует входную и выходную информацию программ для синхронизации и управления

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

(3) воспроизведение механизма семафоров допускает значительно больше возможностей по взаимодействию программ

Номер 3

Исследуйте возможную организацию параллельных вычислений. Как рассмотренные в лекции схемы организации вычислений концептуально соответствуют организации распараллеливания в отечественном семействе "Эльбрус"?

Ответ:

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

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

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

Номер 4

Исследуйте возможную организацию параллельных вычислений. Могут ли предложенные в лекции 20 методы точного решения задач распараллеливания быть основой построения диспетчеров в составе ОС ВС?

Ответ:

(1) могут

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

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

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