Heejin Ahn will present her general exam on May 21, 2015 at 1:30pm in CS 401. The members of her committee are: David August (adviser), Aarti Gupta, and Andrew Appel. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Program Approximation by Partial Loop Execution Many application domains, such as multimedia applications, simulations, and machine learning algorithms, allow opportunities to trade-off the quality of results for performance or energy improvements. Various compilation techniques have proposed to approximate program results in order to improve performance or reduce energy consumption. However, the applicability of previous work has been limited to DOALL-style loops with very regular structures. This work presents a compiler technique that transforms loops to skip parts of iterations even in the presence of loop-carried dependences or recursive data structure traversal. From a given loop iteration, we use compiler analysis to identify computations that are essential for the loop to continue, and skip or use memoized results for the remaining non-critical computations at a configured frequency. As a result, this work provides similar speedup with previous techniques while being applicable to a wider range of loops.
1 Reading List 1.1 Textbooks • A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 • J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach, Fourth Edition. Morgan Kaufmann, 2006 1.2 Software-only Approximation • J. Liu, W.-K. Shih, K.-J. Lin, R. Bettati, and J.-Y. Chung. Imprecise computations. Proceedings of the IEEE, 82(1):83–94, Jan 1994 • M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In Proceedings of the 20th Annual International Conference on Supercomputing, ICS ’06, pages 324–334, New York, NY, USA, 2006. ACM • W. Baek and T. M. Chilimbi. Green: A framework for supporting energy-conscious programming using controlled approximation. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 198–209, 2010 • S. Sidiroglou-Douskos, S. Misailovic, H. Hoffmann, and M. Rinard. Managing performance vs. accuracy tradeoffs with loop perforation. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE ’11, pages 124–134, New York, NY, USA, 2011. ACM • S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. ACM Trans. Embed. Comput. Syst., 12(2s):88:1–88:26, May 2013 • M. Samadi, D. A. Jamshidi, J. Lee, and S. Mahlke. Paraprox: Pattern-based approximation for data parallel applications. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’14, pages 35–50, New York, NY, USA, 2014. ACM • S. Campanoni, G. Holloway, G.-Y. Wei, and D. Brooks. Helix-up: Relaxing program semantics to unleash parallelization. In Code Generation and Optimization (CGO), 2015 IEEE/ACM International Symposium on, pages 235–245, Feb 2015 1.3 Approximation on Unreliable Hardware • A. Sampson, W. Dietl, E. Fortuna, D. Gnanapragasam, L. Ceze, and D. Grossman. Enerj: Approximate data types for safe and general low-power computation. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, pages 164–174, New York, NY, USA, 2011. ACM • H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger. Neural acceleration for general-purpose approximate programs. In Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-45, pages 449–460, Washington, DC, USA, 2012. IEEE Computer Society • J. Park, X. Zhang, K. Ni, H. Esmaeilzadeh, and M. Naik. Expax: A framework for automating approximate programming. Technical report, College of Computing, Georgia Institute of Technology, North Ave NW, Atlanta, GA 30332, USA, 2014
References [1] A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998. [2] W. Baek and T. M. Chilimbi. Green: A framework for supporting energy-conscious programming using controlled approximation. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 198–209, 2010. [3] S. Campanoni, G. Holloway, G.-Y. Wei, and D. Brooks. Helix-up: Relaxing program semantics to unleash parallelization. In Code Generation and Optimization (CGO), 2015 IEEE/ACM International Symposium on, pages 235–245, Feb 2015. [4] H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger. Neural acceleration for general-purpose approximate programs. In Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-45, pages 449–460, Washington, DC, USA, 2012. IEEE Computer Society. [5] J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach, Fourth Edition. Morgan Kaufmann, 2006. [6] J. Liu, W.-K. Shih, K.-J. Lin, R. Bettati, and J.-Y. Chung. Imprecise computations. Proceedings of the IEEE, 82(1):83–94, Jan 1994. [7] S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. ACM Trans. Embed. Comput. Syst., 12(2s):88:1–88:26, May 2013. [8] J. Park, X. Zhang, K. Ni, H. Esmaeilzadeh, and M. Naik. Expax: A framework for automating approximate programming. Technical report, College of Computing, Georgia Institute of Technology, North Ave NW, Atlanta, GA 30332, USA, 2014. [9] M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In Proceedings of the 20th Annual International Conference on Supercomputing, ICS ’06, pages 324–334, New York, NY, USA, 2006. ACM. [10] M. Samadi, D. A. Jamshidi, J. Lee, and S. Mahlke. Paraprox: Pattern-based approximation for data parallel applications. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’14, pages 35–50, New York, NY, USA, 2014. ACM. [11] A. Sampson, W. Dietl, E. Fortuna, D. Gnanapragasam, L. Ceze, and D. Grossman. Enerj: Approximate data types for safe and general low-power computation. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, pages 164–174, New York, NY, USA, 2011. ACM. [12] S. Sidiroglou-Douskos, S. Misailovic, H. Hoffmann, and M. Rinard. Managing performance vs. accuracy trade-offs with loop perforation. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European