A Nonprecedence－based Query Schedule Algorithm on Heterogeneous Multiprocessor System

ＡＮｏｎｐｒｅｃｅｄｅｎｃｅ－ｂａｓｅｄＱｕｅｒｙＳｃｈｅｄｕｌｅＡｌｇｏｒｉｔｈｍｏｎＨｅｔｅｒｏｇｅｎｅｏｕｓＭｕｌｔｉｐｒｏｃｅｓｓｏｒＳｙｓｔｅｍ￥ＨｅＪｕｎ；ｂａｎｇＤｉｎｇｘｉｎｇ＆ＺｈｅｎｇＷｅｉｍｉｎ（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐ...

A Nonprecedence-based Query Schedule Algorithm on Heterogeneous Multiprocessor System

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.