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

На правах рукописи 0

Чернецов Андрей Михайлович

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

Специальность: 05.13.11 - Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 7 МАЙ Ш

Москва 2012

005044513

005044513

Работа выполнена в Национальном исследовательском университете «МЭИ» на кафедре Прикладной математики.

Научный руководитель: кандидат технических наук, доцент,

Шамаева Ольга Юрьевна

Официальные оппоненты: Топорков Виктор Васильевич

доктор технических наук, профессор,

заведующий кафедрой вычислительной технию

Национального исследовательского университета «МЭИ»

Попов Виктор Юрьевич

доктор физико-математических наук, профессор, профессор кафедры математики Физического факультета МГУ им. М.В. Ломоносова

Ведущая организация: ФГБОУ ВПО Московский государственный

технологический университет «Станкин».

Защита состоится «8» июня 2012 г. в 18.00 в ауд. Г-3 0£ на заседании диссертационного совета Д 212.157.01 при Национальном исследовательском университете «МЭИ» по адресу: 111250, Москва, Красноказарменная ул., д. 17.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «МЭИ».

Отзывы в двух экземплярах, заверенные печатью организации, просьба отправлять по адресу: 111250, Москва, Красноказарменная ул., д. 14, Ученый совет ФГБОУ ВПО «НИУ «МЭИ».

Автореферат разослан « р » 2012 г.

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук, доцент

Фомина Марина Владимировна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Характерной особенностью современного периода развития науки и техники является тенденция роста сложности, размерности решаемых задач, стимулирующая разработку методов, алгоритмов и программных средств, ориентированных на высокопроизводительные вычислительные архитектуры.

Одной из сложнейших задач современности является квантово-химическая задача расчёта электронной структуры больших органических молекул, которые насчитывают десятки тысяч взаимодействующих электронов и ядер. Результаты расчётов используются, например, в фармакологии при решении задачи конструирования лекарств, в нанотехнологиях, при создании высокотемпературных сверхпроводников и др.

Расчёт электронной структуры сводится к решению уравнения Шредингера, которое описывает пространственное движение всех частиц системы, перемещающихся в силовом поле. Так как положение каждой частицы описывается тремя декартовыми координатами, то возникает уравнение в частных производных второго порядка в трёхмерном пространстве, решаемое аналитически лишь для очень малого класса систем, состоящих из одного или двух атомов. Для молекулярных систем с бо'льшим числом атомов применяются трудоёмкие численные итерационные методы, которые могут быть реализованы только при использовании высокопроизводительных средств и параллельной обработки. Практическими результатами решения задачи расчёта электронной структуры являются взаимные расположения атомов в пространстве, создающих стабильные молекулы и относительные энергии этих молекул, а также временная зависимость между структурой молекул и их свойствами.

В общем случае размерность задачи расчёта молекулярной системы есть функция от числа атомов и размерности применяемого базиса в итерационном методе. Трудоёмкость задачи расчёта зависит от метода решения, размерности молекулярной системы и формы расчёта - с фиксированной или измененяемой геометрией положения атомов.

В современных квантово-химических исследованиях допустимыми временами расчёта считаются величины порядка секунд и минут, в исключительных случаях - часов. Однако, расчёт больших молекул, содержащих более 104 атомов, классическими методами даже с использованием высокопроизводительных систем, составляет порядка нескольких десятилетий. По мнению специалистов компании Intel компьютер, способный проводить квантовохимические расчеты любой сложности за допустимое время, должен иметь производительность не менее 1021 FLOPS, и такая мощность будет достигнута не ранее 2030 года.

Таким образом, актуальными являются исследования, направленные на организацию эффективных расчётов электронной структуры больших молекул на существующих сегодня высокопроизводительных архитектурах.

Данная работа посвящена исследованию методов расчёта и созданию на их основе эффективных последовательных и параллельных схем вычислений, учитывающих особенности структур обрабатываемых данных, с последующей реализацией на высокопроизводительных системах, а также выводу характеристик трудоёмкости и эффективности разработанных алгоритмов, позволяющих оценить качество созданных программных средств.

Выполненные исследования опираются на результаты работ отечественных ученых В.А. Фока, В.В. Воеводина, A.A. Самарского, Вл.В. Воеводина, В.П.Гергеля, В.В. Корнеева, а также зарубежных ученых 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. реализация эффективной последовательной программы прямого расчёта матрицы плотности Р по методам Гоедекера-Коломбо и Пальцера-Манолополиса в среде ОС Linux;

3. разработка алгоритма расчёта фокиана по методу Austin Model/1 (AMI) для разреженных матриц и обоснование целесообразности его параллельной модификации;

4. разработка параллельно-последовательных алгоритмов расчёта для плотных и разреженных структур данных и создание на их основе комплекса параллельных программ;

5. анализ теоретических оценок ускорения для разработанных алгоритмов и программ;

6. исследование эффективности разработанных программных средств.

Методы исследования. Поставленные задачи решаются с использованием методов вычислительной математики, параллельного программирования, теории вычислительной сложности алгоритмов. При разработке программного обеспечения использовались: методы нисходящего проектирования, методика крупнозернистого распараллеливания, модель передачи сообщений, модель потокового параллелизма графических процессоров CUDA, модель параллельного программирования в пакете MATLAB для реализации параллельных модификаций алгоритмов.

На защиту выносятся:

1. параллельные алгоритмы расчётов на основе методов Гоедекера-Коломбо и Пальцера-Манолополиса;

2. параллельная модификация метода Пальцера-Манолополиса для обработки разреженных структур данных;

3. методы хранения и преобразования разреженных структур данных;

4. теоретические оценки трудоёмкости разработанных алгоритмов;

5. результаты экспериментов, выполненных с помощью разработанных программных средств.

Достоверность научных результатов подтверждается соответствием теоретических выкладок и результатов экспериментов, а также сопоставлением полученных результатов с результатами, приведёнными в зарубежной научной литературе.

Научная новизна исследования состоит в следующем:

1. разработаны параллельные алгоритмы расчёта электронной структуры больших органических молекул для плотных матриц, сократившие время расчётов;

2. на основании исследования разреженных структур данных разработаны схемы хранения и метод обработки, позволившие значительно увеличить допустимую размерность решаемых задач, сократить время решения и требования к используемой памяти;

3. разработан алгоритм расчёта фокиана по методу AMI для разреженных структур матриц, исследования которого показали нецелесообразность его параллельной модификации в модели распределённой памяти;

