Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Чернецов Андрей Михайлович
Методы и программные средства организации эффективных вычислений для расчета электронной структуры больших молекулярных систем
Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Москва 2012
Работа выполнена в Национальном исследовательском университете МЭИ на кафедре Прикладной математики.
Научный консультант: кандидат технических наук, доцент, Шамаева Ольга Юрьевна
Официальные оппоненты: Топорков Виктор Васильевич доктор технических наук, профессор, заведующий кафедрой вычислительной техники Национального исследовательского университета МЭИ Попов Виктор Юрьевич доктор физико-математических наук, профессор, профессор кафедры математики Физического факультета МГУ им. М.В. Ломоносова
Ведущая организация: ФГБОУ ВПО Московский государственный технологический университет Станкин.
Защита состоится л8 июня 2012 г. в 18.00 в ауд. Г-306 на заседании диссертационного совета Д 212.157.01 при Национальном исследовательском университете МЭИ по адресу: 111250, Москва, Красноказарменная ул., д.17.
С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета МЭИ.
Отзывы в двух экземплярах, заверенные печатью организации, просьба отправлять по адресу: 111250, Москва, Красноказарменная ул., д.14, Ученый совет ФГБОУ ВПО НИУ МЭИ.
Автореферат разослан л___ мая 2012 г.
Ученый секретарь диссертационного совета Д 212.157.кандидат технических наук, доцент Фомина Марина Владимировна
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Характерной особенностью современного периода развития науки и техники является тенденция роста сложности, размерности решаемых задач, стимулирующая разработку методов, алгоритмов и программных средств, ориентированных на высокопроизводительные вычислительные архитектуры.
Одной из сложнейших задач современности является квантово-химическая задача расчёта электронной структуры больших органических молекул, которые насчитывают десятки тысяч взаимодействующих электронов и ядер. Результаты расчётов используются, например, в фармакологии при решении задачи конструирования лекарств, в нанотехнологиях, при создании высокотемпературных сверхпроводников и др.
Расчёт электронной структуры сводится к решению уравнения Шредингера, которое описывает пространственное движение всех частиц системы, перемещающихся в силовом поле. Так как положение каждой частицы описывается тремя декартовыми координатами, то возникает уравнение в частных производных второго порядка в трёхмерном пространстве, решаемое аналитически лишь для очень малого класса систем, состоящих из одного или двух атомов. Для молекулярных систем с большим числом атомов применяются трудоёмкие численные итерационные методы, которые могут быть реализованы только при использовании высокопроизводительных средств и параллельной обработки. Практическими результатами решения задачи расчёта электронной структуры являются взаимные расположения атомов в пространстве, создающих стабильные молекулы и относительные энергии этих молекул, а также временная зависимость между структурой молекул и их свойствами.
В общем случае размерность задачи расчёта молекулярной системы есть функция от числа атомов и размерности применяемого базиса в итерационном методе. Трудоёмкость задачи расчёта зависит от метода решения, размерности молекулярной системы и формы расчёта - с фиксированной или измененяемой геометрией положения атомов.
В современных квантово-химических исследованиях допустимыми временами расчёта считаются величины порядка секунд и минут, в исключительных случаях - часов. Однако, расчёт больших молекул, содержащих более 104 атомов, классическими методами даже с использованием высокопроизводительных систем, составляет порядка нескольких десятилетий. По мнению специалистов компании Intel компьютер, способный проводить квантовохимические расчеты любой сложности за допустимое время, должен иметь производительность не менее 1021 FLOPS, и такая мощность будет достигнута не ранее 2030 года.
Таким образом, актуальными являются исследования, направленные на организацию эффективных расчётов электронной структуры больших молекул на существующих сегодня высокопроизводительных архитектурах.
Данная работа посвящена исследованию методов расчёта и созданию на их основе эффективных последовательных и параллельных схем вычислений, учитывающих особенности структур обрабатываемых данных, с последующей реализацией на высокопроизводительных системах, а также выводу характеристик трудоёмкости и эффективности разработанных алгоритмов, позволяющих оценить качество созданных программных средств.
Выполненные исследования опираются на результаты работ отечественных ученых В.А. Фока, В.В. Воеводина, А.А. Самарского, Вл.В. Воеводина, В.П. Гергеля, В.В. Корнеева, а также зарубежных ученых 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 для реализации параллельных модификаций алгоритмов.
На защиту выносятся:
1. параллельные алгоритмы расчётов на основе методов ГоедекераКоломбо и Пальцера-Манолополиса;
2. параллельная модификация метода Пальцера-Манолополиса для обработки разреженных структур данных;
3. методы хранения и преобразования разреженных структур данных;
4. теоретические оценки трудоёмкости разработанных алгоритмов;
5. результаты экспериментов, выполненных с помощью разработанных программных средств.
Достоверность научных результатов подтверждается соответствием теоретических выкладок и результатов экспериментов, а также сопоставлением полученных результатов с результатами, приведёнными в зарубежной научной литературе.
Научная новизна исследования состоит в следующем:
1. разработаны параллельные алгоритмы расчёта электронной структуры больших органических молекул для плотных матриц, сократившие время расчётов;
2. на основании исследования разреженных структур данных разработаны схемы хранения и метод обработки, позволившие значительно увеличить допустимую размерность решаемых задач, сократить время решения и требования к используемой памяти;
3. разработан алгоритм расчёта фокиана по методу АМ1 для разреженных структур матриц, исследования которого показали нецелесообразность его параллельной модификации в модели распределённой памяти;
4. выведены, исследованы и экспериментально подтверждены теоретические оценки ускорения и эффективности разработанных алгоритмов с целью определения допустимых размерностей задачи и требований к ресурсам аппаратных средств, а также позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах.
Практическая значимость полученных результатов заключается в разработке методов, алгоритмов и программных средств, которые сокращают время расчётов электронной структуры больших органических молекул.
Реализованные программные средства обладают большей эффективностью по сравнению с применяемыми ранее и позволяют значительно повысить допустимую размерность решаемой задачи. Разработанные методы и программные средства учитывают особенности современных высокопроизводительных архитектур, таких как вычислительные кластеры и графические процессоры.
Реализация результатов. Работа выполнялась в рамках грантов РФФИ 01-07-90072, 04-07-90220, 05-07-08031-офи-а, 11-07-00470, что подтверждено актом об использовании, выданном Институтом органической химии им. Н.Д. Зелинского РАН. Результаты работы внедрены в научноисследовательскую деятельность Вычислительного центра им. А.А. Дородницына РАН, что подтверждено актом о внедрении.
Апробация полученных результатов. Основные положения и результаты диссертации докладывались и обсуждались на международных научно-технических конференциях студентов и аспирантов УРадиоэлектроника, электротехника и энергетикаФ (г. Москва, 2005 г., 2007 г., 2008 г.), на международных научно-технических конференциях УИнформационные средства и технологииФ (г. Москва, 2004 - 2008 гг.), на международных научнопрактических семинарах УВысокопроизводительные параллельные вычисления на кластерных системахФ (г. Самара, 2004 г., г. Н.Новгород, 2005 г., г. Казань, 2008 г.), на третьей международной конференции Dependability of Computer Systems Depcos-RELCOMEX 2008 (Польша, 2008 г.), на электронной конференции УИнформационно-вычислительные технологии в наукеФ ИВТН2011, на международной конференции УИнформатизация инженерного образованияФ (г. Москва, 2012 г.).
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 16 печатных работах, включая статьи в изданиях из перечня ВАК и 1 монографию.
Структура и объем работы. Работа состоит из введения, 4 глав, заключения, списка использованной литературы, содержащего наименований, и приложений. Основной текст занимает 161 машинописных страницы, в том числе 32 рисунка и 15 таблиц. Полный объём диссертации (с приложениями) составляет 182 страницы.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, её научная новизна и практическая значимость, сформулирована цель работы и приведено краткое содержание диссертации по главам.
В первой главе рассматриваются физическая и математическая модели задачи расчёта электронной структуры молекул. Анализируются существующие методы расчёта электронной структуры, приводится их классификация, в том числе по вычислительной сложности и затратам оперативной памяти.
Методы расчёта электронной структуры молекул можно разбить на несколько больших классов - класс многоэлектронных методов, класс одноэлектронных методов и ряд других.
В одноэлектронных методах для определения состояния многоэлектронной системы, имеющей минимальный уровень полной энергии, используется концепция эффективного одноэлектронного гамильтониана 1, где v - оператор потенциальной энергии, - оператор Лапласа, r H 2 (r) - радиус-вектор. При этом возникает задача на собственные значения Hi ii, где i нумерует собственные значения и соответствующие собственные вектора.
Схема строгих методов расчёта, изображенная на рис. 1, основывается на методе Хартри-Фока, в котором в качестве эффективного одноэлектронного гамильтониана применяется оператор Фока. Эти схемы относятся к классу методов самосогласованного поля (ССП). Эффективные одноэлектронные гамильтонианы H в этих методах зависят от матрицы плотности Р. Сначала рассчитывается начальное приближение к матрице Р, затем из Р рассчитывается одноэлектронный гамильтониан H (фокиан F), для него решается задача на собственные значения, из собственных векторов рассчитывается новая матрица плотности Р, из неё строится новый гамильтониан (фокиан), затем процедура итерационно повторяется.
Рисунок 1 - Общая процедура расчётов методами ССП.
Рассмотренная схема расчётов является основой для построения полуэмпирических методов, в которых заметно упрощается расчёт фокиана в базисе атомных орбиталей (АО), а матрица плотности P определяется классическим способом - путем диагонализации. Обозначим N - размерность задачи. Для полуэмпирических методов N измеряется в атомных орбиталях.
В работе показано, что при формировании математической модели органической молекулы, в силу её физико-химических свойств возникают матричные разреженные структуры, использование свойств которых позволяет повысить скорость и эффективность расчётов.
В работе исследованы следующие полуэмпирические методы: метод Гоедекера-Коломбо (ГК) и Пальцера-Манолополиса (ПМ) как для плотных, так и для разреженных структур данных.
На примере метода ГК показано, что использование свойства разреженности структур данных для больших молекул приводит к оценке O(N) как трудоёмкости по времени, так и затратам памяти. На рис. 2 приведены основные расчётные формулы метода.
В методе ПМ, называемом также канонической очисткой (purification), итерационная формула для нахождения матрицы P выглядит следующим образом:
1 (1 2cn ) Pn (1 cn ) Pn2 Pn3,cn 1 cn tr(P2 P3 ) n n Pn1 ,cn ,(1) 1 1 tr(Pn Pn2 ) (1 cn ) P2 P3,cn n n cn где n - номер шага итерационного процесса. Процесс останавливается при достижении заданной точности по идемпотентности, т.е.
tr(P2) tr(P) tr(P) Таблица 1. Сравнительные характеристики методов расчёта.
Затраты Наличие Наличие Трудоём- Методы расчёта оперативной последовательной параллельной кость памяти реализации реализации Многоэлектронные Gaussian, Gaussian, строгие, O(N!) O(N5) и выше GAMESS-us GAMESS-us корреляционные Одноэлектронные O(N5) O(N4) и выше Gaussian Gaussian строгие, Одноэлектронные Gaussian, полуэмпирические O(N3) O(N3) PRMAT MOPAC 20диагонализации Одноэлектронные полуэмпирические Разработаны и Разработаны и прямые методы без O(N3) O(N3) реализованы в реализованы в учета разреженной данной работе данной работе структуры Одноэлектронные полуэмпирические mopac2009, Разработаны и прямые методы с O(N) O(N) MondoSCF, реализованы в учетом разреженной Gaussian данной работе структуры В табл. 1 приводятся основные характеристики рассмотренных и исследованных в работе методов расчёта электронной структуры молекул.
Указаны трудоёмкость, требования к ёмкости оперативной памяти, а также наличие программных реализаций. Выделяются разработанные в диссертации средства.
Из анализа методов расчёта следует, что для больших и сверхбольших молекул с точки зрения трудоёмкости наиболее эффективными полуэмпирическими методами расчёта электронной структуры являются прямые методы с учётом разреженности.
Во второй главе разрабатываются и исследуются последовательные и параллельные алгоритмы расчёта матрицы плотности на основе полуэмпирических прямых методов. Представлен, реализован и исследован последовательный алгоритм расчёта матрицы плотности по методу ГоедекераКоломбо, использующий матричные полиномы Чебышева.
На основе приведённого на рис. 2 алгоритма разработана и реализована последовательная программа расчёта матрицы P по методу ГК для ОС Linux на языке Фортран-90.
С целью эффективной реализации программы применяются: оптимальная (исходя из свойств матриц) форма хранения данных, оптимизация умножения матриц на основе специализированного пакета, реализующего стандарт BLAS (Basic Linear Algebra Subroutines).
Рисунок 2 - Схема основных этапов метода Гоедекера-Коломбо.
Переход к УтреугольнойФ форме хранения матрицы T резко снижает затраты памяти. В работе предложено за счет симметричности матрицы T по N(N 1) первым двум координатам преобразовать её в массив размерности, где p p - размерность полинома Чебышева.
Имеются различные способы улучшения производительности программного кода умножения матриц в рамках языков высокого уровня.
Оптимальным способом среди них является использование специализированных пакетов, реализующих стандартные базовые операции линейной алгебры BLAS. Применение подпрограммы DGEMM стандарта BLAS позволило повысить эффективность реализации последовательной программы.
Применение библиотеки ATLAS ускорило время матричного умножения в 3050 раз в зависимости от размера матриц для процессора Intel Pentium 4/2.6 ГГц.
В работе предложен и реализован параллельный алгоритм для метода ГК, ориентированный на модель передачи сообщений. В его основе - представление матрицы в блочной форме и возможность организации независимой обработки блоков. Обоснована целесообразность использования двух форм передачи данных при параллельной реализации: широковещательной рассылки и использования двухточечных обменов.
В работе на основе метода ПМ предложены как последовательный, так и параллельный алгоритмы расчёта. Параллельный алгоритм реализован для модели передачи сообщений на языке Фортран 90.
В третьей главе анализируется метод Пальцера-Манолополиса с точки зрения особенностей построения и реализации алгоритмов расчёта для разреженных форм представления и обработки матриц. Производятся оценки требований к памяти, трудоёмкости и эффективности.
Обрабатываемые матрицы в общем случае имеет разреженную форму сложного вида. В работе рассматривается частный случай блочно трёхдиагональных матриц, изображенных на рис. 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 A3 0... 0 B1 B3 0... 0 R1 R3 0... A2 A1 A3...... B2 B1 B3...... R2 R1 R3...... 0 A2 A1...... 0 B2 B1...... 0 R2 R1...... 0......... A3 0......... B3 0......... R3 0...... A2 A1 0...... B2 B1 0...... R2 R1 Рисунок 3 - Умножение блочно-трёхдиагональных матриц R=AB.
В работе предлагается специальная схема хранения блочнотрёхдиагональных матриц: матрицы A, B и R представляются в форме трёх мерных массивов. Факторизованные выражения для блоков матрицы результата имеют вид:
R1 A2 * B2 A1 * B1 A2 * Bi i1 i1 i i i i R2 A2 * B1 A1 * Bi i i i 1 iR3 A1 * B2 A2 * Bi i i i1 iЗдесь Аij - j Ця блочная матрица i-й диагонали исходной матрицы A, Bij - блочная матрица i-й диагонали исходной матрицы B, j - позиция блока в А (B).
Rij - j Цй блок результирующей матрицы.
Поскольку матрица фокиана F является симметричной, а блоки на главной диагонали являются квадратными, то экономится память на хранении массива блоков верхней наддиагонали, и после упрощений имеем:
T T R1 A2 * B2 A1 * B1 A2 * Bi i1 i1 i i i i R2 A2 * B1 A1 * Bi i i i1 i Факторизованные выражения для первых(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.
Тогда можно определить УэффектФ от использования разреженной формы хранения матрицы плотности:
q nbl [4u m nbl v] (1 q) nbl [4u 2 m nbl v] Sразр q [8u 5 mv] (1 q)[8u 10m v] В работе приводятся и анализируются графики полученного УэффектаФ в зависимости от разных характеристик разреженной матрицы.
Для анализа разработанных алгоритмов в работе исследуются оценки трудоёмкости для случая параллельной реализации рассмотренных выше методов на множестве вычислителей p и использования модели распределённой памяти.
В модели распределённой памяти необходимо учитывать время передач между вычислителями, поэтому введём функцию Fswap(x) - взаимная передача x байт от одного процесса к другому (выполнение двухточечного обмена).
Ускорение вычислений S( p) F( p,q, m, nbl,u,v, Fwsap) на p вычислителях можно оценить как:
q nbl m2 [4u m nbl v] (1 q) nbl m2 [8u 10 m v] S( p) 1 nbl m2 [8u 5 m v] (1 q) nbl m2 [8u 10 m v] 3u m2 p 3 Fswap(m2 8) p p p Рисунок 4 - Схема параллельного алгоритма расчёта матрицы плотности по методу ПМ для разреженного случая.
В работе приведены графики зависимости ускорения от числа процессоров для разных размерностей задачи расчёта при различных размерах блока m. На рис. 5 приведён график зависимости ускорения от числа процессоров p при использовании разреженности, числа блоков nbl=300, и для различных значений размерности УмелкогоФ блока m=100;150;200;250.
Из анализа графиков в работе следуют выводы:
для любой размерности исходной задачи существует целесообразный диапазон изменения числа используемых процессоров p, в рамках которого возможно достижение максимального ускорения;
чем больше размерность исходной задачи, тем шире диапазон изменения p и тем дальше он сдвигается в сторону больших значений p;
при увеличении размерности блока и фиксированной исходной размерности задачи ускорение растёт до определенного предела, а затем начинает снижаться. При этом происходит рост числа ненулевых элементов матрицы 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.
Следовательно, требуется хранить не всю матрицу, а только нижний или верхний треугольник.
A A21 A 0 0 A 0 A42 0 A 0 0 0 A54 A B61 B62 0 0 0 C B71 B72 B73 0 0 C76 C77 0 0 0 B84 B85 0 C87 C88 Рисунок 6 - Разреженное представление фокиана.
В диссертации предложен параллельный алгоритм построения фокиана F по методу АМ1 в модели распределённой памяти, который реализован на языке Fortran 95 с использованием инструментальных средств MPI.
В четвёртой главе проведено исследование эффективности разработанных программных средств расчёта электронной структуры больших молекулярных систем с позиций: моделей вычислений, применяемых методов расчёта, множества специфических параметров метода, размера молекулярной системы, используемой структуры хранения (плотная/разреженная), множества характеристик аппаратной среды.
В табл. 2 для каждого разработанного алгоритма указаны аппаратнопрограммные средства реализации, а также размеры исходного кода соответствующих программ.
Таблица 2. Разработанные алгоритмы и аппаратно-программные средства их реализации.
Метод Разработанные Программные/аппаратные Размер кода алгоритмы средства программного продукта Гоедекера- Параллельный MPI, Коломбо (ГК) алгоритм для Кластер В - РАН 1190 строк, 32 кб плотных матриц Пальцера- Параллельный MPI, 1400 строк, 36 кб, Манолополиса алгоритм для Кластер В - РАН, 604 строки, 20 кб (ПМ) плотных матриц MATLAB Модификация Параллельный MPI, метода алгоритм для Кластер В - РАН, 2628 строк, 48 кб Пальцера- разреженных МВС-6000, Манолополиса матриц Кластер НИУ МЭИ АМ1 для Последовательный MPI, Последовательная разреженных и параллельный Кластер В - РАН программа 350 кб матриц алгоритмы Параллельная программа 380 кб Пальцера- Параллельный CUDA, GPU Манолополиса алгоритм для 1993 строки, разреженных кб матриц В работе приведён краткий обзор существующих моделей параллельного программирования, и дано обоснование использования модели распределенной памяти, гибридных моделей, средств графических процессоров и математических пакетов.
Для контроля точности полученных в результате экспериментов решений выполнен альтернативный расчёт некоторых молекул с помощью метода диагонализации матрицы фокиана.
В работе проведено исследование зависимости скорости сходимости метода Гоедекера-Коломбо (числа итераций) к окончательному (истинному с заданной степенью точности 10-2) решению в зависимости от входных параметров - обратной температуры и порядка полинома Чебышева p. Для этого проведен ряд экспериментов с различными исходными данными.
В результате показано, что:
применение полиномов Чебышева не ниже 9 порядка в методе ГК позволяет рассчитать электронную структуру молекулы в 1.5 раза быстрее, чем методом матричной диагонализации;
параметр метода для исследуемых молекул не влияет на скорость сходимости к решению.
В главе приводятся и анализируются результаты различных экспериментов по расчёту электронной структуры молекул с помощью последовательных и параллельных алгоритмов, выполненных на различных программно-аппаратных кластерных системах.
Последовательная программа расчёта разреженного фокиана использовалась для нахождения F молекулы одномерного полиглицина размерности около 56000 атомов.
В работе при создании параллельных алгоритмов используется методика крупнозернистого распараллеливания, которая наиболее адекватно реализуется в модели вычислений с распределённой памятью. Однако, при тестировании параллельной программы для расчета разреженного фокиана по методу АМдля молекулы полиглицина из 56000 атомов на кластере В - РАН получены низкие значения ускорения: 1,33 для 2 процессоров и 1,22 для 3-х процессоров, что свидетельствует о нецелесообразности распараллеливания процесса построения фокиана в выбранной модели. Эффективнее использовать системы с общей памятью, где возможно минимизировать временные задержки, связанные с передачей данных.
На рис. 7 представлены достигнутые ускорения при расчётах модельного фокиана молекулы полипептида размера около 4500 АО для плотных матриц по методу ГК. Значения ускорения, полученные с помощью разработанной параллельной программы не хуже, чем в коммерческом пакете MOPAC2002 для молекулы фуллерена похожей размерности. Использование двухточечных обменов является более эффективной схемой, чем широковещательная рассылка.
Рисунок 7 - Графики ускорений параллельной программы по методу ГК для разных схем обменов в зависимости от числа процессоров.
На рис. 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.3 2.91 / 2.44 / 2.97 97.0 /81.27/ 99.4 3.76 / 3.14 /3.88 94.0 / 78.45/ 97.5 4.58 / 3.74 / 4.91 91.6 / 74.6/ 98.6 5.29 / 4.02 / 5.73 88.17 / 67.05/95.7 5.72 / 4.52 / 6.50 81.7 / 64.59/92.8 6.36 / 5.16 / 6.93 79.5 /64.46/86.12 -/ 6.34 / 10.27 / 52.79/85.16 -/ 7.17 /- / 44.83/ 24 -/8.03 /- /33.46/ 28 -/9.38 /- /33.5/ 30 /5.31 /- /17.7/ Рисунок 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). При увеличении размерности блока превосходство становится существенно больше.
Для молекулы полиглицина размерности около 2900 АО реализация параллельной программы расчёта по методу ПМ с применением GPU показала в 2 раза лучшие результаты, чем реализация той же программы на всех используемых 8 ядрах (2*Xeon 5520).
Рисунок 11 - График производительности GPU для матричного умножения в зависимости от размерности.
В работе также исследовался математический пакет MATLAB с точки зрения создания методики разработки параллельных программ для выполнения научных расчётов. Основные постулаты в порядке сложности применения следующие:
активизация встроенных в ядро средств пакета для распараллеливания;
указание использования средств GPU, совместимого с требованиями пакета (при его наличии);
выявление в задаче независимо выполняющихся подзадач.
Использование средств пакетного запуска batch и spmd;
в случае полного отсутствия взаимодействия между подзадачами использование parfor;
в случае взаимодействия между подзадачами организация обменов с использованием функций двухточечных и коллективных обменов;
с целью отладки параллельных алгоритмов использование средств режима pmode.
В заключении приведены основные результаты диссертационной работы и сделаны общие выводы.
В Приложения вынесены вспомогательные обзорные материалы, приведены копии актов о внедрении и использовании результатов диссертации.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Исследована физико-математическая модель задачи расчёта электронной структуры больших и сверхбольших молекулярных систем и основные методы её решения. На основе анализа трудоёмкости методов и их требований к затратам памяти, а также структур обрабатываемых данных сделан вывод, что для повышения эффективности расчётов целесообразно использовать полуэмпирические методы расчёта с учётом разреженности структур данных.
2. Реализована последовательная программа расчётов для плотных матриц по методу Гоедекера-Коломбо на языке Фортран-90 в среде Linux.
3. Разработан параллельный алгоритм расчёта матрицы плотности по методу Гоедекера-Коломбо, реализована и экспериментально исследована соответствующая параллельная MPI-программа.
4. Разработан параллельный алгоритм расчёта для плотных матриц по методу Пальцера-Манолополиса, который реализован в рамках модели MPI и двух способов обмена - широковещательной рассылки и двухточечных обменов.
5. Разработаны схемы хранения и предложены методы обработки разреженных структур на примере блочно-трёхдиагональных матриц, позволившие значительно сократить время расчётов P и увеличить размерность решаемых задач.
6. Разработаны последовательный и параллельный алгоритмы на основе метода Пальцера-Манолополиса для случая матриц с блочно- трёхдиагональным портретом.
7. Исследованы оценки трудоёмкости разработанных алгоритмов, позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах, которые соответствуют проведённым экспериментам.
8. Разработана схема хранения для разреженного фокиана и предложен последовательный алгоритм расчёта по методу АМ1, позволивший рассчитать фокиан молекулы, содержащей более 5104 атомов.
9. Разработана параллельная модификация расчёта фокиана методом АМ1 для разреженных матриц и выполнена её реализация, показавшая неэффективность использования для данного расчёта модели распределённой памяти.
10. Разработана методика создания параллельных программ для выполнения научных расчётов в среде математического пакета MATLAB, которая была применена для реализации программы по методу Пальцера-Манолополиса.
11. Разработан, реализован и исследован параллельный алгоритм по методу Пальцера-Манолополиса для NVIDIA GPU (CUDA), показавший существенное увеличение производительности расчётов по сравнению с использованием многоядерных процессоров в кластере за счёт только эффективного выполнения блочного матричного умножения.
СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ 1. А.М. Чернецов, О.Ю. Шамаева. О параллельной реализации алгоритмов расчета электронной структуры больших молекул // Вестник МЭИ. -2009. - №3.- С. 67-71.
2. А.М. Чернецов, О.Ю. Шамаева. Эффективные вычисления для расчета электронной структуры больших молекул. // Программные продукты и системы. - 2012. -№ 2. -С. 84-88.
3. Н.Н. Оленев, Р.В. Печенкин, А.М. Чернецов. Параллельное программирование в MATLAB и его приложения, М., Издательство В - РАН, 2007.- 120 с.
4. М.Б. Кузьминский, В.В. Бобриков, А.М. Чернецов, О.Ю. Шамаева. Распараллеливание в кластере полуэмпирических квантово-химических методов при прямом вычислении матрицы плотности для больших молекулярных систем // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы 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 C20для HPC-приложений, //Электронная конференция УИнформационно-вычислительные технологии в наукеФ ИВТН-2011:
16. А.М. Чернецов. УИспользование средств MATLAB для организации распределенной обработки Ф// Труды междунар. конф. Информатизация инженерного образования -М.:
Изд. МЭИ. 2012 г. -С. 127-130.
Подписано в печать Зак. Тир. 100 П.л.
Полиграфический центр НИУ МЭИ Красноказарменная ул., д.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям