Читать статью 'Сверхоптимистичные вычисления: концепция и апробация в задаче о моделировании электростатической линзы' в журнале Программные системы и вычислительные методы на сайте nbpublish.com
Рус Eng За 365 дней одобрено статей: 1937,   статей на доработке: 335 отклонено статей: 578 
Библиотека

Вернуться к содержанию

Программные системы и вычислительные методы
Правильная ссылка на статью:

Сверхоптимистичные вычисления: концепция и апробация в задаче о моделировании электростатической линзы

Пекунов Владимир Викторович

доктор технических наук

Инженер-программист, ОАО "Информатика"

153000, Россия, Ивановская область, г. Иваново, ул. Ташкентская, 90

Pekunov Vladimir Viktorovich

Doctor of Technical Science

Software Engineer, JSC "Informatika"

153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90

pekunov@mail.ru
Другие публикации этого автора
 

 

DOI:

10.7256/2454-0714.2020.2.32232

Дата направления статьи в редакцию:

20-02-2020


Дата публикации:

15-07-2020


Аннотация.

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

Ключевые слова: сверхоптимистичные вычисления, предикция значений, программная транзакционная память, предицирующие каналы, численное моделирование, частицы в ячейках, прогностические зависимости, распараллеливание, дифференциальные уравнения, электростатическая линза

Keywords:

super-optimistic evaluations, value prediction, software transactional memory, predictive funnels, numerical simulation, particles in cells, predictive dependencies, parallelizing, partial differential equations, electrostatic lens

В настоящее время подавляющее большинство вычислительных систем использует многоядерные процессоры. При этом ресурсы таких процессоров, как правило, большую часть времени задействуется на 30÷40%, что связано с недостаточно активным применением параллельных вычислений приложениями. Во многом это связано с тем, что значительная часть алгоритмов не обладает существенным потенциалом параллелизма, реализация которого позволила бы более полно задействовать вычислительные ресурсы и получить определенный выигрыш в скорости работы. В частности, речь идет о циклических алгоритмах с зависимыми витками и телом, требующим сугубо линейного порядка исполнения. Проблема распараллеливания [1] здесь кажется не реализуемой и в литературе практически не рассмотрена, в связи с чем поиск ее решения является достаточно актуальной задачей. Рассмотрим случай, когда вышеуказанный алгоритм решает задачу из области вычислительной математики, которая предполагает расчет с определенными погрешностями (например, моделирование динамики пучка заряженных частиц в электростатической линзе методом частиц в ячейках [2]). Можно попытаться применить подход с заменой части явных зависимостей в линейном теле цикла прогностическими, с возможными погрешностями предикции (как это сделано, например, в работе [3]). Тогда можно разбить тело цикла на две или более параллельных частей, которые вместо ожидания данных из предыдущих частей будут пытаться спрогнозировать актуальные значения таких данных путем экстраполяции, а потом, дождавшись получения данных, либо принимать результаты проделанного к данному моменту расчета, либо пересчитать те его части, в которых прогноз оказался слишком неточным. Эта схема определенно напоминает идеологию работы транзакционной памяти [4] в сочетании с применением неких прогнозирующих каналов передачи данных, например, предложенных автором в работе [5]. Следует отметить, что идея транзакционной памяти с прогнозированием значений переменных известна, однако в соответствующих работах (см., например, [6]) речь обычно идет о прогнозировании целочисленных значений отдельных ячеек памяти или переменных, а не об экстраполяции вещественных значений в каналах для повышения степени параллелизма. Соответственно, для рассматриваемого класса задач классическая транзакционная память по типу [6] не пригодна.

Целью данной работы является исследование возможностей прогностического распараллеливания с применением вышеуказанной схемы. Для достижения данной цели поставим следующие задачи:

а) четко сформулировать схему распараллеливания линейных тел циклов (с зависимыми витками) путем ввода прогностических зависимостей, разрешаемых применением предикционно-решающих каналов [5];

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

в) апробировать предложенный подход на задаче моделирования работы электростатической линзы.

Распараллеливание линейных тел циклов с зависимыми витками. Сверхоптимистичные вычисления.

Итак, пусть дан цикл с зависимыми витками, линейное тело которого можно декомпозировать на две части A и B (B следует за A), которые имеют зависимости по некоторому множеству переменных V. Заменим данную явную зависимость прогностической, воспользовавшись точечным авторегрессионным каналом [5]. Введем такой канал. Пусть в конце части A в канал будут отправляться рассчитанные значения V. Тогда в начале части B необходимо организовать прием значений V* в прогностическом режиме с таймаутом: часть B будет некоторое заданное малое время ожидать поступления значения от A и, если они не успели придти, будет генерировать прогнозное значение V*, основываясь на предыдущих значениях V, поступавших в данный канал ранее, на некотором множестве предыдущих витков цикла. После получения или генерации V* часть B незамедлительно начинает считаться.

