Как вы могли бы запрограммировать симуляцию 2D boids таким образом, чтобы он мог использовать вычислительную мощность из разных источников (кластеров, GPU).
В приведенном выше примере неокрашенные частицы перемещаются, пока не сгруппируются (желтые) и не перестанут двигаться.
Проблема заключается в том, что все объекты могут потенциально взаимодействовать друг с другом, хотя вряд ли объект в левом верхнем углу будет взаимодействовать с объектом в нижнем правом углу. Если домен был разбит на разные сегменты, это может ускорить процесс, но если организация захотела перейти в другой сегмент, могут возникнуть проблемы.
На данный момент эта симуляция работает с 5000 объектами с хорошей частотой кадров, я хотел бы попробовать это с миллионами, если это возможно.
Можно ли будет использовать квад-деревья для дальнейшей оптимизации? Любые другие предложения?
Ответы:
Магистерская диссертация Маттиаса Линде " Параллельное моделирование частиц жидкости" может дать некоторое представление о разделении данных и алгоритмах для крупномасштабного моделирования.
Его статья ориентирована на гидродинамику сглаженных частиц , которая для наивного решения имеет тенденцию использовать пространственное хеширование с размером сегмента, равным размеру следа ядра частиц в симуляции.
Поскольку расстояние взаимодействия жестко ограничено в типичных ядрах SPH, такая оптимизация разбиения практически необходима для расширения системы.
источник
Термин, который я выучил давным-давно, был скоростью информации в игре.
Если скорость ваших boids равна 1, и они заботятся только о своих соседях, то скорость информации равна 3, то есть boid, который находится на расстоянии двух квадратов от вас, может находиться в пределах диапазона, о котором вы заботитесь, в пределах одного кадра:
1 квадратное движение за бой во взаимодействии (1 + 1) плюс расстояние, на которое вы можете заметить вещи (1), равно 3.
Исходя из этого, мы узнаем, что можем разбить карту на куски, размер которых настолько мал, насколько нам нужно, но с такой скоростью информация пересекается с любыми соседними кусками.
Я предполагаю, что вы позволяете вашим боидам двигаться только на один квадрат, но они могут видеть три
Если вы хотите запустить массивного параллельного сима, вы разбиваетесь на сетки 10x10, но перекрываете по 5 квадратов на каждом ребре. Всякий раз, когда кто-то из вас оказывается в пределах информационного расстояния от границы локального чанка, вы должны обновить соседа, и как только они пересекают границу, они не принадлежат вам. Если сосед говорит, что бид, которым он управляет, переместился в ваш чанк, вы должны взять на себя его ИИ.
Это означает, что связь локализована с соседними менеджерами чанков, а трафик сведен к минимуму. Чем больше заданий вы выполняете, тем больше процессоров вы можете использовать для управления имитацией, но чем больше заданий вы выполняете, тем больше их наложений и, следовательно, больше информации, передаваемой между заданиями / блоками в процессе симуляции. Именно здесь вам нужно взять на себя ответственность и настроить размер чанка в зависимости от сложности ИИ и того, какое у вас оборудование.
источник
Читая свой вопрос, кажется, вы можете воспользоваться квадра-деревьями, создать квад-дерево и запустить симуляцию для каждого сегмента в отдельном блоке обработки. Это приведет к тому, что проверка произойдет только с объектами, расположенными близко друг к другу. но вам нужно синхронизировать ваши потоки каждый цикл. Что означает перенос некоторых из этих boids из одной группы обработки в другую. в общем, каждый цикл будет состоять из 3 шагов:
* Для создания групп вы можете использовать шаблон ниже:
Обратите внимание, что некоторые boids могут быть частью более чем одной группы, но этот шаблон дает вам более точные результаты. Вы также можете создать столько групп, сколько захотите, используя этот шаблон, это просто число, которое вы должны найти, сколько бидов и экран, какой размер экрана, какое количество групп вам лучше всего создать.
--редактировать--
есть другая идея о сегментации, которая описана в статье @LarsViklund sugested, таким образом, гораздо меньше двойных проверок и нет необходимости увеличивать / уменьшать количество потоков между шагами:
Обратите внимание, что некоторые области все еще являются частью двух групп. а ширина зоны покрытия обеих групп точно
2*maximum speed. В вашем случае, если boids перемещается на один пиксель за шаг симуляции, вам нужно всего лишь разделить область шириной в 2 пикселя между двумя группами. и есть небольшая территория, которая входит в 4 группы. но в целом этот метод проще реализовать и намного быстрее, если он реализован правильно. и, кстати, нет обратного хода таким образом, если какой-то объект может двигаться, он может двигаться, больше не требуется проверка.источник
Недавно я решил эту проблему, используя некоторые из этих ответов в качестве отправной точки. Самое полезное, что нужно иметь в виду, это то, что boids - это своего рода простая симуляция n-тела: каждый boid - это частица, которая воздействует на соседей.
Мне было трудно читать бумагу Линде; Вместо этого я предлагаю взглянуть на «Быстрые параллельные алгоритмы короткой молекулярной динамики» С. Дж. Плимптона , на которые ссылается Линде. Бумага Плимптона гораздо более читабельна и детальна с лучшими цифрами:
Я рекомендую вам попробовать AD. Это проще всего понять и реализовать. ФД очень похож. Вот симуляция n-тела nVidia с использованием CUDA с использованием FD, которая должна дать вам общее представление о том, как мозаичное построение и сокращение могут помочь значительно превзойти производительность последовательного интерфейса.
Реализации SD, как правило, оптимизируют методы и требуют определенной степени хореографии для реализации. Они почти всегда быстрее и лучше масштабируются.
Это потому, что AD / FD требует построения «списка соседей» для каждого boid. Если каждому бойду необходимо знать положение своих соседей, связь между ними будет O ( n ²). Вы можете использовать списки соседей Verlet, чтобы уменьшить размер области, которую проверяет каждый boid, что позволяет вам перестраивать список каждые несколько шагов вместо каждого шага, но это все равно O ( n ²). В SD каждая ячейка содержит список соседей, тогда как в AD / FD у каждого boid есть список соседей. Таким образом, вместо того, чтобы каждый бид общался друг с другом, каждая клетка общалась друг с другом. Это сокращение в общении, откуда происходит увеличение скорости.
К сожалению, проблема Boids немного саботирует SD. Отслеживание ячейки каждым процессором является наиболее выгодным, когда боиды несколько равномерно распределены по всему региону. Но вы хотите, чтобы boids собирались вместе! Если ваша стая ведет себя должным образом, подавляющее большинство ваших процессоров будут отсчитывать время, обмениваясь пустыми списками, и небольшая группа ячеек в итоге выполнит те же вычисления, что и AD или FD.
Чтобы справиться с этим, вы можете либо математически настроить размер ячеек (который является постоянным), чтобы минимизировать количество пустых ячеек в любой момент времени, либо использовать алгоритм Барнса-Хата для четырех деревьев. Алгоритм ЧД невероятно мощный. Как это ни парадоксально, это очень сложно реализовать на параллельных архитектурах. Это связано с тем, что дерево BH нерегулярно, поэтому параллельные потоки будут проходить по нему с сильно изменяющимися скоростями, что приведет к расхождению потоков. Salmon и Dubinski представили ортогональные рекурсивные алгоритмы деления пополам для равномерного распределения квадродеревьев между процессорами, которые должны быть повторены итеративно для большинства параллельных архитектур.
Как видите, на данный момент мы явно находимся в области оптимизации и черной магии. Опять же, попробуйте прочитать статью Плимптона и посмотрите, имеет ли это смысл.
источник
Я предполагаю, что у вас тороидальная система, вы можете разделить пространство, чтобы у каждого юнита была своя область.
На каждом шаге частицы перемещаются, частицы, которые выходят из подобласти, отправляются в соответствующий процессор; шаг связи синхронизирует процессоры, и последний шаг делается для уточнения позиции посторонних частиц (если есть).
Здесь есть три проблемы:
Можно выбрать прямоугольники, но они показывают небольшое отношение площади / периметра по сравнению с вихрями. Чем больше граница, тем больше частиц уйдет. Несмотря на то, что циклы демонстрируют наилучшее соотношение A / p, их нельзя использовать для тесселяции, поэтому вам следует испытать раздражение по поводу некоторой (возможно, полурегулярной) тесселяции с хорошим средним отношением A / p. Очевидно, что вычисление индекса кисточки по координате ячейки должно быть простым, поэтому подумайте об этом, прежде чем попробовать очень экзотическую тасселяцию.
В зависимости от того, какая у вас инфраструктура связи, вы можете подумать, как распределить информацию о пересечении границ между процессорами. Вещание против одноранговой реконструкции против одноранговой связи - все варианты.
Вы должны сохранять сбалансированность своей разработки, поскольку на каждом этапе происходит синхронизация. Вы можете выбрать статическое или динамическое распределение областей для процессоров. Это не большая проблема, если ваше пространство равномерно покрыто активными частицами, но я верю, что в этом случае это может быть неверным, так как столкновения дезактивируют частицы. Изменение распределения требует более тяжелого шага связи; некоторые ярлыки можно использовать, если все процессоры делятся трансграничной информацией, но вы должны подумать об этом
источник
Попробуйте мою симуляцию для подсказок https://github.com/wahabjawed/Boids-Simulation
Я разработал это на XNA
источник