Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


Heterogeneous systems become popular in both client and cloud. A parallel program can incur operations on multiple processing resources such as CPU, GPU, and vector processor units. This paper investigates scheduling problems on functionally heterogeneous systems with the objective of minimizing the completion time of parallel jobs. We ?rst present performance bounds of online scheduling and show that any online algorithm is at best around (K + 1)-competitive with respect to job completion time, where K is the total number of resource types. There exist ”bad” jobs that prevent any online algorithms from obtaining good interleaving of heterogeneous tasks. This lower bound suggests that the relative performance of online algorithms versus an of?ine optimal could degrade linearly as types of heterogeneous resources increase. The limitation of online scheduling motivates our study of how additional of?ine or lookahead information can help improve scheduling performance. We propose a Multi-Queue Balancing algorithm (MQB) that effectively transforms the problem of minimizing completion time to one of maximizing utilization of heterogeneous resources. It promotes interleaving of heterogeneous tasks through balancing the task queues of different types. Our simulation results suggest that MQB reduces the execution time of online greedy algorithms up to 40% over various workloads and outperforms other of?ine schemes in most cases. Furthermore, MQB can use limited and approximated of?ine information to improve scheduling decisions.

Questions and Answers

You need to be logged in to be able to post here.