Устранение недостатка точности с плавающей точкой в ​​системе частиц OpenCL

Question

Я пишу систему частиц на основе OpenCL для ускорения визуализации крупномасштабных сетей. По сути, это двухфазная проблема, когда первая фаза применяет отрицательную гравитацию к каждой частице (типичная проблема n-тел), поэтому все они отталкиваются, а вторая фаза притягивает частицы на основе ребер (или пружин) между частицами.

Во время каждой итерации алгоритма гравитации местоположение каждой частицы, представленное в виде пары поплавков, зависит от расстояния до другой частицы (классическая физическая модель, без сопротивления, что упрощает задачу).

В ситуации, когда человек имеет идеально разнесенный квадратный массив частиц, применение силы тяжести должно привести к симметрии по осям X и Y. Это верно в начале применения гравитации, но со временем отсутствие точности, присущей сложению большого количества чисел с плавающей запятой, приводит к небольшим неоднородным отклонениям. Это, в свою очередь, распространяется по всей системе из n тел и происходит потеря симметрии.

Один из простых способов избежать этого - использовать числа с двойной точностью, однако GeForce 9600M GT на моем MacBook Pro не поддерживает числа с двойной точностью. Итак, как можно решить такие проблемы в OpenCL? Я думал об обрезании чисел с плавающей запятой, которые я добавляю к нескольким десятичным знакам, чтобы избежать этой проблемы, но это выглядит немного странно.

Answer 1

Вы затронули большинство вопросов, имеющих фундаментальное значение для численного анализа; Вы должны подготовиться к чтению о том, как обычно решаются эти проблемы.

Во-первых, если у вашей задачи есть симметрия, вы можете использовать это для уменьшения объема необходимых вычислений, а также избавиться от любых спонтанных нарушений симметрии из-за числовой ошибки.

Во-вторых, осознайте, что даже при работе с одинаковой конечной точностью не все алгоритмы одинаковы: некоторые алгоритмы более численно устойчивы , чем другие. Использование арифметики с более высокой точностью не устраняет числовую нестабильность, а просто заставляет дольше становиться очевидным. Вполне вероятно, что в настоящее время в гравитационном моделировании используется то, что эквивалентно методу Эйлера . Не переключаясь на двойную точность, вы можете сделать ваше моделирование намного более стабильным / точным, используя метод более высокого порядка, такой как Runge-Kutta .

Наконец, звучит так, как будто вы делаете макет принудительно ориентированного графа . Простое выполнение физического моделирования вперед склонно к нахождению только локального оптимума, сильно зависящего от стартовых позиций, и (как вы обнаружили) обычно довольно нестабильно. На связанной вики-странице упоминается несколько других методов, которые могут гораздо лучше решить проблему.

Answer 2

Это довольно распространенная проблема;даже на процессорах иногда нужно избегать использования двойной точности, чтобы избежать двухкратного увеличения объема памяти / пропускной способности памяти.

В ряде кодов молекулярной динамики и n-телец, написанных для графических процессоров, используется «смешанная точность».арифметика;они сохраняют положения и скорости частиц в виде одинарной точности, но затем они используют двойную точность для нескольких ключевых операций - обычно для хранения различий в положениях и для накопления ускорений.(googling "смешанная точность" "молекулярная динамика" или "n-тело" дает тонны результатов).

Таким образом, уменьшается число вычислений двойной точности,но не до нуля.Чтобы реализовать арифметику с более высокой точностью, чем та, которую изначально поддерживает ваше оборудование, вы можете выполнить программную эмуляцию, эмулируя двойное с двумя числами с плавающей запятой.Это была почтенная библиотека Fortran dsfun90 , которая реализовала это, и кто-то на этом форуме NVidia реализовал нечто подобное в CUDA (на основе операций в примере Мандельброта NVIDIA).Я не знаю о реализации OpenCL, но копирование ее из CUDA должно быть довольно простым.Очевидно, что это не так быстро, как нативные удвоения, но если это только для нескольких ключевых операций, это не так уж плохо.