Optimal parallel algorithm for two-processor scheduling

Abstract

In this paper, we present a parallel algorithm for two-processor scheduling of tasks with treelike precedence constraints (outforests and inforests). The algorithm runs in O(log n) time using n/log n processors on the EREW PRAM. The said algorithm is optimal and has a better time-processor product compared to the existing two-processor scheduling algorithms for outforests and inforests.

Source or Periodical Title

Proceedings of the Conference on High Performance Computing on the Information Superhighway, HPC Asia'97

Page

220-223

Document Type

Article

This document is currently not available here.

Share

COinS