基于多面体模型的数据依赖分析方法

doi:10.3969/j.issn.1674-1579.2015.03.009

空间控制技术与应用 ›› 2015, Vol. 41 ›› Issue (5): 43-.doi: 10.3969/j.issn.1674-1579.2015.03.009

基于多面体模型的数据依赖分析方法

出版日期:2015-10-24 发布日期:2015-12-01

DataDependence Analysis Method Based on Polyhedral Model

Online:2015-10-24 Published:2015-12-01

摘要/Abstract

摘要： 设计一种基于多面体模型的静态数据依赖分析方法，对程序中的循环体进行分析，将生存周期思想引入到数据的依赖分析中.数据的依赖关系中只有流依赖是无法消除的固有依赖，必须保持变换前的执行顺序，而输出依赖和反依赖可以通过标量扩展及向前替换等方法消去.对传统数据依赖分析进行改进，通过分析内存单元的生存周期，摒除不必要的伪依赖，从而可以对更多的循环体进行变换.通过实验表明了该方法的可行性和有效性.

关键词: 依赖分析, 多面体模型, 生存周期, 循环变换

Abstract: A static datadependence analysis method for loops based on polyhedral model is designed. The concept of live range is introduced into analysis. Only flow dependences must keep consistent with the order that they appears in the original execution of the program. Output dependences and antidependences can be eliminated by scalar expansion or forward substitution. This analysis method reforms the traditional analysis by introducing live range and eliminating unnecessary false dependence, via which more loops can be transformed. The validity and efficiency of the presented method are demonstrated by experiment．

Key words: dependence analysis, polyhedral model, live range, loop transformation

中图分类号:

李川, 陈朝晖. 基于多面体模型的数据依赖分析方法[J]. 空间控制技术与应用, 2015, 41(5): 43-.

LI Chuan, CHEN Chao-Hui. DataDependence Analysis Method Based on Polyhedral Model[J]. , 2015, 41(5): 43-.

参考文献

［1］GIRBAL S, VASILACHE N BASTOUL C, et al. Semiautomatic composition of loop transformations for deep parallelism and memory hierarchies［J］. International Journal of Parallel Programming, 2006,34(3):261317. ［2］SIMBüRGER A, APEL S, GRLINGER A, et al. The potential of polyhedral optimization［C］//Automated Software Engineering (ASE), IEEE International Conference. New York: IEEE, 2013：1115. ［3］ALNAELI S M, ALALI A, MALETIC J I. Empirically examining the parallelizability of open source software systems［C］//Reverse Engineering, 2012 19th Working Conference. New York: IEEE, 2012:377386. ［4］TRIFUNOVIC K, COHEN A. Enabling more optimizations in GRAPHITE: ignoring memorybased dependences［C］// Proceddings of the 8th GCC Developper’s Summit. Ottawa, Canada: GNU: 2010:129142. ［5］BAGHDADI R, COHEN A, VERDOOLAEGE S, et al. Improved loop tiling based on the removal of spurious false dependences［J］. ACM Transactions on Architecture and Code Optimization, 2013,9(4):5253. ［6］VASILACHE N, MEISTER B, HARTONO A, et al. Trading off memory for parallelism quality［C］// International Workshop on Polyhedral Compilation Techniques. Paris, France: IMPACT, ACM TACO: 2012. ［7］MIDKIFF S P. Automatic parallelization: an overview of fundamental compiler techniques［J］. Synthesis Lectures on Computer Architecture, 2012,7(1):1169. ［8］POP S, COHEN A, BASTOUl C, et al. GRAPHITE: Polyhedral analyses and optimizations for GCC［C］//Proceedings of the 2006 GCC Developers Summit, Ottawa, Canada: GNU, 2006:179197. ［9］VERDOOLAEGE S. isl: An integer set library for the polyhedral model［C］//ICMS’10 Proceedings of the Third International Congress Conference on Mathematical Software Berlin,

基于多面体模型的数据依赖分析方法

DataDependence Analysis Method Based on Polyhedral Model

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 0