Содержание
- Список аббревиатур и сокращений
1. Анализ и исследование моделей и методов расчета электронной структуры больших молекулярных систем.
1.1. Физическая и математическая модели задачи.
1.2. Классификация методов расчета.
1.3. Строгие одноэлектронные методы расчета электронной структуры.
1.4. Упрощенные полуэмпирические методы нулевого дифференциального перекрывания.
1.5. Требования к компьютерным ресурсам. Процесс диагонализации симметричных матриц.
1.6. Современные методы расчета, альтернативные диагонализации матриц.
1.7. Выводы по главе 1.
2. Разработка и исследование эффективных алгоритмов и программных средств для расчета матрицы плотности.
2.1. Разработка и реализация последовательного алгоритма расчета матрицы плотности на основе матричных полиномов Чебышева.
2.2. Оптимизация последовательной программы.
2.2.1. Модификация структуры исходных данных.
2.2.2. Изменение способов хранения массивов.
2.2.3. Оптимизация процессов матричного умножения.
Трудоемкость метода Гоедекера-Коломбо.
2.3. Параллельный алгоритм расчета матрицы плотности на основе матричных полиномов Чебышева.
2.3.1. Использование блочного умножения матриц.
2.3.2. Параллельная модификация алгоритма и спецификация параллельной программы.
2.4. Эффективные вычисления по методу очистки для матриц общего вида.
2.5. Выводы по главе 2.
3. Организация эффективных вычислений для обработки данных разреженной структуры.
3.1. Особенности реализации эффективных вычислений по методу пюрификации для разреженной формы матриц.
3.2. Оценка трудоемкости и эффективности для класса методов очистки.
3.2.1. Случай плотных матриц.
3.2.2. Случай разреженных матриц.
3.3. Особенности расчета разреженной формы фокиана.
3.3.1. Обоснование появления разреженности в структуре фокиана.
3.3.2. Последовательный алгоритм построения матрицы фокиана.
3.3.2. Алгоритм нахождения значений произвольных элементов матрицы фокиана.
3.3.4. Алгоритм расчета вкладов в фокиан.
3.3.5. Параллельная модификация алгоритма.
3.4. Выводы по главе 3.
4. Исследование разработанных программных средств расчета.
4.1. Постановка проблемы исследования.
4.2. Технологии параллельного программирования для реализации разработанных алгоритмов.
MPIhPVM.
4.2.2. Средства параллельного программирования в математическом пакете MATLAB.
4.2.3. Использование средств GPU.
4.2.4.Анализ стандартных программных средств параллельного матричного умножения.
4.3. Используемые аппаратные ресурсы и программное обеспечение.
4.4. Анализ результатов расчетов по последовательной и параллельной программам сборки разреженного фокиана по методу AMI.
4.5. Исследование влияния параметров метода Гоедекера-Коломбо на точность решения.
4.6. Анализ результатов расчетов для случая плотных матриц.
4.6.1. Метод Гоедекера-Коломбо.
4.6.2. Метод Пальцера-Манолополиса.
4.6.3. Влияние типа межсоединения.
4.7. Анализ результатов расчетов для случая разреженных матриц.
4.8. Анализ результатов использования многонитевых средств реализаций BLAS для повышения эффективности вычислений.
4.9. Использование гибридной модели вычислений {MPI+OpenMP}, а также средств GPU, позволило достичь наилучших показателей эффективности разработанных средств при расчетах реальных молекулярных систем средней размерностиАнализ результатов использования реализаций BLAS на GPU для повышения эффективности вычислений.
4.10. Выводы по главе 4.
Расчёты электронной структуры гигантских молекул являются одними из самых сложных в современной науке и требуют использования высокопроизводительных вычислительных средств, таких как супер ЭВМ и кластерные системы. Расчёты электронной структуры, в частности, биомолекул (белков, ДНК) и наночастиц, актуальны для ряда областей науки: химии, биохимии, физики конденсированного состояния вещества и др. В практическом плане эти расчёты важны для фармакологии, нанотехнологий, исследований явлений сверхпроводимости, разработки квантовых компьютеров. Перечисленные проблемы являются одними из самых сложных современных задач. Поэтому входят в список «Великого вызова» (Grand Challenge), сформированный национальным научным фондом США, и включающий наиболее значимые научные проблемы, стоящие перед человечеством, для решения которых требуются высокопроизводительные средства.
Расчет электронной структуры сводится к решению уравнения Шредингера, которое описывает пространственное движение всех частиц системы, перемещающихся в силовом поле. Так как положение каждой частицы описывается тремя декартовыми координатами, то возникает уравнение в частных производных второго порядка в трёхмерном пространстве, решаемое аналитически лишь для очень малого класса систем, состоящих из одного или двух атомов. Для молекулярных систем с большим числом атомов применяются трудоемкие численные итерационные методы, которые могут быть реализованы только при использовании высокопроизводительных средств и параллельной обработки.
В современных квантово-химических исследованиях допустимыми временами расчета считаются величины порядка секунд и минут, в исключительных случаях — часов. Однако, расчет молекул, содержащих более 104 атомов, классическими методами даже с использованием высокопроизводительных систем, составляет порядка нескольких десятилетий. По мнению специалистов компании Intel компьютер, способный проводить квантовохимические расчеты любой сложности за допустимое.
21 время, должен иметь производительность не менее 10 FLOPS, и такая мощность будет достигнута не ранее 2030 года.
Таким образом, актуальными являются исследования, направленные на организацию эффективных расчетов электронной структуры больших молекул на существующих сегодня высокопроизводительных архитектурах.
Для расчета электронной структуры больших молекулярных систем, которые могут содержать от тысячи до миллионов атомов, целесообразно применение полуэмпирических методов квантовой химии в так называемом приближении нулевого дифференциального перекрывания [1], в общем о случае имеющих асимптотическую сложность расчета 0(N), где Nразмерность задачи, пропорциональная числу атомов. Центральным звеном при расчете таких молекулярных систем является решение симметричной задачи на собственные значения. Задача на собственные значения описывается как Ах = Ах, где, А — матрица, X — собственное значение, соотвествующее вектору х. Для симметричных матриц это выражение может быть переписано в виде A = QAQT, где столбцы матрицы Q являются ортогональными собственными векторами А, а диагональная матрица Л содержит соответствующие им собственные значения.
Для расчета физико-химических свойств нужны не сами собственные вектора, а матрица плотности Р, являющаяся функцией от них. Недавно были разработаны численные методы прямого нахождения Р (без диагонализации матриц), которые для разреженных матриц имеют сложность расчета 0(N) [2−4].
Предметом исследования данной работы являются методы, алгоритмы и программные средства для расчета электронной структуры больших органических молекул.
Для большинства методов расчета электронной структуры разработаны соответствующие программы расчёта, в том числе дорогостоящие коммерческие. Однако эти программы либо не ориентированы на высокопроизводительные средства вычисления (не имеют параллельных версий, или плохо распараллеливаются), либо не могут рассчитывать молекулы больших размеров, требуя больших временных затрат и ресурсов памяти.
Целью данной работы является разработка комплекса алгоритмов и программ для высокопроизводительных архитектур, позволяющего повысить эффективность расчетов физико-химических свойств больших органических молекул. В его составе алгоритмы и программы расчета фокиана и матрицы плотности.
Для достижения поставленной цели в работе ставятся и решаются следующие основные задачи:
4.10. Выводы по главе 4.
В данной главе приведены результаты и анализ экспериментов. Экспериментально исследовано влияние параметров метода Гоедекера-Коломбо — обратной температуры, размерности полинома и числа точек интегрирования — на скорость сходимости метода.
По результатам экспериментов можно сформулировать следующие выводы:
1. Проведенные эксперименты показали эффективность разработанных программных средств и принципиальную возможность расчета электронной структуры молекулярных систем размерности N > 104 за приемлемое время.
2. Результаты экспериментов в разделах 4.4 — 4.9 согласуются с теоретическими оценками разработанных в главах 2 и 3 алгоритмических средств расчета.
3. Для расчетов электронной структуры молекул при представлении данных в виде плотных матриц реализация предложенного параллельного алгоритма по методу Пальцера-Манолополиса обладает лучшими характеристиками ускорения, чем реализация параллельного алгоритма по методу Гоедекера-Коломбо и при этом имеет значительно меньшие требования к памяти. Данный вывод подтверждается экспериментами в разд. 4.6.
4. Выявлено, что при расчетах задач одинаковой размерности на одинаковых вычислительных ресурсах при использовании модификации метода Пальцера-Манолополиса для класса блочно-трехдиагональных разреженных структур данных время расчета существенно меньше (в десятки раз), чем для структур общего вида. В целом это подтверждает актуальность исследований, связанных с анализом портрета матрицы плотности и разработкой соответствующих модификаций алгоритмов и программных средств.
5. Использование гибридной модели вычислений {MPI+OpenMP}, а также средств GPU, позволило достичь наилучших показателей эффективности разработанных средств при расчетах реальных молекулярных систем средней размерности.
6. Использование средств параллельного программирования, встроенных в математические пакеты, позволяет, во-первых, ускорить матричные расчеты как внутри последовательных, так и параллельных программ, и, во-вторых — предоставляет непрофессиональному программисту доступные средства параллельной обработки.
7. Программные средства расчета фокиана на основе разработанной модификации метода AMI для разреженных («по-атомных») структур позволили впервые в России осуществить расчет фокиана для молекулы размером более 56 000 атомов.
8. Результаты расчета фокиана с помощью программных средств, разработанных на основе параллельной модификации метода AMI для разреженных («по-атомных») структур в модели распределенной памяти, показывают нецелесообразность распараллеливания этих расчетов в рамках общей схемы расчетов электронной структуры.
Заключение
.
В процессе выполнения диссертационной работы были получены следующие результаты:
1. Проведено исследование физической и математической моделей задачи расчета электронной структуры больших и сверхбольших молекулярных систем. Отмечается, что задача является актуальной для различных областей науки (химии, биохимии и др.) и относится к классу сложных задач большой размерности.
2. Проанализированы различные методы решения данной задачи: строгие (неэмпирические) методы, упрощенные полуэмпирические методы, включая современные методы с прямым расчетом матрицы плотности.
3. В результате анализа, показано, что.
• задача расчета электронной структуры относится к классу сложных и для ее решения необходимо использовать высокопроизводительные вычислительные архитектуры.
• строгие методы расчета имеют асимптотическую сложность от.
0(]Г4) и выше, поэтому неприемлемы для расчета больших молекулярных систем, в которых N > 10 .
• упрощенные полуэмпирические методы НДП сводятся к л диагонализации матриц с асимптотической сложностью 0(И), что также неприемлемо для расчетов больших молекулярных систем.
• выявлено, что при формировании математической модели органической молекулы, возникают матричные разреженные структуры в силу их физико-химических свойств, поэтому для повышения эффективности расчётов целесообразно использовать полуэмпирические методы расчёта с учетом разреженности структур данных.
4. Составлена сравнительная таблица методов с точки зрения сложности расчетов и наличия последовательной/параллельной реализаций.
5. Разработан параллельный алгоритм расчета матрицы плотности по методу Гоедекера-Коломбо, реализована и экспериментально исследована соответствующая параллельная MPI-программа. Применение стандартов Фортран-90 и MPI обеспечили возможность переноса программы в различные аппаратно-программные платформы.
6. Разработан параллельный алгоритм расчёта для плотных матриц по методу Пальцера-Манолополиса, который реализован средствами Fortran+MPI и для двух способов организации обмена — широковещательной рассылки и двухточечных обменов.
7. Разработаны схемы хранения и предложены методы обработки разреженных структур на примере блочно-трехдиагональных матриц, позволившие значительно сократить время расчетов Р и увеличить размерность решаемых задач.
8. Разработаны и реализованы последовательный и параллельный алгоритмы на основе предложенной в работе метода Пальцера-Манолополиса для случая матриц с блочно-трехдиагональным портретом. Программа, реализующая параллельный алгоритм, хорошо масштабируется с ростом числа процессоров.
9. Исследованы оценки трудоемкости разработанных алгоритмов, позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах, которые соответствуют результатам проведенных экспериментов.
Ю.Разработана схема хранения для разреженного фокиана и предложен последовательный алгоритм расчёта по методу AMI, позволивший рассчитать фокиан молекулы, содержащей более 5*104 атомов.
11 .Разработана параллельная модификация расчёта фокиана методом AMI для разреженных матриц и выполнена ее реализация, показавшая неэффективность данного расчета в рамках модели распределенной памяти.
12.Разработана методика создания параллельных программ для выполнения научных расчетов в среде математического пакета MATLAB, которая была применена для реализации программы по методу Пальцера-Манолополиса.
13. Разработан, реализован и исследован параллельный алгоритм по методу Пальцера-Манолополиса для NVIDIA GPU (CUDA), показавший существенное увеличение производительности расчётов по сравнению с использованием многоядерных процессоров в кластере за счет только эффективного выполнения блочного матричного умножения.
Работа поддержана РФФИ, проекты 01−07−90 072, 04−07−90 220, 05−07−8 031-офи-а, 11−07−470.
