ON THE COMPLEXITY OF MAPPING LINEAR CHAIN APPLICATIONS ONTO HETEROGENEOUS PLATFORMS
Abstract
In this paper, we explore the problem of mapping linear chain applications onto large-scale heterogeneous platforms. A series of data sets enter the input stage and progress from stage to stage until the final result is computed. An important optimization criterion that should be considered in such a framework is the latency, or makespan, which measures the response time of the system in order to process one single data set entirely. For such applications, which are representative of a broad class of real-life applications, we can consider one-to-one mappings, in which each stage is mapped onto a single processor. However, in order to reduce the communication cost, it seems natural to group stages into intervals. The interval mapping problem can be solved in a straightforward way if the platform has homogeneous communications: the whole chain is grouped into a single interval, which in turn is mapped onto the fastest processor. But the problem becomes harder when considering a fully heterogeneous platform. Indeed, we prove the NP-completeness of this problem. Furthermore, we prove that neither the interval mapping problem nor the similar one-to-one mapping problem can be approximated in polynomial time by any constant factor (unless P=NP).
References
-
B. A. Shirazi , A. R. Hurson and K. M. Kavi , Scheduling and load balancing in parallel and distributed systems ( IEEE Computer Science Press , 1995 ) . Google Scholar - Parallel Computing 30(3), 389 (2004), DOI: 10.1016/j.parco.2003.12.002. Crossref, ISI, Google Scholar
-
F. Rabhi and S. Gorlatch , Patterns and Skeletons for Parallel and Distributed Computing ( Springer Verlag , 2002 ) . Google Scholar J. Subhlok and G. Vondran , Optimal mapping of sequences of data parallel tasks, Proc. 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'95 (ACM Press, 1995) pp. 134–143. Google ScholarJ. Subhlok and G. Vondran , Optimal latency-throughput tradeoffs for data parallel pipelines, ACM Symposium on Parallel Algorithms and Architectures SPAA'96 (ACM Press, 1996) pp. 62–71. Google ScholarT. Saif and M. Parashar , Understanding the behavior and performance of non-blocking communications in MPI, Proceedings of Euro-Par 2004: Parallel Processing,LNCS 3149 (Springer, 2004) pp. 173–182. Google ScholarP. Bhat , C. Raghavendra and V. Prasanna , Efficient collective communication in distributed heterogeneous systems, ICDCS'99 19th International Conference on Distributed Computing Systems (IEEE Computer Society Press, 1999) pp. 15–24. Google Scholar- Journal of Parallel and Distributed Computing 63, 251 (2003), DOI: 10.1016/S0743-7315(03)00008-X. Crossref, ISI, Google Scholar
-
M. R. Garey and D. S. Johnson , Computers and Intractability, a Guide to the Theory of NP-Completeness ( W.H. Freeman and Company , 1979 ) . Google Scholar -
A. Benoit , V. Rehn-Sonigo and Y. Robert , Optimizing latency and reliability of pipeline workflow applications , HCW'2008, the 17th International Heterogeneity in Computing Workshop ( IEEE Computer Society Press , 2008 ) . Google Scholar K. Taura and A. A. Chien , A heuristic algorithm for mapping communicating tasks on heterogeneous resources, Heterogeneous Computing Workshop (IEEE Computer Society Press, 2000) pp. 102–115. Google ScholarO. Beaumont , Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms, HeteroPar'2004: International Conference on Heterogeneous Computing, ISPDC'2004: International Symposium on Parallel and Distributed Computing (IEEE Computer Society Press, 2004) pp. 296–302. Google Scholar- "DataCutter Project: Middleware for Filtering Large Archival Scientific Datasets in a Grid Environment." http://www.cs.umd.edu/projects/hpsl/ResearchAreas/DataCutter.htm . Google Scholar
- Future Generation Computer Systems 18(4), 435 (2002), DOI: 10.1016/S0167-739X(01)00070-X. Crossref, ISI, Google Scholar
-
M. Spencer , Executing multiple pipelined data analysis operations in the grid , 2002 ACM/IEEE Supercomputing Conference ( ACM Press , 2002 ) . Google Scholar - N. Vydyanathan, U. Catalyurek, T. Kurc, P. Saddayappan, and J. Saltz, "An approach for optimizing latency under throughput constraints for application work-flows on clusters," Research Report OSU-CISRC-1/07-TR03, Ohio State University, Columbus, OH, Jan. 2007. Available at ftp://ftp.cse.ohio-state.edu/pub/tech-report/2007 . Google Scholar


