eng
Выпуск #10/2020
С.Назаров, А.Барсуков
ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ БОРТОВЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. Часть 1
ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ БОРТОВЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. Часть 1
Просмотры: 792
DOI: 10.22184/1992-4178.2020.201.10.110.116
Развитие бортового оборудования космических, летательных и других объектов характеризуется постоянным увеличением числа решаемых задач, повышением их сложности, расширением интеллектуальных и адаптивных возможностей. Выполнение этих требований возможно путем организации параллельных вычислительных процессов.
Развитие бортового оборудования космических, летательных и других объектов характеризуется постоянным увеличением числа решаемых задач, повышением их сложности, расширением интеллектуальных и адаптивных возможностей. Выполнение этих требований возможно путем организации параллельных вычислительных процессов.
Теги: critical path information-related tasks multiprocessor system parallel computing process информационно-связанные задачи критический путь многопроцессорная система параллельный вычислительный процесс
Оптимизация параллельных вычислений бортовых систем реального времени. Часть 1
С. Назаров, д. т. н., А. Барсуков, к. т. н.
Развитие бортового оборудования космических, летательных и других объектов характеризуется постоянным увеличением числа решаемых задач, повышением их сложности, расширением интеллектуальных и адаптивных возможностей. Это приводит к усложнению бортовой вычислительной системы (БВС). На время решения задач, возлагаемых на БВС, накладываются жесткие временные ограничения. Выполнение этих требований возможно путем организации параллельных вычислительных процессов.
Актуальность тематики параллельных вычислений осознана достаточно давно как в связи с низкой надежностью и производительностью компьютеров, так и в связи с появлением многопроцессорных систем и многоядерных процессоров. Последние годы активно используются программируемые логические матрицы, и, видимо, недалеко то время, когда появятся программируемые матрицы процессорных элементов. Технология обеспечения надежности и высокой производительности на основе параллельных вычислений естественным образом стала преобладающей в бортовых вычислительных системах реального времени. На время решения большинства задач, возлагаемых на БВС, накладываются жесткие временные ограничения. Часто встает вопрос максимально возможного сокращения времени выполнения этих задач. Реализация этих требований приводит к необходимости организации параллельных вычислительных процессов.
В данной работе представлена совокупность математических моделей, формулировок задач и подходов к их решению, позволяющих построить параллельный вычислительный процесс реализации информационно-связанных задач в минимально возможное время в условиях заданных ограничений по вычислительной среде. Математической основой решения являются теория графов, сетевого планирования и управления и расписаний.
Как правило, наборы программ, реализуемых современными бортовыми вычислительными системами (БВС), можно представить совокупностью информационно-связанных подпрограмм (заданным набором задач – ЗНЗ). Это позволяет представлять решаемые задачи в виде нагруженного графа и, соответственно, использовать для их анализа методы теории графов и сетевого планирования и управления. ЗНЗ обладает достаточным внутренним параллелизмом, который может быть удобно использован при реализации задач многопроцессорными (многоядерными) бортовыми системами. Основной недостаток этого подхода связан с тем, что архитектура аппаратных средств многопроцессорной системы зачастую фиксируется на этапе проектирования и остается неизменной на время выполнения программ. Это означает, что разработчик должен выбирать соответствующую систему для предполагаемых приложений. С этой целью разработчик должен разбить приложение на части, рассмотреть возможности параллелизма при выполнении приложения и выбрать соответствующую систему для своего приложения. Ограничением такого подхода является недостаток распространенных существующих многопроцессорных систем, заключающийся в отсутствии адаптивности на стадии разработки и во время выполнения программы [1].
Программируемая разработчиком логическая матрица предлагает более гибкое решение, потому что с ее помощью аппаратные средства можно переконфигурировать с новыми функциями и использовать повторно с различными приложениями. Некоторые поставщики программируемых пользователем логических матриц (компания Xilinx) предлагают специальную функцию, называемую динамическим и частичным переконфигурированием [2]. Это означает, что часть аппаратных средств системы может быть изменена во время выполнения программы, а другая часть остается действующей и неизменной. Программируемая логика от Xilinx позволяет применять интеллектуальные решения в широчайшем спектре отраслей промышленной, научной и потребительской деятельности человека. Это программируемые логические интегральные схемы ПЛИС (FPGA), 3D-микросхемы и системы на кристалле (SoC), которые устанавливают стандарты низкой стоимости, высокой производительности и пониженного энергопотребления.
Архитектура Xilinx UltraScale™ дает беспрецедентный уровень интеграции и возможностей, обеспечивая при этом производительность на системном уровне ASIC-класса для самых требовательных приложений, требующих высочайшей пропускной способности, быстродействия памяти, массовых потоков данных, DSP и производительности обработки пакетов [3].
Постановка задачи
Предположим: задана структура приложения, состоящего из некоторого множества информационно-связанных частей (задач) с известным (ожидаемым) временем выполнения каждой задачи заданного набора задач. Примем следующие ограничения и допущения по ЗНЗ:
С учетом заданных ограничений необходимо определить следующие требования:
В данной статье рассмотрим возможное решение, позволяющее на основе анализа приложения определить целесообразную структуру многопроцессорной системы с выполнением требований на время выполнения приложений. Все далее принимаемые решения и разрабатываемые модели будем сразу иллюстрировать конкретными примерами.
Структуру подлежащего выполнению приложения удобно представить графом, например, как это показано на рис. 1, который будем далее использовать для иллюстрации решения поставленной задачи:
G = {⟨zi, zj⟩, tij | j > i, i = 0, 1, ..., M – 2, j = 1, 2, ..., M – 1},
где zi, zj – номера событий (вершины) в графе; tij – время решения задачи (вес соответствующей дуги) при использовании одного вычислителя; M – количество задач в пакете G.
Для дальнейшей формализации задачи будем использовать понятия сетевого планирования и управления. В нашем случае работы представляются дугами графа ⟨zi, zj⟩ или просто «i, j», причем для любой дуги j > i. Обмен информацией между задачами инициируется событиями, например, событие z1 инициирует завершение работы ⟨z0, z1⟩ длительность t01 – возможность запуска вычислений ⟨z1, z4⟩, ⟨z1, z5⟩ и ⟨z1, z6⟩. Организация вычислительного процесса при выполнении данного приложения сводится к определению временных параметров сетевого графика и его оптимизации по длительности выполнения всего комплекса задачи и затратам вычислительных ресурсов в соответствии с заданными требованиями.
Решение задачи
Определение величины критического пути и резервов времени по отдельным вычислительным работам при выделении для каждой работы одного вычислителя
Критический путь Tkr – это полный путь, определяющий длительность всего комплекса вычислительных работ и имеющий наибольшую продолжительность. Для решения поставленной задачи необходимо найти длину критического пути и возможные резервы времени при выполнении отдельных вычислительных работ. Определение длины критического пути можно проводить различными способами. Наиболее удобным способом расчета сетевого графика при небольшом количестве работ является расчет непосредственно на сети графика и заключается в нахождении критического пути и определении резервов времени для работ, которые не располагаются на этом пути.
При производстве расчетов сетевых моделей применяют следующие наименования его параметров [4, 5]:
1. Общий резерв времени работы Rij характеризуется возможностью роста продолжительности работы без увеличения продолжительности критического пути и определяется, как разность между поздним и ранним окончанием рассматриваемой работы. Общий резерв работы принадлежит не только первой работе, но и всем последующим работам данного пути. В случае использования на одной из работ общего резерва критический путь не изменит своей продолжительности, но все последующие работы окажутся критическими и лишатся резерва.
2. Частный резерв времени работы rij характеризуется возможностью увеличения продолжительности работы без изменения раннего начала последующей работы и определяется разностью между ранним началом последующей работы и ранним окончанием рассматриваемой работы. Частный резерв имеет место, когда одним событием заканчивается не менее двух работ. Отличие частного резерва от общего заключается в том, что частный резерв может быть использован только на рассматриваемой или предшествующих работах и не может быть использован на последующих.
3. Полным резервом некоторого пути в сетевой модели R называют разность между продолжительностью критического пути модели и продолжительностью рассматриваемого пути. Результаты расчета сетевой модели выполнения ЗНЗ, представленного на рис. 1, приведены в табл. 1. Работы, не имеющие резерва времени и выделенные жирным шрифтом, образуют критический путь Tkr = 240.
Если заданное значение времени T ≥ Tkr и разработчика это устраивает, то можно считать, что задача в части директивного времени решения ЗНЗ выполнена и предварительно определить требуемое количество вычислителей Vmin. Полное время занятости вычислителей можно найти, просуммировав значения времени выполнения отдельных задач:
. (1)
Минимальное количество вычислителей в этом случае можно определить, разделив вычислительную нагрузку на длину критического пути, то есть
Vmin ≥ Tз / Tkr = 4. (2)
Если выделить один вычислитель на выполнение задач, образующих критический путь, то оставшаяся вычислительная нагрузка потребует для своего выполнения еще не менее трех вычислителей. Знак «больше или равно» в соотношении (2) определяется тем фактом, что организация параллельного вычислительного процесса может потребовать дополнительного числа вычислителей.
Минимизация длины критического пути
Проведенные расчеты показывают, что при выделении для каждой задачи ЗНЗ одного вычислителя время решения заданного набора задач не может быть меньше, равного 240 условным временным единицам. Рассмотрим, какие имеются возможности для сокращения времени решения ЗНЗ, а в нашем случае – сокращения длины критического пути.
Повышение производительности вычислителей БВС
Наиболее простое решение – использование вычислителей более высокой производительности. Это – «лобовое» решение, которое, конечно, приведет к уменьшению времени критического пути. Однако оно, во‑первых, не всегда возможно, во‑вторых, может привести к неполному использованию вычислительных возможностей бортовой вычислительной системы и, наконец, удорожает всю систему.
Отметим еще одну особенность использования вычислителей БВС. Как все современные процессорные элементы, вычислитель БВС работает в режиме квантования процессорного времени, что позволяет организовать его мультипрограммную работу. Режим разделения времени позволяет рассматривать один физический вычислитель как совокупность виртуальных вычислителей (процессоров), которые могут выделяться отдельным задачам ЗНЗ. При этом суммарная производительность физического вычислителя, за исключением издержек мультипрограммирования (которыми далее пренебрегаем), равна сумме производительности его виртуальных вычислителей.
Использование имеющегося резерва времени вычислителей БВС
Имеющийся резерв времени по работам, не лежащим на критическом пути, свидетельствует о том, что имеется возможность изъятия некоторых временных ресурсов с целью добавления времени на работы, лежащие на критическом пути. Это приведет к уменьшению длины критического пути, то есть к сокращению всего цикла выполняемых вычислений.
В нашем примере суммарный резерв времени составляет значение
.
Передача ресурса от какой-либо работы означает увеличение ее выполнения в зависимости от величины изъятого ресурса, добавление ресурса к другой работе, лежащей на критическом пути, означает уменьшение времени ее выполнения в соответствии с величиной добавленного ресурса. Например, изъятие половины резерва, то есть 30 единиц ресурса от работы «0, 2», приводит к увеличению времени ее выполнения до 100 единиц времени. Это означает, что для ее выполнения нужен будет виртуальный процессор со следующим значением доли физического процессора
.
Изъятый ресурс можно добавить с целью сокращения критического пути, например, к работе «6, 70» (см. табл. 1). При этом время выполнения этой работы уменьшится с 80 до 50 единиц времени, но для выполнения этой работы потребуется виртуальный процессор со следующим значением доли физического процессора
.
Для решения задачи минимизации критического пути необходимо построить модель линейного программирования с целью определения значений Tkr для различных вариантов перераспределения ресурсов. Удобно это сделать в электронных таблицах, например, Excel. Воспользуемся для этого формализацией задачи поиска критического пути, предложенной в [6]. Исходные данные удобно представить в форме таблицы (табл. 2).
Задача поиска критического пути на основе табл. 2 заключается в определении значения функции
(3)
при следующих ограничениях:
x01 + 1 · x02 + 1 · x03 = 1; (4)
–1 · x01 + 1 · x13 + 1 · x14 + 1 · x16 = 0; (5)
–1 · x02 + 1 · x27 = 0; (6)
–1 · x03 – 1 · x13 + 1 · x35 = 0; (7)
–1 · x14 + 1 · x45 + 1 · x46 = 0; (8)
–1 · x35 – 1 · x45 + 1 · x57 = 0; (9)
–1 · x16 – 1 · x46 + 1 · x67 = 0; (10)
∀xij ∈ {0, 1} | i = 0, 1, ... 6; j = 1, 2, ... 7. (11)
Решение задачи (3) – (11) для исходного графа сетевой модели показано на рис. 2.
Определим теперь, как изменится величина критического пути, если 40 единиц резерва изъять у работы «4, 5» и передать их для выполнения работе «6, 7». При этом задача «4, 5» будет выполняться 80 единиц времени, а задача «6, 7» – 40 единиц времени. Решение задачи в этом случае показано на рис. 3 и дает значение критического пути, равное 220.
Если рассчитанное значение критического пути окажется больше директивного, можно рассмотреть другие варианты использования резервов других работ, пока не будет получено требуемое значение критического пути. Если этого не удается сделать за счет резервов в выполнении работ, необходимо увеличить количество ресурсов для их выполнения. В данном случае – перейти к более производительным вычислителям или переписать программы для возможности организации параллельного вычислительного процесса.
Использование потенциальной параллельности задач ЗНЗ для минимизации критического пути
Как отмечено в постановке задачи данной статьи, каждая задача ЗНЗ обладает внутренним параллелизмом. Время выполнения задачи сокращается пропорционально числу выделенных задаче вычислителей. Пусть известен возможный уровень параллелизма по каждой задаче и, соответственно, время выполнения каждой задачи ЗНЗ при максимально возможном распараллеливании (табл. 3).
Определим длину критического пути для случая достаточного количества вычислителей в БВС. В данном случае распараллеленное выполнение задач «0, 2», «1, 4», «1, 6», «2, 7», «3, 5», «4, 5», «4, 6» и «5, 7» потребует кроме основных 12 вычислителей (по одному на каждую задачу) дополнительно 11 вычислителей. Для учета этого факта достаточно в разработанной электронной таблице по рис. 3 изменить содержимое ячеек, содержащих значения tij. Решение в этом случае показано на рис. 4. Таким образом, trk = 150. Можно ли еще сократить длину критического пути? За счет распараллеливания – нет. Здесь все возможности использованы в полной мере. Осталась только одна задача критического пути «0, 1», но ее распараллелить невозможно, разве что написать заново.
Обновленные данные по параметрам сетевого графика приведены в табл. 4. Критический путь длиной 150 условных единиц образует цепочка вершин 0–1–4–5–7. Суммарная трудоемкость критического пути определяется суммой времени выполнения задач «0, 1», «1, 4», «4, 6», «6, 7» и составляет 150 условных единиц. Имеющийся общий резерв, как видно из табл. 4, составляет 240 условных единиц. Этот факт свидетельствует о возможности уменьшения числа вычислителей, выделяемых на задачи некритического пути.
Во второй части статьи будут рассмотрены вопросы минимизации количества ресурсов для выполнения пакета ЗНЗ без увеличения длины критического пути, возможности организации мультипроцессорного выполнения пакета задач, представленного сетевой моделью, вопросы минимизации загрузки БВС и предложены соответствующие математические модели, методы и алгоритмы решения этих задач.
Литература
Гохрингер Д., Хюбнер М., Бекер Ю. Архитектура адаптивных многопроцессорных систем на кристалле: новая степень свободы при проектировании систем и в поддержке при выполнении // Мир радиоэлектроники. – М.: ТЕХНОСФЕРА, 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 с.
С. Назаров, д. т. н., А. Барсуков, к. т. н.
Развитие бортового оборудования космических, летательных и других объектов характеризуется постоянным увеличением числа решаемых задач, повышением их сложности, расширением интеллектуальных и адаптивных возможностей. Это приводит к усложнению бортовой вычислительной системы (БВС). На время решения задач, возлагаемых на БВС, накладываются жесткие временные ограничения. Выполнение этих требований возможно путем организации параллельных вычислительных процессов.
Актуальность тематики параллельных вычислений осознана достаточно давно как в связи с низкой надежностью и производительностью компьютеров, так и в связи с появлением многопроцессорных систем и многоядерных процессоров. Последние годы активно используются программируемые логические матрицы, и, видимо, недалеко то время, когда появятся программируемые матрицы процессорных элементов. Технология обеспечения надежности и высокой производительности на основе параллельных вычислений естественным образом стала преобладающей в бортовых вычислительных системах реального времени. На время решения большинства задач, возлагаемых на БВС, накладываются жесткие временные ограничения. Часто встает вопрос максимально возможного сокращения времени выполнения этих задач. Реализация этих требований приводит к необходимости организации параллельных вычислительных процессов.
В данной работе представлена совокупность математических моделей, формулировок задач и подходов к их решению, позволяющих построить параллельный вычислительный процесс реализации информационно-связанных задач в минимально возможное время в условиях заданных ограничений по вычислительной среде. Математической основой решения являются теория графов, сетевого планирования и управления и расписаний.
Как правило, наборы программ, реализуемых современными бортовыми вычислительными системами (БВС), можно представить совокупностью информационно-связанных подпрограмм (заданным набором задач – ЗНЗ). Это позволяет представлять решаемые задачи в виде нагруженного графа и, соответственно, использовать для их анализа методы теории графов и сетевого планирования и управления. ЗНЗ обладает достаточным внутренним параллелизмом, который может быть удобно использован при реализации задач многопроцессорными (многоядерными) бортовыми системами. Основной недостаток этого подхода связан с тем, что архитектура аппаратных средств многопроцессорной системы зачастую фиксируется на этапе проектирования и остается неизменной на время выполнения программ. Это означает, что разработчик должен выбирать соответствующую систему для предполагаемых приложений. С этой целью разработчик должен разбить приложение на части, рассмотреть возможности параллелизма при выполнении приложения и выбрать соответствующую систему для своего приложения. Ограничением такого подхода является недостаток распространенных существующих многопроцессорных систем, заключающийся в отсутствии адаптивности на стадии разработки и во время выполнения программы [1].
Программируемая разработчиком логическая матрица предлагает более гибкое решение, потому что с ее помощью аппаратные средства можно переконфигурировать с новыми функциями и использовать повторно с различными приложениями. Некоторые поставщики программируемых пользователем логических матриц (компания Xilinx) предлагают специальную функцию, называемую динамическим и частичным переконфигурированием [2]. Это означает, что часть аппаратных средств системы может быть изменена во время выполнения программы, а другая часть остается действующей и неизменной. Программируемая логика от Xilinx позволяет применять интеллектуальные решения в широчайшем спектре отраслей промышленной, научной и потребительской деятельности человека. Это программируемые логические интегральные схемы ПЛИС (FPGA), 3D-микросхемы и системы на кристалле (SoC), которые устанавливают стандарты низкой стоимости, высокой производительности и пониженного энергопотребления.
Архитектура Xilinx UltraScale™ дает беспрецедентный уровень интеграции и возможностей, обеспечивая при этом производительность на системном уровне ASIC-класса для самых требовательных приложений, требующих высочайшей пропускной способности, быстродействия памяти, массовых потоков данных, DSP и производительности обработки пакетов [3].
Постановка задачи
Предположим: задана структура приложения, состоящего из некоторого множества информационно-связанных частей (задач) с известным (ожидаемым) временем выполнения каждой задачи заданного набора задач. Примем следующие ограничения и допущения по ЗНЗ:
- предполагается, что время выполнения каждой задачи набора определяется элементарным вычислителем (процессором или ядром) многопроцессорной бортовой вычислительной системы (БВС), и это время (в условных временных единицах) установлено в процессе отладки;
- каждая задача ЗНЗ (или часть задач) обладает внутренним параллелизмом. Время выполнения задачи сокращается пропорционально числу выделенных задаче вычислителей;
- задано максимальное количество вычислителей, которое может быть выделено задаче. Оно определяется уровнем параллелизма задачи и изменяется от одного (параллелизма в программе нет) до трех (для случая максимально возможного параллелизма);
- определено максимальное количество вычислителей, которое может быть использовано для выполнения ЗНЗ.
С учетом заданных ограничений необходимо определить следующие требования:
- Минимально возможное время решения системой ЗНЗ – T.
- Количество вычислителей Vmin, необходимое для выполнения требования 1.
- Количество вычислителей Vi, выделяемых каждой задаче ЗНЗ, необходимое для выполнения требования 1.
- Количество вычислителей Vтр., необходимое для выполнения ЗНЗ с заданным требованием по времени реализации – T.
- Количество вычислителей Vi, выделяемых каждой задаче ЗНЗ, необходимое для выполнения требования 4.
В данной статье рассмотрим возможное решение, позволяющее на основе анализа приложения определить целесообразную структуру многопроцессорной системы с выполнением требований на время выполнения приложений. Все далее принимаемые решения и разрабатываемые модели будем сразу иллюстрировать конкретными примерами.
Структуру подлежащего выполнению приложения удобно представить графом, например, как это показано на рис. 1, который будем далее использовать для иллюстрации решения поставленной задачи:
G = {⟨zi, zj⟩, tij | j > i, i = 0, 1, ..., M – 2, j = 1, 2, ..., M – 1},
где zi, zj – номера событий (вершины) в графе; tij – время решения задачи (вес соответствующей дуги) при использовании одного вычислителя; M – количество задач в пакете G.
Для дальнейшей формализации задачи будем использовать понятия сетевого планирования и управления. В нашем случае работы представляются дугами графа ⟨zi, zj⟩ или просто «i, j», причем для любой дуги j > i. Обмен информацией между задачами инициируется событиями, например, событие z1 инициирует завершение работы ⟨z0, z1⟩ длительность t01 – возможность запуска вычислений ⟨z1, z4⟩, ⟨z1, z5⟩ и ⟨z1, z6⟩. Организация вычислительного процесса при выполнении данного приложения сводится к определению временных параметров сетевого графика и его оптимизации по длительности выполнения всего комплекса задачи и затратам вычислительных ресурсов в соответствии с заданными требованиями.
Решение задачи
Определение величины критического пути и резервов времени по отдельным вычислительным работам при выделении для каждой работы одного вычислителя
Критический путь Tkr – это полный путь, определяющий длительность всего комплекса вычислительных работ и имеющий наибольшую продолжительность. Для решения поставленной задачи необходимо найти длину критического пути и возможные резервы времени при выполнении отдельных вычислительных работ. Определение длины критического пути можно проводить различными способами. Наиболее удобным способом расчета сетевого графика при небольшом количестве работ является расчет непосредственно на сети графика и заключается в нахождении критического пути и определении резервов времени для работ, которые не располагаются на этом пути.
При производстве расчетов сетевых моделей применяют следующие наименования его параметров [4, 5]:
- продолжительность работы tij (здесь i и j – номера соответственно начального и конечного событий);
- раннее начало работы t– характеризуется выполнением всех предшествующих работ и определяется продолжительностью максимального пути от исходного события всей модели до начального события рассматриваемой работы;
- раннее окончание работы t– определяется суммой раннего начала и продолжительности рассматриваемой работы;
- позднее начало работы t– определяется разностью позднего окончания и продолжительности рассматриваемой работы;
- позднее окончание работы t– определяется разностью продолжительности критического пути и максимальной продолжительности пути от завершающего события всей модели до конечного события рассматриваемой работы.
1. Общий резерв времени работы Rij характеризуется возможностью роста продолжительности работы без увеличения продолжительности критического пути и определяется, как разность между поздним и ранним окончанием рассматриваемой работы. Общий резерв работы принадлежит не только первой работе, но и всем последующим работам данного пути. В случае использования на одной из работ общего резерва критический путь не изменит своей продолжительности, но все последующие работы окажутся критическими и лишатся резерва.
2. Частный резерв времени работы rij характеризуется возможностью увеличения продолжительности работы без изменения раннего начала последующей работы и определяется разностью между ранним началом последующей работы и ранним окончанием рассматриваемой работы. Частный резерв имеет место, когда одним событием заканчивается не менее двух работ. Отличие частного резерва от общего заключается в том, что частный резерв может быть использован только на рассматриваемой или предшествующих работах и не может быть использован на последующих.
3. Полным резервом некоторого пути в сетевой модели R называют разность между продолжительностью критического пути модели и продолжительностью рассматриваемого пути. Результаты расчета сетевой модели выполнения ЗНЗ, представленного на рис. 1, приведены в табл. 1. Работы, не имеющие резерва времени и выделенные жирным шрифтом, образуют критический путь Tkr = 240.
Если заданное значение времени T ≥ Tkr и разработчика это устраивает, то можно считать, что задача в части директивного времени решения ЗНЗ выполнена и предварительно определить требуемое количество вычислителей Vmin. Полное время занятости вычислителей можно найти, просуммировав значения времени выполнения отдельных задач:
. (1)
Минимальное количество вычислителей в этом случае можно определить, разделив вычислительную нагрузку на длину критического пути, то есть
Vmin ≥ Tз / Tkr = 4. (2)
Если выделить один вычислитель на выполнение задач, образующих критический путь, то оставшаяся вычислительная нагрузка потребует для своего выполнения еще не менее трех вычислителей. Знак «больше или равно» в соотношении (2) определяется тем фактом, что организация параллельного вычислительного процесса может потребовать дополнительного числа вычислителей.
Минимизация длины критического пути
Проведенные расчеты показывают, что при выделении для каждой задачи ЗНЗ одного вычислителя время решения заданного набора задач не может быть меньше, равного 240 условным временным единицам. Рассмотрим, какие имеются возможности для сокращения времени решения ЗНЗ, а в нашем случае – сокращения длины критического пути.
Повышение производительности вычислителей БВС
Наиболее простое решение – использование вычислителей более высокой производительности. Это – «лобовое» решение, которое, конечно, приведет к уменьшению времени критического пути. Однако оно, во‑первых, не всегда возможно, во‑вторых, может привести к неполному использованию вычислительных возможностей бортовой вычислительной системы и, наконец, удорожает всю систему.
Отметим еще одну особенность использования вычислителей БВС. Как все современные процессорные элементы, вычислитель БВС работает в режиме квантования процессорного времени, что позволяет организовать его мультипрограммную работу. Режим разделения времени позволяет рассматривать один физический вычислитель как совокупность виртуальных вычислителей (процессоров), которые могут выделяться отдельным задачам ЗНЗ. При этом суммарная производительность физического вычислителя, за исключением издержек мультипрограммирования (которыми далее пренебрегаем), равна сумме производительности его виртуальных вычислителей.
Использование имеющегося резерва времени вычислителей БВС
Имеющийся резерв времени по работам, не лежащим на критическом пути, свидетельствует о том, что имеется возможность изъятия некоторых временных ресурсов с целью добавления времени на работы, лежащие на критическом пути. Это приведет к уменьшению длины критического пути, то есть к сокращению всего цикла выполняемых вычислений.
В нашем примере суммарный резерв времени составляет значение
.
Передача ресурса от какой-либо работы означает увеличение ее выполнения в зависимости от величины изъятого ресурса, добавление ресурса к другой работе, лежащей на критическом пути, означает уменьшение времени ее выполнения в соответствии с величиной добавленного ресурса. Например, изъятие половины резерва, то есть 30 единиц ресурса от работы «0, 2», приводит к увеличению времени ее выполнения до 100 единиц времени. Это означает, что для ее выполнения нужен будет виртуальный процессор со следующим значением доли физического процессора
.
Изъятый ресурс можно добавить с целью сокращения критического пути, например, к работе «6, 70» (см. табл. 1). При этом время выполнения этой работы уменьшится с 80 до 50 единиц времени, но для выполнения этой работы потребуется виртуальный процессор со следующим значением доли физического процессора
.
Для решения задачи минимизации критического пути необходимо построить модель линейного программирования с целью определения значений Tkr для различных вариантов перераспределения ресурсов. Удобно это сделать в электронных таблицах, например, Excel. Воспользуемся для этого формализацией задачи поиска критического пути, предложенной в [6]. Исходные данные удобно представить в форме таблицы (табл. 2).
Задача поиска критического пути на основе табл. 2 заключается в определении значения функции
(3)
при следующих ограничениях:
x01 + 1 · x02 + 1 · x03 = 1; (4)
–1 · x01 + 1 · x13 + 1 · x14 + 1 · x16 = 0; (5)
–1 · x02 + 1 · x27 = 0; (6)
–1 · x03 – 1 · x13 + 1 · x35 = 0; (7)
–1 · x14 + 1 · x45 + 1 · x46 = 0; (8)
–1 · x35 – 1 · x45 + 1 · x57 = 0; (9)
–1 · x16 – 1 · x46 + 1 · x67 = 0; (10)
∀xij ∈ {0, 1} | i = 0, 1, ... 6; j = 1, 2, ... 7. (11)
Решение задачи (3) – (11) для исходного графа сетевой модели показано на рис. 2.
Определим теперь, как изменится величина критического пути, если 40 единиц резерва изъять у работы «4, 5» и передать их для выполнения работе «6, 7». При этом задача «4, 5» будет выполняться 80 единиц времени, а задача «6, 7» – 40 единиц времени. Решение задачи в этом случае показано на рис. 3 и дает значение критического пути, равное 220.
Если рассчитанное значение критического пути окажется больше директивного, можно рассмотреть другие варианты использования резервов других работ, пока не будет получено требуемое значение критического пути. Если этого не удается сделать за счет резервов в выполнении работ, необходимо увеличить количество ресурсов для их выполнения. В данном случае – перейти к более производительным вычислителям или переписать программы для возможности организации параллельного вычислительного процесса.
Использование потенциальной параллельности задач ЗНЗ для минимизации критического пути
Как отмечено в постановке задачи данной статьи, каждая задача ЗНЗ обладает внутренним параллелизмом. Время выполнения задачи сокращается пропорционально числу выделенных задаче вычислителей. Пусть известен возможный уровень параллелизма по каждой задаче и, соответственно, время выполнения каждой задачи ЗНЗ при максимально возможном распараллеливании (табл. 3).
Определим длину критического пути для случая достаточного количества вычислителей в БВС. В данном случае распараллеленное выполнение задач «0, 2», «1, 4», «1, 6», «2, 7», «3, 5», «4, 5», «4, 6» и «5, 7» потребует кроме основных 12 вычислителей (по одному на каждую задачу) дополнительно 11 вычислителей. Для учета этого факта достаточно в разработанной электронной таблице по рис. 3 изменить содержимое ячеек, содержащих значения tij. Решение в этом случае показано на рис. 4. Таким образом, trk = 150. Можно ли еще сократить длину критического пути? За счет распараллеливания – нет. Здесь все возможности использованы в полной мере. Осталась только одна задача критического пути «0, 1», но ее распараллелить невозможно, разве что написать заново.
Обновленные данные по параметрам сетевого графика приведены в табл. 4. Критический путь длиной 150 условных единиц образует цепочка вершин 0–1–4–5–7. Суммарная трудоемкость критического пути определяется суммой времени выполнения задач «0, 1», «1, 4», «4, 6», «6, 7» и составляет 150 условных единиц. Имеющийся общий резерв, как видно из табл. 4, составляет 240 условных единиц. Этот факт свидетельствует о возможности уменьшения числа вычислителей, выделяемых на задачи некритического пути.
Во второй части статьи будут рассмотрены вопросы минимизации количества ресурсов для выполнения пакета ЗНЗ без увеличения длины критического пути, возможности организации мультипроцессорного выполнения пакета задач, представленного сетевой моделью, вопросы минимизации загрузки БВС и предложены соответствующие математические модели, методы и алгоритмы решения этих задач.
Литература
Гохрингер Д., Хюбнер М., Бекер Ю. Архитектура адаптивных многопроцессорных систем на кристалле: новая степень свободы при проектировании систем и в поддержке при выполнении // Мир радиоэлектроники. – М.: ТЕХНОСФЕРА, 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 с.
Отзывы читателей