4. выведены, исследованы и экспериментально подтверждены теоретические оценки ускорения и эффективности разработанных алгоритмов с целью определения допустимых размерностей задачи и требований к ресурсам аппаратных средств, а также позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах.

Практическая значимость полученных результатов заключается в разработке методов, алгоритмов и программных средств, которые сокращают время расчётов электронной структуры больших органических молекул. Реализованные программные средства обладают большей эффективностью по сравнению с применяемыми ранее и позволяют значительно повысить допустимую размерность решаемой задачи. Разработанные методы и программные средства учитывают особенности современных высокопроизводительных архитектур, таких как вычислительные кластеры и графические процессоры.

Реализация результатов. Работа выполнялась в рамках грантов РФФИ 01-07-90072, 04-07-90220, 05-07-08031-офи-а, 11-07-00470, что подтверждено актом об использовании, выданном Институтом органической химии им. Н.Д. Зелинского РАН. Результаты работы внедрены в научно-исследовательскую деятельность Вычислительного центра

им. A.A. Дородницына РАН, что подтверждено актом о внедрении.

Апробация полученных результатов. Основные положения и результаты диссертации докладывались и обсуждались на международных научно-технических конференциях студентов и аспирантов "Радиоэлектроника, электротехника и энергетика" (г. Москва, 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 страницы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, её научная новизна и практическая значимость, сформулирована цель работы и приведено краткое содержание диссертации по главам.

В первой главе рассматриваются физическая и математическая модели задачи расчёта электронной структуры молекул. Анализируются существующие методы расчёта электронной структуры, приводится их классификация, в том числе по вычислительной сложности и затратам оперативной памяти.

Методы расчёта электронной структуры молекул можно разбить на несколько больших классов - класс многоэлектронных методов, класс одноэлектронных методов и ряд других.

В одноэлектронных методах для определения состояния

многоэлектронной системы, имеющей минимальный уровень полной энергии,

используется концепция эффективного одноэлектронного гамильтониана

п+у(г), где v- оператор потенциальной энергии, V- оператор Лапласа, г 2

- радиус-вектор. При этом возникает задача на собственные значения = е,ср,, где i нумерует собственные значения и соответствующие собственные вектора. Схема строгих методов расчёта, изображенная на рис. 1, основывается на методе Хартри-Фока, в котором в качестве эффективного одноэлектронного гамильтониана применяется оператор Фока. Эти схемы относятся к классу

методов самосогласованного поля (ССП). Эффективные одноэлектронные гамильтонианы Н в этих методах зависят от матрицы плотности Р. Сначала рассчитывается начальное приближение к матрице Р, затем ■ из Р рассчитывается одноэлектронный гамильтониан Н (фокиан Р), для него решается задача на собственные значения, из собственных векторов рассчитывается новая матрица плотности Р, из неё строится новый гамильтониан (фокиан), затем процедура итерационно повторяется.

Рисунок 1 - Общая процедура расчётов методами ССП.

Рассмотренная схема расчётов является основой для построения полуэмпирических методов, в которых заметно упрощается расчёт фокиана в базисе атомных орбиталей (АО), а матрица плотности Р определяется классическим способом - путем диагонализации. Обозначим N - размерность задачи. Для полуэмпирических методов N измеряется в атомных орбиталях.

В работе показано, что при формировании математической модели органической молекулы, в силу её физико-химических свойств возникают матричные разреженные структуры, использование свойств которых позволяет повысить скорость и эффективность расчётов.

В работе исследованы следующие полуэмпирические методы: метод Гоедекера-Коломбо (ГК) и Пальцера-Маиолополиса (ПМ) как для плотных, так и для разреженных структур данных.

На примере метода ГК показано, что использование свойства разреженности структур данных для больших молекул приводит к оценке 0(Ы) как трудоёмкости по времени, так и затратам памяти. На рис. 2 приведены основные расчётные формулы метода.

В методе ПМ, называемом также канонической очисткой (рип/юаНоп), итерационная формула для нахождения матрицы Р выглядит следующим образом:

/1-е/ ■ ■ 2 нр^-Р;) ...

и(а+с.)-л'-л'к>£ «л-и

где п - номер шага итерационного процесса. Процесс останавливается при достижении заданной точности по идемпотентности, т.е.

\нр7)-НР) V НР)

Таблица 1. Сравнительные характеристики методов расчёта.

Методы расч&га Трудоёмкость Затраты оперативной памяти Наличие последовательной реализации Наличие параллельной реализации

Многоэлектронные строгие, корреляционные 0(N!) 0(N5) и выше Gaussian, GAMESS-us Gaussian, GAMESS-us

Одноэлектронные строгие, 0(N5) 0(N4) и выше Gaussian Gaussian

Одноэлектронные полуэмпирические диагонализации 0(N3) 0(N3) Gaussian, MOPAC 2009 PRMAT

Одноэлектронные полуэмпирические прямые методы без учета разреженной структуры 0(N3) 0(N3) Разработаны и ' --реализованы в Разработаны и реализованы в' данной работе

Одноэлектронные полуэмпирические прямые методы с учетом разреженной структуры 0(N) 0(N) торас2009, MondoSCF, Gaussian Разработаны и реализоиаиы в данной работе ■

В табл. 1 приводятся основные характеристики рассмотренных и исследованных в работе методов расчёта электронной структуры молекул. Указаны трудоёмкость, требования к ёмкости оперативной памяти, а также наличие программных реализаций. Выделяются разработанные в диссертации средства.

Из анализа методов расчёта следует, что для больших и сверхбольших молекул с точки зрения трудоёмкости наиболее эффективными полуэмпирическими методами расчёта электронной структуры являются прямые методы с учётом разреженности.

Во второй главе разрабатываются и исследуются последовательные и параллельные алгоритмы расчёта матрицы плотности на основе полуэмпирических прямых методов. Представлен, реализован и исследован последовательный алгоритм расчёта матрицы плотности по методу Гоедекера-Коломбо, использующий матричные полиномы Чебышева.

На основе приведённого на рис. 2 алгоритма разработана и реализована последовательная программа расчёта матрицы Р по методу ГК для ОС Linux на языке Фортран-90.

С целью эффективной реализации программы применяются: оптимальная (исходя из свойств матриц) форма хранения данных, оптимизация умножения

матриц на основе специализированного пакета, реализующего стандарт BLAS (Basic Linear Algebra Subroutines).

