Publications

Detailed Information

Advanced compilation issues for Coarse-Grained Reconfigurable Architecture (CGRA) : 재구성형프로세서를위한 고급 컴파일 기법

DC Field Value Language
dc.contributor.advisor백윤흥-
dc.contributor.authorYongjoo Kim-
dc.date.accessioned2017-07-13T06:55:51Z-
dc.date.available2017-07-13T06:55:51Z-
dc.date.issued2012-08-
dc.identifier.other000000005192-
dc.identifier.urihttps://hdl.handle.net/10371/118875-
dc.description학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2012. 8. 백윤흥.-
dc.description.abstract재구성형 프로세서는 소프트웨어 적으로 프로그래밍이 가능하면서도 최대 10-100 MOps/mW 의 성능을 낼 수 있는 유망한 플랫폼이다. 하지만 그 유망함은 응용을 재구성형 프로세서 플랫폼에 얼마나 효율적으로 매핑 하느냐에 달려 있다. 기존의 연구들은 재구성형 프로세서의 계산 성능 향상에 뛰어난 성과를 이룩하였지만 아직도 풀어야 할 문제가 많은 실정이다.
여러가지 남아있는 문제들 중 재구성형 프로세서를 위한 데이터 매핑 알고리즘은 더 강력한 성능을 얻기 위해 꼭 풀어야할 중요한 문제이다. 이 논문에서는 메모리를 고려한 응용 매핑이 필요한 당위성을 고찰하고, 메모리 크기, 메모리 구조, 통신 구조 등을 고려한 효율적인 응용 매핑 방법을 제안 하였다. 거기에 더블 버퍼링(double-buffering)을 이용하여 메모리의 데이터를 관리하는 경우, 타겟 룹에 data dependency가 있을 경우 데이터 관리가 어려운데, 이를 위한 효율적인 데이타 관리 기법을 제안하였다. 또한 메모리 성능을 최적화 하기 위한 코드 최적화 기법도 제안하였다.
파이프라이닝 알고리즘은 일반적으로 steady-state의 성능, 즉 커널의 수행시간을 향상시키기 위해서 사용된다. 파이프라인 셋업 타임은 일반적으로 커널의 수행시간에 비해서 무시 가능할 정도로 작다고 여겨진다. 하지만 메인 프로세서의 보조 프로세서로 쓰이는 재구성형 프로세서의 경우 빠른 계산 수행능력으로 인해 이 셋업 타임이 상대적으로 훨씬 길 수 있다. 그리고 작은 룹이 큰 외부 룹에 의해서 반복 될 경우, 매번 내부 룹을 수행할 때 마다 파이프라인을 셋업해야 하므로 셋업을 위한 통신시간이 전체 수행시간 중 큰 비중을 차지할 수 있다. 여기서는 중첩된 룹을 수행할 경우에 kernel 룹 이외의 수행시간에 대해서 분석을 하였고, 이 overhead를 줄일 수 있는 새로운 아키택처-컴파일러 협동 수행 방법을 제안하였다. 이 제안된 방식은 추가적으로 재구성형 프로세서의 configuration의 크기도 줄여주었다.
재구성형 프로세서는 현재 사용하고 있는 매핑 알고리즘에 문제가 있었다. 기존의 알고리즘은 재구성형 프로세서의 크기를 늘릴 경우 효율적으로 늘린 자원을 사용하지 못하였다. 나는 이 문제를 해결하기 위해 SIMD paradigm을 사용하여 매핑 알고리즘을 확장 하였다. 기존의 매핑 알고리즘에 SIMD paradigm을 적용하는 것은 기존의 operation mapping과 data mapping 이외에도 룹의 iteration을 각 core에 매핑하는 문제까지 동시에 풀어야 하는 것이 된다. 이 논문에서는 코드의 여러 레벨에서 SIMD mapping을 할 수 있는 SIMD 재구성형 프로세서를 제안하였고 주요한 성능 저하의 원인이 되는 local 메모리 bank 충돌 문제를 해결하는 스케쥴링 알고리즘을 제안하였다. 또한 스케쥴링 알고리즘과 연동하여 bank 충돌 문제를 효율적으로 줄일 수 있는 data tiling 방법을 제안하였다.
-
dc.description.abstractCoarse-Grained Reconfigurable Array architectures (CGRAs) are a very promising platform, providing both up to 10-100 MOps/mW of power efficiency and software programmability. However, this promise of CGRAs critically hinges on the effectiveness of application mapping onto CGRA platforms. While previous solutions have greatly improved the computation speed, there is still a lot of problems.
One major challenge comes in the form of data mapping. This thesis motivates the need for memory-aware application mapping for CGRAs, and proposes an effective solution for application mapping that considers the effects of various memory architecture parameters including the number of banks, local memory size, and the communication bandwidth between the local memory and the external main memory. Further I propose efficient methods to handle dependent data on a double-buffering local memory, which is necessary for recurrent loops. In addition to these, I propose a code optimization technique for higher memory performance.
Pipelining algorithms are typically concerned with improving only the steady-state performance, or the kernel time. The pipeline setup time happens only once and therefore can be negligible compared to the kernel time. However, for CGRAs used as a coprocessor to a main processor, pipeline setup can take much longer due to the communication delay between the two processors, and can become significant if it is repeated in an outer loop of a loop nest. I evaluate the overhead of such non-kernel execution times when mapping nested loops for CGRAs, and propose a novel architecture-compiler cooperative scheme to reduce the overhead, while also minimizing the number of extra configurations required.
CGRAs have a problem that current mapping algorithms for it do not scale well with the number of cores. One approach to this problem is using SIMD (Single Instruction Multiple Data) paradigm. However, SIMD can complicate the mapping problem by adding an additional dimension, i.e., iteration mapping, to the already interdependent problems of data mapping and operation mapping, and can significantly affect performance through memory bank conflicts. In this thesis I introduce SIMD reconfigurable architecture, which allows for SIMD mapping at multiple levels of granularity, and investigate ways to minimize bank conflicts in a SIMD reconfigurable architecture with the related sub-problems taken into consideration. I further present data tiling and evaluate a conflict-free scheduling algorithm as a way to eliminate bank conflicts for a certain class of iteration and data mapping.
-
dc.description.tableofcontentsAbstract i
Chapter 1 Introduction 1
1.1 Demand on high performance and power-efficiency . . . . . . . . . . 1
1.2 CGRA architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Compilation for CGRA . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.1 Architecture Focus . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.2 Compilation Focus . . . . . . . . . . . . . . . . . . . . . . . 6
Chapter 2 Memory Access Optimization 8
2.1 Background on target CGRA . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Target Memory Architecture . . . . . . . . . . . . . . . . . . 10
2.1.2 Execution Model and Application Mapping . . . . . . . . . . 12
2.2 Problem of Memory Aware Mapping . . . . . . . . . . . . . . . . . . 14
2.3 Conflict Avoidance: Eliminating Bank Conflicts . . . . . . . . . . . . 15
2.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Array Clustering . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Conflict Free Scheduling . . . . . . . . . . . . . . . . . . . . 21
2.4 Load Reduction: Removing Memory Operations . . . . . . . . . . . . 26
2.4.1 Optimization Opportunity . . . . . . . . . . . . . . . . . . . 26
2.4.2 Graph Transformation . . . . . . . . . . . . . . . . . . . . . 29
2.4.3 Routing Reuse Edge . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.2 Effectiveness of Conflict Avoidance Only . . . . . . . . . . . 33
2.5.3 Effectiveness of Load Reduction . . . . . . . . . . . . . . . . 37
2.5.4 Effectiveness of Our Combined Compiler Approach . . . . . 39
2.5.5 Effect of Using DMQ with Our Approach . . . . . . . . . . . 40
Chapter 3 Data Mapping for multi-bank memory 43
3.1 Target Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3 Simultaneous Data and Computation Mapping . . . . . . . . . . . . . 48
3.3.1 Balancing Computation and Data Transfer . . . . . . . . . . . 49
3.3.2 Maximizing Data Reuse . . . . . . . . . . . . . . . . . . . . 49
3.3.3 Balancing Bank Utilization . . . . . . . . . . . . . . . . . . . 53
3.4 Handling Recurrent Loops . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.2 Proposed Methods . . . . . . . . . . . . . . . . . . . . . . . 55
3.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.2 Efficiency of Our Memory-Aware Mapping . . . . . . . . . . 61
3.5.3 Partial Shutdown Exploration . . . . . . . . . . . . . . . . . 62
3.5.4 Effect of Memory Bandwidth and Register Files . . . . . . . 65
3.5.5 Recurrent Loop Overhead Reduction . . . . . . . . . . . . . 66
Chapter 4 Improving Performance of Nested Loops 69
4.1 Previous Pipelining approaches . . . . . . . . . . . . . . . . . . . . . 71
4.2 Single-Loop Pipelining for CGRA . . . . . . . . . . . . . . . . . . . 73
4.2.1 CGRA Architecture . . . . . . . . . . . . . . . . . . . . . . 73
4.2.2 Single-Loop Pipelining . . . . . . . . . . . . . . . . . . . . . 74
4.3 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4 Nested Loop Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4.1 Baseline: ILP + SW Outerloop . . . . . . . . . . . . . . . . . 81
4.4.2 ILP + HW Outerloop . . . . . . . . . . . . . . . . . . . . . . 82
4.4.3 Outerloop Pipelining . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . 92
4.5.2 Performance Improvement . . . . . . . . . . . . . . . . . . . 93
4.5.3 Effect of Communication Latency . . . . . . . . . . . . . . . 96
4.5.4 Trip Count Effect . . . . . . . . . . . . . . . . . . . . . . . . 98
4.5.5 Energy Reduction . . . . . . . . . . . . . . . . . . . . . . . . 98
4.5.6 Configuration Size . . . . . . . . . . . . . . . . . . . . . . . 101
Chapter 5 Exploiting Both Pipelining and Data Parallelism with SIMD
RA 103
5.1 Previous SIMD approaches . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 SIMD Reconfigurable Architecture . . . . . . . . . . . . . . . . . . . 106
5.2.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.2.2 Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.3 Minimizing Bank Conflicts in SIMD Mapping . . . . . . . . . . . . . 109
5.3.1 Microcore Mapping . . . . . . . . . . . . . . . . . . . . . . 110
5.3.2 Macrocore Mapping . . . . . . . . . . . . . . . . . . . . . . 113
5.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.4.1 Effect of SIMD Mapping: Performance and Configuration Size 116
5.4.2 Macrocore Mapping Comparisons . . . . . . . . . . . . . . . 117
5.4.3 Compilation Time . . . . . . . . . . . . . . . . . . . . . . . 119
Chapter 6 Conclusions 120
Bibliography 123
초록 134
-
dc.formatapplication/pdf-
dc.format.extent5721436 bytes-
dc.format.mediumapplication/pdf-
dc.language.isoen-
dc.publisher서울대학교 대학원-
dc.subjectCGRA-
dc.subjectreconfigurable architecture-
dc.subjectcompiler-
dc.subjectoptimization-
dc.titleAdvanced compilation issues for Coarse-Grained Reconfigurable Architecture (CGRA)-
dc.title.alternative재구성형프로세서를위한 고급 컴파일 기법-
dc.typeThesis-
dc.contributor.AlternativeAuthor김용주-
dc.description.degreeDoctor-
dc.citation.pagesxiii, 135-
dc.contributor.affiliation공과대학 전기·컴퓨터공학부-
dc.date.awarded2012-08-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share