Applying Cilk in provably efficient task scheduling

We examine the application of Cilk, a C-based runtime system for multithrea ded parallel programming in task scheduling Given a task graph G, the outpu t of the scheduling algorithm is an intermediate schedule S which, when int erpreted by the Cilk runtime scheduler, guarantees that the tasks will be e xecuted concurrently in a manner consistent with the precedence requirement of G, However, there are certain precedence relations that cannot be expre ssed exactly in the Cilk model-hence no algorithms can guarantee an optimal schedule for task graphs containing such relations. Nonetheless, this limi tation does not prevent Cilk from becoming a useful tool for task schedulin g. Let n and e denote the number of nodes and edges of a task graph, By usi ng Tarjan's disjoint-set algorithm to handle tasks that can be scheduled co ncurrently, 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 wi th P processors, the expected completion time for the scheduled tasks achie ves a near-optimum of Gamma(P) approximate to Gamma(1)/P + 1.5 Gamma(infini ty), where Gamma(1) denotes the work, i.e. the sequential execution time of all tasks, and Gamma(infinity) denotes the critical path, i.e. the total e xecution time of all tasks lying on the longest dependency path. Besides co nfirming 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.