Рисунок 2 - Схема основных этапов метода Гоедекера-Коломбо.

Переход к "треугольной" форме хранения матрицы Т резко снижает затраты памяти. В работе предложено за счет симметричности матрицы Т по первым двум координатам преобразовать её в массив размерности где

р - размерность полинома Чебьппева,

Имеются различные способы улучшения производительности программного кода умножения матриц в рамках языков высокого уровня. Оптимальным способом среди них является использование специализированных пакетов, реализующих стандартные базовые операции линейной алгебры BLAS. Применение подпрограммы DGEMMстандарта BLAS позволило повысить эффективность реализации последовательной программы. Применение библиотеки ATLAS ускорило время матричного умножения в 3050 раз в зависимости от размера матриц для процессора Intel Pentium 4/2.6 ГТц.

В работе предложен и реализован параллельный алгоритм для метода ГК, ориентированный па модель передачи сообщений. В его основе - представление матрицы в блочной форме и возможность организации независимой обработки блоков. Обоснована целесообразность использования двух форм передачи данных при параллельной реализации: широковещательной рассылки и использования двухточечных обменов.

В работе на основе метода ПМ предложены как последовательный, так и параллельный алгоритмы расчёта. Параллельный алгоритм реализован для модели передачи сообщений на языке Фортран 90.

В третьей главе анализируется метод Пальцера-Манолополиса с точки зрения особенностей построения и реализации алгоритмов расчёта для разреженных форм представления и обработки матриц/Производятся оценки требований к памяти, трудоёмкости и эффективности.

Обрабатываемые матрицы в общем случае имеет разреженную форму сложного вида. В работе рассматривается частный случай блочно трёхдиагональных матриц, изображенных на рис. 3. Здесь L - число блоков главной диагонали, А1ь В1ь Rlb А2Ь B2j, R2;, A3i, В3„ R3; - матричные, в общем случае плотно заполненные, блоки; Ali (i=l,L)- матрицы блоков главной диагонали, А2; и A3j (i=l,L-l) - соответственно матрицы блоков нижней подциагонали и верхней наддиагонали. Количество блоков ограничено только доступными ресурсами памяти.

Для эффективной реализации метода ПМ в случае представления матрицы фокиана в форме блочно-трёхдиагонального вида необходимо организовать эффективное выполнение линейных операций с матрицами (сложение, умножение на число) и умножение матриц.

При умножении двух блочно-трёхдиагональных матриц А и В в матрице результата R помимо 3-х указанных диагоналей появляется 4-ая ненулевая блочная диагональ, значениями элементов которой можно пренебречь с точки зрения анализа (расчётов) электронной структуры молекул. Поэтому результирующая матрица R также представляется в форме блочно- трёхдиагональной матрицы:

AI A3 0 ... О

А2 AI A3 ......

0 AI А\ ......

0 ......... A3

0 ...... А2 AI

В\ ВЗ О

В2 В\ ВЗ ......

О В2 В1 ......

0 ......... ВЗ

о ...... В2 т

R\ R3 0

R2 R1 R3 ......

0 R2 Ä1 ......

0 ......... R3

О ...... R2 R\

Рисунок 3 - Умножение блочно-трёхдиагональных матриц 11=А-В.

В работе предлагается специальная схема хранения блочно-трёхдиагональных матриц: матрицы А, В и Я представляются в форме трёх мерных массивов. Факторизованные выражения для блоков матрицы результата имеют вид:

Äl, = A2lt* В2, Х + А\* В 1, + A2t * В2, _ • *В2

Ki]=A\*B2l+A2^BC

R2,=A2*B\, + AV

Здесь А^ - j -я блочная матрица 1-й диагонали исходной матрицы А, В^ -блочная матрица 1-й диагонали исходной матрицы В, ] - позиция блока в А (В). -) -й блок результирующей матрицы.

Поскольку матрица фокиана Е является симметричной, а блоки на главной диагонали являются квадратными, то экономится память на хранении массива блоков верхней наддиагонали, и после упрощений имеем:

Ж =А2п*В21]Т +А\, *В1,+А2,Т*В2, Л21=А2,*В1,+А1М*В2М

Факторизованные выражения для nepBbix(Rli и R2i) и последних (R1l и R2L-i) блоков получаются из общих формул.

На рис. 4 представлена схема разработанного параллельного алгоритма, эффективность которого зависит от варианта обмена блоками при рассылке блоков. Схема реализует множество распределенных расчётов, при этом в качестве начальных данных рассылаются только части матрицы F. Каждый процесс получает от главного блоки матриц, необходимые для расчётов, в конце работы происходит сбор всех результатов в главном процессе. Это позволяет в отдельно взятом процессе выполнять действия по умножению матриц только над теми блоками, которые назначены процессу.

Процесс вычислений повторяется итерационно до достижения заданной точности матрицы плотности. На каждой i-й итерации взаимодействие между различными процессами минимально: большая часть вычислений происходит независимо, а данные от других процессов требуются только для вычисления "пограничных" блоков. Более того, на каждой итерации возможно заранее сделать все необходимые пересылки данных и уже затем производить умножение блоков.

В работе выводятся и анализируются оценки трудоёмкости и требуемой оперативной памяти для методов очистки для плотных и разреженных матриц.