В конце счета частей A и B необходимо дождаться поступления через канал (из A в B) реальных значений V и сравнить их с прогнозными V*. Если различие существенно, то часть B откатывается (при этом корректируется предиктор канала) и пересчитывается на основе реально полученных значений V (при этом выигрыш по времени отсутствует). Если же различие оказалось несущественным, то часть B сразу принимается, и исполнение витка заканчивается с теоретическим максимальным ускорением в два раза (поскольку части A и B исполнялись параллельно). Пусть эти проверки и согласования производятся некоторым модифицированным механизмом транзакционной памяти, с точки зрения которой A и B являются транзакциями, а канал – особым образом обрабатываемая глобальная переменная.

Таким образом, можно, в данном случае, по аналогии с идеей оптимистичных вычислений [7] (согласно которой некоторые значения в программе частично вычисляются предварительно за некий установленный промежуток времени, а полностью вычисляются при прямой необходимости использовать эти значения), данный подход охарактеризовать как концепцию сверхоптимистичных вычислений.

При этом тело цикла приобретает вид:

Транзакция {

Если это процессор 1 то {

Вычислить часть A

Канал.put(V)

} иначе если это процессор 2 {

Канал.get(V, с таймаутом и предикцией)

Вычислить часть B

}

}

Перейдем к вопросу о реализации соответствующего механизма модифицированной транзакционной памяти.

Частично транзакционная память

Как уже было сказано, по отношению к каналу пересогласование транзакций выполняется по контролю значений в канале, а не по времени их модификации. Таким образом, стандартные для современных языков программирования (например, GNU C++) средства работы с транзакционной памятью здесь неприменимы. Требуемый механизм можно было бы обозначить как частичную транзакционную память , в которой допускается как минимум три разновидности глобальных переменных :

а) со стандартным механизмом согласования, характерным для классической транзакционной памяти;

б) каналы, со специфическим механизмом согласования;

в) без согласования (обычные глобальные переменные, не требующие согласования). Значения таких переменных не меняются при откате транзакции.

Рассмотрим более подробно механизм согласования транзакций относительно каналов .

Для простоты можно рассматривать случай, когда в пределах каждой транзакции каналы срабатывают однократно, фактически, в соответствии с механизмом promise-future [8]. Если передающий коннектор канала находится в транзакции B, а приемный – в транзакции C, то

а) если транзакция B откатывается, то должна откатиться и транзакция C;

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

Автором была разработана специальная библиотека [9] на языке C++, реализующая (с применением OpenMP, используется отложенная стратегия обнаружения конфликтов [10]) идею частичной транзакционной памяти с помощью одного нового ключевого слова transaction_atomic и обычных шаблонных классов TScalar (скалярная переменная с пересогласованием), TArray (массив с пересогласованием), TIn и TOut (входной и выходной коннекторы авторегрессионных точечных каналов со специальным механизмом пересогласования). При этом на обычные переменные, не относящиеся к упомянутым классам, концепция пересогласования не распространяется.

Апробация (моделирование электростатической линзы)

Цикл рассматриваемого в работе рода характерен, например, для решения задачи симуляции работы электростатической линзы методом частиц в ячейках [2]. Сформулируем данную задачу.

Пусть имеется расчетная область с размерным параметром d = 0,2 м, показанная на рисунке 1, представляющая собой электростатическую линзу, в левую часть которой попал плотный поток отрицательно заряженных частиц.

Рис. 1. Расчетная область для решаемой задачи

Процессы в такой линзе описываются системой уравнений:

где U — потенциал электрического поля; ro(x,y) — плотность заряда в ячейке (x,y); eps0 = 8,85×10‑12 Ф/м (диэлектрическая проницаемость вакуума); E — вектор напряженности электрического поля; e – заряд частицы; n(x,y) — количество частиц в ячейке (x,y); vol — объем ячейки; m – масса частицы; N — число частиц; Vi, xi — вектора скорости и координат i-й частицы соответственно.

Присоединим граничные условия:

Пусть U2 > U1 (собирающая линза, U1 = 200 В, U2 = 5000 В) и число частиц N достаточно велико (N = 15000). К приведенным выше уравнениям применяются следующие численные методы:

а) метод верхней релаксации для уравнения Пуассона для потенциала U;

б) явный метод Эйлера для уравнений движения частиц (уравнения для координат x и скоростей V);

в) метод частиц в ячейках для расчета плотности заряда ro(x,y).

Разностные схемы данных методов хорошо известны и в данной работе не приводятся.

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

