Purdue University Purdue e-Pubs Open Access Dissertations Theses and Dissertations 12-2016 Approximate computing: An integrated cross-layer framework Swagath Venkataramani Purdue University Follow this and additional works at:https://docs.lib.purdue.edu/open_access_dissertations Part of theComputer Engineering Commons, and theElectrical and Computer Engineering Commons Recommended Citation Venkataramani, Swagath, "Approximate computing: An integrated cross-layer framework" (2016).Open Access Dissertations. 1022. https://docs.lib.purdue.edu/open_access_dissertations/1022 This document has been made available through Purdue e-Pubs, a service of the Purdue University Libraries. Please contact [email protected] for additional information. APPROXIMATE COMPUTING: AN INTEGRATED CROSS-LAYER FRAMEWORK A Dissertation Submitted to the Faculty of Purdue University by Swagath Venkataramani In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy December 2016 Purdue University West Lafayette, Indiana ii க(cid:3)ற(cid:5) ைகம(cid:8) அள(cid:11), க(cid:12)லாத(cid:5) உலகள(cid:11) -- ஔைவயா(cid:20) What you have learned is a mere handful; What is yet to be learnt is the size of the world! – Auvayar iii ACKNOWLEDGMENTS The true highlight of my PhD, more than the projects I worked on, was the people I worked with. I had the opportunity to collaborate with people from diverse technical backgrounds ranging from devices to algorithms, and the unique perspective that each brought forward was truly an enriching learning experience, for which I am ever grateful. I truly relish the relationships I have developed with my collaborators over the years, and wish to take it forward in the same spirit, as I take the next step in my profession career. The single most reason behind all I have learnt and achieved, both professionally and personally, is my advisor Prof. Anand Raghunathan. He had undisputedly cared for my development and put my interests first in all decisions. I have always looked up to him and emulate him in all aspects of research, right from what problems to choose, what unique angles I as a researcher can bring in, where to spend my effort so that it is most impactful, and how best to present my work such that it is as intuitive to others as it is to me. The sheer experience of spending over half a decade with him has immensely helped me to organically develop as a researcher. I thank him all the flexibility and he is undoubtedly my superhero, the epitome of kindness, work ethic and intelligence. In the same breath, I thank all my teachers, right from my childhood, for who I am is a direct result of the knowledge they imparted. My lab, Integrated Systems Laboratory, could not have been a more productive environment. My longevity at Purdue allowed me to work with some uniquely amaz- ing people, seniors Vinay, Jacques, Vivek, Rangha, Yue Du, Younghyun and juniors Shankar, Ashish, Younghoon Shubham, Sanchari, Junshi, Neel, Arnab, and Sanjay. Needless to say, our relationships transcend beyond the walls of the MSEE 337. We always had our backs in thick and thin, and I enjoyed and learned from every bit (pun intended) of interaction. I truly care about each one of their successes, continue iv to feel proud of their accomplishments and strive to imbibe their finest qualities in me. ISL is the prime example of a truly synergistic academic lab, its strength purely stemming from the mutual care and respect people show for each other. I interacted significantly with Prof. Vijay Raghunathan and Prof. Kaushik Roy throughout my PhD. I thank them for their support and guidance at each important step in my development. I also worked closely with students from Nanoelectron- ics Research Labs, Embedded Systems Lab, Integrating Imaging Lab at Purdue. I equally cherish those relationships and look forward to continue working with them in future. I also thank those I collaborated with in the industry, specifically during my internships at Exa-scale computing research and parallel computing labs at Intel, and Sensing and energy research group at Microsoft. I thank my mentors for their support and trust in my abilities. I spent most of my time outside lab at the badminton courts in Purdue. Bad- minton was so integral to me, and I thank the Purdue Badminton Club members and other badminton enthusiasts in the midwest region for all the fun and competition we had on and off court. I also thank my cricket buddies for the fun times we shared. On the personal front, I am undeservedly fortunate to have met Vijay, Kaushik, Priyanka, Chandana, Shankar, Samyuktha and Tanmay at Purdue. The veracity in their characters demonstrated the true kinship I never felt over the years. They kept me honest and their care for me kept me unfazed. I attribute every smile I enjoyed and every pain I felt to them. I cannot understate the influence my roomate Ashiwan has had on me. I never felt a stranger when he was around, and eternal gratitude to him and Sanju. I also thank my friends, Leena, Anand and others at Bangalore for all the fond memories. I will be amiss not to thank my family in the US for their inspiration and incessant support. Finally, I thank my parents, Chithra and Venkataramani, for unconditionally be- ing there for me and imparting values that defines my very identity today. The fol- lowing pages are a product their emboldened vision, unfettering hope, and countless scarifies, and for that I humbly dedicate what is rightly theirs to them. v TABLE OF CONTENTS Page LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi ABBREVIATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Intrinsic Application Resilience . . . . . . . . . . . . . . . . . . . . 2 1.2 Approximate Computing . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Approximate and Quality Configurable Circuits: Design and Synthesis . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Programmable Approximate Computing Architectures . . . 10 1.3.3 Software and Algorithms for Approximate Computing . . . . 11 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 DESIGN AND SYNTHESIS OF APPROXIMATE AND QUALITY CON- FIGURABLE CIRCUITS . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Quality Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.1 Metrics Constraining the Magnitude of Error . . . . . . . . . 17 2.2.2 Metrics Constraining the Frequency of Error . . . . . . . . . 18 2.2.3 Composite Metrics . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 SALSA: Don’t Care based Logic Approximation . . . . . . . . . . . 20 2.3.1 Preliminaries and Approach . . . . . . . . . . . . . . . . . . 21 2.3.2 SALSA Methodology . . . . . . . . . . . . . . . . . . . . . . 27 2.3.3 Speedup techniques and other heuristics . . . . . . . . . . . 33 vi Page 2.3.4 Experimental Methodology . . . . . . . . . . . . . . . . . . . 38 2.3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4 SASIMI: A Unified Circuit Transformation for Approximate and Qual- ity Configurable Circuit Design . . . . . . . . . . . . . . . . . . . . 52 2.4.1 SASIMI: Design Approach . . . . . . . . . . . . . . . . . . . 53 2.4.2 Quality Configurable circuit design using SASIMI . . . . . . 55 2.4.3 SASIMI Methodology . . . . . . . . . . . . . . . . . . . . . . 59 2.4.4 Experimental Methodology . . . . . . . . . . . . . . . . . . . 63 2.4.5 Results: Approximate Circuits . . . . . . . . . . . . . . . . . 65 2.4.6 Results: Quality configurable circuits . . . . . . . . . . . . . 68 2.4.7 Application-level evaluation of SASIMI circuits . . . . . . . 69 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3 QUALITY PROGRAMMABLE PROCESSORS . . . . . . . . . . . . . . 72 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.2 A Case for Quality Programmability . . . . . . . . . . . . . . . . . 74 3.3 Quality Programmable Processors: Concept & Overview . . . . . . 75 3.3.1 QP-ISA: Quality Programmable ISA . . . . . . . . . . . . . 76 3.3.2 QP-uArch: Micro-architecture with Accuracy-Energy Trade-off 77 3.3.3 Quality Monitors: Error Feedback to Software . . . . . . . . 78 3.3.4 Programming QPPs . . . . . . . . . . . . . . . . . . . . . . 78 Quora 3.4 : A Quality Programmable Vector Processor . . . . . . . . 79 Quora 3.4.1 Instruction Set . . . . . . . . . . . . . . . . . . . . 80 Quora 3.4.2 Micro-architecture . . . . . . . . . . . . . . . . . . 86 3.5 Micro-architectural Mechanisms for Quality Scaling . . . . . . . . . 92 3.5.1 Precision Scaling . . . . . . . . . . . . . . . . . . . . . . . . 92 3.5.2 Array Level Organization of Precision Scaling Units . . . . . 96 3.5.3 Precision Scaling: Impact on Energy . . . . . . . . . . . . . 98 3.5.4 Quality Translation and Error Estimation . . . . . . . . . . 99 vii Page 3.6 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 101 3.6.1 RTL Implementation . . . . . . . . . . . . . . . . . . . . . . 102 3.6.2 Application Benchmarks . . . . . . . . . . . . . . . . . . . . 102 3.6.3 Energy and Quality Measurements . . . . . . . . . . . . . . 104 3.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.7.1 Energy Benefits . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.7.2 Quality Programmability in Instructions . . . . . . . . . . . 106 3.7.3 Energy Contribution of Quality Programmable Instructions . 107 3.7.4 Precision Scaling Mechanisms . . . . . . . . . . . . . . . . . 108 3.7.5 Architectural Exploration . . . . . . . . . . . . . . . . . . . 109 3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4 ENERGY-EFFICIENTDEEPLEARNINGUSINGAPPROXIMATECOM- PUTING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.1.1 Deep Learning Networks: Computational Challenges . . . . 111 4.1.2 Efficiency of DLNs: Prior Research Directions . . . . . . . . 113 4.1.3 Deep Learning ⇔ Approximate Computing . . . . . . . . . . 114 4.2 Neural Nets: Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 117 4.3 AxNN: Approach and Design Methodology . . . . . . . . . . . . . . 119 4.3.1 AxNN: Design Approach . . . . . . . . . . . . . . . . . . . . 120 4.3.2 AxNN Design Methodology . . . . . . . . . . . . . . . . . . 124 4.4 Quality Configurable Neuromorphic Processing Engine . . . . . . . 126 4.5 Experimental Methodology . . . . . . . . . . . . . . . . . . . . . . . 128 4.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.6.1 Energy benefits of AxNN . . . . . . . . . . . . . . . . . . . . 129 4.6.2 Uniform approximation: Comparison . . . . . . . . . . . . . 130 4.6.3 Resilience Characterization: Insights . . . . . . . . . . . . . 131 4.6.4 Impact of Retraining . . . . . . . . . . . . . . . . . . . . . . 132