Летняя школа 2012 Проект Программирование графических ускорителей Задача Моделирование движения N тел в гравитационном поле автор: Купчишин А.Б. руководитель: - презентация

1 Летняя школа 2012 Проект Программирование графических ускорителей Задача Моделирование движения N тел в гравитационном поле автор: Купчишин А.Б. руководитель: Калгин К.В.

2 Постановка задачи Эффективно запрограммировать на графическом ускорителе N body system с небольшим количеством тел (N~20) Эффективно запрограммировать на графическом ускорителе N body system с небольшим количеством тел (N~20) Особенности Хранится вся траектория движения каждого тела Хранится вся траектория движения каждого тела Малое количество тел в системе, N~20 Малое количество тел в системе, N~20

3 F Модель N-body-system F F F F F Fr Fr Fr 1) 1) R->F->a->coord

4 Реализация последовательная реализация CPU (N 2 ) последовательная реализация CPU (N 2 ) оптимизированная последовательная реализация CPU (N 2 /2) оптимизированная последовательная реализация CPU (N 2 /2) параллельная реализация GPU: 1 поток = 1 тело параллельная реализация GPU: 1 поток = 1 тело параллельная реализация GPU: количество потоков = (количество тел) 2 параллельная реализация GPU: количество потоков = (количество тел) 2 параллельная реализация GPU: с учетом warp параллельная реализация GPU: с учетом warp параллельная реализация GPU: аналог SSE параллельная реализация GPU: аналог SSE Решение данной задачи производилось в несколько этапов

5 последовательная реализация Rij Aij NewCoord i = 1,количество j = 1,количество

6 оптимизированная последовательная реализация i = 1,количество j = i+1,количество Rij Aij, Aji NewCoord

7 параллельная реализация: 1 тело = 1 поток j = 1,количествоj = 2,количествоj = i+1,количество i = ID потока Rij Aij, Aji NewCoord Rij Aij, Aji NewCoord Rij Aij, Aji NewCoord

8 параллельная реализация: количество потоков = количество тел*количество тел ID - идентификатор потока i = f(ID) j = g(ID) R(01) A(01) A(10) R(0N) A(0,N) A(N0) R(12) A(12) A(21) Rij Aij Aji R(1N) A(1N) A(N1) NewCoord 000

9 параллельная реализация: warp ID - идентификатор потока i = f(ID) j = g(ID) R(01) A(01) A(10) R(0N) A(0,N) A(N0) R(12) A(12) A(21) RiN AiN ANi R(i,i+1) A(i,i+1) A(i+1,i) NewCoord R(1N) A(1N) A(N1) N N-1...

10 параллельная реализация: SSE ID - идентификатор потока i = f(ID) j = g(ID) R(01) A(01) A(10) R(0N) A(0,N) A(N0) R(12) A(12) A(21) RiN AiN ANi R(i,i+1) A(i,i+1) A(i+1,i) R(1N) A(1N) A(N1) N N-1... NewCoord X NewCoord Y NewCoord Z NewCoord X NewCoord Y NewCoord Z

11 производительность Время последовательного оптимизированного CPU = 1 у.е. Время последовательного оптимизированного CPU = 1 у.е. CPU не оптимизированный = 30 у.е. GPU N потоков = 2 GPU N*N потоков = 0.86 GPU warp = 0.75 GPU sse = 0.35

12 Продолжение внедрить параллельное суммирование xyz на ВСЕХ операциях такого типа. внедрить параллельное суммирование xyz на ВСЕХ операциях такого типа. реализация метода для большого количества тел реализация метода для большого количества тел использование более одного блока потоков, при N>256 использование более одного блока потоков, при N>256 конечная скорость распространения действия гравитационных сил конечная скорость распространения действия гравитационных сил

13 Cпасибо за внимание!