World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Clusters and Computational Grids for Scientific ComputingNo Access

ON THE COMPLEXITY OF MAPPING LINEAR CHAIN APPLICATIONS ONTO HETEROGENEOUS PLATFORMS

    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
    • M. Cole, Parallel Computing 30(3), 389 (2004), DOI: 10.1016/j.parco.2003.12.002. Crossref, ISIGoogle 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 Scholar
    • J. 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 Scholar
    • T. 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 Scholar
    • P. 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
    • P. Bhat, C. Raghavendra and V. Prasanna, Journal of Parallel and Distributed Computing 63, 251 (2003), DOI: 10.1016/S0743-7315(03)00008-X. Crossref, ISIGoogle 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 Scholar
    • O. Beaumontet al., 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
    • M. D. Beynonet al., Future Generation Computer Systems 18(4), 435 (2002), DOI: 10.1016/S0167-739X(01)00070-X. Crossref, ISIGoogle Scholar
    • M.   Spencer et al. , 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