The partitioning technique of directed cyclic graph for task assignment problem

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 simple partitioning technique is presented to assign a number of tasks onto two processors. Th...

Full description

Saved in:
Bibliographic Details
Main Authors: Ariffin, Wan Nor Munirah, Salleh, Shaharuddin
Format: Conference Proceeding
Language:English
Subjects:
Computer networks
Distributed processing
Mapping
Operations research
Partitioning
Processors
Task scheduling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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 simple partitioning technique 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 Kernighan-Lin algorithm is applied to obtain the partition of tasks. Combining the technique of reduction and partitioning lead to an efficient graph-mapping concept.
ISSN:0094-243X
1551-7616
DOI:10.1063/1.4954523