Speculative out-of-order event processing with software transaction memory

ABSTRACT

In event stream applications, events flow through a network of components that perform various types of operations, e.g., filtering, aggregation, transformation. When the operation only depends on the input events, one can trivially parallelize its processing by replicating the associated components. This is not possible, however, with stateful components or when there exist dependencies between the events. Parallel versions of a number of simple stream mining operators have been designed, but, in general, complex and user-defined operators are limited by single thread performance. In this paper, we propose leveraging the processing capabilities of multi-core processors to improve the efficiency of stateful components using optimistic parallelization techniques (as provided by transactional memory). We show that, even though some speculative event executions might need to be disregarded, the overall throughput increases noticeably in the general case and latency can be reduced by pre-processing out-of-order events. Moreover, we show how simple conflict predictors can boost the parallelism even more and reduce the amount of resources used for a given level of parallelism.

REFERENCES

• 1: 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 Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR'05), Asilomar, CA, January 2005.
• 2: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 3: R. Barga, J. Goldstein, M. Ali, and M. Hong. Consistent streaming through time: a vision for event stream processing. In Proceedings of the third biennial conference on Innovative data systems research (CIDR'07), Asilomar, USA, January 2007.
• 4: D. Dice and N. Shavit. What really makes transactions faster? In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing. Jun 2006.
• 5: Pascal Felber , Christof Fetzer , Torvald Riegel, Dynamic performance tuning of word-based software transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345241]
• 6: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 7: M. Koparanova and T. Risch. High-performance grid stream database manager for scientific data. In Across Grids 2003, pages 86--92. Springer-Verlag Berlin Heidelberg, 2004.
• 8: Ming Li , Mo Liu , Luping Ding , Elke A. Rundensteiner , Murali Mani, Event Stream Processing with Out-of-Order Data Arrival, Proceedings of the 27th International Conference on Distributed Computing Systems Workshops, p.67, June 22-29, 2007 [doi>10.1109/ICDCSW.2007.35]
• 9: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 10: M. F. Spear, V. J. Marathe, W. N. S. III, and M. L. Scott. Conflict Detection and Validation Strategies for Software Transactional Memory. In 20th Intl. Symp. on Distributed Computing (DISC), 2006.
• 11: Jesper H. Spring , Jean Privat , Rachid Guerraoui , Jan Vitek, Streamflex: high-throughput stream programming in java, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 12: J. Steffan , T Mowry, The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.2, January 31-February 04, 1998
• 13: Cheng Wang , Wei-Yu Chen , Youfeng Wu , Bratin Saha , Ali-Reza Adl-Tabatabai, Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language, Proceedings of the International Symposium on Code Generation and Optimization, p.34-48, March 11-14, 2007 [doi>10.1109/CGO.2007.4]
• 14: Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142520]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming; Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
event stream processing, software transactional memory