Front Page

The Liberty Research Group

병렬처리 단계별 과정

예제 프로그램

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

병렬처리 예제로 사용할 프로그램은 ks로 그래프 분할 알고리즘을 구현한 프로그램입니다. 대부분의 수행시간은 FindMaxGpAndSwap에서 소모되는데, 이 함수는 doubly-nested linked list를 따라 정해진 연산과 그 최대값을 찾는 일을 수행합니다.

LVM Bitcode 생성

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

LLVM 툴을 이용하여 C 코드를 LLVM IR로 구성된 bitcode로 변환합니다. 파일이 여러 개인 경우, 이를 묶어 하나의 bitcode 파일로 만듭니다. 또한 그 코드를 실행하여, 각 기본 블럭에 대해 수행 회수를 파악합니다(Profiling).

자동 병렬처리

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

병렬처리 컴파일러를 수행합니다. 우선 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

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

자동 병렬처리 단계 중에 많은 그래프가 생성되여, 개발자들이 프로그램을 이해하는 데 도움을 줍니다. 그 중 하나는 Program Dependence Graph (PDG)로 병렬처리될 순환문에 있는 각 명령어들 사이의 data와 control 의존관계를 보여줍니다. 다른 색의 연결선은 각각 다른 의존 관계를 의미합니다.

Strongly Connected Components 그래프

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

이 그래프에서 각 노드는 Strongly Connected Component (SCC)로 기존 PDG 그래프에서 하나 이상의 노드들로 구성되어 있습니다. PDG 분할은 기존 PDG 노드가 아닌 이 SCC 노드에 대해 이루어집니다. 실행 순서에 따른 의존관계가 없는 SCC는 DOALL로 분류되어, 이후 PS-DSWP 분할시 병렬 수행구획(parallel stage)으로 놓여집니다.

그래프 분할

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

이 그래프는 PS-DSWP로 분할 된 각각의 구획들을 보여줍니다. 빨간색 구획은 순차적 수행 구획을, 초록색 구획은 병렬 수행 구획을 의미합니다. PS-DSWP는 수행 속도를 최대화하기 위해, 가급적 많은 부분을 병렬 수행 구획으로 분류합니다.

순차적 프로그램 실행

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

연산 속도를 비교하기 위해, 기존의 C 코드를 gcc를 이용하여 컴파일한 후 실행합니다. (기존 프로그램과 병렬처리된 프로그램을 비교하기 위해, 다음 비디오와 함께 보시는 것을 권장합니다.)

병렬 프로그램 실행

To play the video here in the webpage, please install Adobe Flash.

Click here to download the video.

8-core에서 병렬처리된 프로그램 수행시간은 약 16.5초로 기존 프로그램의 74초에 비해 약 4.5배 빠릅니다. 이처럼, 저희 툴을 이용하여 기존 프로그램을 수정하지 않고, 실제 컴퓨터에서 상당한 성능향상을 얻을 수 있습니다.