- Suslik
- Постоялец
после тщательного обсуждения, начатого здесь, и продолженного в аське с товарищем Suslik'ом, с параллельностью труъ ригид боди сима с последовательным солвером были резюмированы следующие данные:
имея ЛЦП, последовательный солвер и бинарные связи можно сделать как-то так
( основа - идея Suslik'а )
поскольку связи бинарные, т.е. джоинт действует только на пару тел, можно выделить некоторое число фаз, на которое можно разбить одну итерацию, чтобы солвер оставался последовательным при таком решении системы:
фаза1 ( каждый джоинт разносица по параллельным тредам ) - фаза2 - ... - фаза N
т.е. фазы выполняюца последовательно, используя на текущей итерации данные с предыдущих фаз ( вроде как, последовательности солвера мы не теряем ), но джоинты которые находяца в одной фазе выбраны так, что не имеют общих тел, и поэтому в пределах фазы их можно обсчитывать параллельно.
минимальное количество фаз, следуя логике последовательного солвира, ограничено числом максимального количества джоинтов, присоединенных к одному телу. на примере, есть кучка, в которой у одного из тел максимальное количество контактных соединений с соседями - 12 ( допустим ), и еще есть болл-сокеты и ротейшнл лимиты, итого штук 16 джоинтов. значит, минимальное кол-во фаз, необходимое для соблюдения солвером последовательности - есть 16.
итак, плюсы подхода:
- мы можем получить хоть какую-то параллельность
- при увеличении количества параллельных сопроцессоров, можно тоньше размазать одну фазу по ним, и получить больший прирост
минусы:
- в случае с худшем слуаем, мы можем получить сильную загруженность логически одного сопроцессора ( физически может и на разных - но время ограничено тем, что фазы должны ждать просчета предыдущей для последовательности ).
мое мнение на счет ригид боди на гпу так что примерно такое:
в случае с worst-case мы получим в ботлнек производительность именно одного сопроцессора, а на ГПУ один с юнит обладает довольно слабой вычислительной мощностью, значица получим один большой тормоз вместо конечного приложения
далее, опять же, фидбек - можно говорить за то, что данные малыми порциями перегонять все-таки можно. однакож в худшем случае в отношении фидбека опять же, может получица много данных для трансфера, или забитость шины другими внутридвижковыми данными ( графикой ), и мы запоримся.
можно наверное придумать еще минусов для ГПУ.
а можно придерживаца альтернативной точки зрения на счет worst-case'ов, как у тов Suslik'а.
идеи, комментарии - приветствуюца.
Переформулирую то же самое, но своими словами, может, больше народу поймёт:
Введём понятие группы: группой джойнтов назовём такое множество джойнтов, в котором никакие два джойнта не используют общей памяти. Грубо говоря, никакие два джойнта не связывают одно и то же тело.
Отметим, что совершенно любое множество джойнтов всегда можно разбить на группы, правда, в худшем случае количество групп будет равняться количеству джойнтов. Итак, предположим, что мы разбили все наши джойнты j1, j2, j3 .. jm на группы: (j2, j3, j10, j125), (j1, j5)..
Имея n бинарных Joint'ов(контактов, скажем) и последовательный солвер, нам, в принципе, всё равно, в каком порядке эти джойнты решать : хоть в порядке j1, j2, j3 .. jm, хоть в порядке нашего разбиения на группы j2, j3, j10, j125, j1, j5... Нетрудно заметить, что во втором случае так ввсе джойнты каждой группы независимы, мы можем поручить их обработку отдельному процессору. И теперь вместо того, чтобы решать на одном ядре core1 по схеме
Phase 1) core1: j1
Phase 2) core1: j2
Phase 3) core1: j3
...
Phase 4) core1: jm
пользуясь независимостью джойнтов руппы мы можем распараллить:
Phase1) core1: j2, core2: j3, core3: j10, core4: j125
Phase2) core1: j1, core2: j5
...
буст производительности очевиден. Если, имея 1000 джойнтов, мы их разобъём на две группы по 500 джойнтов и назначим их решать каждому ядру нашего 512ядерного мультипроцессора(видюшный процессор) мы решим их всего за две фазы! Но, как уже упоминал тов. XperienS, существует ворскейс, когда джойнты ну никак не разбиваются на малое количество групп. В худшем случае количество джойнтов равно количеству групп, тогда вообще никакого распараллеливания мы не добъёмся, будет работать только одно относительно слабое ядро мультипроцессора, и производительность нехило упадёт.
Стоть отметить, что суммарная вычислительная мощность 512 процессоров видюхи в десятки/сотни раз превосходит суммарную мощность ядер того же Core2Duo.
Результат:
Имеем подход, который в большинстве игровых сцен может дать десятикратный и более выигрыш производительности, но в ворсткейсе примерно пятикратный фейл. Моё мнение - что ворсткейса возможно избегать, и нельзя из-за него отказываться от всех преимуществ подхода. Хотя, с этим можно не согласиться.
Suslik
Как я понял, под Зейделем ты здесь понимаешь обработку со сдвигом, т.е. примерно так (поправь, если ошибаюсь)
Takt 0 1 2 3 4 5
Proc
0 j1 j6 j10 j14
1 j2 j7 j11 j15
2 j3 j8 j12
3 j4 j9 j13
4 j5 j9
5 j5
Я здесь условно изобразил только 6 процессоров. Данные, рассчитаные при операции j1 используются при расчете j2 и т.д.
>Стоть отметить, что суммарная вычислительная мощность 512 процессоров видюхи в десятки/сотни раз превосходит суммарную мощность ядер того же Core2Duo.
Это в куда максимальное значение числа тредов 512, но это число не совпадает с числом физических процессоров. В gf8800gt их например 112, в современных 200 серии доходит до 240. В последней версии Тесла, при 4 g200 получается больше 1000.
Тема в архиве.