|
DOI: 10.25136/2644-5522.2021.1.35101
Дата направления статьи в редакцию:
22-02-2021
Дата публикации:
01-10-2021
Аннотация:
Рассматриваются некоторые аспекты процесса численного решения задач механики сплошной среды в условиях протекающих химических реакций. Такие задачи, обычно, отличаются наличием множества локальных областей с повышенной температурой, положение которых в пространстве относительно нестабильно. В таких условиях применяются жестко устойчивые методы интегрирования с контролем шага, которые в "горячих" областях имеют существенно большие временные затраты в сравнении с прочими областями. При использовании геометрического параллелизма данный факт приводит к существенному дисбалансу загрузки процессоров, снижающему общую эффективность распараллеливания. Поэтому в данной работе рассматривается проблема балансировки загрузки процессоров при параллельном решении вышеуказанных задач. Предложена новая модификация алгоритма крупноблочной распределенной балансировки с улучшенным предсказанием времени численного интегрирования уравнений химической кинетики, наиболее эффективная в условиях дрейфа "горячих" областей. Улучшение состоит в применении линейного персептрона, анализирующего несколько предыдущих значений времени интегрирования (в базовом варианте алгоритма используется лишь одна предыдущая точка из истории времени интегрирования). Это позволяет работать в условиях как быстрого, так и медленного дрейфа "горячих" областей. Эффективность данного подхода продемонстрирована на задаче моделирования обтекания здания, на крыше которого наблаюдается горение при высокой температуре. Показано, что применение модифицированного алгоритма повышает эффективность распараллеливания на 2,1% по сравнению с исходным алгоритмом.
Ключевые слова:
параллельные вычисления, балансировка загрузки, линейный персептрон, химическая кинетика, механика сплошной среды, распределенная балансировка, численное моделирование, численный эксперимент, апробация, геометрический параллелизм
Abstract: This article explores certain aspects of the process of numerical solution of the tasks of continuous medium mechanics in the conditions of ongoing chemical reactions. Such tasks are usually characterized by the presence of multiple local areas with elevated temperature, which position in space is relatively unstable. In such conditions, rigidly stable methods of integration with step control, which in the “elevated temperature” areas that have higher time input comparing to other areas. In terms of using geometric parallelism, this fact leads to substantial imbalance of CPU load, which reduces the overall effectiveness of parallelization. Therefore, this article examines the problem of CPU load balancing in the context of parallel solution of the aforementioned tasks. The other offers a new modification of the algorithm of large-block distributed balancing with improved time prediction of the numerical integration of chemical kinetics equations, which is most effective in the conditions of drift of the areas with “elevated temperatures”. The improvement consists in application of the linear perceptron, which analyzes several previous values of time integration (the basic version of the algorithm uses only one previous spot from the history of time integration). This allows working in the conditions of fast and slow drift of the areas with “elevated temperatures”. The effectiveness of this approach is demonstrated on the task of modeling the flow-around the building with high-temperature combustion on its roof. It is indicated that the application of modified algorithm increases the effectiveness of parallelization by 2.1% compared to the initial algorithm.
Keywords: parallel computations, load balancing, linear perceptron, chemical kinetics, continuous medium mechanics, distributed balancing, numerical simulation, numerical experiment, approbation, geometrical parallelizing
Введение
Существует большое количество задач механики сплошной среды, осложненных необходимостью учета фактора химической кинетики. Назовем задачи моделирования процессов возникновения и распространения пожаров, задачи моделирования процессов образования фотохимического смога на улицах большого города, а также разнообразные технические задачи, связанные с горением. Обычно такие задачи имеют постановку в виде системы дифференциальных уравнений в частных производных, описывающей распространение реагентов, к которой присоединяется система обыкновенных дифференциальных уравнений химической кинетики, описывающая изменение концентраций реагентов в результате химических реакций.
Обычно задачи такого класса решаются итерационно, с применением схем расщепления. При этом на каждой итерации по времени сначала осуществляется шаг численного интегрирования уравнений в частных производных, определяющий изменение концентраций реагентов в ячейках расчетной сетки в результате межъячеечного переноса, а затем выполняется шаг численного интегрирования обыкновенных дифференциальных уравнений химической кинетики. Важной отличительной чертой второго шага является значительное различие скоростей протекания химических реакций в ячейках, если в расчетной области присутствуют существенные тепловые неоднородности. Расчет протекания таких реакций обычно производится жестко устойчивыми методами с контролем шага (например, методом Гира), причем различие скоростей протекания реакций приводит к существенному различию времени интегрирования уравнений химической кинетики в ячейках.
Задачи рассматриваемого класса трудоемки с вычислительной точки зрения и решаются почти исключительно с применением параллельных вычислений, обычно с применением геометрического параллелизма. При этом различие времени, требуемого на интегрирование кинетических уравнений в разных узлах, в условиях тривиального геометрического параллелизма приводит к значительным неоднородностям времени счета областей, относящихся к различным процессорам, что резко снижает эффективность распараллеливания и значительно увеличивает время счета.
Эффективное решение проблемы неоднородности вычислительной загрузки процессоров возможно, если пытаться (на каждой итерации, при осуществлении шага решения уравнений химической кинетики) динамически перераспределять узлы так, чтобы вычислительная неоднородность загрузки процессоров была минимальной.
Такие алгоритмы динамической балансировки загрузки известны [1], они обладают различной эффективностью для различных систем. Их можно разделить на следующие группы [1]: а) с применением вычисляющей среды [2], б) централизованные (см., например, обзор в [3]), в) распределенные [4], г) диффузные (В.Э.Малышкин, А.П.Карпенко, см. обзор в [3], также Cybenko [5] и Boillat [6]), д) случайные [7]. Подробное сравнение алгоритмов проведено в работе [1], здесь же отметим следующее:
а) алгоритмы вычисляющей среды могут иметь недостаточно высокую эффективность балансировки, поскольку перераспределение нагрузки между процессорами выполняется фиксированными «слоями» узлов;
б) централизованные алгоритмы имеют сравнительно высокие коммуникационные затраты на взаимодействие центрального процессора с рабочими и, как следствие, недостаточные надежность и эффективность распараллеливания;
в) распределенные алгоритмы часто имеют хорошие показатели по эффективности балансировки и эффективности распараллеливания, и вполне могут быть взяты за основу в настоящей работе;
г) алгоритмы диффузной балансировки осуществляют перераспределение узлов между процессорами, обрабатывающими соседние блоки расчетной области, что также может давать недостаточную эффективность балансировки;
д) алгоритмы случайной балансировки также часто могут давать недостаточную эффективность балансировки, давая средние по качеству балансировки результаты.
В работе [1] показано, что для задач с медленным дрейфом «горячих» областей эффективен распределенный алгоритм, при котором распределение нагрузки по процессорам основывается на предполагаемом времени интегрирования, которое считается условно равным времени с предыдущего шага. Недостатком такого подхода к предикции времени является его ограниченная применимость в условиях быстрого дрейфа «горячих» областей. Актуален вопрос об уменьшении данного недостатка.
Целью данной работы является повышение эффективности алгоритма распределенной балансировки загрузки [1] и его распространение на случаи с быстрым дрейфом «горячих» областей. Поставим задачи: а) предложить соответствующие модификации алгоритма на базе более совершенных средств предсказания времени интегрирования; б) провести апробацию полученного алгоритма на реальной задаче.
1. Базовый алгоритм
Алгоритм распределенной крупноблочной балансировки [1] выполняется на каждом шаге интегрирования системы уравнений химической кинетики. Перед началом шага известна история замеров времени счета для каждого узла-ячейки. Используя эту информацию, каждый процессор определяет предполагаемое время обработки каждого изначально приписанного ему (в соответствии с геометрическим параллелизмом) узла (в базовом варианте считается, что это время равно соответствующему времени с предыдущей итерации, по этой причине базовый вариант успешно применим только в условиях медленного дрейфа «горячих» областей с высоким временем обработки) и делится этой информацией с остальными процессорами. На основании этих данных каждый i-й процессор вычисляет предполагаемую среднюю нагрузку M и определяет, насколько она отличается от его текущей, геометрически распределенной нагрузки Ri. Эта информация используется для априорного перераспределения нагрузки в начале текущего шага.
Процессоры с M < Ri однократно определяют, каким процессорам они будут передавать лишнюю нагрузку, а процессоры с M > Ri однократно определяют, от каких процессоров они примут нагрузку. После этого процессоры приступают к обработке оставшихся «своих» узлов, одновременно с этим выполняются крупноблочные (это позволяет передавать данные более быстро) обмены излишней/недостающей нагрузкой. При завершении обменов процессоры-получатели обрабатывают принятые узлы и алгоритм расчета химической кинетики с балансировкой завершает текущий шаг.
2. Модификация
Предположим, что для предсказания загрузки процессора Vi в каждом i-м узле (i = 1…N, где N – число узлов) можно использовать линейную экстраполяцию, опирающуюся на историю из P предыдущих замеров величины загрузки в i-м узле (это величины Hi,j, j = 1…P). Экстраполяция реализуется линейным соотношением:
где Ki,k – коэффициенты i-го экстраполятора, Si – порядок i-го экстраполятора. Такой экстраполятор эквивалентен линейному персептрону из одного нейрона со смещением Ki,0. Персептрон обучается методом наименьших квадратов. В данной работе персептрон программно реализуется авторегрессионным точечным каналом [8].
3. Апробация
Рассмотрим нестационарную задачу с относительно быстрым изменением положения «горячих» областей. Пусть это будет двумерное обтекание здания переменным воздушным потоком, причем отмечается тепловая неоднородность: на крыше здания наблюдается процесс горения при высокой температуре.
Проведем несколько численных экспериментов с балансировкой загрузки (на базе линейной экстраполяции) на вычислительной системе с 4-ядерным процессором Intel Atom. Результаты замеров времени решения и расчетов эффективности распараллеливания кинетического блока сведены в таблицу 1. При расчетах использовалась замеренная величина времени решения на одном процессоре T(1) = 299,45 с. Также было замерено и время решения в параллельном варианте (T(N), на N процессорах), но без балансировки – оно составило величину в 195,73 с. Сравнивая эту величину с данными таблицы 1, легко видеть, что балансировка была оправданной.
Таблица 1. Показатели решения с балансировкой (модификация)
|
Расчетная величина
|
Порядок экстраполятора Si
|
|
1
|
2
|
3
|
|
Время решения T(4), с
|
99,88
|
97,06
|
100,43
|
|
Эффективность распараллеливания T(1)/(4×T(4))
|
0,75
|
0,771
|
0,745
|
Из таблицы 1 очевидно, что расчет по модифицированному алгоритму (Si = 2) оказался несколько быстрее расчета по базовому алгоритму, соответствующему Si = 1. Выигрыш составил величину около 2,1% эффективности распараллеливания. В то же время вариант с Si = 3 не только не дал прироста производительности, но и снизил ее. Это может объясняться двумя причинами: а) ростом затрат на собственно предикцию, которые превысили эффект выравнивания загрузки, б) некорректностью предикции (предиктор реализует фиктивные или частные зависимости, использующие чрезмерно большое количество предыдущих точек). Тем не менее, можно предположить, что модификации алгоритма при Si > 2 могут найти применение в каких-либо еще более сложных случаях.
Заключение
В данной работе предложена модификация алгоритма крупноблочной распределенной балансировки, основанная на применении линейного персептрона для предсказания времени интегрирования в узлах, пригодна для случаев как с медленным, так и с относительно быстрым дрейфом "горячих" областей. Модификация апробирована в задаче о моделировании обтекания одиночного здания с горением на крыше (случай быстрого дрейфа "горячих" областей). Показано, что применение модифицированного алгоритма повышает эффективность распараллеливания на 2,1% по сравнению с исходным алгоритмом.
Библиография
1. Пекунов В.В. Новые методы параллельного моделирования распространения загрязнений в окрестности промышленных и муниципальных объектов // Дис. докт. тех. наук.-Иваново, 2009.-274 с.
2. Нуждин Н.В., Ясинский Ф.Н. Представление о вычисляющей среде и его применение для распараллеливания алгоритмов в механике жидкостей и газов // Вестник ИГЭУ. — Иваново, 2003. — Вып.1. — С.82-84.
3. Якобовский М.В. Вычислительная среда для моделирования задач механики сплошной среды на высокопроизводительных системах: Автореф. дис. докт. физ.-мат. наук. — Москва, 2006. — 37 с.
4. Корнилина М.А., Якобовский М.В. Динамическая балансировка загрузки процессоров при моделировании задач горения // Высокопроизводительные вычисления и их приложения: Тр. Всеросс. науч. конф. — М.: Изд-во МГУ, 2000. — С.34-39.
5. Cybenko G. Load balancing for distributed memory multiprocessors /Par. Distr. Comp.— 1989.— Vol.7.— P.279-301.
6. Boillat J.E. Load balancing and Poisson equation in a graph. /Currency Practice and Experience.— 1990. — Vol.2.— №4.— P.289-313.
7. Rudoph L., Slivkin-Allouf M., Upfal E. A simple load balancing scheme for task allocation in parallel machines. /Proc. 3rd Annual ACM Symp. On Parallel Algorithms and Architectures (APAA, 91).— 1991.— P.237-245.
8. Пекунов В.В. Предицирующие каналы в параллельном программировании: возможное применение в математическом моделировании процессов в сплошных средах // Программные системы и вычислительные методы. – 2019. – № 3. – С. 37-48. DOI: 10.7256/2454-0714.2019.3.30393 URL: https://nbpublish.com/library_read_article.php? id=30393
References
1. Pekunov V.V. Novye metody parallel'nogo modelirovaniya rasprostraneniya zagryaznenii v okrestnosti promyshlennykh i munitsipal'nykh ob''ektov // Dis. dokt. tekh. nauk.-Ivanovo, 2009.-274 s.
2. Nuzhdin N.V., Yasinskii F.N. Predstavlenie o vychislyayushchei srede i ego primenenie dlya rasparallelivaniya algoritmov v mekhanike zhidkostei i gazov // Vestnik IGEU. — Ivanovo, 2003. — Vyp.1. — S.82-84.
3. Yakobovskii M.V. Vychislitel'naya sreda dlya modelirovaniya zadach mekhaniki sploshnoi sredy na vysokoproizvoditel'nykh sistemakh: Avtoref. dis. dokt. fiz.-mat. nauk. — Moskva, 2006. — 37 s.
4. Kornilina M.A., Yakobovskii M.V. Dinamicheskaya balansirovka zagruzki protsessorov pri modelirovanii zadach goreniya // Vysokoproizvoditel'nye vychisleniya i ikh prilozheniya: Tr. Vseross. nauch. konf. — M.: Izd-vo MGU, 2000. — S.34-39.
5. Cybenko G. Load balancing for distributed memory multiprocessors /Par. Distr. Comp.— 1989.— Vol.7.— P.279-301.
6. Boillat J.E. Load balancing and Poisson equation in a graph. /Currency Practice and Experience.— 1990. — Vol.2.— №4.— P.289-313.
7. Rudoph L., Slivkin-Allouf M., Upfal E. A simple load balancing scheme for task allocation in parallel machines. /Proc. 3rd Annual ACM Symp. On Parallel Algorithms and Architectures (APAA, 91).— 1991.— P.237-245.
8. Pekunov V.V. Preditsiruyushchie kanaly v parallel'nom programmirovanii: vozmozhnoe primenenie v matematicheskom modelirovanii protsessov v sploshnykh sredakh // Programmnye sistemy i vychislitel'nye metody. – 2019. – № 3. – S. 37-48. DOI: 10.7256/2454-0714.2019.3.30393 URL: https://nbpublish.com/library_read_article.php? id=30393
Результаты процедуры рецензирования статьи
В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.
Предметом рецензируемой статьи выступает совершенствование балансировки загрузки процессоров при численном решении задач механики сплошной среды, осложненных химической кинетикой. Такие задачи, и соответственно оптимизация загрузки процессоров, имеют важное значение, в частности, при моделировании возникновения и распространения пожаров, процессов образования смога на улицах агломераций.
Методология исследования базируется на применении линейного персептрона для предсказания времени интегрирования в узлах, апробации предлагаемого подхода для моделирования обтекания одиночного здания с горением на крыше (случай быстрого дрейфа «горячих» областей).
К элементам научной новизны представленного исследования, по мнению рецензента, можно отнести модифицированный алгоритм крупноблочной распределенной балансировки загрузки процессоров при численном решении задач механики сплошной среды, осложненных химической кинетикой, распространение этого алгоритма на случаи с быстрым дрейфом «горячих» областей на базе средств предсказания времени интегрирования.
Структурно в статье выделены следующие разделы: Введение; 1. Базовый алгоритм; 2. Модификация; 3. Апробация; Заключение; Библиография.
Во введении описаны задачи, в которых может быть востребован предлагаемый в статье вариант решения проблемы неоднородности вычислительной загрузки процессоров, отражены существующие подходы к балансировке загрузки процессоров, сформулированы цель и задачи исследования.
В представленных материалах рассмотрен базовый алгоритм распределенной крупноблочной балансировки, его модификация на основе использования линейной экстраполяции истории предыдущих замеров величины загрузки, приведена формула для предсказания загрузки процессора в каждом узле, отмечено, что такой экстраполятор эквивалентен линейному персептрону, который обучается методом наименьших квадратов и программно реализуется авторегрессионным точечным каналом. Апробация разработки проведена на примере моделирования процесса горения при высокой температуре на крыше здания с двумерным обтеканием переменным воздушным потоком при наличии тепловой неоднородности. Описаны несколько численных экспериментов на вычислительной системе с 4-ядерным процессором Intel Atom, результаты отражены в таблице, проведен критический анализ модифицированного алгоритма, показаны ситуации, когда его применение приводит к повышению эффективности, а когда – нет.
В заключении статьи отмечается, что применение модифицированного алгоритма повышает эффективность распараллеливания на 2,1 % по сравнению с исходным алгоритмом.
Библиография статьи включает 8 источников, среди которых имеются публикации как в отечественных, так и в зарубежных научных журналах, изданные за тридцатилетний период. На приведенные в списке литературы источники в тексте имеются адресные ссылки, что свидетельствует о наличии в публикации апелляции к оппонентам. В целом содержание и стиль изложения материала соответствует сложившейся при оформлении результатов научных исследований практике публикаций.
Однако, по рецензируемой статья хочется высказать некоторые замечания. Во-первых, в рецензируемом материале автор не использует графический способ подачи информации, в статье не приведены иллюстрации в виде схем и рисунков, наличие которых могло бы привлечь интерес читателей. Во-вторых, в библиографическом списке четверть источников принадлежит одному автору, к тому же на один из них в тексте имеется 6 ссылок, с большой долей вероятности здесь имеет место обширное самоцитирование автором своей предыдущей публикации.
Актуальность темы статьи, наличие элементов приращения научного знания, наличие сведений об увеличении более чем на 2 % эффективности предлагаемого алгоритма, говорят о возможности опубликования рецензируемой статьи.
|
Рус
© 1998 – 2024 Nota Bene. Publishing Technologies. NB-Media Ltd.
