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(maxk (T1k/m) + T∞,n) and the upper bound is O(sumk(T1k /m + T∞k)); where ‘k’ is a variable that denotes places from 1 to ‘n’, ‘m’ denotes the number of processors per place, T1k 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(Dmax) factor (where Dmax 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.
By: Shivali Agarwal, Ankur Narang, Rudrapatna K Shayamasundar
Published in: RI09010 in 2009
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .