Scheduling interval orders with communication delays in parallel

作     者：Stadtherr, H 

作者机构：Tech Univ Munich Inst Informat D-80290 Munich Germany 

出 版 物：《JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING》 (并行与分布式计算杂志)

年 卷 期：2004年第64卷第1期

页      面：1-15页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：scheduling parallel algorithms interval orders PRAM 

摘      要：We investigate the complexity of computing an optimal m-processor schedule for a system of n unit execution time tasks constrained by an interval order, subject to unit delays for interprocessor communication. Our results are twofold. First, we show that the problem can be solved by a sequential algorithm in linear time. Second, we present a fast parallel algorithm that solves the problem on the EREW PRAM in time O(log(2)n) using n(3)/log n processors and on the CRCW PRAM in time O(log n) using n(3) processors. This is the first NC algorithm for this problem. (C) 2003 Elsevier Inc. All rights reserved.