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.
- 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. Google ScholarDigital Library
- 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.Google Scholar
- D. Andre and S. Russell. Programmable reinforcement learning agents. Advances in Neural Information Processing Systems, 13, 2001. MIT Press.Google Scholar
- 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".Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- R. Ennals, R. Sharp, and A. Mycroft. Task partitioning for multi-core network processors. In Compiler Construction, Edinburgh, Scotland, April 2005. Google ScholarDigital Library
- N. Ferguson and B. Schneier. Practical Cryptography. Wiley Publishing Inc, 2003. Google ScholarDigital Library
- 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.Google Scholar
- M. Frigo and S. Johnson. Fftw: An adaptive software architecture for the fft. In ICASSP conference proceedings, volume 3, pages 1381--1384, 1998.Google ScholarCross Ref
- P. V. Hentenryck and V. Saraswat. Strategic directions in constraint programming. ACM Comput. Surv., 28(4):701--726, 1996. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, September 1987.Google ScholarCross Ref
- M. Morgan. http://www.schneier.com/blowfish-bug.txt.Google Scholar
- 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. Google ScholarDigital Library
- W. Thies, M. Karczmarek, and S. Amarasinghe. Streamit: A language for streaming applications. In International Conference on Compiler Construction, Grenoble, France, Apr. 2002. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- E. Young. http://www.openssl.org. libDES is now part of OpenSSL.Google Scholar
Index Terms
- Programming by sketching for bit-streaming programs
Recommendations
Combinatorial sketching for finite programs
Proceedings of the 2006 ASPLOS ConferenceSketching is a software synthesis approach where the programmer develops a partial implementation - a sketch - and a separate specification of the desired functionality. The synthesizer then completes the sketch to behave like the specification. The ...
Programming by sketching for bit-streaming programs
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationThis 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 ...
Sketching user experiences tutorial: stories, strategies, surfaces
ITS '13: Proceedings of the 2013 ACM international conference on Interactive tabletops and surfacesPaper-pencil sketches are a valuable tool during different stages of experience design in human-computer interaction. This hands-on tutorial will demonstrate how to integrate sketching into researchers' and interaction designers' everyday practice -- ...
Comments