高级检索
    赵明宇 张田文. 一种分布式计算环境下并行应用的调度算法[J]. 计算机研究与发展, 2008, 45(4): 695-705.
    引用本文: 赵明宇 张田文. 一种分布式计算环境下并行应用的调度算法[J]. 计算机研究与发展, 2008, 45(4): 695-705.
    Zhao Mingyu and Zhang Tianwen. DAG Scheduling for Synchronous Communication in the Network Computing Environment[J]. Journal of Computer Research and Development, 2008, 45(4): 695-705.
    Citation: Zhao Mingyu and Zhang Tianwen. DAG Scheduling for Synchronous Communication in the Network Computing Environment[J]. Journal of Computer Research and Development, 2008, 45(4): 695-705.

    一种分布式计算环境下并行应用的调度算法

    DAG Scheduling for Synchronous Communication in the Network Computing Environment

    • 摘要: 在网络上运行并行程序不像在并行机上那样可靠,因此对于关键应用需要在应用级保证消息传输的可靠性.人们对以异步方式进行通信的并行程序的调度问题提出了大量的启发式算法,但是它们所产生的调度结果不能用于以同步方式通信的并行程序.提出的PRGSC算法可以防止由同步通信所引起的死锁问题,而且可以降低同步通信所带来的时延的影响.形式化地证明了死锁检测算法的正确性,并通过仿真实验说明了PRGSC算法有很好的调度质量.

       

      Abstract: Although the advance in high-speed networks is rapid, parallel computing on the network computing environments is not so reliable as that performed on parallel machines. Therefore, many applications must rely on synchronous communication in the form of application-level handshaking. In general, application-level handshaking may enhance the reliability of executing parallel programs on the network computing environments, but also simplify the error handling for communication, maintaining easy programability. However, synchronization introduces a waiting time for the sender and an overhead to the already high cost of message-passing. Furthermore, synchronization may result in deadlock among communicating tasks. Most heuristics for scheduling address asynchronous communication DAG is proposed, but they are not suitable for the synchronous ones. Proposed in this paper is a novel algorithm for the synchronous scheduling problem, which is called parameters relation graph-based synchronous clustering (PRGSC). The PRGSC algorithm introduces a parameter relation graph (PRG), which represents relations of timing parameters of tasks and dynamically varies in the scheduling process, for the deadlock detection. In every scheduling step, PRGSC algorithm avoids the deadlock caused by the synchronous communication through examination of the PRG. Meanwhile, it could alleviate the impact of synchronous communicating delay on the makespan by simultaneously considering the ready tasks and scheduled tasks. Simulation shows that the PRGSC algorithm has better performance than the CASC algorithm which deals with the same type of problems.

       

    /

    返回文章
    返回