doi: 10.7873/DATE.2015.1114


Novel Inexact Memory Aware Algorithm Co-design for Energy Efficient Computation – Algorithmic Principles


Guru Prakash Arumugam1,a, Prashanth Srikanthan1,b, John Augustine1,c, Krishna Palem2,g, Eli Upfal3,h, Ayush Bhargava1,d, Parishkrati1,e and Sreelatha Yenugula1,f

1Department of Computer Science and Engineering Indian Institute of Technology Madras Chennai, India.

aguruprakash991@gmail.com
bprashanthxs@gmail.com
caugustine@cse.iitm.ac.in
dayush.bhargava15@gmail.com
eparishkratihhh@gmail.com
fsreelatha.yenugula@gmail.com

2Department of Computer Science Rice University, Houston, USA.

gkvp1@rice.edu

3Department of Computer Science Brown University Providence, RI, USA.

heli@cs.brown.edu

ABSTRACT

It is increasingly accepted that energy savings can be achieved by trading the accuracy of a computing system for energy gains–quite often significantly. This approach is referred to as inexact or approximate computing. Given that a significant portion of the energy in a modern general purpose processor is spent on moving data to and from storage, and that increasingly data movement contributes significantly to activity during the execution of applications, it is important to be able to develop techniques and methodologies for inexact computing in this context. To accomplish this to its fullest level, it is important to start with algorithmic specifications and alter their intrinsic design to take advantage of inexactness. This calls for a new approach to inexact memory aware algorithm design (IMAD) or co-design. In this paper, we provide the theoretical foundations which include novel models as well as technical results in the form of upper and lower bounds for IMAD in the context of universally understood and canonical problems: variations of sorting, and string matching. Surprisingly, IMAD allowed us to design entirely error-free algorithms while achieving energy gain factors of 1.5 and 5 in the context of sorting and string matching when compared to their traditional (textbook) algorithms. IMAD is also amenable to theoretical analysis and we present several asymptotic bounds on energy gains.



Full Text (PDF)