On the thread scheduling problem

Wing Ning Li, Jing Fu Jenq

Research output: Contribution to journalArticlepeer-review


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 efficiency. 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.

Original languageEnglish
Pages (from-to)994-1014
Number of pages21
JournalJournal of Universal Computer Science
Issue number10
StatePublished - 2000


Dive into the research topics of 'On the thread scheduling problem'. Together they form a unique fingerprint.

Cite this