Я написал эту причудливую маленькую 2D-симуляцию N-тела в свободное время на C#. Он работал довольно хорошо с последовательной реализацией, работая с хорошей частотой кадров примерно до 1000 тел, после чего он начал отставать.
Я модифицировал алгоритм так, чтобы обновления позиции и скорости выполнялись в отдельных блоках, чтобы они выполнялись на отдельных ядрах ЦП, и заметил небольшое улучшение производительности.
Обратите внимание, что много времени тратится на математику, а также немного времени на отрисовку сцены.
Я только что скачал библиотеку Microsoft Accelerator V2 и переписал весь код с нуля, чтобы использовать ее. Работает как и раньше, но значительно медленнее! В то время как раньше я мог получить почти 1000 баллов для бесперебойной работы, теперь я могу получить только около 10 баллов в Accelerator.
Вот мой код. Это первый раз, когда я что-то делал с Акселератором, так что более чем вероятно, что я что-то напортачил.
Класс называется Test
, потому что это был мой первый тест. Конструктор просто создает массивы длины n
для положений тел по осям x и y, их скоростей по осям x и y и их масс. dec
— это просто коэффициент демпфирования, так что ошибки округления заставят его взорваться, а не взорваться, а g
— это просто гравитационная постоянная, которую я пока оставлю на уровне 1.0f
.
Tick()
— это функция, которая выполняет все обновления. Сначала я рассматриваю все точки относительно любой заданной точки i, нахожу радиус, строю единичный вектор в направлении других точек, масштабирую этот единичный вектор с помощью замедления и гравитационной постоянной, а затем суммирую для обновления скорости x и y. для этой точки.
Затем я обновляю все скорости и все позиции и конвертирую обратно в float[]
s.
Как я уже сказал, код технически работает. Результат идентичен моей последовательной реализации, за исключением значительного замедления.
Любые идеи, что я могу делать неправильно?
У меня есть ощущение, что это могут быть строки 85 и 86 - я суммирую обновления скорости x и y для точки i и сохраняю это в свой массив с плавающей запятой, что означает, что мне нужно вызвать Target.ToArray1D()[0]
, чтобы получить суммированное значение.
Причина, по которой я это делаю, заключается в том, что сначала у меня есть обновления для всех точек, затем я обновляю точки, а затем применяю изменения положения на основе скорости.
то есть мне не нужна ситуация, когда в момент времени t + 1 я обновляю точку 0 остальными точками в момент времени t, а затем следующая точка обновления 1 с остальными точками снова во время t, но точка 0 с новым t + 1. Если это имеет смысл.
public void Tick()
{
FPA fxPos = new FPA(xPos);
FPA fyPos = new FPA(yPos);
FPA fxVel = new FPA(xVel);
FPA fyVel = new FPA(yVel);
FPA fMass = new FPA(mass);
float[] xUpd = new float[n]; // x-update for velocity
float[] yUpd = new float[n]; // y-update for velocity
for (int i = 0; i < n; i++)
{
// x- and y-pos about point i:
FPA ixPos = PA.Subtract(fxPos, xPos[i]);
FPA iyPos = PA.Subtract(fyPos, yPos[i]);
// radius from point i:
FPA iRad = PA.Sqrt(PA.Add(PA.Multiply(ixPos, ixPos), PA.Multiply(iyPos, iyPos)));
// x- and y-pos are now unit vectors:
ixPos = PA.Divide(ixPos, iRad);
iyPos = PA.Divide(iyPos, iRad);
// vectors are now scaled by mass:
ixPos = PA.Multiply(fMass, ixPos);
iyPos = PA.Multiply(fMass, iyPos);
// vectors are now scaled by G and deceleration:
ixPos = PA.Multiply(dec * g, ixPos);
iyPos = PA.Multiply(dec * g, iyPos);
// sum to get ith update value:
xUpd[i] = target.ToArray1D(PA.Sum(ixPos))[0];
yUpd[i] = target.ToArray1D(PA.Sum(iyPos))[0];
}
FPA fxUpd = new FPA(xUpd);
FPA fyUpd = new FPA(yUpd);
// update velocities:
fxVel = PA.Add(fxUpd, fxVel);
fyVel = PA.Add(fyUpd, fyVel);
// update positions:
fxPos = PA.Add(fxVel, fxPos);
fyPos = PA.Add(fyVel, fyPos);
xPos = target.ToArray1D(fxPos);
yPos = target.ToArray1D(fyPos);
xVel = target.ToArray1D(fxVel);
yVel = target.ToArray1D(fyVel);
}
O(N^2)
наO(N log N)
. - person Mike Bailey   schedule 19.11.2012