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 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 language | English |
|---|---|
| Pages (from-to) | 994-1014 |
| Number of pages | 21 |
| Journal | Journal of Universal Computer Science |
| Volume | 6 |
| Issue number | 10 |
| State | Published - 1 Dec 2000 |
Fingerprint
Cite this
}
On the thread scheduling problem. / Li, Wing Ning; Jenq, John.
In: Journal of Universal Computer Science, Vol. 6, No. 10, 01.12.2000, p. 994-1014.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - On the thread scheduling problem
AU - Li, Wing Ning
AU - Jenq, John
PY - 2000/12/1
Y1 - 2000/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33947115446&partnerID=8YFLogxK
M3 - Article
VL - 6
SP - 994
EP - 1014
JO - Journal of Universal Computer Science
JF - Journal of Universal Computer Science
SN - 0948-695X
IS - 10
ER -