IMPROVING SCHEDULING OF COMMUNICATION INTENSIVE PARALLEL APPLICATIONS ON HETEROGENEOUS COMPUTING ENVIRONMENTS
Abstract
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 , 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 , 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. Culler , 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 - , Job Scheduling Strategies for Parallel Processing,
Lecture Notes in Computer Science 2221, eds.D. G. Feitelson and L. Rudolph (Springer, 2001) pp. 188–205. Crossref, Google Scholar - , Job Scheduling Strategies for Parallel Processing 1459, eds.
D. G. Feitelson and L. Rudolph (Springer, 1998) pp. 1–24. Crossref, Google Scholar - IEEE Transactions on Parallel and Distributed Systems 14(1), 39 (2003). Crossref, ISI, Google Scholar
- T. C. Kerrigan. TSCP benchmark scores, 2004. http://home.comcast.net/~tckerrigan/bench.html . Google Scholar
-
V. Kumar , Introduction to Parallel Computing: Design and Analysis of Algorithms ( Benjamin-Cummings Publishing Co., Inc. , 1994 ) . Google Scholar -
C. Liu , 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- IEEE Transactions on Sofiware Engineering 11(10), 1153 (1985). ISI, Google 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 ScholarS. 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 ScholarJ. 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 ScholarL. 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 ( Springer , 2004 ) . Google Scholar - , Job Scheduling Strategies for Parallel Processing,
Lecture Notes in Computer Science 1911, eds.D. G. Feitelson and L. Rudolph (Springer, 2000) pp. 18–38. Crossref, Google 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


