Сравнение метода Верлет таблицы и метода связанных ячеек для последовательной, векторизованной и многопоточной реализаций

Авторы

  • Э.С. Фомин

Ключевые слова:

метод Верлет таблицы
метод связанных ячеек
поиск ближайших соседей
SIMD
многопоточность

Аннотация

Алгоритмы поиска ближайших соседей широко используются в молекулярной динамике для расчетов короткодействующих межатомных потенциалов. Эти алгоритмы основываются на методах Верлет таблицы и связанных ячеек. Дан анализ особенностей указанных методов и показано, что для плотных систем, таких как вода, метод связанных ячеек требует значительно меньшего объема необходимой памяти и количества операций чтения данных по сравнению с методом Верлет таблицы и может эффективно использоваться в параллельных реализациях. Новая техника для параллелизации расчета короткодействующих потенциалов, названная динамической пространственной декомпозицией, предложена для метода связанных ячеек. Показано, что в параллельной SIMD-версии этот метод превосходит метод Верлет таблицы на 40% и более, несмотря на большое количество излишних расчетов межатомных расстояний. Эффективность обусловлена тем, что данный метод более приспособлен для современных многоядерных SIMD-процессоров. Все методы тестировались на пакете MOLKERN.


Загрузки

Опубликован

2010-10-05

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

Э.С. Фомин

Институт цитологии и генетики СО РАН (ИЦиГ СО РАН)
просп. акад. Лаврентьева, 10, 630090, Новосибирск
• старший научный сотрудник


Библиографические ссылки

  1. Allen M.P., Tildesley D.J. Computer simulation of liquids. New York: Oxford University Press, 1990.
  2. Yao Z., Wang J.-S., Liu G.-R., Cheng M. Improved neighbor list algorithm in molecular simulations using cell decomposition and data sorting method // Comput. Phys. Commun. 2004. 161. 27-36.
  3. Gonnet P. A simple algorithm to accelerate the computation of non-bonded interactions in cell-based molecular dynamics simulations // J. Comput. Chem. 2007. 28. 570-573.
  4. Mattson W., Rice B.M. Near-neighbor calculations using a modified cell-linked list method // Comput. Phys. Commun. 1999. 119. 135-148.
  5. Kahle J.A., Day M.N., Hofstee H.P., Johns C.R., Maeurer T.R., Shippy D. Introduction to the Cell multiprocessor // IBM J. of Research and Development. 2005. 49, N 4/5. 589-604.
  6. Anderson J.A., Lorenz C.D., Travesset A. General purpose molecular dynamics simulations fully implemented on graphics processing units // J. Comput. Science. 2008. 227. 5342-5359.
  7. Smith W. Molecular dynamics on hypercube parallel computers // Comput. Phys. Commun. 1991. 62. 229-248.
  8. Fincham D. Parallel computers and molecular simulation // Molecular Simulation. 1987. 1. 1-45.
  9. Fomin E.S., Alemasov N.A., Chirtsov A.S., Fomin A.E. MOLKERN: A library of software components for molecular modeling programs // Biophysics. 2006. 51 , Suppl. 1. 110-112.
  10. http://www.boost.org
  11. http://www2.sscc.ru