IEICE TRANSACTIONS on transactions
An Efficient Algorithm for Determining the Minimum Number of Parallel Processors Required to Process a Large Number of Parallel Tasks
Summary :
In this paper considered is the problem of scheduling a large number of parallel tasks (tasks having the same release and due times) on parallel processors. It is assumed that tasks all require one unit processing time, and the release and due times are non-negative integers. Task sets each of which consists of parallel tasks are dealt with instead of individual tasks in the conventional manner. The minimum number of processors required to process the given task sets is obtained by increasing stepwise the number of processors. To this end the minimal subset of task sets which cannot be allocated to a certain fixed number of processors is determined by a linear-order breadth-first search using the result of task assignment in two different ways, one top-down and the other bottom-up. The time complexity of the overall procedure is O(min(n, m)(m
- Publication
- IEICE TRANSACTIONS on transactions Vol.E72-E No.10 pp.1141-1148
- Publication Date
- 1989/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takao OZAWA, "An Efficient Algorithm for Determining the Minimum Number of Parallel Processors Required to Process a Large Number of Parallel Tasks" in IEICE TRANSACTIONS on transactions,
vol. E72-E, no. 10, pp. 1141-1148, October 1989, doi: .
Abstract: In this paper considered is the problem of scheduling a large number of parallel tasks (tasks having the same release and due times) on parallel processors. It is assumed that tasks all require one unit processing time, and the release and due times are non-negative integers. Task sets each of which consists of parallel tasks are dealt with instead of individual tasks in the conventional manner. The minimum number of processors required to process the given task sets is obtained by increasing stepwise the number of processors. To this end the minimal subset of task sets which cannot be allocated to a certain fixed number of processors is determined by a linear-order breadth-first search using the result of task assignment in two different ways, one top-down and the other bottom-up. The time complexity of the overall procedure is O(min(n, m)(m
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e72-e_10_1141/_p
Copy
@ARTICLE{e72-e_10_1141,
author={Takao OZAWA, },
journal={IEICE TRANSACTIONS on transactions},
title={An Efficient Algorithm for Determining the Minimum Number of Parallel Processors Required to Process a Large Number of Parallel Tasks},
year={1989},
volume={E72-E},
number={10},
pages={1141-1148},
abstract={In this paper considered is the problem of scheduling a large number of parallel tasks (tasks having the same release and due times) on parallel processors. It is assumed that tasks all require one unit processing time, and the release and due times are non-negative integers. Task sets each of which consists of parallel tasks are dealt with instead of individual tasks in the conventional manner. The minimum number of processors required to process the given task sets is obtained by increasing stepwise the number of processors. To this end the minimal subset of task sets which cannot be allocated to a certain fixed number of processors is determined by a linear-order breadth-first search using the result of task assignment in two different ways, one top-down and the other bottom-up. The time complexity of the overall procedure is O(min(n, m)(m
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - An Efficient Algorithm for Determining the Minimum Number of Parallel Processors Required to Process a Large Number of Parallel Tasks
T2 - IEICE TRANSACTIONS on transactions
SP - 1141
EP - 1148
AU - Takao OZAWA
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 10
JA - IEICE TRANSACTIONS on transactions
Y1 - October 1989
AB - In this paper considered is the problem of scheduling a large number of parallel tasks (tasks having the same release and due times) on parallel processors. It is assumed that tasks all require one unit processing time, and the release and due times are non-negative integers. Task sets each of which consists of parallel tasks are dealt with instead of individual tasks in the conventional manner. The minimum number of processors required to process the given task sets is obtained by increasing stepwise the number of processors. To this end the minimal subset of task sets which cannot be allocated to a certain fixed number of processors is determined by a linear-order breadth-first search using the result of task assignment in two different ways, one top-down and the other bottom-up. The time complexity of the overall procedure is O(min(n, m)(m
ER -
English