Рассмотрим итерационную формулу (I). Определим вероятности того, что коэффициент с„ < Vi или с„ > 1Л как Р{с„ < 'Л} =q, Р{с„ > 'Aj = l-q. Пусть и -время аддитивной операции, v - время мультипликативной операции, m -максимальная размерность "мелких" блоков m=max(m¡), пЫ = L.

Тогда можно определить "эффект" от использования разрежешюй формы хранения матрицы плотности:

^ _ q-nbl-[4-u + m-nbl-v] + (l-q)-nb!-[4-u + 2-m-nbl-v]

В работе приводятся и анализируются графики полученного "эффекта" в зависимости от разных характеристик разреженной матрицы.

Для анализа разработанных алгоритмов в работе исследуются оценки трудоёмкости для случая параллельной реализации рассмотренных выше методов на множестве вычислителей р и использования модели распределённой памяти.

В модели распределённой памяти необходимо учитывать время передач между вычислителями, поэтому введём функцию Fswap(x) - взаимная передача х байт от одного процесса к другому (выполнение двухточечного обмена).

Ускорение вычислений S(p) = F(p,q,m,nbl,u,v,Fwsap) на р вычислителях можно оценить как:

__д-пЫ-т'-14-и + т-пЫ-у] + (\-д)-пЫ-т'-[&и + 10-ту]_

— ni/-m!-[8-a + 5-m-v] + — (1-д)-пЫ-т'■[S-u + W-m-v]+'¡-u-m2 ■ p+i-Fswap(m2-S)-р

Р Р

ПМ для разреженного случая.

В работе приведены графики зависимости ускорения от числа процессоров для разных размерностей задачи расчёта при различных размерах блока т. На рис. 5 приведён график зависимости ускорения от числа процессоров р при использовании разреженности, числа блоков пЫ=300, и для различных значений размерности "мелкого" блока ш=100; 150;200;250.

Из анализа графиков в работе следуют выводы:

• для любой размерности исходной задачи существует целесообразный диапазон изменения числа используемых процессоров р, в рамках которого возможно достижение максимального ускорения;

• чем больше размерность исходной задачи, тем шире диапазон изменения р и тем дальше он сдвигается в сторону больших значений р;

• при увеличении размерности блока и фиксированной исходной размерности задачи ускорение растёт до определенного предела, а затем начинает снижаться. При этом происходит рост числа ненулевых элементов матрицы Р.

. ------------- 1 • х

г——

— • •• • -m-100 •■■■m-iJO — m-200

------ Vs ■ .......-.....

------ у/Г

/.....- ; ¡-

ю it зо

Р

Рисунок 5 - Оценка зависимости ускорения от числа процессоров.

Выведенная теоретическая оценка трудоёмкости метода ПМ позволяет для каждой заданной размерности задачи определить требуемое число процессоров р и возможное ускорение S(p).

Предложенные и реализованные параллельные алгоритмы расчёта матрицы плотности Р позволяют существенно сократить общее время расчёта электронной структуры больших молекул. В этих алгоритмах фокиан F является входным параметром и вопрос его эффективного расчёта не рассматривался.

Следующим уровнем оптимизации общей процедуры расчётов (см. рис. 1), является разработка эффективной процедуры построения фокиана F.

Процедура построения F исследуется с точек зрения учета разреженности и параллельной модификации. Для этого разрабатываются последовательные алгоритмы расчёта для разреженной структуры матрицы фокиана F по методу AMI, а именно: получение значения произвольного элемента, расчёт двухэлектронных вкладов в фокиан, расчёт фокиана. Анализируются используемые структуры данных.

На основе применения "по-атомного" подхода возможно разреженное представление фокиана. Например, для молекулы метана структура фокиана может иметь вид, представленный на рис. 6. Матрицы плотности Р и фокиана F являются блочными, симметричными, поэтому их можно хранить по блокам, выделяя для хранения 3 "крупных" блока А, В и С, где Aye А, В^еВ, Суе С -блоки 3-х типов размерности dim Ад =1x1, dim By=4xl, dim Qj=4x4, Следовательно, требуется хранить не всю матрицу, а только нижний или верхний треугольник.

(Ч

A, An

0 0

0 0 A*

0 0 0 A, Аь

К 0 0 0 Cl6

Вп "n 0 0

^ о о о ви вк о с„ с, J Рисунок 6 - Разреженное представление фокиана.

В диссертации предложен параллельный алгоритм построения фокиана F по методу AMI в модели распределённой памяти, который реализован на языке Fortran 95 с использованием инструментальных средств MPI.

В четвёртой главе проведено исследование эффективности разработанных программных средств расчёта электронной структуры больших молекулярных систем с позиций: моделей вычислений, применяемых методов расчёта, множества специфических параметров метода, размера молекулярной системы, используемой структуры хранения (плотная/разреженная), множества характеристик аппаратной среды.

В табл.2 для каждого разработанного алгоритма указаны аппаратно-программные средства реализации, а также размеры исходного кода соответствующих программ.

Таблица 2. Разработанные алгоритмы и аппаратно-программные средства их реализации.

Метод Разработанные алгоритмы Программные/аппаратные средства Размер кода программного продукта

Гоедекера-Коломбо (ГК) Параллельный алгоритм для плотных матриц MPI, Кластер ВЦ РАН 1190 строк, 32 кб

Пальцера- Манолополиса (ПМ) Параллельный алгоритм для плотных матриц MPI, Кластер ВЦ РАН, MATLAB 1400 строк, 36 кб, 604 строки, 20 кб

Модификация метода Пальцера-Манолополиса Параллельный алгоритм для разреженных матриц MPI, Кластер ВЦ РАН, МВС-6000, Кластер НИУ МЭИ 2628 строк, 48 кб

AMI для разреженных матриц Последовательный и параллельный алгоритмы MPI, Кластер ВЦ РАН Последовательная программа 350 кб Параллельная программа 380 кб

Пальцера-Манолополиса Параллельный алгоритм для разреженных матриц США, GPU 1993 строки, 44 кб

В работе приведён краткий обзор существующих моделей параллельного программирования, и дано обоснование использования модели распределенной памяти, гибридных моделей, средств графических процессоров и математических пакетов.

Для контроля точности полученных в результате экспериментов решений выполнен альтернативный расчёт некоторых молекул с помощью метода диагонализации матрицы фокиана.

В работе проведено исследование зависимости скорости сходимости метода Гоедекера-Коломбо (числа итераций) к окончательному (истинному с заданной степенью точности 10"2) решению в зависимости от входных параметров - обратной температуры р и порядка полинома Чебышева р. Для этого проведен ряд экспериментов с различными исходными данными.

В результате показано, что:

• применение полиномов Чебышева не ниже 9 порядка в методе ГК позволяет рассчитать электронную структуру молекулы в 1.5 раза быстрее, чем методом матричной диагонализации;

• параметр метода р для исследуемых молекул не влияет на скорость сходимости к решению.

В главе приводятся и анализируются результаты различных экспериментов по расчёту электронной структуры молекул с помощью последовательных и параллельных алгоритмов, выполненных на различных программно-аппаратных кластерных системах.

Последовательная программа расчёта разреженного фокиана использовалась для нахождения F молекулы одномерного полиглицина размерности около 56000 атомов,

В работе при создании параллельных алгоритмов используется методика крупнозернистого распараллеливания, которая наиболее адекватно реализуется в модели вычислений с распределённой памятью. Однако, при тестировании параллельной программы для расчета разреженного фокиана по методу AMI для молекулы полиглицина из 56000 атомов на кластере ВЦ РАН получены низкие значения ускорения: 1,33 для 2 процессоров и 1,22 для 3-х процессоров, что свидетельствует о нецелесообразности распараллеливания процесса построения фокиана в выбранной модели. Эффективнее использовать системы с общей памятью, где возможно минимизировать временные задержки, связанные с передачей данных.

На рис. 7 представлены достигнутые ускорения при расчётах модельного фокиана молекулы полипептида размера около 4500 АО для плотных матриц по методу ГК. Значения ускорения, полученные с помощью разработанной параллельной программы не хуже, чем в коммерческом пакете МОРАС2002 для молекулы фуллерена похожей размерности. Использование двухточечных обменов является более эффективной схемой, чем широковещательная рассылка.

Рисунок 7 - Графики ускорений параллельной программы по методу ГК для разных схем обменов в зависимости от числа процессоров.

На рис. 8 приводятся результаты экспериментов параллельных программ, выполненных для модельных фокианов молекул полипептида для плотных матриц по методу ПМ.

Рисунок 8 - Графики ускорения в зависимости от числа процессоров для

параллельной программы по методу ПМ. В табл. 3 и на рис. 9 и 10 представлены результаты экспериментов, проведенных на модельном фокиане молекулы полипептида размерности около 75000 АО, с помощью параллельной программы для разреженных матриц по методу ПМ. Расчёты проводились на кластерных системах ВЦ РАН (Xeon 2.6, Myrinet 2000), НИУ "МЭИ" (Opteron 2.2, Infiniband 10Х) и на суперкомпьютере МВС-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

S - 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/

- • - Itanium 2/1.6 -Xeon/2.6

: \

---f—п I'.'-^f"' "T V"

> - Л ——

/ / / i ✓ —1-------- \

// //' i 1

tt ' // — if----

........- MVH.V TVTf ГТ*~Г ... . -

з ю и ¡о 25 за

Рисунок 9. Зависимость ускорения от числа процессоров для разреженного метода ПМ. Расчёты на кластере ВЦ РАН и МВС-6000.

Как видно из рис. 10, теоретические оценки ускорения, полученные в главе 3, достаточно точно соответствуют экспериментальным данным.

Для молекулы полиглицина размерности около 2900 АО в работе произведено тестирование параллельной программы расчёта по методу ПМ для случая разреженных матриц при автоматическом распараллеливании с использованием ОрепМР-распараллеленных версий матричного умножения DGEMM. На кластере ВЦ РАН достигнутое ускорение на 2 процессорах составляет 2.0, на 4 процессорах -3.6, на 5 процессорах - 4.4.

В работе также проведено исследование ещё одного способа ускорения вычислений - использование потокового параллелизма графических процессоров для повышения эффективности блочного матричного умножения.

Сравнение производительности матричного умножения ядра CPU (Xeon 5520) и GPU (Tesla С2050) представлено на рис. 11. Уже для размерности блока т>256 применение GPU (применяется библиотека CUBLAS) даёт больший эффект, чем распараллеленный на все 4 ядра процессора DGEMM (применяется библиотека MKL). При увеличении размерности блока превосходство становится существенно больше.

Для молекулы полиглицина размерности около 2900 АО реализация параллельной программы расчёта по методу ПМ с применением GPU показала в 2 раза лучшие результаты, чем реализация той же программы на всех

Рисунок 11 - График производительности GPU для матричного умножения в зависимости от размерности. В работе также исследовался математический пакет MATLAB с точки зрения создания методики разработки параллельных программ для выполнения научных расчётов. Основные постулаты в порядке сложности применения следующие:

• активизация встроенных в ядро средств пакета для распараллеливания;

• указание использования средств GPU, совместимого с требованиями пакета (при его наличии);

• выявление в задаче независимо выполняющихся подзадач. Использование средств пакетного запуска batch и spmd;

• в случае полного отсутствия взаимодействия между подзадачами использование parfor;

• в случае взаимодействия между подзадачами организация обменов i использованием функций двухточечных и коллективных обменов;

• с целью отладки параллельных алгоритмов использование средст] режима pmode.

В заключении приведены основные результаты диссертационной работ! и сделаны общие выводы.

В Приложения вынесены вспомогательные обзорные материалы приведены копии актов о внедрении и использовании результатов диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Исследована физико-математическая модель задачи расчёта электронно" структуры больших и сверхбольших молекулярных систем и основны методы её решения. На основе анализа трудоёмкости методов и и: требований к затратам памяти, а также структур обрабатываемых данны: сделан вывод, что для повышения эффективности расчётов целесообразна

использовать полуэмпирические методы расчёта с учётом разреженности структур данных.

2. Реализована последовательная программа расчётов для плотных матриц по методу Гоедекера-Коломбо на языке Фортран-90 в среде Linux.

3. Разработан параллельный алгоритм расчёта матрицы плотности по методу Гоедекера-Коломбо, реализована и экспериментально исследована соответствующая параллельная MPI-программа.

4. Разработан параллельный алгоритм расчёта для плотных матриц по методу Пальцера-Манолополиса, который реализован в рамках модели MPI и двух способов обмена - широковещательной рассылки и двухточечных обменов.

5. Разработаны схемы хранения и предложены методы обработки разреженных структур на примере блочно-трёхдиагональных матриц, позволившие значительно сократить время расчётов Р и увеличить размерность решаемых задач.

6. Разработаны последовательный и параллельный алгоритмы на основе метода Пальцера-Манолополиса для случая матриц с блочно-трёхдиагональным портретом.

7. Исследованы оценки трудоёмкости разработанных алгоритмов, позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах, которые соответствуют проведённым экспериментам.

8. Разработана схема хранения для разреженного фокиана и предложен последовательный алгоритм расчёта по методу AMI, позволивший рассчитать фокиан молекулы, содержащей более 5-104 атомов.

9. Разработана параллельная модификация расчёта фокиана методом AMI для разреженных матриц и выполнена её реализация, показавшая неэффективность использования для данного расчёта модели распределёшюй памяти.

10.Разработана методика создания параллельных программ для выполнения научных расчётов в среде математического пакета MATLAB, которая была применена для реализации программы по методу Пальцера-Манолополиса.

11. Разработан, реализован и исследован параллельный алгоритм по методу Пальцера-Манолополиса для NVIDIA GPU (CUDA), показавший существенное увеличение производительности расчётов по сравнению с использованием многоядерных процессоров в кластере за счёт только эффективного выполнения блочного матричного умножения.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. А.М. Чернецов, О.Ю. Шамаева. О параллельной реализации алгоритмов расчета электронной структуры больших молекул // Вест ник МЭИ. -2009. - №3. - С. 67-71.

2. А.М. Чернецов, О.Ю. Шамаева. Эффективные вычисления для расчета электронной структуры больших молекул // Программные продукты и системы. - 2012. 2, - С. 84-88.

3. H.H. Оленев, Р.В. Печенкин, A.M. Чернецов. Параллельное программирование в MATLAB и его приложения. М.: Издательство ВЦ РАН. -2007.-120 с.

4. М.Б. Кузьминский, В.В. Бобриков, А.М. Чернецов, О.Ю. Шамаева. Распараллеливание в кластере полуэмпирических квантово-химических методов при прямом вычислении матрицы плотности для больших молекулярных систем // Высокопроизводительные параллельные.

вычисления на кластерных системах. Материалы 4-го междунар. науч.-практич. семинара всероссийской молодежной школы. Самара, НГГУ, 2004 г. - С. 141-144.

5. В.В. Бобриков, A.M. Чернецов, О.Ю. Шамаева. Распараллеливание квантово-химичесю расчетов матрицы плотности с использованием полиномов Чебышева // Труды междуш науч.-техн. конф. "Информационные средства и технологии". М.: Япус-К, 2004 г. - Т.1. С. 219-222.

6. A.M. Чернецов. Применение сетевых технологий при распараллеливании задачи прямо расчета матрицы плотности в исследованиях электронной структуры молекул // Тез. дс междунар. науч.-техн. конф. студентов и аспирантов "Радиоэлектроника, электротехни и энергетика" в 3 т. М.: Изд. МЭИ, 2005 г. - Т.1 - С. 354-355.

7. А.М. Чернецов, О.Ю. Шамаева. Параллельная реализация метода Пальцер Манолополиса для вычисления матрицы плотности в задачах расчета электрон» структуры молекул // Труды междунар. науч.-техн. конф. "Информационные средства технологии". М.: Янус-К, 2005 г. - Т.2. - С. 67-70.

8. М.Б. Кузьминский, А.М.Чернецов, О.Ю. Шамаева. Практика использования в кластер аппаратного и программного обеспечения Infiniband от Mellanox. Распараллеливание задачах вычислительной химии // "Высокопроизводительные параллельные вычислен на кластерных системах. Материалы 5-го междунар. науч.- практач. семинара всероссийской молодежной школы". Н. Новгород: Изд. НГГУ, 2005 г. - С. 143-149.

9. A.M. Чернецов, О.Ю. Шамаева. Расчеты разреженной матрицы плотности метода очистки на кластерных системах // Труды междунар. науч.-техн. конф. "Информациоши средства и технологии". М.: Янус-К, 2006 г. - Т. 3. -С. 155-158.

10.А.М. Чернецов. Распараллеливание процесса сборки фокиана // Тез. док. междуш науч.-техн. конф. студентов и аспирантов "Радиоэлектроника, электротехника энергетика" в 3 т. - М.: Изд. МЭИ, 2007 г. -Т.1 -С. 379-380.

11. A.M. Чернецов, Р.В. Печенкин. Параллельное программирование в MATLAB // Тру; междунар. науч.-техн. конф. "Информационные средства и технологии" в 3 т. -М.: И: МЭИ. 2007 г.-Т. 3.-С. 105-109.

12. Andrey Chernetsov, Olga Shamayeva. Problems of Parallel Realization of Algorithms Electronic Structure of Large Molecules // Proceedings of International Conference Dependability of Computer Systems Depcos-RELCOMEX 2008 Szklarska Poreba, Poland, 2 28 June, pp. 324-331. //IEEE Computer Society.

13. A.M. Чернецов, О.Ю. Шамаева. Характеристики трудоемкости и вычислитель» эффективности прямых методов расчета электронной структуры больших молекул Труды междунар. науч.-техн. конф. "Информационные средства и технологии", М.: И: МЭИ, 2008 г. - Т.2 -С. 98-105.

14. A.M. Чернецов, О.Ю. Шамаева, М.Б. Кузьминский. Распараллеливание в кластер полуэмпирического кваптово-химического метода Пальцера-Манолополиса д вычисления матрицы плотности сверхбольших молекул // Высокопроизводительн: параллельные вычисления на кластерных системах. Материалы 8-го междунар. нау практич. семинара и всероссийской молодежной школы. Казань: НГГУ, 2008 г. -С. 347-34

15. М.Б. Кузьминский, A.M. Чернецов. Измерения производительности GPU NVIDIA С20 для НРС-приложений // Электронная конференция "Информационно-вычислительн: технологии в науке" ИВТН-2011: http://ivtn.ru.

16. A.M. Чернецов. Использование средств MATLAB для организации распределенн обработки // Труды междунар. конф. "Информатизация инженерного образования" -У Изд. МЭИ, 2012 г. - С. 127-130.

Подписано в нечать^Д^- /^ТЗак. Тир. 100 П.л.

Полиграфический центр НИУ МЭИ

Красноказарменная ул., д. 13

61 12-5/3808

Национальный исследовательский университет «МЭИ»

На правах рукописи

Чернецов Андрей Михайлович

/ ^

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

молекулярных систем

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: к.т.н. доц. Шамаева О.Ю.

Москва, 2012

Содержание

Список аббревиатур и сокращений.....................................................................4

Введение...............................................................................................................5

1. Анализ и исследование моделей и методов расчета электронной структуры больших молекулярных систем.........................................................................10

1.1. Физическая и математическая модели задачи...................................................10

1.2. Классификация методов расчета.........................................................................19

1.3. Строгие одноэлектронные методы расчета электронной структуры............21

1.4. Упрощенные полуэмпирические методы нулевого дифференциального перекрывания................................................................................................................25

1.5. Требования к компьютерным ресурсам. Процесс диагонализации симметричных матриц.................................................................................................36

1.6. Современные методы расчета, альтернативные диагонализации матриц....40

1.7. Выводы по главе 1.................................................................................................49

2. Разработка и исследование эффективных алгоритмов и программных средств для расчета матрицы плотности...........................................................51

2.1. Разработка и реализация последовательного алгоритма расчета матрицы плотности на основе матричных полиномов Чебышева.........................................51

2.2. Оптимизация последовательной программы....................................................55

2.2.1. Модификация структуры исходных данных.....................................56

2.2.2. Изменение способов хранения массивов...........................................57

2.2.3. Оптимизация процессов матричного умножения.............................60

Трудоемкость метода Гоедекера-Коломбо..................................................64

2.3. Параллельный алгоритм расчета матрицы плотности на основе матричных полиномов Чебышева..................................................................................................65

2.3.1. Использование блочного умножения матриц....................................65

2.3.2. Параллельная модификация алгоритма и спецификация параллельной программы.............................................................................67

2.4. Эффективные вычисления по методу очистки для матриц общего вида.....74

2.5. Выводы по главе 2.................................................................................................80

3. Организация эффективных вычислений для обработки данных разреженной структуры.......................................................................................................................82

3.1. Особенности реализации эффективных вычислений по методу пюрификации для разреженной формы матриц......................................................82

3.2. Оценка трудоемкости и эффективности для класса методов очистки..........89

3.2.1. Случай плотных матриц.....................................................................89

3.2.2. Случай разреженных матриц..............................................................90

3.3. Особенности расчета разреженной формы фокиана........................................97

3.3.1. Обоснование появления разреженности в структуре фокиана.........98

3.3.2. Последовательный алгоритм построения матрицы фокиана..........102

3.3.2. Алгоритм нахождения значений произвольных элементов матрицы фокиана.........................................................................................................106

3.3.4. Алгоритм расчета вкладов в фокиан.................................................108

3.3.5. Параллельная модификация алгоритма............................................110

3.4. Выводы по главе 3..............................................................................................113

4. Исследование разработанных программных средств расчета....................115

4.1. Постановка проблемы исследования...............................................................117

4.2. Технологии параллельного программирования для реализации разработанных алгоритмов......................................................................................119

MPIhPVM...................................................................................................120

4.2.2. Средства параллельного программирования в математическом пакете MATLAB..........................................................................................121

4.2.3. Использование средств GPU.............................................................123

4.2.4.Анализ стандартных программных средств параллельного матричного умножения...............................................................................123

4.3. Используемые аппаратные ресурсы и программное обеспечение..............126

4.4. Анализ результатов расчетов по последовательной и параллельной программам сборки разреженного фокиана по методу AMI.............................127

4.5. Исследование влияния параметров метода Гоедекера-Коломбо на точность решения.......................................................................................................................128

4.6. Анализ результатов расчетов для случая плотных матриц..........................130

4.6.1. Метод Гоедекера-Коломбо................................................................131

4.6.2. Метод Пальцера-Манолополиса.......................................................136

4.6.3. Влияние типа межсоединения...........................................................138

4.7. Анализ результатов расчетов для случая разреженных матриц..................140

4.8. Анализ результатов использования многонитевых средств реализаций BLAS для повышения эффективности вычислений.............................................145

4.9. Использование гибридной модели вычислений {MPI+OpenMP}, а также средств GPU, позволило достичь наилучших показателей эффективности разработанных средств при расчетах реальных молекулярных систем средней размерностиАнализ результатов использования реализаций BLAS на GPU для

повышения эффективности вычислений...............................................................147

4.10. Выводы по главе 4............................................................................................148

Заключение........................................................................................................151

Список используемых источников...................................................................154

Приложение 1. Нестандартные средства параллельного программирования.....162

П1.1. Средства параллельного программирования в графических процессорах

NVIDIA.......................................................................................................................162

П1.2. Средства параллельного программирования в пакете MATLAB............164

Приложение 2. Характеристики используемых в расчетах аппаратных и

программных средств...................................................................................................177

Приложение 3. Акты внедрения и использования..........................................181

Список аббревиатур и сокращений

1 .Англоязычные

BLAS Basic Linear Algebra System

MPI Message Passing Interface

MKL Math Kernel Library

SCF Self Consistent Field

PM Palser-Manolopoulos

AMI Austin Model 1

CPU Central Processor Unit

CPU Graphical Processor Unit

2. Русскоязычные

Метод ССП метод самосогласованного поля

Приближение НДП приближение нулевого дифференциального перекрывания

АО атомная орбиталь

МО молекулярная орбиталь

Л К А О линейная комбинация атомных орбиталей

Введение

Расчёты электронной структуры гигантских молекул являются одними из самых сложных в современной науке и требуют использования высокопроизводительных вычислительных средств, таких как супер ЭВМ и кластерные системы. Расчёты электронной структуры, в частности, биомолекул (белков, ДНК) и наночастиц, актуальны для ряда областей науки: химии, биохимии, физики конденсированного состояния вещества и др. В практическом плане эти расчёты важны для фармакологии, нанотехнологий, исследований явлений сверхпроводимости, разработки квантовых компьютеров. Перечисленные проблемы являются одними из самых сложных современных задач. Поэтому входят в список "Великого вызова" (Grand Challenge), сформированный национальным научным фондом США, и включающий наиболее значимые научные проблемы, стоящие перед человечеством, для решения которых требуются высокопроизводительные средства

Расчет электронной структуры сводится к решению уравнения Шредингера, которое описывает пространственное движение всех частиц системы, перемещающихся в силовом поле. Так как положение каждой частицы описывается тремя декартовыми координатами, то возникает уравнение в частных производных второго порядка в трёхмерном пространстве, решаемое аналитически лишь для очень малого класса систем, состоящих из одного или двух атомов. Для молекулярных систем с большим числом атомов применяются трудоемкие численные итерационные методы, которые могут быть реализованы только при использовании высокопроизводительных средств и параллельной обработки.

В современных квантово-химических исследованиях допустимыми временами расчета считаются величины порядка секунд и минут, в исключительных случаях - часов. Однако, расчет молекул, содержащих более 104 атомов, классическими методами даже с использованием

высокопроизводительных систем, составляет порядка нескольких десятилетий. По мнению специалистов компании Intel компьютер, способный

проводить квантовохимические расчеты любой сложности за допустимое

21

время, должен иметь производительность не менее 10 FLOPS, и такая мощность будет достигнута не ранее 2030 года.

Таким образом, актуальными являются исследования, направленные на организацию эффективных расчетов электронной структуры больших молекул на существующих сегодня высокопроизводительных архитектурах.

Для расчета электронной структуры больших молекулярных систем, которые могут содержать от тысячи до миллионов атомов, целесообразно применение полуэмпирических методов квантовой химии в так называемом приближении нулевого дифференциального перекрывания [1], в общем

о

случае имеющих асимптотическую сложность расчета 0(N), где N -размерность задачи, пропорциональная числу атомов. Центральным звеном при расчете таких молекулярных систем является решение симметричной задачи на собственные значения. Задача на собственные значения описывается как Ах = Ах, где А - матрица, X - собственное значение, соотвествующее вектору х. Для симметричных матриц это выражение может быть переписано в виде A = QAQT, где столбцы матрицы Q являются ортогональными собственными векторами А, а диагональная матрица Л содержит соответствующие им собственные значения.

Для расчета физико-химических свойств нужны не сами собственные вектора, а матрица плотности Р, являющаяся функцией от них. Недавно были разработаны численные методы прямого нахождения Р (без диагонализации матриц), которые для разреженных матриц имеют сложность расчета 0(N) [2-4].

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

Для большинства методов расчета электронной структуры разработаны соответствующие программы расчёта, в том числе дорогостоящие коммерческие. Однако эти программы либо не ориентированы на высокопроизводительные средства вычисления (не имеют параллельных версий, или плохо распараллеливаются), либо не могут рассчитывать молекулы больших размеров, требуя больших временных затрат и ресурсов памяти.

Целью данной работы является разработка комплекса алгоритмов и программ для высокопроизводительных архитектур, позволяющего повысить эффективность расчетов физико-химических свойств больших органических молекул. В его составе алгоритмы и программы расчета фокиана и матрицы плотности.

Для достижения поставленной цели в работе ставятся и решаются следующие основные задачи:

1. анализ и исследование существующих методов расчета электронной структуры больших молекулярных систем с целью выбора оптимального соотношения между трудоёмкостью и точностью;

2. разработка и исследование алгоритма расчета фокиана по методу AMI для разреженных матриц и обоснование возможности и целесообразности его параллельной модификации;

3. реализация эффективной последовательной программы прямого расчета матрицы плотности Р по методам Гоедекера-Коломбо и Пальцера-Манолополиса в среде ОС Linux;

4. разработка параллельно-последовательных алгоритмов расчета для плотных и разреженных структур данных и создание на их основе комплекса параллельных программ;

5. формирование теоретических оценок возможного достигаемого ускорения для разработанных алгоритмических средств.

6. исследование эффективности разработанных последовательных и

параллельных программных средств.

Научная новизна работы состоит в следующем:

1. разработаны параллельные алгоритмы расчета электронной структуры больших органических молекул для плотных матриц, сократившие время расчётов;

2. на основании исследования разреженных структур данных разработаны схемы хранения и метод обработки, позволившие значительно увеличить допустимую размерность решаемых задач, сократить время решения и требования к используемой памяти;

3. разработан алгоритм расчета фокиана по методу AMI для разреженных структур матриц, исследования которого показали нецелесообразность его параллельной модификации в модели распределенной памяти;

4. выведены, исследованы и экспериментально подтверждены теоретические оценки ускорения и эффективности разработанных алгоритмов с целью определения допустимых размерностей задачи и требований к ресурсам аппаратных средств, а также позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах.

Данная диссертационная работа состоит из введения, 4-х глав, заключения, 3-х приложений и списка литературы.

В первой главе рассматриваются физическая и математическая модели задачи расчета электронной структуры молекул. Анализируются существующие методы расчета электронной структуры. Приводятся базовые определения и понятия, дается классификация основных методов решения задачи расчета электронной структуры молекул и описывается современное состояние проблемы. Рассматриваются прямые методы расчета.

Во второй главе разрабатываются и исследуются последовательные и параллельные алгоритмы расчёта матрицы плотности на основе полуэмпирических прямых методов.

Представлен, реализован и исследован последовательный алгоритм расчёта матрицы плотности по методу Гоедекера-Коломбо, использующий матричные полиномы Чебышева. Также разрабатывается и реализуется параллельный алгоритм на основе модификации метода пюрификации (метода Пальцера-Манолополиса) без учета специфики портрета матрицы плотности.

В третьей главе на основе анализа специфики портрета матрицы плотности предлагаются схема хранения и метод обработки данных, которые положены в основу модификации метода Пальцера-Манолополиса.

Выполняется оценка трудоемкости и эффективности для класса методов очистки. Исследуются алгоритмы расчета разреженного фокиана по методу AMI и разрабатываются соответствующие параллельные модификации.

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

В приложении 1 приводится описание средств параллельного программирования в модели CUDA и математическом пакете MATLAB.

В приложении 2 приводятся характеристики различных вычислительных систем, используемых в экспериментах при расчетах электронной структуры молекул.

В приложении 3 представлены копии актов внедрения и использования результатов диссертации.

1. Анализ и исследование моделей и методов расчета электронной структуры больших молекулярных систем

В данной главе рассматриваются физическая и математическая модели задачи расчета электронной структуры молекул. Анализируются существующие методы расчета электронной структуры, приводится их классификация. Выделяются строгие и полуэмпирические методы расчета, сложность которых соответственно 0(1Ч5) и 0(>Г), где N - размерность задачи, а также недавно разработанные современные схемы полуэмпирических методов расчета, имеющие для класса разреженных матриц сложность 0(]Ч).

1.1.Физическая и математическая модели задачи

Планетарная модель атома была предложена Резерфордом в 1911 г. Согласно этой модели, представленной на рис. 1.1, в центре атома располагается положительно заряженное ядро, в котором сосредоточена почти вся масса атома. Атом в целом нейтрален. Вокруг ядра, подобно планетам, под действием кулоновских сил со стороны ядра вращаются электроны. Находиться в состоянии покоя электроны не могут.

и--Ю"10 м—ч

I

1 15

—н I---10 м

I I

и I

[

I I . \

ч

! ^

! ! \ N

X. Д / \ . " \

м Л >

Рис. 1.1. Планетарная модель атома по Резерфорду с круговыми орбитами четырех

электронов

Эта простая планетарная модель сразу противоречила физическим законам того времени. Дело в том, что согласно механике Ньютона электрон, находящийся на орбите, движется с ускорением. Следовательно, согласно

уравнениям Максвелла, он должен излучать электромагнитные волны и, как следствие, терять энергию (в силу закона сохранения энергии) и вскоре сойти с орбиты и упасть на ядро. Поэтому модель атома по Резерфорду требовала уточнения и дополнен