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. G. Almasi and D. Padua. Majic: Compiling matlab for speed and responsiveness. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 294--303, June 2002.
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. A. Chauhan, C. McCosh, and K. Kennedy. Automatic type-driven library generation for telescoping languages. In Proceedings of SC: High-performance Computing and Networking Conference, Nov. 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. N. Ferguson and B. Schneier. Practical Cryptography. Wiley Publishing Inc, 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. P. V. Hentenryck and V. Saraswat. Strategic directions in constraint programming. ACM Comput. Surv., 28(4):701--726, 1996.
12. J. Irwin, J.-M. Loingtier, J. R. Gilbert, G. Kiczales, J. Lamping, A. Mendhekar, and T. Shpeisman. Aspect-oriented programming of sparse matrix code. In Proceedings International Scientific Computing in Object-Oriented Parallel Environments (ISCOPE), number 1343 in LNCS, Marina del Rey, CA, 1997. Springer-Verlag.
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. A. A. Lamb, W. Thies, and S. Amarasinghe. Linear analysis and optimization of stream programs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, June 2003.
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. M. Püschel, B. Singer, J. Xiong, J. Moura, J. Johnson, D. Padua, M. Veloso, and R. Johnson. Spiral: A generator for platform-adapted libraries of signal processing algorithms. Journal of High Performance Computing and Applications, accepted for publication.
19. W. Thies, M. Karczmarek, and S. Amarasinghe. Streamit: A language for streaming applications. In International Conference on Compiler Construction, Grenoble, France, Apr. 2002.
20. L. Wu, C. Weaver, and T. Austin. Cryptomaniac: A fast flexible architecture for secure communication. In 28th Annual International Symposium on Computer Architecture (28th ISCA 2001), Goteborg, Sweden, June-July 2001. ACM SIGARCH / IEEE.
21. E. Young. http://www.openssl.org. libDES is now part of OpenSSL.

Index Terms

• Software and its engineering

  • Software creation and management

    • Designing software

      • Software implementation planning

        • Software design techniques

    • Software development process management

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

      • Language types