Streamflex: high-throughput stream programming in java

ABSTRACT

The stream programming paradigm aims to expose coarse-grained parallelism inapplications that must process continuous sequences of events. The appeal ofstream programming comes from its conceptual simplicity. A program is acollection of independent filters which communicate by the means ofuni-directional data channels. This model lends itself naturally toconcurrent and efficient implementations on modern multiprocessors. As theoutput behavior of filters is determined by the state of their inputchannels, stream programs have fewer opportunities for the errors (such asdata races and deadlocks) that plague shared memory concurrent programming. This paper introduces S<scp>tream</scp>F<scp>lex</scp>, an extension to Java which marries streams with objects and thus enables to combine, in the same Java virtual machine, stream processing code with traditional object-oriented components. S<scp>tream</scp>F<scp>lex</scp> targets high-throughput low-latency applications with stringent quality-of-service requirements. To achieve these goals, it must, at the same time, extend and restrict Java. To allow for program optimization and provide latency guarantees, the S<scp>tream</scp>F<scp>lex</scp> compiler restricts Java by imposing a stricter typing discipline on filters. On the other hand, S<scp>tream</scp>F<scp>lex</scp> extends the Java virtual machine with real-time capabilities, transactional memory and type-safe region-based allocation. The result is a rich and expressive language that can be implemented efficiently.

REFERENCES

• 1: http://www.tglx.de/projects/hrtimers/2.6.17/.
• 2: D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. S. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. The Design of the Borealis Stream Processing Engine. In Second Biennial Conference on Innovative Data Systems Research (CIDR 2005), Asilomar, CA, January 2005.
• 3: C. Andreae, Y. Coady, C. Gibbs, J. Noble, J. Vitek, and T. Zhao. Scoped Types and Aspects for Real-Time Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), pages 124--147, Nantes, France, July 2006.
• 4: A. Armbuster, J. Baker, A. Cunei, D. Holmes, C. Flack, F. Pizlo, E. Pla, M. Prochazka, and J. Vitek. A Real-time Java virtual machine with applications in avionics. ACM Transactions in Embedded Computing Systems (TECS), 2006.
• 5: E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
• 6: Joshua Auerbach , David F. Bacon , Daniel T. Iercan , Christoph M. Kirsch , V. T. Rajan , Harald Roeck , Rainer Trummer, Java takes flight: time-portable real-time programming with exotasks, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 13-15, 2007, San Diego, California, USA
• 7: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 8: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 9: G. Banavar, M. Kaplan, K. Shaw, R. Strom, D. C. Sturman, and W. Tao. Information flow based event distribution middleware. In Proceedings of the Middleware Workshop at the International Conference on Distributed Computing Systems, 1999.
• 10: Andrew P. Black , Jie Huang , Rainer Koster , Jonathan Walpole , Calton Pu, Infopipes: an abstraction for multimedia streaming, Multimedia Systems, v.8 n.5, p.406-419, December 2002 [doi>10.1007/s00530-002-0062-3]
• 11: Greg Bollella , James Gosling, The Real-Time Specification for Java, Computer, v.33 n.6, p.47-54, June 2000 [doi>10.1109/2.846318]
• 12: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 13: P. Caspi , D. Pilaud , N. Halbwachs , J. A. Plaice, LUSTRE: a declarative language for real-time programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.178-188, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41641]
• 14: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 15: R. Ennals, R. Sharp, and A. Mycroft. Linear types for packet processing. In Proceedings of the 13th European Symposium on Programming (ESOP), pages 204--218. Springer, 2004.
• 16: Patrick Eugster, Type-based publish/subscribe: Concepts and experiences, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.6-es, January 2007 [doi>10.1145/1180475.1180481]
• 17: F. Boussinot and R. De Simone. The ESTEREL language. Proc. IEEE, 79(9):1293--1304, Sept. 1991.
• 18: Manuel Fähndrich , Mark Aiken , Chris Hawblitzel , Orion Hodson , Galen Hunt , James R. Larus , Steven Levi, Language support for fast and reliable message-based communication in singularity OS, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 19: A. Ghosal, T. Henzinger, C. Kirsch, and M. Sanvido. Event-driven programming with logical execution times. In Proceedings of the 7th International Workshop, Hybrid Systems Computation and Control, March 2004.
• 20: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 21: P. L. Guernic, M. L. Borgne, T. Gauthier, and C. L. Maire. Programming real time applications with signal. Proceedings of the IEEE, September 1991.
• 22: Arvind S. Krishna , Douglas C. Schmidt , Raymond Klefstad, Enhancing Real-Time CORBA via Real-Time Java Features, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.66-73, March 24-26, 2004
• 23: Ravi Pratap M , Ron K. Cytron , David Sharp , Edward Pla, Transport layer abstraction in event channels for embedded systems, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 24: Jeremy Manson , Jason Baker , Antonio Cunei , Suresh Jagannathan , Marek Prochazka , Bin Xin , Jan Vitek, Preemptible Atomic Regions for Real-Time Java, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.62-71, December 05-08, 2005 [doi>10.1109/RTSS.2005.34]
• 25: James Noble , Jan Vitek , John Potter, Flexible Alias Protection, Proceedings of the 12th European Conference on Object-Oriented Programming, p.158-185, July 20-24, 1998
• 26: Filip Pizlo , Antony L. Hosking , Jan Vitek, Hierarchical real-time garbage collection, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 13-15, 2007, San Diego, California, USA
• 27: Filip Pizlo , Jan Vitek, An Emprical Evaluation of Memory Management Alternatives for Real-Time Java, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.35-46, December 05-08, 2006 [doi>10.1109/RTSS.2006.9]
• 28: R. Sekar , Y. Guang , S. Verma , T. Shanbhag, A high-performance network intrusion detection system, Proceedings of the 6th ACM conference on Computer and communications security, p.8-17, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319712]
• 29: Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 30: Jesper Honig Spring , Filip Pizlo , Rachid Guerraoui , Jan Vitek, Reflexes: abstractions for highly responsive systems, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254837]
• 31: Michael Stonebraker , Uǧur Çetintemel , Stan Zdonik, The 8 requirements of real-time stream processing, ACM SIGMOD Record, v.34 n.4, p.42-47, December 2005 [doi>10.1145/1107499.1107504]
• 32: 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
• 33: O. Vitek, B. Craig, C. Bailey-Kellog, and J. Vitek. Inferential backbone assignment for sparse data. Journal of Biomolecular NMR, 2006.
• 34: . Zhao, J. Baker, J. Hunt, J. Noble, and J. Vitek. ScopeJ: Simple ownership types for memory management. Submitted for publication, Dec. 2006.
• 35: Tian Zhao , James Noble , Jan Vitek, Scoped Types for Real-Time Java, Proceedings of the 25th IEEE International Real-Time Systems Symposium, p.241-251, December 05-08, 2004 [doi>10.1109/REAL.2004.51]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects

General Terms:
Experimentation, Languages

Keywords:
java virtual machine, memory management, ownership types, real-time systems, stream processing