A　Nonprecedence－based　Query　Schedule　Algorithm　on　Heterogeneous　Multiprocessor　System

作     者：He Jun bang Dingxing & Zheng Weimin(Department of Computer Science & Technology,Tsinghua University, Beijing, 100084, China) 

作者机构：Department of Computer Science & Technology Tsinghua University Beijing 100084 China 

出 版 物：《Journal of Systems Engineering and Electronics》 (系统工程与电子技术（英文版）)

年 卷 期：1995年第6卷第3期

页      面：63-69页

核心收录：

学科分类：0711[理学-系统科学] 0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 07[理学] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 071102[理学-系统分析与集成] 

主　　题：Heterogeneous malleable scheduling Makespan Affinity 

摘      要：There has been a number of algorithms designed to handle intra-query or inter-query scheduling in multiprocessor-based parallel database system. They all have the assumption that the processorsare identical. But in some cases, such as shared nothing environment, this assumption would not be fullyvalid. In this paper we devise and evaluate a scheduling algorithm ELLIST to handle nonprecedence-basedheterogeneous malleable scheduling problem. It uses LLIST-NM as subroutine that handles nonmalleablescheduling without precedence and assuming the processors are identical. Even though the problem we considered is NP-hard in the strong sense, the schedule generated by our algorithm is seen experimentally toachieve results that are close to optimum when there are enough tasks to be scheduled.