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버전이다.

Story 01. 프로그래머가 프로세서도 알아야 해요? - 병렬 프로그래밍의 중요성이 대두 되면서 하드웨어를 exploit해야 할 필요성이 커짐. - 소프트웨어 개발에 쓰일 수 있는 다양한 알고리즘 / 아이디어를 습득할 수 있음. Story 02. 프로세서의 언어 : 명령어 집합 구조 (ISA) CISC의 탄생  - 범용 목적 마이크로 프로세서가 처음 나온 1970년대에는 컴파일러의 도움이 크지 못했다. -> 다양한 기능을 제공  - 그리고 메모리가 비싸고 부족했다. -> 짧은(가변) 길이의 명령어 형태  - 그래서 최초의 ISA는 CISC형태를 띔. RISC의 탄생  - CISC의 명령어들 중 자주 사용되는 것은 일부분에 불과했다.  - 제한되고 간단한 형태의 명령어들만 제공함으로서 더 저렴하다. 혹은 다른 것에 트랜지스터들을 투자 가능.  - Make Common Case Fast RISC vs CISC  - RISC는 하드웨어의 복잡함을 컴파일러나 프로그래머에 넘겼다. (레지스터 수가 많고 하드웨어 구현이 더 간단, 슈퍼컴퓨터에 적합)  - CISC는 프로그램의 복잡함을 하드웨어가 도맡아 처리한다.  - 이제는 RISC와 CISC경계가 모호해졌다. CISC인 x86의 경우 CISC 명령어를 내부적으로 micro-op으로 쪼개서 처리한다. (겉은 CISC, 속은 RISC) Story 03. 프로세서의 기본 부품과 개념들 마이크로 아키텍처 : 마이크로 프로세서 하나를 만드는 데 필요한 알고리즘 및 회로 수준의 구조를 자세히 정의 한 것. Story 04. 암달의 법칙과 프로세서의 성능 지표 성능 향상을 위해 해야 할 일 - 명령어 개수 N을 줄이자    * 컴파일러 최적화 : Common Sub-expression Elimination, Constant Propagation, Dead Store El...