JUCS - Journal of Universal Computer Science 6(10): 994-1014, doi: 10.3217/jucs-006-10-0994
On the Thread Scheduling Problem
expand article infoWing-Ning Li‡, Jing-Fu Jenq§
‡ Department of Computer Science and Computer Engineering, University of Arkansas, United States of America§ Department of Computer Science, Montclair State University, United States of America

Corresponding author: Wing-Ning Li ( wingning@uafsysb.uark.edu )

© Wing-Ning Li, Jing-Fu Jenq.
This article is freely available under the J.UCS Open Content License.
Citation: Li W-N, Jenq J-F (2000) On the Thread Scheduling Problem. JUCS - Journal of Universal Computer Science 6(10): 994-1014. https://doi.org/10.3217/jucs-006-10-0994
Open Access
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
scheduling, memory latency, multi-threaded architecture, complexity