Введение к работе
Актуальность темы. Характерной особенностью современного периода развития науки и техники является тенденция роста сложности, размерности решаемых задач, стимулирующая разработку методов, алгоритмов и программных средств, ориентированных на высокопроизводительные вычислительные архитектуры.
Одной из сложнейших задач современности является квантово-химическая задача расчёта электронной структуры больших органических молекул, которые насчитывают десятки тысяч взаимодействующих электронов и ядер. Результаты расчётов используются, например, в фармакологии при решении задачи конструирования лекарств, в нанотехнологиях, при создании высокотемпературных сверхпроводников и др.
Расчёт электронной структуры сводится к решению уравнения Шредингера, которое описывает пространственное движение всех частиц системы, перемещающихся в силовом поле. Так как положение каждой частицы описывается тремя декартовыми координатами, то возникает уравнение в частных производных второго порядка в трёхмерном пространстве, решаемое аналитически лишь для очень малого класса систем, состоящих из одного или двух атомов. Для молекулярных систем с большим числом атомов применяются трудоёмкие численные итерационные методы, которые могут быть реализованы только при использовании высокопроизводительных средств и параллельной обработки. Практическими результатами решения задачи расчёта электронной структуры являются взаимные расположения атомов в пространстве, создающих стабильные молекулы и относительные энергии этих молекул, а также временная зависимость между структурой молекул и их свойствами.
В общем случае размерность задачи расчёта молекулярной системы есть функция от числа атомов и размерности применяемого базиса в итерационном методе. Трудоёмкость задачи расчёта зависит от метода решения, размерности молекулярной системы и формы расчёта - с фиксированной или измененяемой геометрией положения атомов.
В современных квантово-химических исследованиях допустимыми временами расчёта считаются величины порядка секунд и минут, в исключительных случаях - часов. Однако, расчёт больших молекул, содержащих более 10 атомов, классическими методами даже с использованием высокопроизводительных систем, составляет порядка нескольких десятилетий. По мнению специалистов компании Intel компьютер, способный проводить квантовохимические расчеты любой сложности за допустимое время, должен
иметь производительность не менее 10 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.
Объектом исследования являются методы, алгоритмы и программные средства для расчётов электронной структуры больших органических молекул.
Предметом исследования является разработка методов, алгоритмов и программных средств, направленных на повышение эффективности процедур расчёта больших молекул и их вычислительные характеристики.
Целью диссертации является разработка алгоритмов и программных средств, повышающих эффективность расчётов больших молекулярных систем с использованием высокопроизводительных вычислительных средств. Для достижения указанной цели ставились и решались следующие задачи:
анализ и исследование существующих методов расчёта электронной структуры больших молекулярных систем с целью выбора оптимального соотношения между трудоёмкостью и точностью;
реализация эффективной последовательной программы прямого расчёта матрицы плотности Р по методам Гоедекера-Коломбо и Пальцера-Манолополиса в среде ОС Linux;
разработка алгоритма расчёта фокиана по методу Austin Model/1 (AMI) для разреженных матриц и обоснование целесообразности его параллельной модификации;
разработка параллельно-последовательных алгоритмов расчёта для плотных и разреженных структур данных и создание на их основе комплекса параллельных программ;
анализ теоретических оценок ускорения для разработанных алгоритмов и программ;
исследование эффективности разработанных программных средств.
Методы исследования. Поставленные задачи решаются с использованием методов вычислительной математики, параллельного программирования, теории вычислительной сложности алгоритмов. При разработке программного обеспечения использовались: методы нисходящего проектирования, методика крупнозернистого распараллеливания, модель передачи сообщений, модель потокового параллелизма графических процессоров CUDA, модель параллельного программирования в пакете MATLAB для реализации параллельных модификаций алгоритмов.
На защиту выносятся:
параллельные алгоритмы расчётов на основе методов Гоедекера-Коломбо и Пальцера-Манолополиса;
параллельная модификация метода Пальцера-Манолополиса для обработки разреженных структур данных;
методы хранения и преобразования разреженных структур данных;
теоретические оценки трудоёмкости разработанных алгоритмов;
результаты экспериментов, выполненных с помощью разработанных программных средств.
Достоверность научных результатов подтверждается соответствием теоретических выкладок и результатов экспериментов, а также сопоставлением полученных результатов с результатами, приведёнными в зарубежной научной литературе.
Научная новизна исследования состоит в следующем:
разработаны параллельные алгоритмы расчёта электронной структуры больших органических молекул для плотных матриц, сократившие время расчётов;
на основании исследования разреженных структур данных разработаны схемы хранения и метод обработки, позволившие значительно увеличить допустимую размерность решаемых задач, сократить время решения и требования к используемой памяти;
разработан алгоритм расчёта фокиана по методу AMI для разреженных структур матриц, исследования которого показали нецелесообразность его параллельной модификации в модели распределённой памяти;
выведены, исследованы и экспериментально подтверждены теоретические оценки ускорения и эффективности разработанных алгоритмов с целью определения допустимых размерностей задачи и требований к ресурсам аппаратных средств, а также позволяющие прогнозировать получаемое ускорение на реальных вычислительных системах.
Практическая значимость полученных результатов заключается в разработке методов, алгоритмов и программных средств, которые сокращают время расчётов электронной структуры больших органических молекул. Реализованные программные средства обладают большей эффективностью по сравнению с применяемыми ранее и позволяют значительно повысить допустимую размерность решаемой задачи. Разработанные методы и программные средства учитывают особенности современных высокопроизводительных архитектур, таких как вычислительные кластеры и графические процессоры.
Реализация результатов. Работа выполнялась в рамках грантов РФФИ
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 печатных работах, включая 2 статьи в изданиях из перечня ВАК и 1 монографию.
Структура и объем работы. Работа состоит из введения, 4 глав, заключения, списка использованной литературы, содержащего 79 наименований, и приложений. Основной текст занимает 161 машинописных страницы, в том числе 32 рисунка и 15 таблиц. Полный объём диссертации (с приложениями) составляет 182 страницы.
