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

Пекунов Владимир Викторович доктор технических наук Инженер-программист, ОАО "Информатика" 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 Другие публикации этого автора

В настоящее время подавляющее большинство вычислительных систем использует многоядерные процессоры. При этом ресурсы таких процессоров, как правило, большую часть времени задействуется на 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); eps₀ = 8,85×10^‑12 Ф/м (диэлектрическая проницаемость вакуума); E — вектор напряженности электрического поля; e – заряд частицы; n(x,y) — количество частиц в ячейке (x,y); vol — объем ячейки; m – масса частицы; N — число частиц; V_i, x_i — вектора скорости и координат i-й частицы соответственно.

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

Пусть U₂ > U₁ (собирающая линза, U₁ = 200 В, U₂ = 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 очевидно, что применение сверхоптимистичных вычислений в данном случае дало выигрыш по времени в 1,1 раза.

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

Выводы

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