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.

IMPROVING SCHEDULING OF COMMUNICATION INTENSIVE PARALLEL APPLICATIONS ON HETEROGENEOUS COMPUTING ENVIRONMENTS

    This paper presents a new model for the evaluation of the impacts of processing operations resulting from the communication among processes. This model quantifies the traffic volume imposed on the communication network by means of the latency parameters and the overhead. Such parameters represent the load that each process imposes over the network and the delay on CPU, as a consequence of the network operations. This delay is represented on the model by means of metric measurements slowdown. The equations that quantify the costs involved in the processing operation and message exchange are defined. In the same way, equations to determine the maximum network bandwidth are used in the decision-making scheduling. The proposed model uses a constant that delimitates the communication network maximum allowed usage, this constant defines two possible scheduling techniques: group scheduling or through communication network. Such techniques are incorporated to the DPWP policy, generating an extension of this policy. Experimental and simulation results confirm the performance enhancement of parallel applications under supervision of the extended DPWP policy, compared to the executions supervised by the original DPWP.

    References

    • C. Anglano, A comparative evaluation of implicit coscheduling strategies for networks of workstations, Proceedings of the Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00) (IEEE Computer Society, 2000) pp. 221–228. Google Scholar
    • A. P. F.   Arajo et al. , DPWP: A new load balancing algorithm , 5th International Conference on Information Systems Analysis and Synthesis - ISAS'99 ( 1999 ) . Google Scholar
    • F.   Berman and R.   Wolski , Scheduling from the perspective of the application , Proceedings of the High Performance Distributed Computing (HPDC '96) ( IEEE Computer Society , 1996 ) . Google Scholar
    • S.   Chodnekar et al. , Towards a communication characterization methodology for parallel applications , Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture (HPCA '97) ( IEEE Computer Society , 1997 ) . Google Scholar
    • T.   Choe and C.   Park , A task duplication based scheduling algorithm with optimality condition in heterogeneous systems , International Conference on Parallel Processing Workshops (ICPPW'02) ( ) ( IEEE Computer Society , 2002 ) . Google Scholar
    • D. Culleret al., Logp: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (ACM Press, San Diego, California, United States, 1993) pp. 1–12. Google Scholar
    • R. F.   de Mello and L. J.   Senger , A new migration model based on the evaluation of processes load and lifetime on heterogeneous computing environments , 16th Symposium on Computer Architecture and High Performance Computing ( 2004 ) . Google Scholar
    • D. G. Feitelson, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 2221, eds. D. G. Feitelson and L. Rudolph (Springer, 2001) pp. 188–205. CrossrefGoogle Scholar
    • D. G. Feitelson and L. Rudolph, Job Scheduling Strategies for Parallel Processing 1459, eds. D. G. Feitelson and L. Rudolph (Springer, 1998) pp. 1–24. CrossrefGoogle Scholar
    • A. Keren and A. Barak, IEEE Transactions on Parallel and Distributed Systems 14(1), 39 (2003). Crossref, ISIGoogle Scholar
    • T. C. Kerrigan. TSCP benchmark scores, 2004. http://home.comcast.net/~tckerrigan/bench.html . Google Scholar
    • V.   Kumar et al. , Introduction to Parallel Computing: Design and Analysis of Algorithms ( Benjamin-Cummings Publishing Co., Inc. , 1994 ) . Google Scholar
    • C.   Liu et al. , Design and evaluation of a resource selection framework for grid applications , Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 (HPDC'02) ( IEEE Computer Society , 2002 ) . Google Scholar
    • W. Mao, J. Chen and W. W. III, On-line algorithms for a parallel job scheduling problem, Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS-99) (1999) pp. 753–757. Google Scholar
    • L. M. Ni, C. Xu and T. B. Gendreau, IEEE Transactions on Sofiware Engineering 11(10), 1153 (1985). ISIGoogle Scholar
    • A. Radulescu, A. van Gemund and H. Lin, LLB: A fast and effective scheduling algorithm for distributed-memory systems, Proceedings of 13th International and 10th Symposium on Parallel and Distributed Processing - IPPS/SPDP (1999) pp. 525–530. Google Scholar
    • S. Ranaweera and D. P. Agrawal, A task duplication based scheduling algorithm for heterogeneous systems, Proceedings of Parallel and Distributed Processing Symposium - IPDPS 2000 (2000) pp. 445–450. Google Scholar
    • J. Ryou and J. S. K. Wong, A task migration algorithm for load balancing in a distributed system, Proceedings of the XXII Annual Hawaii International Conference on System Sciences (1989) pp. 1041–1048. Google Scholar
    • L. J. Senger, M. J. Santana and R. H. C. Santana, A new approach fo acquiring knowledge of resource usage in parallel applications, Proceedings of International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS'2003) (2003) pp. 607–614. Google Scholar
    • L. J.   Senger , M. J.   Santana and R. H. C.   Santana , Using runtime measurements and historical traces for acquiring knowledge in parallel applications , Lecture Notes in Computer Science   3036 , International Conference on Computational Science (ICCS 2004) ( ) , eds. M.   Bubak et al. ( Springer , 2004 ) . Google Scholar
    • F. A. B. D. Silva and I. D. Scherson, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1911, eds. D. G. Feitelson and L. Rudolph (Springer, 2000) pp. 18–38. CrossrefGoogle Scholar
    • F. G.   Tinetti and A.   Barbieri , An efficient implementation for broadcasting data in parallel applications over ethernet clusters , Proceedings of the 17 th International Conference on Advanced Information Networking and Applications (AINA'03) ( IEEE Computer Society , 2003 ) . Google Scholar