On The Thread Scheduling Problem

Wing Ning Li, John Jenq

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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-hard. New algorithms for analyzing a data dependency graph and for estimating the required minimum number of PEs needed to achieve certain finishing time are presented. The new methods improve upon some of the existing analysis and transformation techniques.

Original languageEnglish
Title of host publicationProceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1
EditorsP.P. Wang, P.P. Wang
Pages449-452
Number of pages4
Edition1
StatePublished - 1 Dec 2000
EventProceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000 - Atlantic City, NJ, United States
Duration: 27 Feb 20003 Mar 2000

Publication series

NameProceedings of the Joint Conference on Information Sciences
Number1
Volume5

Other

OtherProceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000
CountryUnited States
CityAtlantic City, NJ
Period27/02/003/03/00

Fingerprint

Scheduling
Data storage equipment

Cite this

Li, W. N., & Jenq, J. (2000). On The Thread Scheduling Problem. In P. P. Wang, & P. P. Wang (Eds.), Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1 (1 ed., pp. 449-452). (Proceedings of the Joint Conference on Information Sciences; Vol. 5, No. 1).
Li, Wing Ning ; Jenq, John. / On The Thread Scheduling Problem. Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1. editor / P.P. Wang ; P.P. Wang. 1. ed. 2000. pp. 449-452 (Proceedings of the Joint Conference on Information Sciences; 1).
@inproceedings{7cba6a86e52d4f86bc37f7ba409ca2de,
title = "On The Thread Scheduling Problem",
abstract = "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-hard. New algorithms for analyzing a data dependency graph and for estimating the required minimum number of PEs needed to achieve certain finishing time are presented. The new methods improve upon some of the existing analysis and transformation techniques.",
author = "Li, {Wing Ning} and John Jenq",
year = "2000",
month = "12",
day = "1",
language = "English",
isbn = "0964345692",
series = "Proceedings of the Joint Conference on Information Sciences",
number = "1",
pages = "449--452",
editor = "P.P. Wang and P.P. Wang",
booktitle = "Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1",
edition = "1",

}

Li, WN & Jenq, J 2000, On The Thread Scheduling Problem. in PP Wang & PP Wang (eds), Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1. 1 edn, Proceedings of the Joint Conference on Information Sciences, no. 1, vol. 5, pp. 449-452, Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Atlantic City, NJ, United States, 27/02/00.

On The Thread Scheduling Problem. / Li, Wing Ning; Jenq, John.

Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1. ed. / P.P. Wang; P.P. Wang. 1. ed. 2000. p. 449-452 (Proceedings of the Joint Conference on Information Sciences; Vol. 5, No. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - On The Thread Scheduling Problem

AU - Li, Wing Ning

AU - Jenq, John

PY - 2000/12/1

Y1 - 2000/12/1

N2 - 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-hard. New algorithms for analyzing a data dependency graph and for estimating the required minimum number of PEs needed to achieve certain finishing time are presented. The new methods improve upon some of the existing analysis and transformation techniques.

AB - 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-hard. New algorithms for analyzing a data dependency graph and for estimating the required minimum number of PEs needed to achieve certain finishing time are presented. The new methods improve upon some of the existing analysis and transformation techniques.

UR - http://www.scopus.com/inward/record.url?scp=1642305693&partnerID=8YFLogxK

M3 - Conference contribution

SN - 0964345692

SN - 9780964345690

T3 - Proceedings of the Joint Conference on Information Sciences

SP - 449

EP - 452

BT - Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1

A2 - Wang, P.P.

A2 - Wang, P.P.

ER -

Li WN, Jenq J. On The Thread Scheduling Problem. In Wang PP, Wang PP, editors, Proceedings of the Fifth Joint Conference on Information Sciences, JCIS 2000, Volume 1. 1 ed. 2000. p. 449-452. (Proceedings of the Joint Conference on Information Sciences; 1).