Program interpolation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Program interpolation

Full text

Pdf (525 KB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation table of contents

Savannah, GA, USA

SESSION: Static analysis table of contents

Pages: 31-40

Year of Publication: 2009

ISBN:978-1-60558-327-3

Authors

Andrew Moss	University of Bristol, Bristol, United Kingdom
Dan Page	University of Bristol, Bristol, United Kingdom

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 64, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1480945.1480951 What is a DOI?

ABSTRACT

Program interpolation is a new type of transformation that given an input program written in a specially constructed Domain Specific Language (DSL), produces a family of functionally equivalent instruction sequences as output. Each sequence is an "interpolation" between the control-flows of implementation strategies supplied in the input program. The purpose of the transformation is to expose behavioural differences (e.g. performance) within the sequences, and thus allow automated optimisation with respect to architectural trade-offs that are difficult to quantify and model. We present results from a prototype compiler that demonstrate a 63% speedup in the domain of multi-precision integer arithmetic.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D.J. Bernstein. Multidigit multiplication for mathematicians. Available at: http://cr.yp.to/papers.html#m3
	2	D.J. Bernstein. qhasm: tools to help write high-speed software. Available at: http://cr.yp.to/qhasm.html
	3	F. Bouchez, A. Darte, C. Guillon, and F. Rastello. Register Allocation and Spill Complexity Under SSA. Technical Report 2005-33, ENS-Lyon, Lyon France, 2005.
	4	P. Brisk, F. Dabiri, R. Jafari, and M. Sarrafzadeh. Optimal register sharing for high-level synthesis of SSA form programs. In IEEE Trans. Computer Aided Design, Vol. 25, no. 25, May, 2006, 772--779.
	5	P. G. Comba, Exponentiation cryptosystems on the IBM PC, IBM Systems Journal, v.29 n.4, p.526-538, 1990
	6	Computational Algebra Group, University of Sydney. Magma Computational Algebra System. Available at: http://magma.maths.usyd.edu.au/magma/
	7	P. Gaudry and E. Thomè. The mp F q Library and Implementing Curve-based Key Exchanges. In Software Performance Enhancement for Encryption and Decryption (SPEED), 49--64, 2007.
	8	N. Gura, A. Patel, A. Wander, H. Eberle, S. Chang Shantz. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. In Cryptographic Hardware and Embedded Systems (CHES), Springer-Verlag LNCS 3156, 119--132, 2004.
	9	Sebastian Hack , Gerhard Goos, Optimal register allocation for SSA-form programs in polynomial time, Information Processing Letters, v.98 n.4, p.150-155, 31 May 2006 [doi>10.1016/j.ipl.2006.01.008]
	10	Darrel Hankerson , Alfred J. Menezes , Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
	11	Intel Cooperation. Using the RDTSC Instruction for Performance Monitoring. Intel Technical Report, 1997.
	12	A. Karatsuba and Y. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. In Doklady Akad. Nauk SSSR 145, 293--294, 1962.
	13	Vladimir Lifschitz , David Pearce , Agustín Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic (TOCL), v.2 n.4, p.526-541, Oct. 2001 [doi>10.1145/383779.383783]
	14	Henry Massalin, Superoptimizer: a look at the smallest program, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.122-126, October 1987, Palo Alto, California, United States [doi>10.1145/36206.36194]
	15	Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
	16	A. Moss and H. Muller. Efficient Code Generation for a Domain Specific Language. In Generative Programming and Component Engineering, Springer-Verlag LNCS 3676, 47--62, 2005.
	17	Simon L. Peyton Jones , Norman Ramsey , Fermin Reig, C--: A Portable Assembly Language that Supports Garbage Collection, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.1-28, September 29-October 01, 1999
	18	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	19	M. Scott and P. Szczechowiak. Optimizing Multiprecision Multiplication for Public Key Cryptography. In Cryptology ePrint Archive, Report 2007/299, 2007.
	20	L. Uhsadel, A. Poschmann and C. Paar. Enabling Full-Size Public-Key Algorithms on 8-Bit Sensor Nodes. In Security and Privacy in Ad-hoc and Sensor Networks (ESAS), Springer-Verlag LNCS 4572, 73--86, 2007.