Mapping filtering streaming applications with communication costs

ABSTRACT

In this paper, we explore the problem of mapping filtering streaming applications on large-scale homogeneous platforms, with a particular emphasis on communication models and their impact. Filtering application are streaming applications where each node also has a selectivity which either increases or decreases the size of its input data set. This selectivity makes the problem of scheduling these applications more challenging than the more studied problem of scheduling "non-filtering" streaming workflows. We identify three significant realistic communication models. For each of them, we address the complexity of the following important problems:

Given an execution graph, how can one compute the period and latency? A solution to this problem is an operation list which provides the time-steps at which each computation and each communication occurs in the system.

Given a filtering workflow problem, how can one compute the schedule that minimizes the period or latency? A solution to this problem requires generating both the execution graph and the associated operation list.

Altogether, with three models, two problems and two objectives, we present 12 complexity results, thereby providing solid theoretical foundations for the study of filtering streaming applications.

REFERENCES

• 1: Alessandro Agnetis , Paolo Detti , Marco Pranzo , Manbir S. Sodhi, Sequencing unreliable jobs on parallel machines, Journal of Scheduling, v.12 n.1, p.45-54, February 2009 [doi>10.1007/s10951-008-0076-6]
• 2: K. Agrawal, A. Benoit, F. Dufossé, and Y. Robert. Mapping filtering streaming applications with communication costs. Research Report 2009-06, LIP ENS Lyon, France, Feb. 2009.
• 3: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 4: A. Benoit, F. Dufossé, and Y. Robert. Mapping filter services on heterogeneous platforms. Research Report 2008-19, LIP, ENS Lyon, France, June 2008. Available at graal.ens-lyon.fr/~abenoit/.
• 5: A. Benoit, F. Dufossé, and Y. Robert. On the complexity of mapping filtering services on heterogeneous platforms. Research Report 2008-30, LIP, ENS Lyon, France, Oct. 2008. Short version to appear in IPDPS'09.
• 6: Anne Benoit , Yves Robert, Mapping pipeline skeletons onto heterogeneous platforms, Journal of Parallel and Distributed Computing, v.68 n.6, p.790-808, June, 2008 [doi>10.1016/j.jpdc.2007.11.004]
• 7: Prashanth B. Bhat , C. S. Raghavendra , Viktor K. Prasanna, Efficient collective communication in distributed heterogeneous systems, Journal of Parallel and Distributed Computing, v.63 n.3, p.251-263, March 2003 [doi>10.1016/S0743-7315(03)00008-X]
• 8: J. Burge, K. Munagala, and U. Srivastava. Ordering pipelined query operators with precedence constrain Research Report 2005-40, Stanford University, November 2005.
• 9: Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999 [doi>10.1145/320248.320249]
• 10: DataCutter Project: Middleware for Filtering Large Archival Scientific Datasets in a Grid Environment. http://www.cs.umd.edu/projects/hpsl/ResearchAreas/DataCutter.htm.
• 11: D. Florescu, A. Grunhagen, and D. Kossmann. Xl: A platform for web services. In CIDR 2003, First Biennial Conference on Innovative Data Systems Research, 2003. On-line proceedings at http://www-db.cs.wisc.edu/cidr/program/p8.pdf.
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 14: B. Hong and V. Prasanna. Bandwidth-aware resource allocation for heterogeneous computing systems to maximize throughput. In Proceedings of the 32th International Conference on Parallel Processing (ICPP'2003). IEEE Computer Society Press, 2003.
• 15: Mourad Ouzzani , Athman Bouguettaya, Query Processing and Optimization on the Web, Distributed and Parallel Databases, v.15 n.3, p.187-218, May 2004 [doi>10.1023/B:DAPD.0000018574.71588.06]
• 16: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 17: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Query optimization over web services, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 18: Kenjiro Taura , Andrew Chien, A Heuristic Algorithm for Mapping Communicating Tasks on Heterogeneous Resources, Proceedings of the 9th Heterogeneous Computing Workshop, p.102, May 01-01, 2000
• 19: N. Vydyanathan, U. Catalyurek, T. Kurc, P. Saddayappan, and J. Saltz. An approach for optimizing latency under throughput constraints for application workflows on clusters. Research Report OSU-CISRC-1/07-TR03, Ohio State University, Columbus, OH, Jan. 2007.
• 20: N. Vydyanathan, U. Catalyurek, T. Kurc, P. Saddayappan, and J. Saltz. Optimizing latency and throughput of application workflows on clusters. Research Report OSU-CISRC-4/08-TR17, Ohio State University, Columbus, OH, Apr. 2008.
• 21: Qishi Wu , Jinzhu Gao , Mengxia Zhu , Nageswara S. V. Rao , Jian Huang , Sitharama Iyengar, Self-Adaptive Configuration of Visualization Pipeline Over Wide-Area Networks, IEEE Transactions on Computers, v.57 n.1, p.55-68, January 2008 [doi>10.1109/TC.2007.70777]
• 22: Qishi Wu , Yi Gu, Supporting Distributed Application Workflows in Heterogeneous Computing Environments, Proceedings of the 2008 14th IEEE International Conference on Parallel and Distributed Systems, p.3-10, December 08-10, 2008 [doi>10.1109/ICPADS.2008.40]
• 23: Wenci Yu , Han Hoogeveen , Jan Karel Lenstra, Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard, Journal of Scheduling, v.7 n.5, p.333-348, September-October 2004 [doi>10.1023/B:JOSH.0000036858.59787.c2]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory

Keywords:
communication model, complexity results, latency, period, query optimization, streaming application, web service, workflow