Scheduling outtrees of height one in the LogP model
We study the complexity of scheduling fork graphs in the LogP model of parallel computation. This model is a model that characterises a parallel computer system by four parameters: the latency L, the overhead o, the gap g and the number of processors P. It will be proved that constructing minimum-length schedules for fork graphs in the LogP model is a strongly NP-hard optimisation problem. We also present a polynomial-time algorithm that constructs schedules that are at most twice as long as minimum-length schedules. Moreover, we prove that if all tasks of a fork graph have the same execution length, then a minimum-length schedule can be constructed in polynomial time. (C) 2000 Elsevier Science B.V. All rights reserved.
logp model fork graphs multi-processor scheduling communication latency communication overhead