Scalable scheduling for symmetric multiprocessors (SMP)

✍ Scribed by Oh-Han Kang; Dharma P. Agrawal

• Book ID: 104344641
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 737 KB
• Volume: 63
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1016/s0743-7315(03)00018-2

✦ Synopsis

We present a task duplication-based scalable scheduling algorithm for Symmetric Multiprocessors (SMP), called S3MP (Scalable Scheduling for SMP), to address the problem of task scheduling. The algorithm pre-allocates network communication resources so as to avoid potential communication conflicts, and generates a schedule for the number of processors available in a SMP. This algorithm employs heuristics to select duplication of tasks so that schedule length is reduced/minimized. The algorithm can schedule the tasks of a directed acyclic graph (DAG) on to the processors of SMP with a worst case time complexity OðV 2 Þ; where V is the number nodes of the DAG. The performance of the S3MP algorithm has been observed by comparing the schedule length under various number of processors and the ratio of communication to computation cost. This algorithm also has been applied to some practical DAGs.