Dynamic-II Pipeline: Compiling Loops With Irregular Branches on Static-Scheduling CGRA
| Autor: | Jianfeng Zhu, Leibo Liu, Shaojun Wei, Baofen Yuan, Xingchen Man, Shouyi Yin, Zijiao Ma |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Loop (graph theory)
business.industry Computer science Pipeline (computing) Parallel computing Computer Graphics and Computer-Aided Design Scheduling (computing) Reduction (complexity) Software Path (graph theory) Graph (abstract data type) Electrical and Electronic Engineering business Compile time |
| Zdroj: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 41:2929-2942 |
| ISSN: | 1937-4151 0278-0070 |
| Popis: | Coarse-grained reconfigurable architecture (CGRA) is a promising programmable hardware with high power-efficiency and high performance. However, compiling and optimizing loops with irregular branches on CGRAs is a challenge to fulfill the performance potential. Existing predication techniques, such as partial predication (PP) and full predication (FP), conservatively implement software pipeline with a static initiation interval (II) obtained from the maximum graph, and thus only parts of the graph in each loop iteration will be actually executed, resulting in underexploited performance. To exploit more loop-level parallelism for irregular branches, this paper proposes a novel dynamic-II pipeline (DIP) scheme, which realizes a pipeline with variable II by accommodating multiple iterations of short path in one static configuration. Since the DIP scheme is effective to only certain types of branches, this paper designs a hybrid compilation framework integrating other complementary methods, which selects appropriate method for source programs according to a proposed performance evaluation model. Experimental results show that 1) the hybrid compilation framework can effectively extract branch features, correctly choose and implement corresponding branch processing methods within acceptable compile time, 2) as compared to PP and FP, DIP brings a significant total execution time (TET) reduction by 27.21% and 22.04% on average when execution probability of short branch is 50%. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|