© 1999 by British Computer Society
Applying Cilk in Provably Efficient Task Scheduling
1 Centre for Advanced Information Systems, Nanyang Technological University, Singapore Email: vyvee@singnet.com.sg
We examine the application of Cilk, a C-based runtime system for multithreaded parallel programming in task scheduling. Given a task graph G, the output of the scheduling algorithm is an intermediate schedule $\mathcal{S}$ which, when interpreted by the Cilk runtime scheduler, guarantees that the tasks will be executed concurrently in a manner consistent with the precedence requirement of G. However, there are certain precedence relations that cannot be expressed exactly in the Cilk model—hence no algorithms can guarantee an optimal schedule for task graphs containing such relations. Nonetheless, this limitation does not prevent Cilk from becoming a useful tool for task scheduling. Let n and e denote the number of nodes and edges of a task graph. By using Tarjan's disjoint-set algorithm to handle tasks that can be scheduled concurrently, we demonstrate that an intermediate schedule can be derived in $O(n+e)$ time for any task graph of practical size. We further show that with P processors, the expected completion time for the scheduled tasks achieves a near-optimum of $\Gamma_{P} \approx \Gamma_{1} / P + 1.5\Gamma_{\infty}$, where $\Gamma_{1}$ denotes the work, i.e. the sequential execution time of all tasks, and $\Gamma_{\infty}$ denotes the critical path, i.e. the total execution time of all tasks lying on the longest dependency path. Besides confirming its expressive power in handling complicated types of concurrency, our results show that the performance guarantee of Cilk can lead to a new efficient approach for task scheduling.
Received 29 October, 1998. Revised 6 October, 1999.