Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 11
Текст из файла (страница 11)
порядка T *109 flop операций. Например, для того чтобынаблюдать за облаком в течение T = 100 c на одном процессоре IntelCeleron 2,4 ГГц RAM 512 Мб (под управлением Windows XP, компилятор Borland) при шаге интегрирования 0,01 требует порядка 30 минут.Это не удивительно, если учесть, что реальная производительностьпроцессоров Intel линейки x86, нормированная на тактовую частоту1 ГГц не превышает 300–350 Mflops/s [8]. Следовательно, только попрошествии 1000 секунд мы сможем сказать, какое состояние будет уоблака через 100 секунд.
Понятно, что при прогнозировании такая задержка не допустима.Для решения задачи (1), (2) будем использовать метод Галеркина.С помощью метода Галеркина, за счет удачного выбора полной ортонормированной системы функций, можно значительно сократить объем вычислений. При решении кинетического уравнения в качестве такой системы используется система функций Дмитриева [9].Пусть {ϕ k(m) | 0 ≤ m ≤ ∞, k = 1, 2, …, ∞} – полная ортонормированная система функций в L2[0, ∞], полученная при ортогонализации(по Грамму–Шмидту) системы функций {e–0,5km, k = 1, 2, ..., ∞}, т.е.система функций Дмитриева.
Будем искать решение в виде:nf (t , m) = ∑ ak (m)ϕ k (t ) .(3)k =1Подставив (3) в (1) и скалярно умножив обе части полученной системы на первые n функций Дмитриева, получим систему из n обыкновенных дифференциальных уравнений относительно коэффициентовГалеркина:dak (t ) n n= ∑∑ Cijk ai (t )a j (t ) ,(4)dti =1 j =1где∞∞⎛∞⎞Cijk = ∫ ϕ k (m) ⎜ ∫ K11 (m, m′)ϕi (m)ϕ j (m) dm′ ⎟ dm = ∫ I (ϕi , ϕ j )ϕ k (m) dm (5)⎜⎟00⎝0⎠с начальными данными:∞ak (0) = ∫ f (0, m)ϕ k (m) dm .(6)0Полученную задачу можно разбить на три отдельные подзадачи,50которые могут решаться независимо:1) вычисление n(n + 1)/2 чисел – элементов нижней треугольнойматрицы перехода G от экспоненциальной системы функций к системефункций Дмитриева [9];2) вычисление n3 коэффициентов Сijk по формуле (5). Подчеркнемих независимость от времени, а потому их надо вычислить всего лишьодин раз;3) решение (например, с помощью простейшей, явной схемы Эйлера) задачи Коши (4), (6) для системы из n обыкновенных дифференциальных уравнений (СОДУ).Из вышеприведенного разбиения на подзадачи становится ясноосновное преимущество использования метода Галеркина по сравнению с разностной схемой.
Решив сначала 1-и 2 подзадачи, мы можемрешить СОДУ (4), (6), в которой коэффициент пропорциональностимежду временем, на котором мы следим за облаком, и временем счетабез распараллеливания имеет порядок (1/ht)n2 = 100 n2. А при распараллеливании, в N раз меньше, где N – число процессоров.Перейдем к распараллеливанию каждой из подзадач. Распараллеливать мы будем на MPI под Microsoft Visual C++ 6.0.Подзадача 1) распараллеливается на n процессорах очевидным образом, поскольку есть явные формулы для элементов матрицы G [9].Действительно, k-й процесс считает k чисел, помещает их в массивдлины n, а оставшимся элементам массива он присваивает 0 значение.Затем каждый процесс вызывает MPI_Allgather [10], таким образом,каждый из n процессов знает все n(n + 1)/2 чисел.
Следует отметить,что при использовании MPI_Allgather и некоторых других функцийпараллельной библиотеки, в силу их специфики, необходимо знать, какв C++ хранятся массивы. К примеру, если у нас двумерный массив, тосначала в памяти размещается его первая строка, потом вторая и т.д.Подзадача 2) самая сложная с точки зрения объема вычислений, и,следовательно, может занимать много времени, если требуется хорошая точность.
В этой связи ее имеет смысл запускать на максимальновозможном количестве процессов. При фиксированном n синхронизационная накладка [10], связанная с обменом данными между процессами, растет значительно медленней с ростом числа процессов, чем время, которое экономиться за счет роста числа процессов. Это обусловлено огромным объемом вычислений, которое приходится на одинпроцесс (следует сравнить с подзадачей 3) ниже). Таким образом, увеличив число процессов, мы увеличим точность, оставаясь в тех же вре51менных рамках. Задача 2) считалась на n2 процессорах.2 Каждый (i, j)-йпроцесс, в декартовой топологии [10], вычисляет n коэффициентов Сijkk = 1, …, n, а затем вызывает MPI_Allgather, таким образом, каждый изn2 процессов знает целиком трехмерный мерный массив Сijk.Подзадача 3) естественным образом распараллеливается на n процессорах.
Сперва k-й процесс считает ak(0) по формуле (5). Затем процессы обмениваются ak(0) и, в результате, каждый процесс знаетn-мерный вектор a (0). Заменив в (4) производную по времени конечной разностью, т.е. используя схему Эйлера, получим:nnak ((i + 1)h ) = ak (ih) + h∑∑ Cijk ai (ih)a j (ih).(7)i =1 j =1Дальше будем действовать по индукции (база у нас уже есть).Предположим, что на шаге i + 1 каждый процесс знает вектор a (ih) .Тогда k-й процесс сможет посчитать по формуле (7) значенияak ((i + 1)h), k = 1, 2, …, n. Затем процессы обмениваются значениямиak ((i + 1)h) и, в результате, каждый процесс знает n-мерный векторa ((i + 1)h). Заметим, что при так организованном распараллеливаниеотсутствует синхронизационная накладка, поскольку все процессы выполняют практически один и тот же объем вычислений.
Поэтому достаточно просто синхронизировать моменты начала выполнения подзадачи 3) у всех процессов, что можно сделать с помощью MPI_Barrier[10]. Возникает естественный вопрос: почему бы не попытаться запустить 3) подзадачу на большем количестве процессов? Ответ достаточнопрост: на каждом шаге каждый процесс делает n2 арифметических операций с double и отправляет n сообщений. Поскольку при современныхмощностях n2 < 700 операций выполняются практически мгновенно, товременные затраты на посылку сообщений становятся сопоставимы свременем выполнения операций. Поэтому, значительно уменьшатьчисло операций выполняемых одним процессом за счет увеличениечисла процессов не имеет смысла, поскольку время при этом экономиться не будет, т.к.
будет расти синхронизационная накладка.2Как правило, n ~ 5–25 (число членов в ряде Галеркина), поэтому n2 процессоров есть в нашем распоряжении. У нас был доступ к суперкомпьютеру «МВС1000М», содержащему порядка 700 процессоров (пиковая производительность1012 flops/s, реальная на порядок ниже), http://www.jscc.ru.52Теперь остановимся поподробнее на некоторых деталях реализации решения задачи.
При интегрировании (5), (6) подынтегральныевыражения имеют экспоненциальное убывание на бесконечности (точнее убывание вида ~e–0,5x), поэтому с хорошей точностью можно ограничиться интегрированием от 0 до Mp ~ 20–30, поскольку коэффициент при этой экспоненте, как показывает расчет, имеет, самое большое,порядок 103. При численном интегрировании нами использоваласьформула Симпсона, которая на отрезке интегрирования [a, b] дает точность:~1| J − J |≤(b − a ) M 4 h 4 ,(8)2880где M4 – максимальное по модулю на отрезке [a, b] значение 4-й производной подынтегрального выражения [11].
Так как b – a <30 и подынтегральное выражение достаточно гладкое3, то из (8) следует, чтобрать шаг интегрирования h меньше чем 0,01 не имеет смысла. В результате, при таком вычислении интегралов, подзадачи 1) и 2) считаются на 25 процессорах Intel Pentium IV4 порядка 5–10 с (h = 0,1).Подзадачи 1)–3) решались в одной программе. В связи с этим возникла необходимость создать новый коммуникатор [10]. Один и тот жепроцесс имел разные ранги в разных коммуникаторах. Также потребовалось широко распространять данные от одного (корневого) процессавсем остальным процессам в этом коммуникаторе MPI_Bcast [10].
Длявычисления интегралов были созданы две универсальные функции,которые получают в качестве одного из аргументов ссылку на функцию – подынтегральное выражение.На рис.1, 2 представлены результаты решения задачи (1), (2) длямоментов времени T = 0,5 и T = 2,5, когда K11(m, m′ ) ≡ 1. Для этогомодельного случая известно точное решение, ему соответствуетсплошная линия, а приближенному - линия с точками. Обратим внимание на то, что в ряде Галеркина было взято всего лишь n = 5 слагаемых, а шаг интегрирования равнялся 0,1. Из графиков можно сделатьвывод о хорошей сходимости приближенного решения к точному.3В силу экспоненциальных множителей и равномерно гладкое на [0, +∞].Этот процессор обладает наиболее высокой производительностью, нормированной на тактовую частоту, и принципиально отличается от остальных тем,что теоретически может выполнять 2 flops операции за один такт. На 25 процессорах задача запускалась на кластерах в ВЦ РАН.4530,70,6f(m)0,50,40,30,20,1000,511,522,522,5mРис.
1. T = 0,50,210,18f(m)0,150,120,090,060,03000,511,5mРис. 2. T = 2,5В заключении отметим, что использование описанного выше подхода для решения ряда систем интегро-дифференциальных уравненийпозволяет существенно сократить время расчета, по сравнению с использованием распараллеленных разностных схем. Это достигаетсяблагодаря тому, что:1) при удачном выборе базисной системы функций можно ограничиться нахождением лишь небольшого количество слагаемых в ряде54Галеркина, как правило, 10 слагаемых достаточно;2) коэффициент пропорциональности между временем, на котороммы следим за облаком, и временем счета, при использовании методаГалеркина, оказывается на несколько порядков меньше, чем коэффициент пропорциональности соответствующий разностному методу;3) приведенное выше распараллеливание не имеет синхронизационных накладок.Исследование сходимости ряда Галеркина, т.е.
проверка условияустойчивости галеркинской аппроксимации интегро-дифференциального оператора [7], для (1), (2) сделана в работе [9] с использованиемпроблемы моментов Чебышева–Маркова–Крейна.Мы выражаем благодарность к.ф-м.н. доценту Н.Н. Оленеву и д.фм.н. профессору А.А. Шананину за оказанную нам помощь при выполнении этой работы.Литература1. Волощук В.М., Седунов Ю.С.
Процессы коагуляции в дисперсныхсистемах. Л.: Гидрометеоиздат, 1975.2. Berry E.X. Cloud droplet growth by collection, Journal of AtmosfericSciences. V. 24. 1967. P. 278–286.3. Степанов А.С. К выводу уравнения коагуляции // Тр. ИЭМ. Вып.23. 1971. С. 3–16.4. Смолуховский М. Опыт математической теории кинетики коагуляции коллоидных растворов. В кн.: Коагуляция коллоидов. М.: ОНТИ, 1936.С. 7–36.5. Галкин В.А., Уравнение Смолуховского.
М.: Физматлит, 2000. 336 с.6. Гаева З.С., Шананин А.А. Численный метод решения задачи управления микроструктурой градового облака // Матем. модел. 2004. Т. 16, №12. С. 69–84.7. Треногин В.А. Функциональный анализ. М.: Физматлит, 2002, гл.VII и §38.8. http://www.computational-battery.org/Maskinvare/Flops.html,http://www.spec.org, http://www.cs.utk.edu/~rwhaley/ATLAS/x86.html.9. Гаева З.С., Шананин А.А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
