• Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    In the distributed memory multiprocessor (DMM) systems, communication overhead, involved among tasks run on different processors, is still large which even offsets the advantages brought by multiprocessor parallelism. In order to execute a parallel application efficiently, it is necessary to choose an appropriate scheduling technology to allocate processors to tasks. In this paper, formal description of general scheduling system including task model, processor model and schedule problem is presented. Three most important problems, concerning schedule in incompletely interconnected homogeneous systems, are studied, which are: (1) How to choose scheduling tasks in sequence, (2) How to choose a route, (3) How to allocate processors to tasks. In addition, the problem on how to choose a route is studied according to store-and-forward and wormhole routing respectively. In the end, a static scheduling algorithm for incompletely interconnected homogeneous systems is constructed according to the solutions to the above three problems.

    Reference
    1  Hwang Jing-jang et al. Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal of Computing, 1989,18(2):244~257 2  Wu Min-you et al. Hypertool: a programming aid for message-passing systems. IEEE Transactions on Parallel and Distributed Systems, 1990,1(3):330~343 3  Yang T et al. PYRROS: static scheduling and code generation for message passing multiprocessors. In: Proceedings of the 6th ACM International Conference of Supercomputing. 1992. 428~437 4  Hesham El-Rewini. Partitioning and scheduling. In: Albert Y H Zomaya ed. Parallel Distributed Computing Handbook. McGraw Hill, Inc., 1996. 239~302 5  Hesham El-Rewini et al. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing, 1990,9(2):138~153 6  Kwok Yu-Kwong et al. Bubble scheduling: a quasi dynamic algorithm for static allocation of tasks to parallel architectures. In: Proceedings of the SPDP'95. Available from: http://www.cs.ust.hk
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

章军,章立生,韩承德.非完全互连同构系统上的静态任务调度.软件学报,1999,10(11):1156-1162

Copy
Share
Article Metrics
  • Abstract:3304
  • PDF: 4438
  • HTML: 0
  • Cited by: 0
History
  • Received:August 28,1998
  • Revised:November 30,1998
You are the first2038598Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063