Affinity Driven Distributed Scheduling Algorithms For Parallel Computations

With the advent of many-core architectures efficient scheduling of parallel computations for higher productivity and performance has become very important. Distributed scheduling of parallel computations on multiple places needs to ensure physical (due to resource dependency cycle) deadlock free execution along with efficient space-time trade-offs. This makes distributed scheduling particularly challenging. This report presents two algorithms for affinity driven distributed scheduling of multi-place parallel computations with physical deadlock freedom.

We first present an online affinity driven distributed scheduling algorithm for strict place annotated multi-threaded computations that assumes unconstrained space. We show that the lower bound on the expected execution time is O(max_k (T₁^k/m) + T_∞,n) and the upper bound is O(sum_k(T₁^k /m + T_∞^k)); where ‘k’ is a variable that denotes places from 1 to ‘n’, ‘m’ denotes the number of processors per place, T₁^k denotes the execution time for place ‘k’ using a single processor and T_∞,n denotes the execution time of the computation on ‘n’ places with infinite processors per place. Further, we derive bounds on expected message complexity and probabilistic lower and upper bounds on time and message complexity for this scheduling algorithm.

Next, we present a novel affinity driven online distributed scheduling algorithm assuming bounded space per place. If the input application has no logical deadlocks due to control, data or synchronization dependencies then this scheduling algorithm guarantees deadlock free execution using distributed deadlock avoidance strategy. This distributed scheduling algorithm is designed for terminally strict parallel computations. We prove that the lower bound on the time complexity of this algorithm does not deviate by more than log(D_max) factor (where D_max is the maximum depth of the activity computation tree) compared to the unconstrained space case. We also present proof for distributed deadlock freedom. To the best of our knowledge, this is the first time affinity driven deadlock-free distributed scheduling algorithms have been presented and analyzed for space and time and message bounds under both unconstrained space and bounded space.