Устройство управления выбором средств распараллеливания циклических участков программного кода

Полезная модель относится к вычислительной технике, в частности к области создания (программирования) параллельных программ. Технической задачей и результатом разработки полезной модели является сокращение временных затрат на выполнение сложных расчетов в циклических участках программ за счет автоматического выбора оптимального (с минимальным временем работы распараллеленного участка) средства распараллеливания под каждый цикл и текущего числа итераций (повторений) в цикле программы.
В последнее время в сфере инженерных и научно-технических расчетов, задач моделирования, задач реального времени наметилась тенденция в сторону отказа от последовательных решений и классических однопроцессорных компьютеров. Практически все современное создаваемое программное обеспечение в указанных выше областях ориентировано на параллельные вычислительные среды. Одновременно с возрастанием потребности в параллельных программах и с распространением многоядерных (многопроцессорных) вычислительных систем разработка параллельных программ становится все более актуальней, поскольку целесообразно максимально полно использовать все имеющиеся возможности современных ЭВМ. При этом многие вычислительные задачи наиболее эффективно решаются с помощью многоядерных вычислительных систем с общей памятью (SMP Symmetric Multiprocessing) [1].
В настоящее время ведутся интенсивные исследования в области применения всевозможных автоматизаций при создании параллельных программ, в частности в области создания инструментов разработки, отладки и исследования параллельных программ. Популярность систем с общей памятью подтверждается ростом и развитием количества всевозможных средств распараллеливания - стандартов и технологий таких как OpenCL, OpenMP, C++AMP, TBB, Cilk Plus, OpenACC и др., ориентированных на параллельное программирование, т.е. создание параллельных программ. Несмотря на то, что все средства распараллеливания предоставляют программисту возможности работы с параллельными потоками, их интерфейсы и внутренняя структура сильно отличаются. На данный момент не существует точного метода определения наиболее эффективного средства распараллеливания кроме сравнения их между собой применительно к конкретной решаемой задаче [2]. Таким образом в зависимости от текущего контекста программы для одного и того же участка программного кода эффективность различных средств распараллеливания будет отличаться. Критерием эффективности распараллеливания является время выполнения прикладной задачи при идентичных требованиях к аппаратному и программному обеспечению.
Непосредственным объектом распараллеливания в целевой программе целесообразно рассматривать циклические участки программы, т.к. около 80% времени работы программы занимает выполнение именно циклов [3]. Таким образом сокращение временных затрат на выполнение целевой программы предполагает распараллеливание циклических участков целевой программы многопоточное параллельное выполнение в многоядерных ПЭВМ.
Средства распараллеливания для разработчика представляются «черным ящиком», они применяются с помощью внесения в программный код специальных дополнений (директив), представленных на фиг. 1.
В практической работе по применению средств распараллеливания было установлено, что существует зависимость времени выполнения цикла от применяемого средства распараллеливания, реализовавшего распараллеливание данного цикла и от количества итераций цикла.
Разные средства распараллеливания имеют свои особенности, и в зависимости от входных параметров распараллеливаемого программного кода могут обладать разной эффективностью работы представленных на фиг. 2. Всего на фиг. 2 представлено 4 цикла с разной длинной (количеством итераций). Каждый циклический участок имеет характеристические параметры такие как номер цикла, количество повторений (итераций) в процессе работы программы и времени выполнения данного цикла. Прямоугольниками обозначены времена выполнения, соответствующих распаралливаемых циклов для указанных средств распараллеливания. Обозначениями T показаны суммарные времена работы целевой программы (состоящей из 4-х циклов), распараллеленной с помощью указанных технологий: Ts - Serial (последовательное выполнение), Tс - Cilk Plus, To - OpenMP, TBT - Boost Threads, TT - TBB. Максимальной эффективности (минимального времени) работы распараллеливаемой целевой программы можно достичь, если обеспечить возможность выбора технологии распараллеливания индивидуально для каждого цикла. Таким образом, оптимальное (Optimal) время выполнения программы будет составлять , где - минимальное среди всех средств распараллеливания время работы i-го цикла, N - число запусков распараллеливаемых циклов.
Заявленное устройство выполняет автоматический выбор оптимального средства распараллеливания циклического участка с минимальным временем выполнения цикла.
Наиболее близким к заявленному устройству решением является система [4], в состав которой входит база знаний, машина логического вывода, рабочая память, блок объяснения, пользовательский интерфейс, блок приобретения знаний. А также близким решением является подход к использованию нескольких средств распараллеливания в одной разрабатываемой программе [5].
Структурная схема заявленного устройства представлена на фиг. 5.
БЗРС - Блок знаний результирующей статистики (1) предназначен для хранения данных результирующей статистики быстрого выбора номера средства распараллеливания полученной устройством в ходе работы и проведенным расчетам, правил и критериев выбора средства распараллеливания по входным параметрам. Вход 1 блока БЗРС соединен с выходом 7 блока МЛВ (2). Выход 3 блока БЗРС соединен с входом 1 блока МЛВ (2). Вход 2 блока БЗРС соединен с выходом 4 блока БОН (10).
МЛВ - Машина логического вывода (2) предназначена для обеспечения логических и арифметических действий с данными, хранящимися в блоке БРП (3), блоке БЗРС (1) и блоке БОН (10), а также для осуществления управляющих действий, запросов, передачи и приема команд и сигналов, необходимых при работе устройства. Входы 1, 2, 3 и 9 блока МЛВ соединены с выходами: 3 блока БЗРС (1), выходом 2 блока БРП (3), выходом 2 блока БПЗ (6) и выходом 3 блока БОН (10) соответственно. Выходы 4, 5, 6, 7 и 8 соединены с входами: 2 блока БОН (10), входом 2 блока БХС (8), входом 1 блока БО (4), входом 1 блока БЗРС (1) и входом 1 блока БРП (3) соответственно.
БРП - Блок рабочей памяти (3) предназначен для хранения в памяти необходимых исходных данных (БИД 3.1) для выполнения тестового прогона в блоке БПК (7) и получения первичной статистики, хранения модифицированного программного кода целевой программы (БПК 3.2), хранения библиотек средств распараллеливания (БСР 3.3), необходимых для осуществления процесса распараллеливания. Входы 1 и 4 блока БРП (3) соединены с выходами: 8 блока МЛВ (2) и 3 блока БТП (7) соответственно, выходы 2 и 3 блока БРП (3) соединены с входами: 2 блока МЛВ (2), 1 блока БТП (7) соответственно.
БО - Блок объяснения (4) предназначен для передачи в блок ПИ (5) информационных сообщений при загрузке и подготовке исходных данных и другой информации в блоке БРП (3), а также передачи выходного параметра номера средства распараллеливания, выбранного устройством на совместно работающую целевую программу через блок ПИ (5). Входы 1 и 2 блока ПИ (5) соединены выходами: 3 блока БО (4) и 1 блока БПЗ (6) соответственно. Выходы 3 и 4 блока ПИ (5) соединены с входами: 2 блока БО (4) и 3 блока БПЗ (6) соответственно.
ПИ - Пользовательский интерфейс (5) предназначен для взаимодействия с пользователем (программистом-разработчиком) или с целевой программой, для оптимизации которой используется заявленное устройство. Входы 1, 2 блока ПИ (5) и выходы 3, 4 блока ПИ (5) соединены с выходами 3, 1 и входами 2, 3 блока БО (4), блока БПЗ (6) соответственно. Вход 6 и выход 5 блока ПИ (5) являются основными внешними входом и выходом заявленного устройства.
БПЗ - Блок приобретения знаний (6) предназначен для организации диалоговой процедуры, целью которой является ввод и корректировка сохраненных данных в блок БРП (3) через блок МЛВ (2). Вход 3 соединен с выходом 4 блока ПИ (5). Выход 2 и 1 блока БПЗ (6) соединены с входом 3 блока МЛВ (2) и входом 2 блока ПИ (5) соответственно.
БТП - Блок тестового прогона (7) предназначен для осуществления тестового запуска введенного программного кода БПК (3.2), запроса и применения при необходимости исходных данных БИД (3.1) и средств распараллеливания БСР (3.3), выходными параметрами блока БТП (7) является первичная статистика тестового прогона в виде табличной строки профиля конкретного цикла в составе: номера цикла, количества итераций, номера средства распараллеливания и времени выполнения. Вход 1 соединен с выходом 3 блока БРП (3). Выход 2 соединен с входом 1 блока БХС (8). Выход 3 соединен с входом 4 блока БРП (3).
БХС - Блок хранения статистики (8) предназначен для хранения статистики, полученной из блока БТП (7). Статистические данные формируются в результате тестового прогона или добавляются вручную. Вход 1 соединен с выходами 2 блока БТП (7), вход 2 соединен с выходом 5 блока МЛВ (2). Выход 3 соединен с входом 1 блока БОВ (9).
БОВ - Блок оценки времени выполнения цикла средствами распараллеливания (9) предназначен для обработки статистики, получаемой из блока БХС (8) и формирования временных отсчетов для получения выборок статистики каждого цикла при определенном числе итераций, а также специальной обработки полученных статистических данных с построением сглаженной эмпирической функции распределения времени, и проведения оценки времени выполнения по верхней границе доверительного интервала для каждого средства распараллеливания. Вход 1 соединен с выходом 3 блока БХС (8). Выход 2 соединен с входом 1 блока БОН (10).
БОН - Блок определения номера (10) предназначен для преобразования обработанной статистики, полученной из блока БОВ (9), в массив оптимальных средств (результирующей статистики) распараллеливания для каждого циклического участка программы и передачи в блок БЗРС (1), данный массив позволяет выполнять ускоренный поиск номера оптимального средства распараллеливания циклов и значительно сократить время программы в целом. Входы 1 и 2 блока БОН (10) соединены с выходами 2 блока БОВ (9) и 4 блока МЛВ (2) соответственно. Выходы 3 и 4 блока БОН (10) соединены с входами 9 блока МЛВ (2) и 2 блока БЗРС (1) соответственно.
На предварительном этапе, представленном на фиг. 3 при подготовке разрабатываемой целевой программы для работы совместно с заявленным устройством, разработчик (программист) определяет в программном коде наиболее затратные циклы (циклические участки программы) номерует их, добавляет дополнительные метки начала и конца цикла, далее копирует их в код программы, создавая так называемые клоны циклов. Затем добавляет в каждый клон средство распараллеливания в виде специальных директив из доступного ему набора средств распараллеливания (см. фиг.1). Таким образом, каждый цикл получает одинаковое количество клонов, равное количеству доступных средств распараллеливания.
Под целевой программой понимается разрабатываемая программа, требующая максимально эффективного использования предоставленных аппаратно-технических возможностей, т.е. распараллеливания, такая как программа управления, моделирования, сложных математических расчетов в реальном масштабе времени.
Тело программного кода увеличивается на определенное количество клонов циклов, равное количеству средств распараллеливания, но при этом продолжительность исполнения программы остается прежней, так как в процессе исполнения все клоны не выполняются, выполняется только один выбранный заявленным устройством это показано на фиг. 4. Процесс управления оптимальным выбором клона (с примененным средством распараллеливания) позволяет снизить временные затраты выполнения циклических участков программы и в целом всей программы. Это связано с тем, что временные затраты на выполнение одного и того же циклического участка с заданным количеством итераций при применении разных средств распараллеливания будут существенно отличаться. Поэтому оптимизация выбора ветки (клона) программы позволяет снизить временные затраты на выполнение цикла и программы в целом. Работа устройства автоматизирована, по входным параметрам циклического участка целевой программы (номера цикла и количества итераций в цикле). Заявленным устройством вырабатывается решение о применяемом средстве распараллеливания и формируется команда о подключении одной из веток клонированного данного циклического участка программы с минимальным временем распараллеливания цикла.
Работа устройства предполагает два этапа. Первый этап подготовительный, необходим для загрузки кода целевой программы, исходных данных и библиотек средств распараллеливания, а также выполнения тестового прогона целевой программы и наполнение начальной статистики. Второй этап - это непосредственно работа устройства с автоматическим выбором средства распараллеливания под каждый циклический участок целевой программы, взаимодействующей с заявленным устройством.
На первом этапе устройство подготавливается к работе, с этой целью на вход 6 блока ПИ (5) последовательно вводятся: код целевой программы, исходные данные и библиотеки средств распараллеливания, с выхода 4 которого пакеты поступают на вход 3 блока БПЗ (6), с выхода 2 которого поступают на вход 3 блока МЛВ (2) и с выхода 8 которого поступают на вход 2 блока БРП (3) (БИД (3.1), БПК (3.2), БСР (3.3)) соответственно на этом подготовка устройства к тестовому прогону заканчивается.
После этого по команде оператора с выхода 4 блока ПИ (5) формируется команда на включение устройства в режим тестового «прогона» целевой программы для сбора первичной статистики, сформированная управляющая команда в виде сигнала подается на вход 3 блока БПЗ (6), с выхода 2 которого подается на вход 3 блока МЛВ (2) с последующей передачей с выходов 4,5,6,7,8 на соответствующие входы: вход 2 блока БОН (10), вход 2 блока БХС (8), вход 1 блока БО (4), вход 1 блока БЗРС (1), вход 1 блока РП (3) для инициирования их работы в заданном режиме.
После получения управляющего сигнала о начале работы устройства, с выхода 3 блока БПК (3.2) на вход 1 блока БТП (7) подается модифицированный программный код с последующей загрузкой исходных данных из блока БИД (3.1) для тестового прогона. В блоке БТП (7) на основании модифицированной программы и исходных данных выполняется тестовый прогон всех клонов всех циклов с фиксацией номера цикла, времени его начала и конца, количества итераций в данном цикле, а также номера средства распараллеливания. Применение средств распараллеливания происходит по директивам, установленным перед каждым клоном циклического участка программы. При обнаружении директивы на распараллеливание очередного клона циклического участка с выхода 3 блока БТП (7) формируется команда запроса на подключение библиотеки средства распараллеливания к данному клону для управления распараллеливанием клона, которая подается на вход 4 блока БСР(3.3).
По окончанию выполнения одного из клонов данного циклического участка фиксируется время выполнения клона. Последующие клоны циклических участков целевой программы выполняются аналогичным образом.
На выходе 2 блока БТП формируются параметры время-итерационный профиля цикла для каждого клона в виде четырех параметров (номера цикла, количества итераций, номера средства распараллеливания, время выполнения клона данного цикла), которые подаются на вход 1 блока БХС (8) для наполнения таблицы первичной статистики (время-итерационного профиля). Модифицированный программный код целевой программы целиком «прогоняется» блоком БТП (7) с формированием время-итерационного профиля всех циклов и клонов циклов.
В связи с тем, что параметр времени выполнения цикла является случайной величиной, и функция распределения вероятности времени выполнения цикла неизвестна, поэтому возникает необходимость повторно 3-5 раз выполнять «тестовый прогон» для сбора достаточного количества статистических данных и последующего формирования временной выборки из профиля статистики с 3-5 отсчетами под каждый цикл и средство распараллеливания.
Накопленные в блоке БХС (8) данные первоначальной статистики с выхода 3 подаются на вход 1 блока БОВ (9), где происходит обработка первичных поступивших на вход статистических данных, математически строятся эмпирические функции распределения времени выполнения каждого цикла для определенного числа итераций [6], каждая эмпирическая функция распределения аппроксимируется гладкой кривой с применением полиномов Бернштейна [7], оцениваются значения верхней границы доверительного интервала времени выполнения каждого цикла для определенного числа итераций, формируется измененный время-итерационный профиль для каждого цикла в виде (номер цикла, количество итераций, номер средства распараллеливания, верхняя граница времени выполнения данного цикла). Полученный измененный профиль передается с выхода 2 на вход 1 блока БОН (10).
В блоке БОН (10) для всех поступивших и обработанных в блоке БОВ (10) время-итерационных профилей каждого цикла формируется массив результирующей статистики оптимальных средств распараллеливания цикла. Таким образом, результирующая статистика имеет вид массива с интервалами начального и конечного числа итераций цикла, номера оптимального средства распараллеливания для этого интервала итераций. С выхода 4 блока БОН (10) на вход 2 блока БЗРС(1) подается результирующая статистика для сохранения и последующего использования при выборе средства распараллеливания, что позволит осуществлять быстрый выбор оптимально средства.
На втором этапе функционирования заявленного устройства, когда происходит совместная работа целевой программы и подключенного к ней устройства, работа происходит следующим образом, с целевой программы на вход 6 блока ПИ (5) подаются входные данные, полученные от целевой программы в виде номера цикла и количества итераций в цикле, с выхода 4 которого эти данные подаются на вход 3 блока БПЗ (6) и с выхода 2 которого подаются на вход 3 блока МЛВ (2). На другой вход 1 блока МЛВ (2) с выхода 3 блока БЗРС (1) подается массив результирующей статистики оптимальных средств распараллеливания цикла. На основе входных данных и имеющихся результирующих статистик, в блоке МЛВ (2) выполняется их сравнение и делается вывод о попадании входных данных в соответствующий итерационный интервал массива результирующей статистики и мгновенно происходит выбор оптимального средства распараллеливания. По результатам выбора номера оптимального средства распараллеливания формируется ответный сигнал с номером средства, который с выхода 6 блока МЛВ (2) подается на вход 1 блока БО (4), и далее с выхода 3 которого поступает на вход 1 блока ПИ (5) и через выход 5 блока ПИ (5) подается на управление подключением оптимального средства в целевой программе совместно работающей с заявленным устройством.
При непопадании в сформированные интервалы результирующей статистики, поступившие входные данные с выхода 4 блока МЛВ (2) подаются на вход 2 блока БОН (10), где производится математический расчет времени выполнения цикла по графикам аппроксимированных трендов изменения времени от количества итераций для доступных средств распараллеливания. Далее производится выбор оптимального средства по минимальному времени выполнения цикла и с выхода 3 блока БОН (10) сигнал поступает на вход 9 блока МЛВ (2), а далее на выход 6 и дальнейшие этапы аналогичны при попадании входных данных цикла в итерационный интервал.
В текущем режиме совместной работы целевой программы и заявленного устройства собирается статистика выполнения циклических участков целевой программы и происходит систематическое пополнение первичной статистики в блоке БХС (8) для корректировки массива результирующей статистики оптимальных средств распараллеливания.
Кроме того, данные находящиеся в блоке БХС (8) и данные находящиеся в блоке БЗРС (1), могут быть скорректированы через блок ПИ (5) в ручном режиме.
Элементы заявленной полезной модели выполнены в виде программно-технических модулей на плате расширения ПЭВМ архитектуры типа х86.
Путем проведения экспериментов на исследовательском моделирующем комплексе военных действий в Военной академии воздушно-космической обороны имени Маршала Советского Союза Г.К. Жукова, было установлено, что применение заявленного устройства позволяет сократить время на получение результатов моделирования и оперативно-тактических расчетов в 1,3-1,4 раза.
Представленный вариант заявленного устройства не исчерпывает возможные способы его практического исполнения.
Источники, принятые во внимание:
1. Automatic Paralleli/ation. Carnegie Mellon University, HPCA-4, February 1-4, 1998. Sutter H. The Free Lunch Is Over A Fundamental Turn Toward Concurrency in Software. Dr. Dobb's Journal, March 2005.
2. Аксенов М.А. Анализ технологий параллельного программирования для применения в моделирующих комплексах военного назначения в интересах повышения эффективности моделирования//Сборник научных трудов IV Всероссийской научно-практической конференции «Актуальные вопросы состояния и перспектив развития сложных технических систем военного назначения» ВУЦ МГТУ имени Н.Э. Баумана. 2020. С.77-86.
3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Спб.:Санкт-Петербург, 2002. 608 с.
4. Джаратано Д., Райли Г. Экспертные системы. Принципы разработки и программирования. - М.: Издательский дом "Вильяме", 2007, рис. 1.6, с. 70;
5. Андреев А.Е. Технологии программирования многопроцессорных систем: учеб. пособие / Андреев А.Е., Егунов В.А., Шаповалов О.В.; ВолгГТУ. Волгоград, 2015. 103 с.
6. Красовский Ю.М. Математические основы военной кибернетики [Текст]: (Учеб. пособие) / Ю.М. Красовский, М.С. Любушкин; Отв. ред. М.С. Любушкин; Воен. командная акад. противовоздуш. обороны. Кафедра №12. - Калинин: [б. и.], 1971. - 446 с.
7. Голик Ф.В. Аппроксимация эмпирических распределений вероятностей полиномами Бернштейна. Журнал радиоэлектроники [электронный журнал]. 2018. №7.