В данном случае можно воспользоваться предикцией плотности заряда с применением авторегрессионного точечного канала [5]. В самом деле, если по ходу расчета «обучить» канал предсказывать очередные «новые» значения плотности ro, то можно запустить подзадачи (а) и (б) одновременно, при этом подзадача (б) обратится к каналу за значением плотности (уже реально полученным, или прогнозным, генерируемым при таймауте) и попытается вычислить потенциал U, после чего будет ожидать завершения подзадачи (а). При завершении подзадачи (а) будут известны точные значения плотности ro, которые можно сравнить с предсказанными в подзадаче (б). Если погрешность невелика, то можно принять результаты вычисления потенциала и завершить текущую итерацию по времени. Если же погрешность велика, то необходимо решить подзадачу (б) повторно, опираясь уже на значения плотности, полученные в подзадаче (а).

Реализуем данный алгоритм и смоделируем работу собирающей электростатической линзы в параллельном режиме с применением сверхоптимистичных вычислений в частичной транзакционной памяти. Тексты программы и подключаемого модуля частично транзакционной памяти приведены в работе [9], используются каналы из стандартной библиотеки языка Planning C (см., например, [9]). При запуске программа запрашивает значение таймаута канала передачи плотности заряда в миллисекундах. При указании минимального значения (1) реализуются сверхоптимистичные вычисления, при указании больших значений (например, 1000) программа, фактически, работает с последовательным исполнением расчетов плотности заряда и потенциала.

За образцовые были приняты результаты работы программы в режиме с последовательным расчетом плотности заряда и потенциала. Как показали эксперименты, расчет с применением сверхоптимистичных вычислений дал относительную погрешность (объясняемую ошибками прогнозов в каналах) по скоростям и координатам частиц в размере 0,008%, а по потенциалу – 0,02%. Это доказывает, что расчет в режиме сверхоптимистичных вычислений был адекватен. Поскольку визуально такая погрешность незаметна, приведем результаты моделирования (на интервале времени 90 мс) только для режима с последовательным расчетом. На рис. 2 показано распределение потенциала U, на рис. 3 показано распределение частиц в расчетной области.

Рис. 2. Распределение потенциала в электростатической линзе

Рис. 3. Распределение заряженных частиц в линзе

Приведенные результаты вполне достоверны качественно, достаточно хорошо заметно, что линза действительно является собирающей, поскольку поток влетающих в нее слева частиц заметно шире потока вылетающих частиц справа.

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

Таблица 1. Усредненные (по пяти экспериментам) результаты замеров времени моделирования электростатической линзы (апробация библиотеки сверхоптимистичных вычислений в частично транзакционной памяти)

Значение таймаута (режим), мс

1 (сверхоптимистичный)

1000 (обычный)

Время счета, с

9,242

10,155

Из данных таблицы 1 очевидно, что применение сверхоптимистичных вычислений в данном случае дало выигрыш по времени в 1,1 раза.

Заметим, что теоретически возможен и более существенный выигрыш (но не более чем в 2 раза), если количество неверных прогнозов каналом невелико, а значения времени исполнения транзакций с разных сторон канала сопоставимы (различаются не более чем в 1,5÷3 раза).

Выводы

Итак, в данной работе впервые предложена концепция сверхоптимистичных вычислений на базе предицирующих каналов, позволяющая, в частности реализовать параллельную обработку циклов с зависимыми витками и телом с линейным порядком исполнения операторов. Введено понятие частично транзакционной памяти, используемой при таких вычислениях, описаны ее отличия от классической транзакционной памяти. Данная концепция опробована при параллельном решении задачи моделирования собирающей электростатической линзы (методом частиц в ячейках). Дана постановка задачи, приведены результаты моделирования. Показано, что при использовании сверхоптимистичных вычислений удалось получить выигрыш по скорости в 1,1 раза (при теоретически возможном максимуме в 2 раза) при крайне небольшой дополнительной погрешности (0,008÷0,02%), вносимой предикторами каналов.

