DocumentCode :
703935
Title :
Algorithmic Principles1
Author :
Arumugam, Guru Prakash ; Augustine, John ; Upfal, Eli ; Parishkrati ; Srikanthan, Prashanth ; Palem, Krishna ; Bhargava, Ayush ; Yenugula, Sreelatha
Author_Institution :
Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India
fYear :
2015
fDate :
9-13 March 2015
Firstpage :
752
Lastpage :
757
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.
Keywords :
Algorithm design and analysis; Arrays; Computational modeling; Delays; Energy consumption; Energy states; Sorting;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design, Automation & Test in Europe Conference & Exhibition (DATE), 2015
Conference_Location :
Grenoble, France
Print_ISBN :
978-3-9815-3704-8
Type :
conf
Filename :
7092487
Link To Document :
بازگشت