TODO: 소개 영상과 요약 영상을 추가합니다.
이 작은 프로그램은 무작위 입자 운동을 시뮬레이션합니다. 2D 평면 위에서 제약 없이 움직이는 입자 1000개가 있습니다. 즉, 경계가 없으므로 입자는 초기 좌표에서 원하는 만큼 멀리 이동할 수 있습니다. 각 입자는 [-1000,1000] 범위의 초기 x, y 좌표와 [0;1] 범위의 일정한 속도를 가집니다. 프로그램은 입자 운동을 1000단계 시뮬레이션합니다.
시뮬레이션 결과(입자의 최종 위치)를 검증하기 위해, 전역 상태를 사용하여 항상 같은 수열을 생성하는 결정론적 난수 생성기(가짜)를 사용합니다.
시뮬레이션을 빠르게 실행하지 못하게 만드는 아주 고약한 성능 문제가 하나 있습니다. 코드에서 의존성 체인을 찾아 해결할 수 있겠습니까?
참고: 검증을 통과하기만 한다면, 여러분의 해법은 원래 프로그램과 기능적으로 동등하지 않아도 됩니다. 예를 들어, RNG가 이전과 다른 난수열을 생성하더라도 괜찮습니다. 어차피 입자의 운동은 무작위이므로 사용자는 그 차이를 구별할 수 없습니다.
힌트
힌트 1:
이것은 의존성 체인 문제입니다. 가장 먼저 해 볼 일은
solution.hpp에 있는 randomParticleMotion의
루프에서 각 반복이 왜 서로 독립적이지 않은지 파악하는 것입니다. N번째
반복에서 사용하는 값 중에 N-1번째 반복에서 계산한 결과에 의존하는 값이
있습니까?
힌트 2:
XorShift32::gen()의 구현을 살펴보십시오. 이 함수의
반환값에서 무엇을 알 수 있습니까?
힌트 3:
(의존성 자체를 바꿀 수 없는) 의존성 체인 문제에서 성능을 개선하는 요령은 반복마다 노드 하나가 아니라 체인의 "덩어리"를 처리하도록 하는 것입니다. 여러분의 머신에 맞는 최적의 해법을 찾아보십시오.
풀이:
배경:
이 실습의 프로그램은 무작위 입자 운동을 시뮬레이션합니다. 관련 코드
루프는 solution.hpp에 있습니다:
template <class RNG>
void randomParticleMotion(std::vector<Particle> &particles, uint32_t seed) {
RNG rng(seed);
for (int i = 0; i < STEPS; i++)
for (auto &p : particles) {
uint32_t angle = rng.gen();
float angle_rad = angle * DEGREE_TO_RADIAN;
p.x += cosine(angle_rad) * p.velocity;
p.y += sine(angle_rad) * p.velocity;
}
}난수 생성기가 사용되며, 이는 템플릿 타입(RNG)일 수
있음을 알 수 있습니다. 이 실습에서는 다음 클래스의 gen()
함수로 다음 난수를 생성합니다:
struct XorShift32 {
uint32_t val;
XorShift32 (uint32_t seed) : val(seed) {}
uint32_t gen() {
val ^= (val << 13);
val ^= (val >> 17);
val ^= (val << 5);
return val;
}
};randomParticleMotion의 루프를 주의 깊게 분석하면,
XorShift32의 구현이 코드에 큰 의존성 체인을 만들어 냈다는
것을 알 수 있습니다. XorShift32의 구현은 상태를 가지며,
gen()의 반환값은 XorShift32::val의 현재 값에
의존합니다. 이제 다시 루프를 살펴보면, 앞선 반복이 모두 끝나기 전까지는
gen()이 다음에 반환할 값을 알 수 없으므로 CPU가 이후 반복을
미리 수행할 수 없다는 것을 알 수 있습니다.
다음은 원본 코드의 벤치마크 결과입니다:
----------------------------------------------------------------
Benchmark Time CPU Iterations
----------------------------------------------------------------
bench1/iterations:200 19.4 ms 19.4 ms 200해결책
gen()의 의존성 체인은 비트 연산 명령어 여섯 개에
불과하므로, 루프를 수동으로 펼치기만 해도 처리 속도를 높일 수
있습니다:
template <class RNG>
void randomParticleMotion(std::vector<Particle>& particles, uint32_t seed) {
RNG rng(seed);
for (int i = 0; i < STEPS; i++) {
auto sz = particles.size();
for (int j = 0; j + 1 < sz; j += 2) {
uint32_t angle1 = rng.gen();
float angle_rad = angle1 * DEGREE_TO_RADIAN;
particles[j].x += cosine(angle_rad) * particles[j].velocity;
particles[j].y += sine(angle_rad) * particles[j].velocity;
uint32_t angle2 = rng.gen();
float angle_rad2 = angle2 * DEGREE_TO_RADIAN;
particles[j+1].x += cosine(angle_rad2) * particles[j+1].velocity;
particles[j+1].y += sine(angle_rad2) * particles[j+1].velocity;
}
if (sz % 2) {
uint32_t angle = rng.gen();
float angle_rad = angle * DEGREE_TO_RADIAN;
particles[sz-1].x += cosine(angle_rad) * particles[sz-1].velocity;
particles[sz-1].y += sine(angle_rad) * particles[sz-1].velocity;
}
}
}보너스 해결책
위의 해결책에서는 의존성 체인이 꽤 짧았기 때문에 루프를 수동으로 펼칠
수 있었습니다. XorShift32::gen()의 원래 의존성 체인은
명령어 여섯 개(몇 가지 비트 연산) 길이에 불과했습니다. 체인이 훨씬 더
복잡한 상황에서는 루프를 펼쳐도 이점을 얻을 수 없습니다. 전체 명령어
수가 CPU가 앞으로 실행될 명령어로서 (예약 스테이션에서)
물리적으로 볼 수 있는 개수를 초과하기 때문입니다.
이러한 상황에서는 gen() 안에서 의존성 체인들을 함께
인터리빙하도록 XorShift32를 다시 작성해야
합니다.
논리는 다음과 같습니다:
체인을 두 개 만들기로 정했다고 합시다. 이 경우 한 번에 두
개의 난수를 생성하게 됩니다. 기본적으로 현재 gen()에
있는 모든 코드 줄을 가져와 두 번째 난수를 위해 복제합니다. 그러나 이
줄들은 반드시 인터리빙되어야 합니다:
int val1 = 0, int val2 = 0;
...
// WRONG - all the operations done on `val1` come before `val2`
val1 = doSomething(val1);
val1 = doSomethingElse(val1);
val2 = doSomething(val2);
val2 = doSomethingElse(val2);
...
// CORRECT - the operations on `val1` and `val2` are interleaved
val1 = doSomething(val1);
val2 = doSomething(val2);
val1 = doSomethingElse(val1);
val2 = doSomethingElse(val2);이렇게 변경한 후의 난수 생성기는 다음과 같은 모습이 될 수 있습니다:
/// Lightweight Pair class - the overheads of std::pair are unnecessary here
template<typename First, typename Second>
struct Pair {
First first;
Second second;
};
struct XorShift32 {
Pair<uint32_t, uint32_t> val;
XorShift32 (uint32_t seed) {
val.first = seed;
uint32_t second = val.first;
second ^= (second << 13);
second ^= (second >> 17);
second ^= (second << 5);
val.second = second;
}
auto gen() {
val.first ^= (val.first << 13);
val.second ^= (val.second << 13);
val.first ^= (val.first >> 17);
val.second ^= (val.second >> 17);
val.first ^= (val.first << 5);
val.second ^= (val.second << 5);
return val;
}
};randomParticleMotion의 루프는 다음과 같이 다시 작성할 수
있습니다:
template <class RNG>
void randomParticleMotion(std::vector<Particle>& particles, uint32_t seed) {
RNG rng(seed);
for (int i = 0; i < STEPS; i++) {
auto sz = particles.size();
for (int j = 0; j + 1 < sz; j += 2) {
Pair<uint32_t, uint32_t> angle = rng.gen();
float angle_rad = angle.first * DEGREE_TO_RADIAN;
particles[j].x += cosine(angle_rad) * particles[j].velocity;
particles[j].y += sine(angle_rad) * particles[j].velocity;
float angle_rad2 = angle.second * DEGREE_TO_RADIAN;
particles[j+1].x += cosine(angle_rad2) * particles[j+1].velocity;
particles[j+1].y += sine(angle_rad2) * particles[j+1].velocity;
}
if (sz % 2) {
Pair<uint32_t, uint32_t> angle = rng.gen();
float angle_rad = angle.first * DEGREE_TO_RADIAN;
particles[sz-1].x += cosine(angle_rad) * particles[sz-1].velocity;
particles[sz-1].y += sine(angle_rad) * particles[sz-1].velocity;
}
}
}이 경우에는 이 방법으로 성능상 이점을 거의 얻지 못하지만,
rng.gen()의 의존성 체인이 극히 짧으므로 이는 예상된
결과입니다. 그러나 의존성 체인의 영향을 받는 대부분의 코드에서는 체인이
이렇게 단순하지 않으므로, 실제 상황 대부분에서는 이 보너스 기법을 알아
두는 것이 꼭 필요합니다!