Библиография
1.
Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин.— СПб.: БХВ-Петербург, 2002. — 608 с.
2.
Хокни Р., Иствуд Дж. Численное моделирование методом частиц. — М.: Мир, 1987. — 640 с.
3.
Пекунов В. В. Новые методы параллельного моделирования распространения загрязнений в окрестности промышленных и муниципальных объектов // Дис. докт. тех. наук.-Иваново, 2009.-274 с.
4.
Черняк, Л. Транзакционная память-первые шаги / Л. Черняк // Открытые системы. СУБД. — 2007.— №4.— С.12-15.
5.
Пекунов В.В. Предицирующие каналы в параллельном программировании: возможное применение в математическом моделировании процессов в сплошных средах // Программные системы и вычислительные методы. – 2019. – № 3. – С. 37-48. DOI: 10.7256/2454-0714.2019.3.30393 URL: https://nbpublish.com/ library_read_article.php?id=30393
6.
Salil Pant and Greg Byrd. A case for using value prediction to improve performance of transactional memory. In TRANSACT ’09: 4th Workshop on Transactional Computing, feb 2009. URL: http://transact09.cs.washington.edu/35_paper.pdf
7.
Ennals R., Peyton Jones S. (2003). Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict Programs. Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP. 8. 10.1145/944746.944731.
8.
Kisalaya Prasad, Avanti Patil, and Heather Miller. Futures and Promises. In Programming Models for Distributed Computing. URL: http://dist-prog-book.com/chapter/2/futures.html
9.
Пекунов В.В. Нейронные сети в задачах предикции, возникающих в программировании. Применение в целях оптимального распараллеливания программ численного моделирования.-LAP LAMBERT Academic Publishing, 2019.-100 с.
10.
Смирнов В.А., Омельниченко А.Р., Пазников А.А. Алгоритмы реализации потокобезопасных ассоциативных массивов на основе транзакционной памяти // Известия СПбГЭТУ «ЛЭТИ». – 2018. – № 1. – С. 12-18.
References (transliterated)
1.
Voevodin, V.V. Parallel'nye vychisleniya / V.V. Voevodin, Vl.V. Voevodin.— SPb.: BKhV-Peterburg, 2002. — 608 s.
2.
Khokni R., Istvud Dzh. Chislennoe modelirovanie metodom chastits. — M.: Mir, 1987. — 640 s.
3.
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.
4.
Chernyak, L. Tranzaktsionnaya pamyat'-pervye shagi / L. Chernyak // Otkrytye sistemy. SUBD. — 2007.— №4.— S.12-15.
5.
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
6.
Salil Pant and Greg Byrd. A case for using value prediction to improve performance of transactional memory. In TRANSACT ’09: 4th Workshop on Transactional Computing, feb 2009. URL: http://transact09.cs.washington.edu/35_paper.pdf
7.
Ennals R., Peyton Jones S. (2003). Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict Programs. Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP. 8. 10.1145/944746.944731.
8.
Kisalaya Prasad, Avanti Patil, and Heather Miller. Futures and Promises. In Programming Models for Distributed Computing. URL: http://dist-prog-book.com/chapter/2/futures.html
9.
Pekunov V.V. Neironnye seti v zadachakh prediktsii, voznikayushchikh v programmirovanii. Primenenie v tselyakh optimal'nogo rasparallelivaniya programm chislennogo modelirovaniya.-LAP LAMBERT Academic Publishing, 2019.-100 s.
10.
Smirnov V.A., Omel'nichenko A.R., Paznikov A.A. Algoritmy realizatsii potokobezopasnykh assotsiativnykh massivov na osnove tranzaktsionnoi pamyati // Izvestiya SPbGETU «LETI». – 2018. – № 1. – S. 12-18.

Результаты процедуры рецензирования статьи

В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.

Сверхоптимистичные вычисления: концепция и апробация в задаче о моделировании электростатической линзы Журнал: Программные системы и вычислительные методы Автор четко охарактеризовал существующее положение вещей с использованием многоядерных процессоров. Подчеркнуто, что «ресурсы таких процессоров, как правило, большую часть времени задействуется [лучше сказать задействованы] на 30÷40%». Научная новизна и актуальность четко изложены во вступительной части: «Проблема распараллеливания здесь кажется не реализуемой», «в литературе практически не рассмотрена, в связи с чем поиск ее решения является достаточно актуальной задачей». Среди возможных решений автор охарактеризовал подход «с заменой части явных зависимостей в линейном теле цикла прогностическими, с возможными погрешностями предикции» как неудачный, что позволило ему сформулировать собственную задачу и этапы (пути) ее решения. Подчеркнем, что такой подход позволил автору очень четко выразить не только цель, задачи, но и показать, как их реализовать. Структура и содержание последовательно выдержаны. В целом статья грамотно составлена, лаконична, и имеет четкую структуру. Автор вызывает уважение хорошим стилем. Библиографическая часть демонстрирует знание современной отечественной и зарубежной специальной литературы и будет полезна специалистам. Проблема, поднятая автором, заинтересует достаточное количество специалистов и программистов, а главное, показывает, как целесообразнее использовать новейшую технику для полноценной ее загрузки. В этом отношении статья, на мой взгляд, привлечет читателей из среды инженерного корпуса. Не вдаваясь в суть исследования, необходимо подчеркнуть, что по оформлению статья соответствует всем высоким требованиям и рекомендуется к публикации.