Developing parallel algorithm for research and information system of MD-SLAG-MELT BASED on CUDA technology

Full Text

Информационно-исследовательская система (ИИС) MD-SLAG-MELT [1; 3; 7] - программный комплекс, реализующий компьютерные эксперименты по исследованию физико-химических свойств и структуры материалов, ресурс по направлению компьютерного материаловедения. Базовым методом в ИИС является метод молекулярной динамики (МД), который включает анализ сложного силового взаимодействия между частицами модельной системы. Размер системы (число исследуемых частиц) при МД-моделировании является критически важным. С увеличением числа частиц до 106 линейные размеры модельного куба достигают нанометров, что позволяет получать результаты нового качества, обладающие практической значимостью. Однако расчет систем, содержащих 105-107 частиц, требует серьезных временных затрат и вычислительных ресурсов, что делает невозможным проведение компьютерных экспериментов без привлечения высокопроизводительных вычислений. В условиях ограниченных аппаратных ресурсов повышение производительности вычислений возможно за счет привлечение графического процессора видеокарты, используемого для компьютерных экспериментов вычислительного устройства (персонального компьютера). Делегирование части вычислений исходной задачи графическому процессору позволит разгрузить центральный процессор, что сократит общее время обработки. Для реализации описанной модели (модель распределенных вычислений MapReduce) необходимо разработать и имплементировать параллельный алгоритм, адаптирующий существующий линейный алгоритм расчета сил межмолекулярного взаимодействия под распределенные вычисления на центральном и графическом процессорах вычислительного устройства. В статье описан разработанный авторами и реализованный в ИИС MD-MELT параллельный алгоритм расчета сил межмолекулярного взаимодействия. В основе разработанного распределенного алгоритма лежит технология параллельного программирования CUDA (Compute Unified Device Architecture). Разработка параллельного алгоритма для вычисления результирующих сил взаимодействия между всеми частицами состоит из нескольких этапов: декомпозиция вычислений на независимые подзадачи, выделение информационных зависимостей между подзадачами, масштабирование подзадач - определение необходимой для решения вычислительной схемы и распределение подзадач между исполнительными процессорами [6]. Модель предметной области - коррелированная система N-частиц. Под коррелированной системой понимается система взаимодействующих объектов (частиц), в которой часть характеристик индивидуального объекта или системы в целом зависит от совокупности характеристик всех остальных объектов. Каждая модельная частица имеет набор сохраняющихся и переменных атрибутов. В этом случае МД-моделирование представляет собой численное решение краевой задачи Коши. Для распределенного МД-моделирования коррелированной системы N-частиц авторами разработана модель неоднородных дескрипторов. На основе концептуальной модели МД-метода и тщательного анализа программного кода legacy application - локального МД-приложения построены наборы дескрипторов, описывающих бизнес-логику МД-приложения с точки зрения разделения его кода на блоки, пригодные для распределения. Выделено два класса - одночастичные дескрипторы (D1s(i), D1v(i)) и агрегаторы (двух- и трехчастичные (D∑2(i), D∑3(i)) дескрипторы). Оба класса предполагают возможность параллельного расчета дескрипторов на разных вычислителях. Однако, если одночастичные дескрипторы можно произвольно распределять по вычислителям, то агрегаторы (содержат элементы, описывающие перекрестные отношения разных порядков между одночастичными дескрипторами и/или агрегаторами) являются «зависимыми» от одночастичного дескриптора и рассчитываются на том же вычислительном устройстве, что и «родительский» одночастичный дескриптор. Предложенный подход позволяет отвлечься от конкретного наполнения элементов дескрипторов, перенести акцент с описания физических взаимодействий в системе на информационное описание перераспределения потоков данных между дескрипторами [2; 4]. Метод равномерной загрузки вычислителей Равномерное распределение задач между исполнительными процессорами повышает общую эффективность вычислений (балансировка системы за счет отсутствия простоев). При этом необходимо учитывать загрузку нитей (единичных процессов, выполняемых на единичных процессорах) - обеспечить не только минимизацию их простоев, но и сокращение количества операций по передаче данных от центрального процессора графическому при вычислениях. Наиболее трудоемкая операция на каждом шаге моделирования - расчет взаимодействий между объектами. Она требует выполнения числа операций, квадратичного по отношению к числу объектов. Для реализации параллельного расчета нужно разделить систему из N объектов на блоки. Каждый блок рассчитывается на отдельном процессоре. Предварительная схема разбиения задачи на подзадачи: каждый процесс выполняет задачу по подсчету взаимодействия между двумя выбранными частицами системы. Внутри блока (группы программно организованных процессоров) выполняется задача по агрегации результатов выполнения на более низком уровне. Таким образом, результат работы каждого блока - подсчет взаимодействия всех частиц с данной. Верхний уровень системы (сетка - совокупность программно организованных блоков) агрегирует результаты, полученные на блочном уровне (взаимодействие каждой частицы со всеми) и передает их хосту. Первоначально для организации нитей (threads) и блоков (blocks) внутри сетки (grid) использовалась линейная схема [5] организации процессов, что казалось целесообразным, так как на вход алгоритму подается серия одномерных массивов, и каждая нить осуществляет подсчет взаимодействия между двумя определенными частицами. В алгоритме используется пошаговая проверка эффективности с возможным возвращением на несколько шагов назад. Авторами проведены компьютерные эксперименты, показавшие высокий процент ожидания процессов, что делает представленную декомпозицию частей неэффективной. Авторами предложен блочный алгоритм, в котором каждый процесс получил задачу по аналитике частицы (взаимодействие выбранной частицы со всеми), а блок процессов - задачу по аналитике группы частиц. Для представленной организации ленточный метод индексирования неприемлем (стал сложным), поэтому для разработки параллельного алгоритма используется блочная схема организации базовых подзадач. Для оценки корректности этапа разделения вычислений на независимые части используют контрольный список обязательных условий для разбиения: выполненная декомпозиция не увеличивает объем вычислений и необходимый объем памяти; при выбранном способе декомпозиции все процессоры равномерно загружены; выделенных частей процесса вычислений достаточно для эффективной загрузки имеющихся процессоров (с учетом возможности увеличения их количества). Выделение информационных зависимостей Учитывая, что передача данных от процессора процессору занимает определенное время и снижает эффективность параллельного алгоритма, ее нужно минимизировать. Оптимальный вариант - перед каждым шагом моделирования передавать всю информацию о системе на каждый процессор. На рисунке 1 показана схема разделения системы из N объектов на блоки с учетом информационных зависимостей. Pn Рис. 1. Разделение системы из N объектов на блоки с учетом информационных зависимостей Для оценки корректности этапа выделения информационных зависимостей так же, как и для этапа разделения на независимые части, используют контрольный список обязательных условий функционирования: вычислительная сложность подзадач соответствует интенсивности их информационных взаимодействий; интенсивность информационных взаимодействий одинакова для разных подзадач; схема информационного взаимодействия локальна; выявленная информационная зависимость не препятствует параллельному решению подзадач. Масштабирование и распределение задач по потокам Параллельный алгоритм называется масштабируемым, если при росте числа процессоров он одновременно обеспечивает увеличение ускорения и сохраняет эффективность использования процессоров. Масштабирование проводится в случае, если количество имеющихся подзадач отличается от числа планируемых к использованию процессоров. Ниже приведены правила агрегации и декомпозиции подзадач, которые параметрически зависят от числа процессоров, применяемых для вычислений. На рисунке 2 представлен параллельный алгоритм расчета одного шага моделирования системы из N объектов. Алгоритм является оптимальным для системы с количеством взаимодействий N2. Рассмотрим более детально систему с количеством взаимодействий (N*(N-1))/2 (каждая частица со всеми без повторений для следующих итераций). На рисунке 3 в матрице отражены системы с количеством взаимодействий N2(слева) и (N*(N-1))/2 (справа), где объекты обозначаются O1…On и серым цветом закрашены области, где не рассчитываются взаимодействия между объектами. Представленный алгоритм является оптимальными для однородной информационной среды, но его реализация в гетерогенной среде требует доработки. Во-первых, с числом увеличения частиц увеличивается нагрузка на каждый процессор, время выполнения блока расчетов, связанного с i-ой частицей, увеличивается. Во-вторых, из-за гетерогенности среды более мощные компьютеры простаивают, т.к. выполняют свои расчеты быстрее. Для решения этих задач создана модель балансировки нагрузки процессоров. Для оценки правильности масштабирования используют контрольный список обязательных условий функционирования: локальность вычислений не ухудшится после масштабирования имеющегося набора подзадач; подзадачи после масштабирования сохраняют одинаковую вычислительную и коммуникационную сложность; количество задач соответствует числу имеющихся процессоров; правила масштабирования зависят параметрически от количества процессоров. Psize N/Psize Pn Рис. 2. Алгоритм расчета одного шага моделирования системы из N объектов Рис. 3. Количество взаимодействий, выполняемое каждым объектом Распределение подзадач между процессорами является завершающим этапом разработки параллельного метода. Основной показатель успешности выполнения данного этапа - эффективность использования процессоров, определяемая как относительная доля времени, в течение которого процессоры использовались для вычислений, связанных с решением исходной задачи. Пути достижения хороших результатов в этом направлении остаются прежними: обеспечение равномерного распределения вычислительной нагрузки между процессорами и минимизация числа сообщений между ними. Для оценки правильности распределения использован контрольный список обязательных условий функционирования: распределение нескольких задач на один процессор не приводит к росту дополнительных вычислительных затрат; существует необходимость динамической балансировки вычислений; процессор-менеджер не является «узким» местом при использовании схемы «менеджер - исполнитель». Разработанный алгоритм (рис. 4) удовлетворяет всем обязательным пунктам контрольных списков по каждому этапу разработки, также учитываются функциональные и нефункциональные требования. Рис. 4. Алгоритм распределенного вычисления сил межчастичного взаимодействия Результаты компьютерных экспериментов Компьютерные эксперименты проводились на центральном процессоре Intel ® Core i3-4030U CPU 1.90 GHz с ОЗУ, равной 4,00 Gb, и на графическом процессоре с использованием видеокарты NVidia GeForce 820M для приложения, реализующего расчет на CUDA. Результаты компьютерных экспериментов, отражающие время вычисления (в секундах) одного программного модуля расчета сил межмолекулярного взаимодействия для параллельного (CUDA) и линейного (host) алгоритмов, представлены в таблице 1. Таблица 1 Результаты компьютерных экспериментов Количество частиц 1000 5000 10000 50000 100000 500000 1000000 устройство CUDA 0,2 2 10 345 1287 42234 589711 host 15 188 1286 53649 218023 7376529 104063567 Таблица 2 Результаты компьютерных экспериментов для разного количества нитей Количество частиц 1000 5000 10000 50000 100000 500000 1000000 количество нитей 32 0,5 4,7 22 754 1859 60992 3068950 64 0,2 2,5 10 355 1292 42399 1422241 128 0,3 2,7 11 370 1294 42453 1017201 256 0,3 2,3 10 360 1297 42563 784484 512 0,3 2,3 11 365 1295 42508 652894 1024 0,2 2,0 10 345 1287 42234 589711 Анализируя полученные результаты, можно сделать предварительное заключение, что реализация параллельного алгоритма дала выигрыш в скорости исполнения модуля подсчета сил межмолекулярного взаимодействия по одной характеристике в более чем 100 раз (усредненное табличное значение ускорения). В таблице 2 приведены результаты компьютерных экспериментов, отражающих время вычисления одного программного модуля расчета сил межмолекулярного взаимодействия для параллельного (CUDA) алгоритма при разном количестве потоков (нитей). Наибольшее ускорение достигается за счет организации блока с максимально возможным количеством нитей. Такая поточная организация позволит увеличить размерность моделируемой системы, но с увеличением числа нитей вырастает потребность в дополнительном выделении памяти на графическом процессоре. На рисунке 5 представлена кривая ускорения разработанного параллельного алгоритма. Рис. 5. Кривая ускорения параллельного алгоритма Пиковое значение скорости наблюдается возле отметки в 50 тыс. частиц, а минимальное значение выигрыша в производительности составляет 80 раз.

About the authors

A. S Trunov

Russian State University for Humanities

Senior Lecturer at the Department of Information Systems and Modeling, Russian State University for Humanities

L. I Voronova

Moscow Technical University of Communications and Informatics; Russian State University for Humanities

Email: voronova2001@mail.ru
Head of the Department of Information Systems and Modeling, Russian State University for Humanities, and Professor at the Department of Mathematical Cybernetics and Information Technologies, Moscow Technical University of Communications and Informatics

V. I Voronov

Russian State University for Humanities

Associate Professor at the Department of Information Systems and Modeling, Russian State University for Humanities.

References

Supplementary files