병렬처리 단계별 과정
예제 프로그램
병렬처리 예제로 사용할 프로그램은 ks로 그래프 분할 알고리즘을 구현한 프로그램입니다. 대부분의 수행시간은 FindMaxGpAndSwap에서 소모되는데, 이 함수는 doubly-nested linked list를 따라 정해진 연산과 그 최대값을 찾는 일을 수행합니다.
LVM Bitcode 생성
LLVM 툴을 이용하여 C 코드를 LLVM IR로 구성된 bitcode로 변환합니다. 파일이 여러 개인 경우, 이를 묶어 하나의 bitcode 파일로 만듭니다. 또한 그 코드를 실행하여, 각 기본 블럭에 대해 수행 회수를 파악합니다(Profiling).
자동 병렬처리
병렬처리 컴파일러를 수행합니다. 우선 Program Dependence Graph(PDG)를 생성한 후, DSWP와 PS-DSWP를 이용하여 PDG를 분할합니다. Multi-Threaded Code Generator(MTCG)를 이용하여 병렬처리된 multi-threaded LLVM IR를 출력합니다. 이 결과물은 queue library, thread pool library와 link되어 실행 프로그램을 생성합니다.
Program Dependence Graph
자동 병렬처리 단계 중에 많은 그래프가 생성되여, 개발자들이 프로그램을 이해하는 데 도움을 줍니다. 그 중 하나는 Program Dependence Graph (PDG)로 병렬처리될 순환문에 있는 각 명령어들 사이의 data와 control 의존관계를 보여줍니다. 다른 색의 연결선은 각각 다른 의존 관계를 의미합니다.
Strongly Connected Components 그래프
이 그래프에서 각 노드는 Strongly Connected Component (SCC)로 기존 PDG 그래프에서 하나 이상의 노드들로 구성되어 있습니다. PDG 분할은 기존 PDG 노드가 아닌 이 SCC 노드에 대해 이루어집니다. 실행 순서에 따른 의존관계가 없는 SCC는 DOALL로 분류되어, 이후 PS-DSWP 분할시 병렬 수행구획(parallel stage)으로 놓여집니다.
그래프 분할
이 그래프는 PS-DSWP로 분할 된 각각의 구획들을 보여줍니다. 빨간색 구획은 순차적 수행 구획을, 초록색 구획은 병렬 수행 구획을 의미합니다. PS-DSWP는 수행 속도를 최대화하기 위해, 가급적 많은 부분을 병렬 수행 구획으로 분류합니다.
순차적 프로그램 실행
연산 속도를 비교하기 위해, 기존의 C 코드를 gcc를 이용하여 컴파일한 후 실행합니다. (기존 프로그램과 병렬처리된 프로그램을 비교하기 위해, 다음 비디오와 함께 보시는 것을 권장합니다.)
병렬 프로그램 실행
8-core에서 병렬처리된 프로그램 수행시간은 약 16.5초로 기존 프로그램의 74초에 비해 약 4.5배 빠릅니다. 이처럼, 저희 툴을 이용하여 기존 프로그램을 수정하지 않고, 실제 컴퓨터에서 상당한 성능향상을 얻을 수 있습니다.