Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 10

available in:   PDF (301 kB) PS (91 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-10-0994


On the Thread Scheduling Problem

Wing-Ning Li (Department of Computer Science and Computer Engineering, University of Arkansas, USA)

Jing-Fu Jenq (Department of Computer Science, Montclair State University, USA)

Abstract: This paper considers the thread scheduling problem. The thread scheduling problem abstracts the problem of minimizing memory latency, using a directed data dependency graph generated form a compiler, to improve run time effciency. Two thread scheduling problems are formulated and shown to be strongly NP-complete. New methods and algorithms for analyzing a data dependency graph in order to compute the theoretical best runtime (lower bound of the finishing time) and to estimate the required minimum number of PEs needed to achieve certain finishing time are presented. The new methods and algorithms improve upon some of the existing analysis and transformation techniques.

Keywords: complexity, memory latency, multi-threaded architecture, scheduling