When Instruction Set Extensions Change Algorithm Design: A Study in Elliptic Curve Cryptography
Johann Großschädl, Stefan Tillich, Paolo Ienne, Laura Pozzi, Ajay Kumar Verma · 2005
In recent years, processor customization has matured to become a trusted way of achieving aggressive performance with limited cost/energy in embedded applications. In particular, instruction set extensions (ISEs) have been proven very effective in many cases. A large body of work exists today on creating algorithms that can select efficient ISEs given an application source code: ISE automation is paramount for increasing the efficiency of design teams. In this paper we show that an additional motivation to automate the ISE process is to help algorithmic design: the availability of ISE can have a dramatic impact on the effectiveness of different algorithmic choices to implement identical or equivalent functionality. Algorithm designers need fast feedbacks on the ISE-ability of various algorithmic flavors. We use a case study in elliptic curve (EC) cryptography to prove the following contributions: (1) ISE can reverse the relative interest of different algorithm versions and (2) automatic ISE, even without predicting speedups as precisely as detailed simulation can, is able to show exactly the trends that the algorithm designer should follow. 1.