Taeguk's Blog

안녕하세요. 오늘은 제가 예전에 HPX 라는 오픈소스에 구현했던 parallel partition 알고리즘에 대해 간단히 소개하고 설명하는 시간을 가져보도록 하겠습니다. 출처 먼저 이 포스팅에서 다루는 알고리즘/코드의 출처는 다음과 같습니다. HPX : https://github.com/STEllAR-GROUP/hpx 관련 MR : https://github.com/STEllAR-GROUP/hpx/pull/2778 소스코드 : https://github.com/STEllAR-GROUP/hpx/blob/master/hpx/parallel/algorithms/partition.hpp 소개 parallel partition 알고리즘은 여러 개의 연산 유닛 (쉽게 말하면 cpu) 들을 이용해서 partition 알고리즘을 수행하는 것을 말합니다. 이 포스팅에서는 독자가 partition 알고리즘에 대해서 이미 알고있다고 가정합니다. partition 알고리즘에 대한 설명은 cppreference 를 참고하시기 바랍니다. 알고리즘 설명 partition 알고리즘은 주어진 영역을 정해진 규칙을 만족하는지 아닌지에 따라 두 영역으로 분류하는 알고리즘입니다. 예를 들어, 짝수인지 여부에 대해 partition 알고리즘을 수행한다고 하면 결과는 다음과 같습니다. 적용 전 : 3 5 7 4 2 1 9 8 6 적용 후 : 6 8 2 4 * 7 1 9 5 3 즉, partition 알고리즘의 핵심은 다음과 같습니다. 두 영역을 구분할 수 있는 boundary 를 찾는다. 그 boundary 의 왼쪽에는 조건을 만족하는 원소들이, 오른쪽에는 조건을 만족하지 않는 원소들이 위치하게 된다. 자, 위의 핵심을 기억하면서 parallel partition 알고리즘을 살펴보도록 합시다. 결론적으로 parallel partition 알고리즘은 크게 4단계로 이루어집니다. 주어진 영역을 여러 개의 block 으로 쪼개서 병렬로 sub-pa...

결론부터 말하면, OpenMP for loop scheduling 방법으로서 제공되는 것 중 하나인 static이 이상하게 구현된 것 같다. (거지같다) 서로 처리 시간이 같은 task들이 있을 때 이 것들을 scheduling할 때는 static이 제일 빨라야 정상이다. 근데 내가 실험을 하는데 guided가 더 빨라서, 그것도 월등히 빨라서 정말 혼란이 왔었다. static의 chunk size가 1이여서 그런가? 하고 chunk size를 늘리며 실험했더니 빠르게 작동했다. 사실 chunk size가 작으면, cache miss가 뜰 확률이 높아져서 성능이 하락하기 때문에 guided가 더 빠를 수 있다. 그러나, 좀 심각하게 느렸다. 그래서 내가 직접 static을 구현해서 실험을 다시 해보니까... 이론대로 나온다. 그래 my static처럼 결과가 나와야 정상이지... chunk size가 최대일 때는 당연히 guided보다 빨라야하고, chunk size가 최소인 1일 때는 cache miss를 고려해서 guided보다 약간 느려야 이론대로 잘 나오는 것이다. 그런데, OpenMP static은 정말 '비상식적인' 결과를 보여주고 있다... 흠.... 뭐 사실 이 case 하나만 가지고 OpenMP의 static은 쓰레기다!!! 라고 단정지을 수 없지만... 아무래도 실망스러움을 감출수가 없다....ㅠㅠ https://github.com/taeguk/dist-prog-assignment/issues/4   에 가면 좀 더 자세한 나의 한풀이를 들을 수 있다. 어쨌든, 대체 OpenMP의 static이 구체적으로 어떻게 구현되었는지 알아보고 싶다... 나중에 시간되면 binary나 까서 분석해볼까 한다... 참고로 실험에 사용한 OpenMP는 3.0버전이다.

요즘 학교 고급소프트웨어실습 (이하 고소실) 이라는 과목에서 cache friendly code를 작성하는 것을 해보고 있다. 평소에도 memory access pattern에 따라 성능 차이가 극심하게 날 수 있고 어쩌구~저쩌구~.... 개념적으로는 알고 있었지만 실제로 cache를 고려하면서 code를 작성하고, 간단한 코드를 memory access pattern을 다양하게 바꿔보면서 성능을 실험해본 것은 처음이다. 실제로 실험해보니 matrix multiplication 함수를 그냥 짰을 때랑 cache friendly하게 짰을 때 성능 차이가 극심하게 났다. (정확하게 얼마나 났는지는 기억이 안 나는데 아마 열 몇 배 빨랐던 것 같다. 기억이 틀릴 수 도 있다. ㅠㅜ 어쨌든 많이 빨라졌다..) 뭐, cache friendly code는 CPU뿐만 아니라 GPU에서도 상당히 중요하다. CUDA Programming에서, cache friendly 하지 않은 어떤 코드를 800ms정도 걸리는 걸 cache를 고려해서 수정을 하니까 200ms정도로 최적화를 시킬 수 있었다. 물론 GPU는 SIMD구조고, block, warp등 CPU와는 상당히 다른 아키텍처를 가지고 있기 때문에 CPU와는 cache friendly code를 짜는 법이 좀 차이가 났다. 어쨌든 이렇듯 cache friendly code를 작성하는 것은 상당히 중요하다. memory access pattern을 계속 고려하면서 최적화를 하는 작업은 상당히 노가다처럼 느껴지기도 하지만 참 재밌다.. 최적화쪽으로 공부를 한 번 해볼까하는 생각도 든다.. 또 한편으로 과연 그러나 이런 최적화기법들을 얼마나 실제에 적용할 수 있을 지에 대한 생각도 든다. 다른 모듈과 종속성이 별로 없는 특정 모듈이나 알고리즘들은 적용할 만하겠지만, 특정 자료구조가 예를 들어 다양한 곳에서 쓰이는 경우, 이 자료구조를 특정 memory access pattern을 가정해서 최적화하거나 하는게 ...