eng
Выпуск #1/2021
С. Назаров, А. Барсуков
ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ БОРТОВЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. Часть 2
ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ БОРТОВЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. Часть 2
Просмотры: 505
DOI: 10.22184/1992-4178.2021.202.1.130.136
Показано, что эффективное планирование параллельного вычислительного процесса в БВС можно обеспечить, используя методы сетевого планирования и управления в совокупности с математическим аппаратом ярусно-параллельных графов и математического программирования.
Показано, что эффективное планирование параллельного вычислительного процесса в БВС можно обеспечить, используя методы сетевого планирования и управления в совокупности с математическим аппаратом ярусно-параллельных графов и математического программирования.
Теги: critical path information-related tasks multiprocessor system parallel computing process информационно-связанные задачи критический путь многопроцессорная система параллельный вычислительный процесс
Оптимизация параллельных вычислений бортовых систем реального времени
Часть 2
С. Назаров, д. т. н.1, А. Барсуков, к. т. н.2
Во второй части статьи приводится пример оптимизации параллельного вычислительного процесса в бортовых вычислительных системах. Показано, что эффективное планирование параллельного вычислительного процесса в БВС можно обеспечить, используя методы сетевого планирования и управления в совокупности с математическим аппаратом ярусно-параллельных графов и математического программирования.
Решение задачи
Минимизация количества ресурсов выполнения пакета ЗНЗ без увеличения длины критического пути
Будем считать, определенный выше критический путь, равный 150 единицам времени, соответствует директивному времени решения заданного пакета задач. В этом случае становится актуальной задача минимизации ресурсов (в нашем случае количества процессоров), необходимых для реализации всех задач при условии непревышения директивного значения длины критического пути. Другими словами, длительности выполнения всех работ пакета нужно изменить так, чтобы длина любого пути в графе была в идеале равна или меньше длины критического пути. Практически все вычислительные работы будут увеличены с учетом возможных резервов времени для их выполнения.
Для формализации задачи введем дополнительные обозначения:
– время выполнения работы (i, j) после минимизации количества выделяемых ресурсов;
– время свершения событий в графе работ (события отождествляются с вершинами графа);
– исходное число процессоров, которое позволяет выполнить все работы с учетом возможного параллельного выполнения задачи;
– минимальное количество процессоров, которое будет получено в результате решения оптимизационной задачи (пока еще без учета возможности параллельной работы различных задач ЗНЗ);
– доля физического вычислителя соответствующего виртуального процессора, необходимая для выполнения работы (i, j) после минимизации количества выделяемых ресурсов,
.
В качестве исходного количества вычислителей можно принять сумму (вычисляется по формуле (2) из первой части статьи ) с дополнительным числом вычислителей, которые надо добавить для выполнения параллельных ветвей задач ЗНЗ (см. табл. 3, первая часть статьи). Таким образом, N = 4 + 11 = 15. Значение минимального количества процессоров определяется как сумма долей физических процессоров в виртуальных вычислителях, то есть
.
В качестве целевой функции задачи выбираем время занятости процессоров (полное машинное время) на решение пакета задач ЗНЗ. Его нужно минимизировать за счет использования имеющихся резервов времени на выполнение отдельных задач. Таким образом, необходимо найти такие значения множества переменных выполнения работ (i, j), которые минимизируют целевую функцию времени выполнения ЗНЗ
. (12)
Первое слагаемое этой функции представляет собой полные затраты машинного времени на решение всего пакета задач. Второе – экономию машинного времени при условии того, что можно увеличить время решения некоторых задач за счет имеющегося резерва времени на их выполнение (здесь ). Рассмотрим ограничения, которые должны учитываться при решении этой задачи.
Первый вид ограничений связан с принятым условием использования для решения задачи только имеющихся резервов для выполнения задач пакета. Отсюда следует система ограничений для продолжительности выполнения работ следующего вида:
. (13)
Второй вид ограничений должен обеспечить такое изменение длительности выполнения всех работ пакета, чтобы длина любого пути в графе была в идеале равна длине критического пути. В рассматриваемом примере таких путей шесть (перечислим их последовательностями вершин графа): P1: 0–2–7; P2: 0–3–5–7; P3: 0–1–6–7; P4: 0–1–3–5–7; P5: 0–1–4–5–7; P6: 0–1–4–6–7. Ограничения на длину этих путей имеют следующий вид:
. (14)
Решение задачи (12) – (14) показано на рис. 5.
Как видно из результата решения задачи минимизации использования ресурсов, число процессоров при назначении отдельного вычислителя на одну и только одну задачу для реализации ЗНЗ без увеличения длины критического составляет физических процессоров (сумма по столбцу G на рис. 5). При этом физические вычислители могут простаивать значительное количество времени. Переход на виртуальные процессоры более низкой производительности, но работающие без простоев, позволяет сократить число вычислителей до виртуальных процессоров (сумма по столбцу H на рис. 5). Однако структура пакета (см. рис. 1) свидетельствует о возможности параллельной и мультипрограммной работы этих процессоров при выполнении задач пакета ЗНЗ.
Возможности организации мультипроцессорного выполнения пакета задач, представленного сетевой моделью
Потенциальную параллельность выполнения заданного набора задач можно определить, преобразовав граф задач в ярусно-параллельную форму [7]. Ярусно-параллельная форма графа (ЯПФ) – деление вершин ориентированного ациклического графа на перенумерованные подмножества , такие, что, если дуга идет от вершины к вершине , то обязательно .
Каждое из множеств называется ярусом ЯПФ, j – его номером, количество вершин в ярусе – его шириной. Количество ярусов в ЯПФ называется ее высотой, а максимальная ширина ее ярусов – шириной ЯПФ. Для ЯПФ графа важным является тот факт, что операции, которым соответствуют вершины одного яруса, не зависят друг от друга (не находятся в отношении связи), и поэтому заведомо существует параллельная реализация алгоритма, в которой они могут быть выполнены параллельно на разных устройствах вычислительной системы. Поэтому ЯПФ графа алгоритма может быть использована для подготовки такой параллельной реализации алгоритма.
Для получения ЯПФ пакета задач, представленного в форме сетевой модели, как показано на рис. 1, его предварительно необходимо преобразовать, заменив дуги графа (работы) вершинами. В преобразованном графе (рис. 6) номера вершин соответствуют работам, длительность которых пересчитана в соответствии с решением задачи (12–14) по рис. 5.
Получить ЯПФ можно, построив матрицу смежности графа. Матрица смежности – это квадратная матрица размерностью , где M – число вершин графа, однозначно представляющая его структуру. Обозначим ее как , где каждый элемент матрицы определяется следующим образом: aij = 1, если есть дуга (i, j), aij = 0, если нет дуги (i, j). В нашем примере матрица смежности будет иметь следующий вид, приве-
денный на рис. 7.
Алгоритм распределения модулей системы по уровням:
Находим в матрице нулевые строки. В нашем случае это только одна строка с номером 13.
Вершина с этим номером образует нулевой (низший) уровень ЯПФ.
Вычеркиваем столбцы с номерами найденных вершин. В нашем случае – столбец 13.
Находим в матрице нулевые строки (7, 11, 12). Это вершины 1‑го уровня.
Вычеркиваем столбцы с номерами 7, 11, 12.
Находим в матрице нулевые строки (3, 4, 8, 9 и 10). Это вершины 2‑го уровня.
Вычеркиваем столбцы с номерами найденных вершин.
Находим в матрице нулевые строки (2, 5, 6). Это вершины 3‑го уровня.
Вычеркиваем столбцы с номерами 5, 6.
Вершина с номером 1 образует 4‑й уровень.
ЯПФ графа задач пакета, полученная на основе матрицы смежности, представлена на рис. 8. В каждой вершине графа в виде дроби указан номер вершины (числитель) и время выполнения (знаменатель). Рядом с вершиной указано количество виртуальных процессоров, которые необходимы для выполнения задачи соответствующего номера.
Построенный граф задач в ЯПФ далеко не прямоугольный, что неудобно для организации параллельного вычислительного процесса и определения минимально необходимого количества вычислителей. Визуально из рис. 8 понятно, что граф можно легко перестроить, не меняя связей между вершинами, например, можно переместить вершины 2 и 3 на 4‑й уровень, а вершину 4 – на 3‑й. После таких преобразований граф примет вид, показанный на рис. 9.
По ЯПФ (рис. 9) легко построить план реализации вычислительного процесса во времени. На рис. 10 сверху показана шкала времени (равная длине критического пути), под которой обозначены временные промежутки реализации задач пакета. В нижней части диаграммы приведены сведения о необходимом количестве виртуальных вычислителей. Красными стрелками показаны передачи данных между задачами ЗНЗ. В нашем примере минимальное количество виртуальных вычислителей . В этом случае можно получить минимально возможное время решения системой ЗНЗ со значением условных единиц. Для этого результата БВС должна содержать физических процессоров.
Минимизация загрузки БВС
Как показывает диаграмма по рис. 10, требуемое количество вычислителей для реализации ЗНЗ с требуемым минимальным значением условных единиц процессорного времени равно 10. При этом полная величина затрат процессорного времени БВС составит 1 500 условных единиц. Реальные затраты (без учета простоя процессоров) легко определить по рис. 10.
Здесь можно выделить четыре этапа выполнения задач пакета ЗНЗ. Каждый этап характеризуется неизменным количеством вычислителей и продолжительностью. Так, на первом этапе выполнения ЗНЗ занято 2,74 вычислителя, а продолжительность этапа – 30 условных единиц. Таким образом, затраты этого этапа составляют 30 · 2,74 = 82,0 единиц процессорного времени. Аналогично вычисляются затраты процессорного времени на последующих этапах (табл. 5).
Полагая, что ПЛИС вычислителей обладает свойством реконфигурации, имеет смысл заранее запрограммировать переключения освободившихся от выполнения текущей задачи процессоров на последующие задачи согласно диаграмме выполнения работ ЗНЗ. Другими словами, надо составить расписание загрузки и переключения процессоров. Постановка и формализация задачи построения такого расписания достаточно сложна и могла бы быть темой отдельной статьи. Однако в нашем небольшом примере можно легко увидеть возможности уменьшения простоя вычислителей. После завершения задачи 1 (желтый цвет на диаграмме) освободившийся вычислитель можно назначить на выполнение задачи 5, затем 9 и 12. Таким образом, этот вычислитель будет работать без простоя.
* * *
Приведенные в статье математические модели и пример оптимизации параллельного вычислительного процесса в бортовых вычислительных системах позволяет сделать следующие выводы:
Эффективное планирование параллельного вычислительного процесса в бортовых вычислительных системах можно обеспечить, используя методы сетевого планирования и управления в совокупности с математическим аппаратом ярусно-параллельных графов и математического программирования.
Реализация в программируемых логических интегральных схемах ПЛИС процессорных элементов с разделяемой производительностью позволяет удобно использовать аппарат виртуальных процессоров для решения задачи распараллеливания вычислительного процесса и минимизации физических ресурсов для выполнения ЗНЗ с заданными требованиями по времени выполнения.
Возможности программируемой реконфигурации разрабатываемых в настоящее время ПЛИС процессорных элементов с разделяемой производительностью целесообразно использовать для построения эффективных расписаний загрузки процессоров БВС.
Литература
Гохрингер Д., Хюбнер М., Бекер Ю. Архитектура адаптивных многопроцессорных систем на кристалле: новая степень свободы при проектировании систем и в поддержке при выполнении // Мир радиоэлектроники. М.: ТЕХНОСФЕРА, 2012. С. 146–173.
Хитт Д. Стратегия Xilinx – быстрее двигаться к адаптируемому, интеллектуальному миру // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. 2018. № 4. С. 84–87.
Xilinx Ultrascale + Обзор. [Электронный ресурс]. URL: https://developer.ridgerun.com/wiki/index.php?title=Xilinx_-Ultrascale%2B_Overview
Кофман А. В. Сетевые методы планирования: Применение системы ПЕРТ и ее разновидностей при управлении производственными и научно-исследовательскими проектами / Пер. с фр. М.: Прогресс, 1968. 181 с.
Сетевой график. [Электронный ресурс].
URL: http://www.stroitelstvonew.ru/1/sete-voy_grafik. shtml.
Вагнер Г. Основы исследования операций. Том 1 / Пер. с англ. М.: МИР, 1972. 336 с.
Назаров С. В. Операционные системы специализированных вычислительных комплексов: теория построения и системного проектирования. М.: Машиностроение, 1989. 400 с.
Часть 2
С. Назаров, д. т. н.1, А. Барсуков, к. т. н.2
Во второй части статьи приводится пример оптимизации параллельного вычислительного процесса в бортовых вычислительных системах. Показано, что эффективное планирование параллельного вычислительного процесса в БВС можно обеспечить, используя методы сетевого планирования и управления в совокупности с математическим аппаратом ярусно-параллельных графов и математического программирования.
Решение задачи
Минимизация количества ресурсов выполнения пакета ЗНЗ без увеличения длины критического пути
Будем считать, определенный выше критический путь, равный 150 единицам времени, соответствует директивному времени решения заданного пакета задач. В этом случае становится актуальной задача минимизации ресурсов (в нашем случае количества процессоров), необходимых для реализации всех задач при условии непревышения директивного значения длины критического пути. Другими словами, длительности выполнения всех работ пакета нужно изменить так, чтобы длина любого пути в графе была в идеале равна или меньше длины критического пути. Практически все вычислительные работы будут увеличены с учетом возможных резервов времени для их выполнения.
Для формализации задачи введем дополнительные обозначения:
– время выполнения работы (i, j) после минимизации количества выделяемых ресурсов;
– время свершения событий в графе работ (события отождествляются с вершинами графа);
– исходное число процессоров, которое позволяет выполнить все работы с учетом возможного параллельного выполнения задачи;
– минимальное количество процессоров, которое будет получено в результате решения оптимизационной задачи (пока еще без учета возможности параллельной работы различных задач ЗНЗ);
– доля физического вычислителя соответствующего виртуального процессора, необходимая для выполнения работы (i, j) после минимизации количества выделяемых ресурсов,
.
В качестве исходного количества вычислителей можно принять сумму (вычисляется по формуле (2) из первой части статьи ) с дополнительным числом вычислителей, которые надо добавить для выполнения параллельных ветвей задач ЗНЗ (см. табл. 3, первая часть статьи). Таким образом, N = 4 + 11 = 15. Значение минимального количества процессоров определяется как сумма долей физических процессоров в виртуальных вычислителях, то есть
.
В качестве целевой функции задачи выбираем время занятости процессоров (полное машинное время) на решение пакета задач ЗНЗ. Его нужно минимизировать за счет использования имеющихся резервов времени на выполнение отдельных задач. Таким образом, необходимо найти такие значения множества переменных выполнения работ (i, j), которые минимизируют целевую функцию времени выполнения ЗНЗ
. (12)
Первое слагаемое этой функции представляет собой полные затраты машинного времени на решение всего пакета задач. Второе – экономию машинного времени при условии того, что можно увеличить время решения некоторых задач за счет имеющегося резерва времени на их выполнение (здесь ). Рассмотрим ограничения, которые должны учитываться при решении этой задачи.
Первый вид ограничений связан с принятым условием использования для решения задачи только имеющихся резервов для выполнения задач пакета. Отсюда следует система ограничений для продолжительности выполнения работ следующего вида:
. (13)
Второй вид ограничений должен обеспечить такое изменение длительности выполнения всех работ пакета, чтобы длина любого пути в графе была в идеале равна длине критического пути. В рассматриваемом примере таких путей шесть (перечислим их последовательностями вершин графа): P1: 0–2–7; P2: 0–3–5–7; P3: 0–1–6–7; P4: 0–1–3–5–7; P5: 0–1–4–5–7; P6: 0–1–4–6–7. Ограничения на длину этих путей имеют следующий вид:
. (14)
Решение задачи (12) – (14) показано на рис. 5.
Как видно из результата решения задачи минимизации использования ресурсов, число процессоров при назначении отдельного вычислителя на одну и только одну задачу для реализации ЗНЗ без увеличения длины критического составляет физических процессоров (сумма по столбцу G на рис. 5). При этом физические вычислители могут простаивать значительное количество времени. Переход на виртуальные процессоры более низкой производительности, но работающие без простоев, позволяет сократить число вычислителей до виртуальных процессоров (сумма по столбцу H на рис. 5). Однако структура пакета (см. рис. 1) свидетельствует о возможности параллельной и мультипрограммной работы этих процессоров при выполнении задач пакета ЗНЗ.
Возможности организации мультипроцессорного выполнения пакета задач, представленного сетевой моделью
Потенциальную параллельность выполнения заданного набора задач можно определить, преобразовав граф задач в ярусно-параллельную форму [7]. Ярусно-параллельная форма графа (ЯПФ) – деление вершин ориентированного ациклического графа на перенумерованные подмножества , такие, что, если дуга идет от вершины к вершине , то обязательно .
Каждое из множеств называется ярусом ЯПФ, j – его номером, количество вершин в ярусе – его шириной. Количество ярусов в ЯПФ называется ее высотой, а максимальная ширина ее ярусов – шириной ЯПФ. Для ЯПФ графа важным является тот факт, что операции, которым соответствуют вершины одного яруса, не зависят друг от друга (не находятся в отношении связи), и поэтому заведомо существует параллельная реализация алгоритма, в которой они могут быть выполнены параллельно на разных устройствах вычислительной системы. Поэтому ЯПФ графа алгоритма может быть использована для подготовки такой параллельной реализации алгоритма.
Для получения ЯПФ пакета задач, представленного в форме сетевой модели, как показано на рис. 1, его предварительно необходимо преобразовать, заменив дуги графа (работы) вершинами. В преобразованном графе (рис. 6) номера вершин соответствуют работам, длительность которых пересчитана в соответствии с решением задачи (12–14) по рис. 5.
Получить ЯПФ можно, построив матрицу смежности графа. Матрица смежности – это квадратная матрица размерностью , где M – число вершин графа, однозначно представляющая его структуру. Обозначим ее как , где каждый элемент матрицы определяется следующим образом: aij = 1, если есть дуга (i, j), aij = 0, если нет дуги (i, j). В нашем примере матрица смежности будет иметь следующий вид, приве-
денный на рис. 7.
Алгоритм распределения модулей системы по уровням:
Находим в матрице нулевые строки. В нашем случае это только одна строка с номером 13.
Вершина с этим номером образует нулевой (низший) уровень ЯПФ.
Вычеркиваем столбцы с номерами найденных вершин. В нашем случае – столбец 13.
Находим в матрице нулевые строки (7, 11, 12). Это вершины 1‑го уровня.
Вычеркиваем столбцы с номерами 7, 11, 12.
Находим в матрице нулевые строки (3, 4, 8, 9 и 10). Это вершины 2‑го уровня.
Вычеркиваем столбцы с номерами найденных вершин.
Находим в матрице нулевые строки (2, 5, 6). Это вершины 3‑го уровня.
Вычеркиваем столбцы с номерами 5, 6.
Вершина с номером 1 образует 4‑й уровень.
ЯПФ графа задач пакета, полученная на основе матрицы смежности, представлена на рис. 8. В каждой вершине графа в виде дроби указан номер вершины (числитель) и время выполнения (знаменатель). Рядом с вершиной указано количество виртуальных процессоров, которые необходимы для выполнения задачи соответствующего номера.
Построенный граф задач в ЯПФ далеко не прямоугольный, что неудобно для организации параллельного вычислительного процесса и определения минимально необходимого количества вычислителей. Визуально из рис. 8 понятно, что граф можно легко перестроить, не меняя связей между вершинами, например, можно переместить вершины 2 и 3 на 4‑й уровень, а вершину 4 – на 3‑й. После таких преобразований граф примет вид, показанный на рис. 9.
По ЯПФ (рис. 9) легко построить план реализации вычислительного процесса во времени. На рис. 10 сверху показана шкала времени (равная длине критического пути), под которой обозначены временные промежутки реализации задач пакета. В нижней части диаграммы приведены сведения о необходимом количестве виртуальных вычислителей. Красными стрелками показаны передачи данных между задачами ЗНЗ. В нашем примере минимальное количество виртуальных вычислителей . В этом случае можно получить минимально возможное время решения системой ЗНЗ со значением условных единиц. Для этого результата БВС должна содержать физических процессоров.
Минимизация загрузки БВС
Как показывает диаграмма по рис. 10, требуемое количество вычислителей для реализации ЗНЗ с требуемым минимальным значением условных единиц процессорного времени равно 10. При этом полная величина затрат процессорного времени БВС составит 1 500 условных единиц. Реальные затраты (без учета простоя процессоров) легко определить по рис. 10.
Здесь можно выделить четыре этапа выполнения задач пакета ЗНЗ. Каждый этап характеризуется неизменным количеством вычислителей и продолжительностью. Так, на первом этапе выполнения ЗНЗ занято 2,74 вычислителя, а продолжительность этапа – 30 условных единиц. Таким образом, затраты этого этапа составляют 30 · 2,74 = 82,0 единиц процессорного времени. Аналогично вычисляются затраты процессорного времени на последующих этапах (табл. 5).
Полагая, что ПЛИС вычислителей обладает свойством реконфигурации, имеет смысл заранее запрограммировать переключения освободившихся от выполнения текущей задачи процессоров на последующие задачи согласно диаграмме выполнения работ ЗНЗ. Другими словами, надо составить расписание загрузки и переключения процессоров. Постановка и формализация задачи построения такого расписания достаточно сложна и могла бы быть темой отдельной статьи. Однако в нашем небольшом примере можно легко увидеть возможности уменьшения простоя вычислителей. После завершения задачи 1 (желтый цвет на диаграмме) освободившийся вычислитель можно назначить на выполнение задачи 5, затем 9 и 12. Таким образом, этот вычислитель будет работать без простоя.
* * *
Приведенные в статье математические модели и пример оптимизации параллельного вычислительного процесса в бортовых вычислительных системах позволяет сделать следующие выводы:
Эффективное планирование параллельного вычислительного процесса в бортовых вычислительных системах можно обеспечить, используя методы сетевого планирования и управления в совокупности с математическим аппаратом ярусно-параллельных графов и математического программирования.
Реализация в программируемых логических интегральных схемах ПЛИС процессорных элементов с разделяемой производительностью позволяет удобно использовать аппарат виртуальных процессоров для решения задачи распараллеливания вычислительного процесса и минимизации физических ресурсов для выполнения ЗНЗ с заданными требованиями по времени выполнения.
Возможности программируемой реконфигурации разрабатываемых в настоящее время ПЛИС процессорных элементов с разделяемой производительностью целесообразно использовать для построения эффективных расписаний загрузки процессоров БВС.
Литература
Гохрингер Д., Хюбнер М., Бекер Ю. Архитектура адаптивных многопроцессорных систем на кристалле: новая степень свободы при проектировании систем и в поддержке при выполнении // Мир радиоэлектроники. М.: ТЕХНОСФЕРА, 2012. С. 146–173.
Хитт Д. Стратегия Xilinx – быстрее двигаться к адаптируемому, интеллектуальному миру // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. 2018. № 4. С. 84–87.
Xilinx Ultrascale + Обзор. [Электронный ресурс]. URL: https://developer.ridgerun.com/wiki/index.php?title=Xilinx_-Ultrascale%2B_Overview
Кофман А. В. Сетевые методы планирования: Применение системы ПЕРТ и ее разновидностей при управлении производственными и научно-исследовательскими проектами / Пер. с фр. М.: Прогресс, 1968. 181 с.
Сетевой график. [Электронный ресурс].
URL: http://www.stroitelstvonew.ru/1/sete-voy_grafik. shtml.
Вагнер Г. Основы исследования операций. Том 1 / Пер. с англ. М.: МИР, 1972. 336 с.
Назаров С. В. Операционные системы специализированных вычислительных комплексов: теория построения и системного проектирования. М.: Машиностроение, 1989. 400 с.
Отзывы читателей
