| Abstract |
|---|
| A k-linear schedule may map up to k directed paths of a task graph onto one processor. We consider k-linear scheduling algorithms for the communication cost model of the LogP-machine, i.e. without assumption on processor bounds. The main result of this paper is that optimal k-linear schedules of trees and tree-like task graphs G with n tasks can be computed in time O(n^{k+2} log n) and O(n^{k+3} log n), respectively, if o >= g. These schedules satisfy a capacity constraint, i.e., there are most ceil(L/g) messages in transit from any or to any processor at any time. |
| Contact |
| Wolf Zimmermann Institut fuer Programmstrukturen und Datenorganisation,Universitaet Karlsruhe,P.O. Box 6980,76128 Karlsruhe,Germany zimmer@ipd.info.uni-karlsruhe.de |