CPU-GPU 이기종 플랫폼에서 하둡 맵리듀스의 가속: CKY 파서 사례 분석 정보과학회논문지: 컴퓨팅의 실제 및 레터 제20권 제6호, 2014.6, 329-338 15.03.31 CSLAB Park Se Won

Contents Method Idea Experiment Summary Hadoop Pipes CUDA CKY parser 정적분할 입력 전처리를 통한 부하 균등 GPU 커널의 동적 수행 Experiment 동종수행 이기종 수행 Summary

Method Method Hadoop pipes CUDA CKY parser

Hadoop pipes Map/ Reduce Task Child JVM C++ wrapper Library Input key/value launch Child Map/ Reduce Task C++ Map/Reduce class TaskTracker socket Output key/value 그림 1 하둡 파이프의 실행 모델

Hadoop pipes(1) #include <hadoop/Pipes.h> #include <cutil.h> Class mapper: public HadoopPipes::Mapper{ public: void map(MapContext context){ d_abc = cudaMalloc(); cudaMemcpy(d_abc,h_abc,H2D); PaserGPU<<blocks,threads>>(d_abc); cudaMemcpy(h_abc,d_abbc<H2D); cudaFree(d_abc); } 그림 3 하둡 맵리듀스에서 GPU 매퍼

Hadoop pipes(2) #define SPLIT_SLOP 1.1 public InputSplit[] getSplits(JObConf job, int numSplits){ totalSize = file.getLen() goalSize = totalSize/numSplits bytesRemaining = totalSize while(bytesRemaining/goalSize > SPLIT_SLOP){ splits.add(new FileSplit(file.path, totalSize - bytesRemaining, goalSize)) bytesRemaining -= goalSize } ... return splits

Hadoop pipes(3) #define SPLIT_SLOP 1.1 public InputSplit[] getSplits(JObConf job, int numSplits){ totalSize = file.getLen() cpu_totalSize = totalSize * pf gpu_totalSize = totalSize – cpu_totalSize num_gpu_maptask = num_nodes num_cpu_maptask = numSplits – num_gpu_maptask cpu_goalSize = cpu_totalSize / num_cpu_maptask gpu_goalSize = gpu_totalSize / num_gpu_maptask cnt = 0 splitSize = gpu_goalSize bytesRemaining = totalSize #define SPLIT_SLOP 1.1 public InputSplit[] getSplits(JObConf job, int numSplits){ totalSize = file.getLen() goalSize = totalSize/numSplits bytesRemaining = totalSize

Hadoop pipes(4) while(bytesRemaining/goalSize > SPLIT_SLOP){ if( cnt % max_maptask !=0){ splitSize = cpu_goalSize offset = cpu_offset + (cpu_totalSize – cpu_bytesRemaining) cpu_bytesRemaining -= splitSize }else{ splitSize = gpu_goalSize offset = fpu_offset + (gpu_totalSize – gpu_bytesRemaining -= splitSize } splits.add(new FileSplit(file.path, totalSize - bytesRemaining, goalSize)) bytesRemaining -= cpu_bytesRemaining + gpu_bytesRemaining cnt++ ... return splits while(bytesRemaining/goalSize > SPLIT_SLOP){ splits.add(new FileSplit(file.path, totalSize - bytesRemaining, goalSize)) bytesRemaining -= goalSize } ... return splits

CUDA

CKY parser Cocke-Kasami-Younger, CKY 특정한 문자열에 대해 어떠한 방식으로 생성되는지를 판단하는 파싱 알고리즘 문법에 포함된 규칙의 수: G 문장의 단어 수 n O(|G| 𝑛 2 ) 복잡도

Idea Idea 정적분할 입력 전처리를 통한 부하 균등 GPU 커널의 동적 수행

Environment CPU 2 * Intel Xeon E5-2630 (6 cores @ 2.3GHz) GPU Tesla K20c (2496 cores @ 0.71 GHz) Host Memory 64 GB Device Memory 5 GB System specification WC Bytes CPU(ms) GPU(ms) Sp. Up Min 1 8 3 5 0.6 Max 47 298 36398 937 43.31 Avg 22.6 124.3 6650.5 205.6 26.16 입력 문장들에 대한 정보

노드 수 증가에 따른 가속 정도

노드 당 매퍼 수에 따른 영향 𝑡𝑖𝑚𝑒 |#𝑚𝑎𝑝𝑝𝑒𝑟=12 𝑡𝑖𝑚𝑒 |#𝑚𝑎𝑝𝑝𝑒𝑟=1

. . . 노드 당 매퍼 수에 따른 영향 노드 당 매퍼 증가  I/O 병목 발생 Mapper Mapper Mapper Hard or Memory

정적분할 𝑝𝑓= 𝑛 ∗𝑐𝑝𝑢 𝑛 ∗𝑐𝑝𝑢+𝑚 ∗𝑔𝑝𝑢 전체 입력 중 CPU 매퍼 군이 처리하는 입력의 비율(partition factor) n: CPU 매퍼 수 m: GPU 매퍼 수 cpu: 하나의 CPU매퍼가 처리하는 입력의 양 gpu: 하나의 GPU매퍼가 처리하는 입력의 양 최적의 성능: pf에 의한 양보다 더 낮게 설정

입력 전처리를 통한 부하 균등 단어 수에 의해 정렬 GPU1 부하 불균형 GPU2 pf CPU1 CPU2

입력 전처리를 통한 부하 균등 Interleaving 단어 수에 의해 정렬 GPU1 GPU2 pf CPU1 CPU2

GPU 커널의 동적 수행 CPU Mapper가 GPU Mapper에게 처리할 문장 전달 불가 Mapper 통신불가

GPU 커널의 동적 수행 GPU CPU Memory Mapper MODE = CPU wc = word_count(input_sentence) If(MODE != GPU && wc < threshold) Parser_CPU(input) else Parser_GPU(input) 단어 개수가 역치 미만이면 CPU 그렇지 않은 경우GPU

Idea Experiment 동종 수행 이기종 수행

동종 수행(Homogeneous Execution) 단일 노드 CPU 수행 단일 노드 GPU 수행 하둡 맵리듀스 이용, 14개 노드 Hadoop XXX(#매퍼) 노드 증가 노드 당 매퍼 증가 12*14 = 168 23*14 = 322

이기종 수행(Heterogeneous Execution) -8.86% 0% 3.16% 12.66%

Summary Ver. 1~3 CPU 매퍼 11개, GPU 매퍼 1개 Ver. 1: 정적 분할 이용 (pf) Ver. 2: Input을 단어 수대로 정렬 후 인터리빙 방식으로 매퍼에 할당 Ver. 3: Input을 정렬하지 않고 pf 기반으로 정적으로 분할 후 CPU 매퍼에서 입력에 따라 동적으로 수행  Ver .1 의 pf 값 이용

How to use GPU for Hadoop? CPU + GPU Summary How to use GPU for Hadoop? CPU + GPU