Сравнение метода Верлет таблицы и метода связанных ячеек для последовательной, векторизованной и многопоточной реализаций
Ключевые слова:
метод Верлет таблицы
метод связанных ячеек
поиск ближайших соседей
SIMD
многопоточность
Аннотация
Алгоритмы поиска ближайших соседей широко используются в молекулярной динамике для расчетов короткодействующих межатомных потенциалов. Эти алгоритмы основываются на методах Верлет таблицы и связанных ячеек. Дан анализ особенностей указанных методов и показано, что для плотных систем, таких как вода, метод связанных ячеек требует значительно меньшего объема необходимой памяти и количества операций чтения данных по сравнению с методом Верлет таблицы и может эффективно использоваться в параллельных реализациях. Новая техника для параллелизации расчета короткодействующих потенциалов, названная динамической пространственной декомпозицией, предложена для метода связанных ячеек. Показано, что в параллельной SIMD-версии этот метод превосходит метод Верлет таблицы на 40% и более, несмотря на большое количество излишних расчетов межатомных расстояний. Эффективность обусловлена тем, что данный метод более приспособлен для современных многоядерных SIMD-процессоров. Все методы тестировались на пакете MOLKERN.
Раздел
Раздел 1. Вычислительные методы и приложения
Библиографические ссылки
- Allen M.P., Tildesley D.J. Computer simulation of liquids. New York: Oxford University Press, 1990.
- 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.
- 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.
- Mattson W., Rice B.M. Near-neighbor calculations using a modified cell-linked list method // Comput. Phys. Commun. 1999. 119. 135-148.
- 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.
- 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.
- Smith W. Molecular dynamics on hypercube parallel computers // Comput. Phys. Commun. 1991. 62. 229-248.
- Fincham D. Parallel computers and molecular simulation // Molecular Simulation. 1987. 1. 1-45.
- 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.
- http://www.boost.org
- http://www2.sscc.ru