David Bernstein, Izidor Gertner
ACM Transactions on Programming Languages and Systems (TOPLAS)
Paper
On the Complexity of Scheduling Problems for Parallel/Pipelined Machines
Abstract
We consider a machine model with two functional units, each can be either sequential or pipelined. The complexity of optimal scheduling for a set of expressions on such machines is investigated. We review some previous NP-completeness results, and present several new ones. For one restricted case, a polynomial time algorithm is described and analyzed. © 1989 IEEE
Related
Nurit Dor, Michael Rodeh, et al.
PLDI 2003
Alon Itai, Michael Rodeh
Information and Computation
David Bernstein, Haran Boral, et al.
ACM SIGPLAN Notices