Presentation	1999/1/21 The Scheduling onto Hypercubes Satoshi TAYU,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	The task scheduling has been extensively investigated in connection with parallel computing. In those studies, the structure of the parallel processor is restricted to be fully connected. However, the structures of the realistic parallel processor models, such as hypercubes, meshs, and so forth, are not fully connected and then, the number of those connection links is small. Since parallel processors are not fully connected in the realistic model, we have to choose the communication routings to reduce the data conflictions on the links when we schedule tasks. Taking the communication routings into account, the problem become complicated. We formulate such schedulings and show that the problem scheduling trees onto hypercube is NP-complete.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Scheduling / Hypercube / Parallel processor / Task / Embedding
Paper #	CAS98-70
Date of Issue

Conference Information
Committee	CAS
Conference Date	1999/1/21(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Circuits and Systems (CAS)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	The Scheduling onto Hypercubes
Sub Title (in English)
Keyword(1)	Scheduling
Keyword(2)	Hypercube
Keyword(3)	Parallel processor
Keyword(4)	Task
Keyword(5)	Embedding
1st Author's Name	Satoshi TAYU
1st Author's Affiliation	School of Information Science, Japan Advanced Institute of Science and Technology()
Date	1999/1/21
Paper #	CAS98-70
Volume (vol)	vol.98
Number (no)	515
Page	pp.pp.-
#Pages	8
Date of Issue