Возьмем статью Эндрю Эппеля об эффективном моделировании задачи многих тел (Andrew Appel, SIAM Journal on Scientific and Statistical Computing, Jan. Применив многоуровневый подход к улучшению производительности, он сократил время работы программы с 1 года до 1 дня.
Программа решала классическую задачу многих тел — расчет взаимодействия п объектов (планет, звезд, галактик) в собственном гравитационном поле в трехмерном пространстве. Исходными данными служили их массы, начальные положения и скорости. В двухмерной задаче входные данные могли бы выглядеть следующим образом (рис. 6.1).
В статье Эппеля описываются две астрофизические задачи, в которых п=10 ООО. Изучая результаты моделирования, физики могли проверить соответствие теорий астрономическим наблюдениям. Подробнее о задаче и последующих решениях, в которых использовался подход Эппеля, рассказывается в книге Пфалзпера и Гиббона (Pfalzner, Gibbon, Many-Body Tree Methods in Physics, Cambridge University Press, 1996).
В первоначальном варианте моделируютцей программы время делится на маленькие «шаги», и вычисляется перемещение каждого объекта на очередном шаге. Так как для каждого из объектов нужно учесть его взаимодействие со всеми прочими объектами, один шаг по времени требует порядка п2 операций. Эппель подсчитал, что на выполнение 1000 шагов такого алгоритма при п=10 ООО потребуется примерно год вычислений на имевшемся у пего компьютере.
Главная
Каталог файлов
