Task Clustering and Scheduling to Multiprocessors with Duplication

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Li Guodong Articles by Chen Daoxu Articles by Wang Daming Articles by Zhang Defu

International Parallel and Distributed Processing Symposium (IPDPS'03)

Nice, France

April 22-April 26

ISBN: 0-7695-1926-1

	ASCII Text	x
	Li Guodong, Chen Daoxu, Wang Daming, Zhang Defu, "Task Clustering and Scheduling to Multiprocessors with Duplication," Parallel and Distributed Processing Symposium, International, pp. 6b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003.

	BibTex	x
	@article{ 10.1109/IPDPS.2003.1213079, author = {Li Guodong and Chen Daoxu and Wang Daming and Zhang Defu}, title = {Task Clustering and Scheduling to Multiprocessors with Duplication}, journal ={Parallel and Distributed Processing Symposium, International}, volume = {0}, year = {2003}, issn = {1530-2075}, pages = {6b}, doi = {http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213079}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel and Distributed Processing Symposium, International TI - Task Clustering and Scheduling to Multiprocessors with Duplication SN - 1530-2075 SP EP A1 - Li Guodong, A1 - Chen Daoxu, A1 - Wang Daming, A1 - Zhang Defu, PY - 2003 KW - null VL - 0 JA - Parallel and Distributed Processing Symposium, International ER -

Li Guodong, Nanjing University

Chen Daoxu, Nanjing University

Wang Daming, Nanjing University

Zhang Defu, Nanjing University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213079

Optimal task-duplication-based scheduling of tasks represented by a directed acyclic graph (DAG) onto a set of homogenous distributed memory processors, is a strong NP-hard problem. In this paper we present a clustering and scheduling algorithm with time complexity 0(v³logv), where v is the number of nodes, which is able to generate optimal schedule for some specific DAGs. For arbitrary DAGs, the schedule generated is at most two times as the optimal one. Simulation results show that the performance of TCSD is superb to those of four renowned algorithms: PY, TDS, TCS and CPFD.

Citation:

Li Guodong, Chen Daoxu, Wang Daming, Zhang Defu, "Task Clustering and Scheduling to Multiprocessors with Duplication," ipdps, pp.6b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.