Task scheduling for directed cyclic graph using matching technique
The scheduling and mapping of task graph to processors is considered to be the most crucial NP-complete in parallel and distributed computing systems. In this paper, the theoretical graph application using matching is presented to assign a number of tasks onto two processors. This paper addresses a...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Hikari Ltd.
2015
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/id/eprint/58885/ http://dx.doi.org/10.12988/ces.2015.56193 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Universiti Teknologi Malaysia |
| Summary: | The scheduling and mapping of task graph to processors is considered to be the most crucial NP-complete in parallel and distributed computing systems. In this paper, the theoretical graph application using matching is presented to assign a number of tasks onto two processors. This paper addresses a directed-weighted cyclic graph. The effort is to reduce the graph onto directed acyclic graph. A co-comparability graph is presented in order to assign the task onto two processors. Combining several innovative techniques lead to an efficient graph-mapping concept, called DCGSimplify. Our simulation model found that the proposed techniques and algorithms are easy to be implemented. |
|---|