close

Вход

Забыли?

вход по аккаунту

?

Методы и программные средства повышения эффективности расчетов электронной структуры больших молекулярных систем

код для вставкиСкачать
ФИО соискателя: Чернецов Андрей Михайлович Шифр научной специальности: 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Шифр диссертационного совета: Д 212.157.01 Название организации: Московс
На правах рукописи
Чернецов Андрей Михайлович
Методы и программные средства организации
эффективных вычислений для расчета электронной
структуры больших молекулярных систем
Специальность: 05.13.11 – Математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Москва 2012
2
Работа выполнена в Национальном исследовательском университете «МЭИ»
на кафедре Прикладной математики.
Научный руководитель:
кандидат технических наук, доцент,
Шамаева Ольга Юрьевна
Официальные оппоненты: Топорков Виктор Васильевич
доктор технических наук, профессор,
заведующий
кафедрой
вычислительной
техники
Национального исследовательского университета «МЭИ»
Попов Виктор Юрьевич
доктор физико-математических наук, профессор,
профессор кафедры математики Физического
факультета МГУ им. М.В. Ломоносова
Ведущая организация:
ФГБОУ ВПО Московский государственный
технологический университет «Станкин».
Защита состоится «8» июня 2012 г. в 18.00 в ауд. Г-306 на заседании
диссертационного совета Д 212.157.01 при Национальном исследовательском
университете «МЭИ» по адресу: 111250, Москва, Красноказарменная ул., д.17.
С диссертацией можно ознакомиться в библиотеке Национального
исследовательского университета «МЭИ».
Отзывы в двух экземплярах, заверенные печатью организации, просьба
отправлять по адресу: 111250, Москва, Красноказарменная ул., д.14, Ученый
совет ФГБОУ ВПО «НИУ «МЭИ».
Автореферат разослан «___» мая 2012 г.
Ученый секретарь
диссертационного совета Д 212.157.01
кандидат технических наук, доцент
Фомина Марина Владимировна
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Характерной особенностью современного периода
развития науки и техники является тенденция роста сложности, размерности
решаемых задач, стимулирующая разработку методов, алгоритмов и программных
средств, ориентированных на высокопроизводительные вычислительные
архитектуры.
Одной из сложнейших задач современности является квантово-химическая
задача расчёта электронной структуры больших органических молекул, которые
насчитывают десятки тысяч взаимодействующих электронов и ядер. Результаты
расчётов используются, например, в фармакологии при решении задачи
конструирования
лекарств,
в
нанотехнологиях,
при
создании
высокотемпературных сверхпроводников и др.
Расчёт электронной структуры сводится к решению уравнения
Шредингера, которое описывает пространственное движение всех частиц
системы, перемещающихся в силовом поле. Так как положение каждой
частицы описывается тремя декартовыми координатами, то возникает
уравнение в частных производных второго порядка в трёхмерном пространстве,
решаемое аналитически лишь для очень малого класса систем, состоящих из
одного или двух атомов. Для молекулярных систем с бо′льшим числом атомов
применяются трудоёмкие численные итерационные методы, которые могут
быть реализованы только при использовании высокопроизводительных средств
и параллельной обработки. Практическими результатами решения задачи
расчёта электронной структуры являются взаимные расположения атомов в
пространстве, создающих стабильные молекулы и относительные энергии этих
молекул, а также временная зависимость между структурой молекул и их
свойствами.
В общем случае размерность задачи расчёта молекулярной системы есть
функция от числа атомов и размерности применяемого базиса в итерационном
методе. Трудоёмкость задачи расчёта зависит от метода решения, размерности
молекулярной системы и формы расчёта – с фиксированной или измененяемой
геометрией положения атомов.
В современных квантово-химических исследованиях допустимыми
временами расчёта считаются величины порядка секунд и минут, в
исключительных случаях – часов. Однако, расчёт больших молекул, содержащих
более 104 атомов, классическими методами даже с использованием
высокопроизводительных систем, составляет порядка нескольких десятилетий. По
мнению специалистов компании Intel компьютер, способный проводить
квантовохимические расчеты любой сложности за допустимое время, должен
иметь производительность не менее 1021 FLOPS, и такая мощность будет
достигнута не ранее 2030 года.
Таким образом, актуальными являются исследования, направленные на
организацию эффективных расчётов электронной структуры больших молекул
на существующих сегодня высокопроизводительных архитектурах.
4
Данная работа посвящена исследованию методов расчёта и созданию на их
основе эффективных последовательных и параллельных схем вычислений,
учитывающих особенности структур обрабатываемых данных, с последующей
реализацией на высокопроизводительных системах, а также выводу
характеристик трудоёмкости и эффективности разработанных алгоритмов,
позволяющих оценить качество созданных программных средств.
Выполненные исследования опираются на результаты работ
отечественных ученых В.А. Фока,
В.В. Воеводина, А.А. Самарского,
Вл.В. Воеводина, В.П. Гергеля, В.В. Корнеева, а также зарубежных ученых
D.R. Hartree, J. Pople, A.H.R. Palser, D.E. Manolopoulos, S.Goedecker, L.Colombo,
G.E. Scuseria, J.H. Wilkinson, B.Parlett, E. Golub, S. Pissanetzky, R. Tewarson, I.
Foster, J. Dongarra.
Объектом исследования являются методы, алгоритмы и программные
средства для расчётов электронной структуры больших органических молекул.
Предметом исследования является разработка методов, алгоритмов и
программных средств, направленных на повышение эффективности процедур
расчёта больших молекул и их вычислительные характеристики.
Целью диссертации является разработка алгоритмов и программных средств,
повышающих эффективность расчётов больших молекулярных систем с
использованием высокопроизводительных вычислительных средств. Для
достижения указанной цели ставились и решались следующие задачи:
1. анализ и исследование существующих методов расчёта электронной
структуры больших молекулярных систем с целью выбора оптимального
соотношения между трудоёмкостью и точностью;
2. реализация эффективной последовательной программы прямого расчёта
матрицы плотности P по методам Гоедекера-Коломбо и ПальцераМанолополиса в среде ОС Linux;
3. разработка алгоритма расчёта фокиана по методу Austin Model/1 (АМ1) для
разреженных матриц и обоснование целесообразности его параллельной
модификации;
4. разработка параллельно-последовательных алгоритмов расчёта для плотных
и разреженных структур данных и создание на их основе комплекса
параллельных программ;
5. анализ теоретических оценок ускорения для разработанных алгоритмов и
программ;
6. исследование эффективности разработанных программных средств.
Методы исследования. Поставленные задачи решаются с использованием
методов вычислительной математики, параллельного программирования, теории
вычислительной сложности алгоритмов. При разработке программного обеспечения
использовались: методы нисходящего проектирования, методика крупнозернистого
распараллеливания, модель передачи сообщений, модель потокового параллелизма
графических процессоров CUDA, модель параллельного программирования в
пакете MATLAB для реализации параллельных модификаций алгоритмов.
5
На защиту выносятся:
1. параллельные алгоритмы расчётов на основе методов ГоедекераКоломбо и Пальцера-Манолополиса;
2. параллельная модификация метода Пальцера-Манолополиса для
обработки разреженных структур данных;
3. методы хранения и преобразования разреженных структур данных;
4. теоретические оценки трудоёмкости разработанных алгоритмов;
5. результаты экспериментов, выполненных с помощью разработанных
программных средств.
Достоверность научных результатов подтверждается соответствием
теоретических выкладок и результатов экспериментов, а также сопоставлением
полученных результатов с результатами, приведёнными в зарубежной научной
литературе.
Научная новизна исследования состоит в следующем:
1. разработаны параллельные алгоритмы расчёта электронной
структуры больших органических молекул для плотных матриц, сократившие
время расчётов;
2. на основании исследования разреженных структур данных
разработаны схемы хранения и метод обработки, позволившие значительно
увеличить допустимую размерность решаемых задач, сократить время решения
и требования к используемой памяти;
3. разработан алгоритм расчёта фокиана по методу АМ1 для разреженных
структур матриц, исследования которого показали нецелесообразность его
параллельной модификации в модели распределённой памяти;
4. выведены, исследованы и экспериментально подтверждены
теоретические оценки ускорения и эффективности разработанных
алгоритмов с целью определения допустимых размерностей задачи и
требований к ресурсам аппаратных средств, а также позволяющие
прогнозировать получаемое ускорение на реальных вычислительных системах.
Практическая значимость полученных результатов заключается в
разработке методов, алгоритмов и программных средств, которые сокращают
время расчётов электронной структуры больших органических молекул.
Реализованные программные средства обладают большей эффективностью по
сравнению с применяемыми ранее и позволяют значительно повысить
допустимую размерность решаемой задачи. Разработанные методы и программные
средства учитывают особенности современных высокопроизводительных архитектур,
таких как вычислительные кластеры и графические процессоры.
Реализация результатов. Работа выполнялась в рамках грантов РФФИ
01-07-90072, 04-07-90220, 05-07-08031-офи-а, 11-07-00470, что подтверждено
актом об использовании, выданном Институтом органической химии
им. Н.Д. Зелинского РАН. Результаты работы внедрены в научноисследовательскую
деятельность
Вычислительного
центра
им. А.А. Дородницына РАН, что подтверждено актом о внедрении.
6
Апробация полученных результатов. Основные положения и
результаты диссертации докладывались и обсуждались на международных
научно-технических конференциях студентов и аспирантов “Радиоэлектроника,
электротехника и энергетика” (г. Москва, 2005 г., 2007 г., 2008 г.), на
международных научно-технических конференциях “Информационные
средства и технологии” (г. Москва, 2004 - 2008 гг.), на международных научнопрактических семинарах “Высокопроизводительные параллельные вычисления
на кластерных системах” (г. Самара, 2004 г., г. Н.Новгород, 2005 г., г. Казань,
2008 г.), на третьей международной конференции Dependability of Computer
Systems Depcos-RELCOMEX 2008 (Польша, 2008 г.), на электронной
конференции “Информационно-вычислительные технологии в науке” ИВТН2011, на международной конференции “Информатизация инженерного
образования” (г. Москва, 2012 г.).
Публикации. Основные результаты, полученные при выполнении
диссертационной работы, опубликованы в 16 печатных работах, включая 2
статьи в изданиях из перечня ВАК и 1 монографию.
Структура и объем работы. Работа состоит из введения, 4 глав,
заключения,
списка
использованной литературы,
содержащего
79
наименований, и приложений. Основной текст занимает 161 машинописных
страницы, в том числе 32 рисунка и 15 таблиц. Полный объём диссертации (с
приложениями) составляет 182 страницы.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, её научная
новизна и практическая значимость, сформулирована цель работы и приведено
краткое содержание диссертации по главам.
В первой главе рассматриваются физическая и математическая модели
задачи
расчёта
электронной
структуры
молекул.
Анализируются
существующие методы расчёта электронной структуры, приводится их
классификация, в том числе по вычислительной сложности и затратам
оперативной памяти.
Методы расчёта электронной структуры молекул можно разбить на
несколько больших классов – класс многоэлектронных методов, класс
одноэлектронных методов и ряд других.
В
одноэлектронных
методах
для
определения
состояния
многоэлектронной системы, имеющей минимальный уровень полной энергии,
используется концепция эффективного одноэлектронного гамильтониана
1
H 2 (r ) , где v – оператор потенциальной энергии, – оператор Лапласа, r
2
2
– радиус-вектор. При этом возникает задача на собственные значения Hi ii ,
где i нумерует собственные значения и соответствующие собственные вектора.
Схема строгих методов расчёта, изображенная на рис. 1, основывается на
методе Хартри-Фока, в котором в качестве эффективного одноэлектронного
гамильтониана применяется оператор Фока. Эти схемы относятся к классу
7
методов самосогласованного поля (ССП). Эффективные одноэлектронные
гамильтонианы H в этих методах зависят от матрицы плотности Р. Сначала
рассчитывается начальное приближение к матрице Р, затем из Р
рассчитывается одноэлектронный гамильтониан H (фокиан F), для него
решается задача на собственные значения, из собственных векторов
рассчитывается новая матрица плотности Р, из неё строится новый
гамильтониан (фокиан), затем процедура итерационно повторяется.
Рисунок 1 - Общая процедура расчётов методами ССП.
Рассмотренная схема расчётов является основой для построения
полуэмпирических методов, в которых заметно упрощается расчёт фокиана в
базисе атомных орбиталей (АО), а матрица плотности P определяется
классическим способом - путем диагонализации. Обозначим N – размерность
задачи. Для полуэмпирических методов N измеряется в атомных орбиталях.
В работе показано, что при формировании математической модели
органической молекулы, в силу её физико-химических свойств возникают
матричные разреженные структуры, использование свойств которых позволяет
повысить скорость и эффективность расчётов.
В работе исследованы следующие полуэмпирические методы: метод
Гоедекера-Коломбо (ГК) и Пальцера-Манолополиса (ПМ) как для плотных, так и
для разреженных структур данных.
На примере метода ГК показано, что использование свойства разреженности
структур данных для больших молекул приводит к оценке O(N) как трудоёмкости
по времени, так и затратам памяти. На рис. 2 приведены основные расчётные
формулы метода.
В методе ПМ, называемом также канонической очисткой (purification),
итерационная формула для нахождения матрицы P выглядит следующим образом:
1
1
(1 2c n ) Pn (1 c n ) Pn2 Pn3 , c n 1 cn
2
Pn1 1
1
(1 c n ) Pn2 Pn3 , c n cn
2
, cn tr ( Pn2 Pn3 )
,(1)
tr ( Pn Pn2 )
8
где n – номер шага итерационного процесса. Процесс останавливается при
достижении заданной точности по идемпотентности, т.е.
tr ( P 2 ) tr ( P )
tr ( P )
Таблица 1. Сравнительные характеристики методов расчёта.
Методы расчёта
Многоэлектронные
строгие,
корреляционные
Одноэлектронные
строгие,
Одноэлектронные
полуэмпирические
диагонализации
Одноэлектронные
полуэмпирические
прямые методы без
учета разреженной
структуры
Одноэлектронные
полуэмпирические
прямые методы с
учетом разреженной
структуры
Трудоёмкость
Затраты
оперативной
памяти
Наличие
последовательной
реализации
Наличие
параллельной
реализации
O(N!)
O(N5) и выше
Gaussian,
GAMESS-us
Gaussian,
GAMESS-us
O(N5)
O(N4) и выше
Gaussian
Gaussian
O(N3)
O(N3)
Gaussian,
MOPAC 2009
PRMAT
Разработаны и
реализованы в
данной работе
Разработаны и
реализованы в
данной работе
3
O(N )
O(N )
Разработаны и
реализованы в
данной работе
O(N)
O(N)
mopac2009,
MondoSCF,
Gaussian
3
В табл. 1 приводятся основные характеристики рассмотренных и
исследованных в работе методов расчёта электронной структуры молекул.
Указаны трудоёмкость, требования к ёмкости оперативной памяти, а также
наличие программных реализаций. Выделяются разработанные в диссертации
средства.
Из анализа методов расчёта следует, что для больших и сверхбольших
молекул
с
точки
зрения
трудоёмкости
наиболее
эффективными
полуэмпирическими методами расчёта электронной структуры являются прямые
методы с учётом разреженности.
Во второй главе разрабатываются и исследуются последовательные и
параллельные алгоритмы расчёта матрицы плотности на основе
полуэмпирических прямых методов. Представлен, реализован и исследован
последовательный алгоритм расчёта матрицы плотности по методу ГоедекераКоломбо, использующий матричные полиномы Чебышева.
На основе приведённого на рис. 2 алгоритма разработана и реализована
последовательная программа расчёта матрицы P по методу ГК для ОС Linux на
языке Фортран-90.
С целью эффективной реализации программы применяются: оптимальная
(исходя из свойств матриц) форма хранения данных, оптимизация умножения
9
матриц на основе специализированного пакета, реализующего стандарт BLAS
(Basic Linear Algebra Subroutines).
Рисунок 2 - Схема основных этапов метода Гоедекера-Коломбо.
Переход к “треугольной” форме хранения матрицы T резко снижает
затраты памяти. В работе предложено за счет симметричности матрицы T по
первым двум координатам преобразовать её в массив размерности N ( N 1) p , где
2
p – размерность полинома Чебышева.
Имеются
различные
способы
улучшения
производительности
программного кода умножения матриц в рамках языков высокого уровня.
Оптимальным
способом
среди
них
является
использование
специализированных пакетов, реализующих стандартные базовые операции
линейной алгебры BLAS. Применение подпрограммы DGEMM стандарта BLAS
позволило повысить эффективность реализации последовательной программы.
Применение библиотеки ATLAS ускорило время матричного умножения в 3050 раз в зависимости от размера матриц для процессора Intel Pentium 4/2.6 ГГц.
В работе предложен и реализован параллельный алгоритм для метода ГК,
ориентированный на модель передачи сообщений. В его основе - представление
матрицы в блочной форме и возможность организации независимой обработки
блоков. Обоснована целесообразность использования двух форм передачи
данных при параллельной реализации: широковещательной рассылки и
использования двухточечных обменов.
В работе на основе метода ПМ предложены как последовательный, так и
параллельный алгоритмы расчёта. Параллельный алгоритм реализован для
модели передачи сообщений на языке Фортран 90.
10
В третьей главе анализируется метод Пальцера-Манолополиса с точки
зрения особенностей построения и реализации алгоритмов расчёта для
разреженных форм представления и обработки матриц. Производятся оценки
требований к памяти, трудоёмкости и эффективности.
Обрабатываемые матрицы в общем случае имеет разреженную форму
сложного вида. В работе рассматривается частный случай блочно
трёхдиагональных матриц, изображенных на рис. 3. Здесь L – число блоков
главной диагонали, A1i, B1i, R1i, A2i, B2i, R2i, A3i, B3i, R3i – матричные, в
общем случае плотно заполненные, блоки; A1i (i=1,L)– матрицы блоков
главной диагонали, A2i и A3i (i=1,L-1) – соответственно матрицы блоков
нижней поддиагонали и верхней наддиагонали. Количество блоков ограничено
только доступными ресурсами памяти.
Для эффективной реализации метода ПМ в случае представления матрицы
фокиана в форме блочно-трёхдиагонального вида необходимо организовать
эффективное выполнение линейных операций с матрицами (сложение, умножение
на число) и умножение матриц.
При умножении двух блочно-трёхдиагональных матриц A и B в матрице
результата R помимо 3-х указанных диагоналей появляется 4-ая ненулевая блочная
диагональ, значениями элементов которой можно пренебречь с точки зрения
анализа (расчётов) электронной структуры молекул. Поэтому результирующая
матрица R также представляется в форме блочно- трёхдиагональной матрицы:
A1
A2
0
0
0
A3
0
...
A1
A3
...
A2
A1
...
...
...
...
...
...
A2
0 B1 B3 0 ... 0 R1 R3 0 ... 0 ... B 2 B1 B3 ... ... R 2 R1 R3 ... ... ... 0 B 2 B1 ... ... 0 R 2 R1 ... ... A3 0 ... ... ... B3 0 ... ... ... R3
A1 0 ... ... B 2 B1 0 ... ... R 2 R1
Рисунок 3 - Умножение блочно-трёхдиагональных матриц R=A∙B.
В работе предлагается специальная схема хранения блочнотрёхдиагональных матриц: матрицы A, B и R представляются в форме трёх
мерных массивов. Факторизованные выражения для блоков матрицы результата
имеют вид:
R1i A2 i 1 * B 2 i 1 A1i * B1i A2 i * B 2 i
R 2 i A2 i * B1i A1i 1 * B 2 i 1
R3i A1i * B 2 i A2 i 1 * B1i 1
Здесь Аij – j –я блочная матрица i-й диагонали исходной матрицы A, Bij –
блочная матрица i-й диагонали исходной матрицы B, j – позиция блока в А (B).
Rij – j –й блок результирующей матрицы.
Поскольку матрица фокиана F является симметричной, а блоки на
главной диагонали являются квадратными, то экономится память на хранении
массива блоков верхней наддиагонали, и после упрощений имеем:
T
T
R1i A2 i1 * B 2 i1 A1i * B1i A2 i * B 2 i
R 2 i A2 i * B1i A1i1 * B 2 i1
11
Факторизованные выражения для первых(R11 и R21) и последних (R1L и
R2L-1) блоков получаются из общих формул.
На рис. 4 представлена схема разработанного параллельного алгоритма,
эффективность которого зависит от варианта обмена блоками при рассылке
блоков. Схема реализует множество распределенных расчётов, при этом в
качестве начальных данных рассылаются только части матрицы F. Каждый
процесс получает от главного блоки матриц, необходимые для расчётов, в
конце работы происходит сбор всех результатов в главном процессе. Это
позволяет в отдельно взятом процессе выполнять действия по умножению
матриц только над теми блоками, которые назначены процессу.
Процесс вычислений повторяется итерационно до достижения заданной
точности матрицы плотности. На каждой i-й итерации взаимодействие между
различными процессами минимально: большая часть вычислений происходит
независимо, а данные от других процессов требуются только для вычисления
“пограничных” блоков. Более того, на каждой итерации возможно заранее сделать
все необходимые пересылки данных и уже затем производить умножение блоков.
В работе выводятся и анализируются оценки трудоёмкости и требуемой
оперативной памяти для методов очистки для плотных и разреженных матриц.
Рассмотрим итерационную формулу (1). Определим вероятности того,
что коэффициент cn ½ или cn > ½ как P{cn ½} =q, P{cn > ½} = 1-q. Пусть u –
время аддитивной операции, v – время мультипликативной операции. m –
максимальная размерность “мелких” блоков m=max(mi), nbl = L.
Тогда можно определить “эффект” от использования разреженной формы
хранения матрицы плотности:
S разр q nbl [4 u m nbl v ] (1 q ) nbl [4 u 2 m nbl v]
q [8 u 5 m v ] (1 q ) [8 u 10 m v]
В работе приводятся и анализируются графики полученного “эффекта” в
зависимости от разных характеристик разреженной матрицы.
Для анализа разработанных алгоритмов в работе исследуются оценки
трудоёмкости для случая параллельной реализации рассмотренных выше
методов на множестве вычислителей p и использования модели
распределённой памяти.
В модели распределённой памяти необходимо учитывать время передач
между вычислителями, поэтому введём функцию Fswap(x) – взаимная передача x
байт от одного процесса к другому (выполнение двухточечного обмена).
Ускорение вычислений S ( p ) F ( p, q, m, nbl , u , v, Fwsap ) на p вычислителях
можно оценить как:
S ( p) q nbl m 2 [4 u m nbl v ] (1 q) nbl m 2 [8 u 10 m v]
1
1
nbl m 2 [8 u 5 m v] (1 q) nbl m 2 [8 u 10 m v] 3 u m 2 p 3 Fswap (m 2 8) p
p
p
12
Рисунок 4 - Схема параллельного алгоритма расчёта матрицы плотности по методу
ПМ для разреженного случая.
В работе приведены графики зависимости ускорения от числа процессоров
для разных размерностей задачи расчёта при различных размерах блока m. На
рис. 5 приведён график зависимости ускорения от числа процессоров p при
использовании разреженности, числа блоков nbl=300, и для различных значений
размерности “мелкого” блока m=100;150;200;250.
Из анализа графиков в работе следуют выводы:
для любой размерности исходной задачи существует целесообразный
диапазон изменения числа используемых процессоров p, в рамках которого
возможно достижение максимального ускорения;
чем больше размерность исходной задачи, тем шире диапазон изменения p и
тем дальше он сдвигается в сторону больших значений p;
13
при увеличении размерности блока и фиксированной исходной размерности
задачи ускорение растёт до определенного предела, а затем начинает
снижаться. При этом происходит рост числа ненулевых элементов матрицы P.
Рисунок 5 - Оценка зависимости ускорения от числа процессоров.
Выведенная теоретическая оценка трудоёмкости метода ПМ позволяет для
каждой заданной размерности задачи определить требуемое число процессоров p
и возможное ускорение S(p).
Предложенные и реализованные параллельные алгоритмы расчёта
матрицы плотности P позволяют существенно сократить общее время расчёта
электронной структуры больших молекул. В этих алгоритмах фокиан F является
входным параметром и вопрос его эффективного расчёта не рассматривался.
Следующим уровнем оптимизации общей процедуры расчётов (см.
рис. 1), является разработка эффективной процедуры построения фокиана F.
Процедура построения F исследуется с точек зрения учета разреженности
и параллельной модификации. Для этого разрабатываются последовательные
алгоритмы расчёта для разреженной структуры матрицы фокиана F по методу
AM1, а именно: получение значения произвольного элемента, расчёт
двухэлектронных вкладов в фокиан, расчёт фокиана. Анализируются
используемые структуры данных.
На основе применения “по-атомного” подхода возможно разреженное
представление фокиана. Например, для молекулы метана структура фокиана
может иметь вид, представленный на рис. 6. Матрицы плотности P и фокиана F
являются блочными, симметричными, поэтому их можно хранить по блокам,
выделяя для хранения 3 “крупных” блока A, B и C, где AijA, BijB, Cij C блоки 3-х типов размерности dim Aij =1x1, dim Bij=4x1, dim Cij=4x4.
Следовательно, требуется хранить не всю матрицу, а только нижний или
верхний треугольник.
A11
A21
0
0
0
B61
B
71
0
A22
0
A33
A42
0
A44
0
0
A54
A55
B62
0
0
0
C66
B72
0
B73
0
0
B84
0
B85
C76
0
C77
C87
C88 Рисунок 6 – Разреженное представление фокиана.
14
В диссертации предложен параллельный алгоритм построения фокиана F
по методу АМ1 в модели распределённой памяти, который реализован на языке
Fortran 95 с использованием инструментальных средств MPI.
В четвёртой главе проведено исследование эффективности
разработанных программных средств расчёта электронной структуры больших
молекулярных систем с позиций: моделей вычислений, применяемых методов
расчёта, множества специфических параметров метода, размера молекулярной
системы, используемой структуры хранения (плотная/разреженная), множества
характеристик аппаратной среды.
В табл. 2 для каждого разработанного алгоритма указаны аппаратнопрограммные средства реализации, а также размеры исходного кода
соответствующих программ.
Таблица 2. Разработанные алгоритмы и аппаратно-программные средства их реализации.
Метод
Разработанные
алгоритмы
ГоедекераПараллельный
Коломбо (ГК) алгоритм
для
плотных матриц
ПальцераПараллельный
Манолополиса алгоритм
для
(ПМ)
плотных матриц
Модификация Параллельный
метода
алгоритм
для
Пальцераразреженных
Манолополиса матриц
АМ1
для Последовательный
разреженных и
параллельный
матриц
алгоритмы
ПальцераПараллельный
Манолополиса алгоритм
для
разреженных
матриц
Программные/аппаратные
средства
MPI,
Кластер ВЦ РАН
MPI,
Кластер ВЦ РАН,
MATLAB
MPI,
Кластер ВЦ РАН,
МВС-6000,
Кластер НИУ МЭИ
MPI,
Кластер ВЦ РАН
Размер кода
программного
продукта
1190 строк, 32 кб
1400 строк, 36 кб,
604 строки, 20 кб
2628 строк, 48 кб
Последовательная
программа 350 кб
Параллельная
программа 380 кб
CUDA, GPU
1993 строки, 44
кб
В работе приведён краткий обзор существующих моделей параллельного
программирования, и дано обоснование использования модели распределенной
памяти, гибридных моделей, средств графических процессоров и
математических пакетов.
Для контроля точности полученных в результате экспериментов решений
выполнен альтернативный расчёт некоторых молекул с помощью метода
диагонализации матрицы фокиана.
В работе проведено исследование зависимости скорости сходимости
метода Гоедекера-Коломбо (числа итераций) к окончательному (истинному с
заданной степенью точности 10-2) решению в зависимости от входных
параметров – обратной температуры β и порядка полинома Чебышева p. Для
этого проведен ряд экспериментов с различными исходными данными.
15
В результате показано, что:
применение полиномов Чебышева не ниже 9 порядка в методе ГК
позволяет рассчитать электронную структуру молекулы в 1.5 раза
быстрее, чем методом матричной диагонализации;
параметр метода β для исследуемых молекул не влияет на скорость
сходимости к решению.
В главе приводятся и анализируются результаты различных
экспериментов по расчёту электронной структуры молекул с помощью
последовательных и параллельных алгоритмов, выполненных на различных
программно-аппаратных кластерных системах.
Последовательная
программа
расчёта
разреженного
фокиана
использовалась для нахождения F молекулы одномерного полиглицина
размерности около 56000 атомов.
В работе при создании параллельных алгоритмов используется методика
крупнозернистого распараллеливания, которая наиболее адекватно реализуется
в модели вычислений с распределённой памятью. Однако, при тестировании
параллельной программы для расчета разреженного фокиана по методу АМ1
для молекулы полиглицина из 56000 атомов на кластере ВЦ РАН получены
низкие значения ускорения: 1,33 для 2 процессоров и 1,22 для 3-х процессоров,
что свидетельствует о нецелесообразности распараллеливания процесса
построения фокиана в выбранной модели. Эффективнее использовать системы
с общей памятью, где возможно минимизировать временные задержки,
связанные с передачей данных.
На рис. 7 представлены достигнутые ускорения при расчётах модельного
фокиана молекулы полипептида размера около 4500 АО для плотных матриц по
методу ГК. Значения ускорения, полученные с помощью разработанной
параллельной программы не хуже, чем в коммерческом пакете MOPAC2002 для
молекулы фуллерена похожей размерности. Использование двухточечных
обменов является более эффективной схемой, чем широковещательная
рассылка.
Рисунок 7 - Графики ускорений параллельной программы по методу ГК для разных
схем обменов в зависимости от числа процессоров.
16
На рис. 8 приводятся результаты экспериментов параллельных программ,
выполненных для модельных фокианов молекул полипептида для плотных
матриц по методу ПМ.
Рисунок 8 - Графики ускорения в зависимости от числа процессоров для
параллельной программы по методу ПМ.
В табл. 3 и на рис. 9 и 10 представлены результаты экспериментов,
проведенных на модельном фокиане молекулы полипептида размерности около
75000 АО, с помощью параллельной программы для разреженных матриц по
методу ПМ. Расчёты проводились на кластерных системах ВЦ РАН (Xeon 2.6,
Myrinet 2000), НИУ “МЭИ” (Opteron 2.2, Infiniband 10X) и на суперкомпьютере
МВС-6000 (Itanium 2/1.6, Myrinet 2000).
Таблица 3. Достигаемое ускорение на кластерах ВЦ РАН, МВС-6000 и НИУ МЭИ.
Число
Ускорение
Эффективность, %
Процессов
Кластер ВЦ РАН/МВС-
Кластер ВЦ РАН/МВС-
6000/ Кластер НИУ МЭИ
6000/ Кластер НИУ МЭИ
2
1.98 / 1.72/1.99
99.0 /86.0/ 99.5
3
2.91 / 2.44 / 2.97
97.0 /81.27/ 99.0
4
3.76 / 3.14 /3.88
94.0 / 78.45/ 97.0
5
4.58 / 3.74 / 4.91
91.6 / 74.6/ 98.2
6
5.29 / 4.02 / 5.73
88.17 / 67.05/95.5
7
5.72 / 4.52 / 6.50
81.7 / 64.59/92.9
8
6.36 / 5.16 / 6.93
79.5 /64.46/86.6
12
-/ 6.34 / 10.27
/ 52.79/85.6
16
-/ 7.17 /-
/ 44.83/
24
-/8.03 /-
/33.46/
28
-/9.38 /-
/33.5/
30
/5.31 /-
/17.7/
17
Рисунок 9. Зависимость ускорения от числа процессоров для разреженного метода
ПМ. Расчёты на кластере ВЦ РАН и МВС-6000.
Как видно из рис. 10, теоретические оценки ускорения, полученные в
главе 3, достаточно точно соответствуют экспериментальным данным.
Рисунок 10 - Сравнение зависимости ускорения от числа процессоров, полученного
на кластере НИУ “МЭИ”, с выведенной теоретической оценкой.
Для молекулы полиглицина размерности около 2900 АО в работе
произведено тестирование параллельной программы расчёта по методу ПМ для
случая разреженных матриц при автоматическом распараллеливании с
использованием OpenMP-распараллеленных версий матричного умножения
DGEMM. На кластере ВЦ РАН достигнутое ускорение на 2 процессорах
составляет 2.0, на 4 процессорах -3.6, на 5 процессорах - 4.4.
В работе также проведено исследование ещё одного способа ускорения
вычислений – использование потокового параллелизма графических процессоров
для повышения эффективности блочного матричного умножения.
Сравнение производительности матричного умножения ядра CPU (Xeon
5520) и GPU (Tesla C2050) представлено на рис. 11. Уже для размерности блока
m>256 применение GPU (применяется библиотека CUBLAS) даёт больший
эффект, чем распараллеленный на все 4 ядра процессора DGEMM (применяется
библиотека MKL). При увеличении размерности блока превосходство
становится существенно больше.
18
Для молекулы полиглицина размерности около 2900 АО реализация
параллельной программы расчёта по методу ПМ с применением GPU показала
в 2 раза лучшие результаты, чем реализация той же программы на всех
используемых 8 ядрах (2*Xeon 5520).
Рисунок 11 - График производительности GPU для матричного умножения в
зависимости от размерности.
В работе также исследовался математический пакет MATLAB с точки
зрения создания методики разработки параллельных программ для выполнения
научных расчётов. Основные постулаты в порядке сложности применения
следующие:
активизация встроенных в ядро средств пакета для распараллеливания;
указание использования средств GPU, совместимого с требованиями
пакета (при его наличии);
выявление в задаче независимо выполняющихся подзадач.
Использование средств пакетного запуска batch и spmd;
в случае полного отсутствия взаимодействия между подзадачами
использование parfor;
в случае взаимодействия между подзадачами организация обменов с
использованием функций двухточечных и коллективных обменов;
с целью отладки параллельных алгоритмов использование средств
режима pmode.
В заключении приведены основные результаты диссертационной работы
и сделаны общие выводы.
В Приложения вынесены вспомогательные обзорные материалы,
приведены копии актов о внедрении и использовании результатов диссертации.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Исследована физико-математическая модель задачи расчёта электронной
структуры больших и сверхбольших молекулярных систем и основные
методы её решения. На основе анализа трудоёмкости методов и их
требований к затратам памяти, а также структур обрабатываемых данных
сделан вывод, что для повышения эффективности расчётов целесообразно
19
использовать полуэмпирические методы расчёта с учётом разреженности
структур данных.
2. Реализована последовательная программа расчётов для плотных матриц по
методу Гоедекера-Коломбо на языке Фортран-90 в среде Linux.
3. Разработан параллельный алгоритм расчёта матрицы плотности по методу
Гоедекера-Коломбо, реализована и экспериментально исследована
соответствующая параллельная MPI-программа.
4. Разработан параллельный алгоритм расчёта для плотных матриц по методу
Пальцера-Манолополиса, который реализован в рамках модели MPI и двух
способов обмена - широковещательной рассылки и двухточечных обменов.
5. Разработаны схемы хранения и предложены методы обработки разреженных
структур на примере блочно-трёхдиагональных матриц, позволившие
значительно сократить время расчётов P и увеличить размерность решаемых
задач.
6. Разработаны последовательный и параллельный алгоритмы на основе
метода Пальцера-Манолополиса для случая матриц с блочнотрёхдиагональным портретом.
7. Исследованы
оценки
трудоёмкости
разработанных
алгоритмов,
позволяющие прогнозировать получаемое ускорение на реальных
вычислительных
системах,
которые
соответствуют
проведённым
экспериментам.
8. Разработана схема хранения для разреженного фокиана и предложен
последовательный алгоритм расчёта по методу АМ1, позволивший
рассчитать фокиан молекулы, содержащей более 5∙104 атомов.
9. Разработана параллельная модификация расчёта фокиана методом АМ1 для
разреженных матриц и выполнена её реализация, показавшая неэффективность
использования для данного расчёта модели распределённой памяти.
10. Разработана методика создания параллельных программ для выполнения
научных расчётов в среде математического пакета MATLAB, которая была
применена для реализации программы по методу Пальцера-Манолополиса.
11. Разработан, реализован и исследован параллельный алгоритм по методу
Пальцера-Манолополиса для NVIDIA GPU (CUDA), показавший
существенное увеличение производительности расчётов по сравнению с
использованием многоядерных процессоров в кластере за счёт только
эффективного выполнения блочного матричного умножения.
СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ
1. А.М. Чернецов, О.Ю. Шамаева. О параллельной реализации алгоритмов расчета
электронной структуры больших молекул // Вестник МЭИ. -2009. - №3.- С. 67-71.
2. А.М. Чернецов, О.Ю. Шамаева. Эффективные вычисления для расчета электронной
структуры больших молекул. // Программные продукты и системы. – 2012. -№ 2. -С. 84-88.
3. Н.Н. Оленев, Р.В. Печенкин, А.М. Чернецов. Параллельное программирование в
MATLAB и его приложения, М., Издательство ВЦ РАН, 2007.- 120 с.
4. М.Б. Кузьминский, В.В. Бобриков, А.М. Чернецов, О.Ю. Шамаева. Распараллеливание в
кластере полуэмпирических квантово-химических методов при прямом вычислении матрицы
плотности для больших молекулярных систем // Высокопроизводительные параллельные
20
вычисления на кластерных системах. Материалы 4-го междунар. науч.-практич. семинара и
всероссийской молодежной школы. Самара, НГГУ. 2004 г. -С. 141-144.
5. В.В. Бобриков, А.М. Чернецов, О.Ю. Шамаева. Распараллеливание квантово-химических
расчетов матрицы плотности с использованием полиномов Чебышева, // Труды
междунар. науч.-техн. конф. “Информационные средства и технологии”, М.: Янус-К,
2004 г. -Т.1. -С. 219-222.
6. А.М. Чернецов. Применение сетевых технологий при распараллеливании задачи прямого
расчета матрицы плотности в исследованиях электронной структуры молекул, // Тез. док.
междунар. науч.–техн. конф. студентов и аспирантов “Радиоэлектроника, электротехника
и энергетика” в 3 т. М.: Изд. МЭИ, 2005 г. – Т.1 - С. 354-355.
7. А.М. Чернецов, О.Ю. Шамаева. Параллельная реализация метода ПальцераМанолополиса для вычисления матрицы плотности в задачах расчета электронной
структуры молекул // Труды междунар. науч.-техн. конф. “Информационные средства и
технологии”, М.: Янус-К, 2005 г. -Т.2. - С. 67-70.
8. М.Б. Кузьминский, А.М.Чернецов, О.Ю. Шамаева. Практика использования в кластерах
аппаратного и программного обеспечения Infiniband от Mellanox. Распараллеливание в
задачах вычислительной химии, // “Высокопроизводительные параллельные вычисления
на кластерных системах. Материалы 5-го междунар. науч.- практич. семинара и
всероссийской молодежной школы”. Н. Новгород: Изд. НГГУ.- 2005 г. -С. 143-149.
9. А.М. Чернецов, О.Ю. Шамаева. Расчеты разреженной матрицы плотности методом
очистки на кластерных системах, // Труды междунар. науч.-техн. конф.
“Информационные средства и технологии”, М.: Янус-К. -2006 г. -Т. 3. -С. 155-158.
10. А.М. Чернецов. Распараллеливание процесса сборки фокиана, // Тез. док. междунар.
науч.–техн. конф. студентов и аспирантов «Радиоэлектроника, электротехника и
энергетика” в 3 т. –Москва: Изд. МЭИ.- 2007 г. -Т.1 -С. 379-380.
11. А.М. Чернецов, Р.В. Печенкин. Параллельное программирование в MATLAB, // Труды
междунар. науч.-техн. конф. «Информационные средства и технологии» в 3 т. -М.: Изд.
МЭИ. 2007 г. -Т. 3. -С. 105-109.
12. Andrey Chernetsov, Olga Shamayeva. Problems of Parallel Realization of Algorithms of
Electronic Structure of Large Molecules //Proceedings of International Conference on
Dependability of Computer Systems Depcos-RELCOMEX 2008 Szklarska Poreba, Poland, 2628 June, pp. 324-331. //IEEE Computer Society.
13. А.М. Чернецов, О.Ю. Шамаева. Характеристики трудоемкости и вычислительной
эффективности прямых методов расчета электронной структуры больших молекул, //
Труды междунар. науч.-техн. конф. «Информационные средства и технологии», М.: Изд.
МЭИ. 2008 г. -Т.2 -С. 98-105.
14. А.М. Чернецов, О.Ю. Шамаева, М.Б. Кузьминский. Распараллеливание в кластерах
полуэмпирического квантово-химического метода Пальцера-Манолополиса для
вычисления матрицы плотности сверхбольших молекул. // Высокопроизводительные
параллельные вычисления на кластерных системах. Материалы 8-го междунар. науч.практич. семинара и всероссийской молодежной школы. Казань, НГГУ, 2008 г. -С. 347-349.
15. М.Б. Кузьминский, А.М. Чернецов. Измерения производительности GPU NVIDIA C2050
для HPC-приложений, //Электронная конференция “Информационно-вычислительные
технологии в науке” ИВТН-2011: http://ivtn.ru.
16. А.М. Чернецов. “Использование средств MATLAB для организации распределенной
обработки ”// Труды междунар. конф. «Информатизация инженерного образования» -М.:
Изд. МЭИ. 2012 г. -С. 127-130.
Подписано в печать
Зак.
Полиграфический центр НИУ МЭИ
Красноказарменная ул., д. 13
Тир. 100
П.л.
Документ
Категория
Технические науки
Просмотров
81
Размер файла
656 Кб
Теги
кандидатская
1/--страниц
Пожаловаться на содержимое документа