Space efficient execution of deterministic parallel programs

作     者：Simpson, DJ Burton, FW 

作者机构：Simon Fraser Univ Burnaby BC V5A 1S6 Canada 

出 版 物：《IEEE TRANSACTIONS ON SOFTWARE ENGINEERING》 (IEEE Trans Software Eng)

年 卷 期：1999年第25卷第6期

页      面：870-882页

核心收录：

基　　金：Natural Science and Engineering Research Council 

主　　题：memory management scheduling worst case performance parallel programming memory bounds shared memory 

摘      要：We model a deterministic parallel program by a directed acyclic graph of tasks, where a task can execute as soon as all tasks preceding it have been executed. Each task can allocate or release an arbitrary amount of memory (i.e., heap memory allocation can be modeled). We call a parallel schedule space efficient if the amount of memory required is at mast equal to the number of processors times the amount of memory required for some depth-first execution of the program by a single processor. We will describe a simple, locally depth-first, scheduling algorithm and shaw that it is always space efficient. Since the scheduling algorithm is greedy, it will be within a factor of two of being optimal with respect to time. For the special case of a program having a series-parallel structure, we show how to efficiently compute the worst case memory requirements over all possible depth-first executions of a program. Finally, we show how scheduling can be decentralized, making the approach scalable to a large number of processors when there is sufficient parallelism.