Programming by sketching for bit-streaming programs

ABSTRACT

This paper introduces the concept of programming with sketches, an approach for the rapid development of high-performance applications. This approach allows a programmer to write clean and portable reference code, and then obtain a high-quality implementation by simply sketching the outlines of the desired implementation. Subsequently, a compiler automatically fills in the missing details while also ensuring that a completed sketch is faithful to the input reference code. In this paper, we develop StreamBit as a sketching methodology for the important class of bit-streaming programs (e.g., coding and cryptography).A sketch is a partial specification of the implementation, and as such, it affords several benefits to programmer in terms of productivity and code robustness. First, a sketch is easier to write compared to a complete implementation. Second, sketching allows the programmer to focus on exploiting algorithmic properties rather than on orchestrating low-level details. Third, a sketch-aware compiler rejects "buggy" sketches, thus improving reliability while allowing the programmer to quickly evaluate sophisticated implementation ideas.We evaluated the productivity and performance benefits of our programming methodology in a user-study, where a group of novice StreamBit programmers competed with a group of experienced C programmers on implementing a cipher. We learned that, given the same time budget, the ciphers developed in StreamBit ran 2.5x faster than ciphers coded in C. We also produced implementations of DES and Serpent that were competitive with hand optimized implementations available in the public domain.

REFERENCES

• 1: George Almási , David Padua, MaJIC: compiling MATLAB for speed and responsiveness, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 2: R. Anderson, E. Biham, and L. Knudsen. Serpent: A proposal for the advanced encryption standard. The implementation we tested can be found at http://www.cl.cam.ac.uk/ rja14/serpent.html.
• 3: D. Andre and S. Russell. Programmable reinforcement learning agents. Advances in Neural Information Processing Systems, 13, 2001. MIT Press.
• 4: J. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt. Ptolemy: A framework for simulating and prototyping heterogeneous systems. Int. Journal of Computer Simulation, 4:155--182, April 1994. special issue on "Simulation Software Development".
• 5: Arun Chauhan , Cheryl McCosh , Ken Kennedy , Richard Hanson, Automatic Type-Driven Library Generation for Telescoping Languages, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.51, November 15-21, 2003
• 6: J. Demmel, J. Dongarra, V. Eijkhout, E. Fuentes, A. Petitet, R. Vuduc, C. Whaley, and K. Yelick. Self adapting linear algebra algorithms and software. Proceedings of the IEEE, 93(2), 2005.
• 7: R. Ennals, R. Sharp, and A. Mycroft. Task partitioning for multi-core network processors. In Compiler Construction, Edinburgh, Scotland, April 2005.
• 8: Niels Ferguson , Bruce Schneier, Practical Cryptography, John Wiley & Sons, Inc., New York, NY, 2003
• 9: Data encryption standard (des). U.S. DEPARTMENT OF COM-MERCE/National Institute of Standards and Technology, December 1993. http://www.itl.nist.gov/fipspubs/fip46-2.htm.
• 10: M. Frigo and S. Johnson. Fftw: An adaptive software architecture for the fft. In ICASSP conference proceedings, volume 3, pages 1381--1384, 1998.
• 11: Pascal Van Hentenryck , Vijay Saraswat, Strategic directions in constraint programming, ACM Computing Surveys (CSUR), v.28 n.4, p.701-726, Dec. 1996 [doi>10.1145/242223.242279]
• 12: John Irwin , Jean-Marc Loingtier , John R. Gilbert , Gregor Kiczales , John Lamping , Anurag Mendhekar , Tatiana Shpeisman, Aspect-Oriented Programming of Sparse Matrix Code, Proceedings of the Scientific Computing in Object-Oriented Parallel Environments, p.249-256, December 08-11, 1997
• 13: K. Kennedy, B. Broom, A. Chauhan, R. Fowler, J. Garvin, C. Koelbel, C. McCosh, and J. Mellor-Crummey. Telescoping languages: A system for automatic generation of domain languages. Proceedings of the IEEE, 93(2), 2005.
• 14: G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. V. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In proceedings of the European Conference on Object-Oriented Programming (ECOOP), number 1241 in LNCS. Springer-Verlag, June 1997.
• 15: Andrew A. Lamb , William Thies , Saman Amarasinghe, Linear analysis and optimization of stream programs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 16: E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, September 1987.
• 17: M. Morgan. http://www.schneier.com/blowfish-bug.txt.
• 18: Markus Püschel , José M. F. Moura , Bryan Singer , Jianxin Xiong , Jeremy Johnson , David Padua , Manuela Veloso , Robert W. Johnson, Spiral: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.21-45, February 2004 [doi>10.1177/1094342004041291]
• 19: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 20: Lisa Wu , Chris Weaver , Todd Austin, CryptoManiac: a fast flexible architecture for secure communication, Proceedings of the 28th annual international symposium on Computer architecture, p.110-119, June 30-July 04, 2001, Göteborg, Sweden
• 21: E. Young. http://www.openssl.org. libDES is now part of OpenSSL.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
      D.3.3 Language Constructs and Features
      D.3.4 Processors

General Terms:
Design, Languages, Performance

Keywords:
StreamIt, domain specific compiler, domain specific language, sketching, stream programming, synchronous dataflow