On the thread scheduling problem

Wing Ning Li, Jing Fu Jenq

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)994-1014
Number of pages21
JournalJournal of Universal Computer Science
Volume6
Issue number10
StatePublished - 1 Dec 2000

Fingerprint

Thread
Dependency Graph
Scheduling Problem
Data Dependency
Scheduling
Compiler
Latency
NP-complete problem
Lower bound
Data storage equipment
Estimate
Form

Cite this

Li, Wing Ning ; Jenq, Jing Fu. / On the thread scheduling problem. In: Journal of Universal Computer Science. 2000 ; Vol. 6, No. 10. pp. 994-1014.
@article{67c114bdda144219b72c1b55d6e244e4,
title = "On the thread scheduling problem",
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.",
author = "Li, {Wing Ning} and Jenq, {Jing Fu}",
year = "2000",
month = "12",
day = "1",
language = "English",
volume = "6",
pages = "994--1014",
journal = "Journal of Universal Computer Science",
issn = "0948-695X",
publisher = "Technische Universitat Graz from Austria",
number = "10",

}

On the thread scheduling problem. / Li, Wing Ning; Jenq, Jing Fu.

In: Journal of Universal Computer Science, Vol. 6, No. 10, 01.12.2000, p. 994-1014.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the thread scheduling problem

AU - Li, Wing Ning

AU - Jenq, Jing Fu

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

AN - SCOPUS:33947115446

VL - 6

SP - 994

EP - 1014

JO - Journal of Universal Computer Science

JF - Journal of Universal Computer Science

SN - 0948-695X

IS - 10

ER -