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

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