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...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
American Institute of Physics Inc.
2016
|
| Subjects: |
| _version_ | 1796862041751814144 |
|---|---|
| author | Ariffin, W. N. M. Salleh, S. |
| author_facet | Ariffin, W. N. M. Salleh, S. |
| author_sort | Ariffin, W. N. M. |
| collection | ePrints |
| description | 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. |
| first_indexed | 2024-03-05T20:05:34Z |
| format | Conference or Workshop Item |
| id | utm.eprints-73206 |
| institution | Universiti Teknologi Malaysia - ePrints |
| last_indexed | 2024-03-05T20:05:34Z |
| publishDate | 2016 |
| publisher | American Institute of Physics Inc. |
| record_format | dspace |
| spelling | utm.eprints-732062017-11-28T05:01:10Z http://eprints.utm.my/73206/ The partitioning technique of directed cyclic graph for task assignment problem Ariffin, W. N. M. Salleh, S. QA Mathematics 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. American Institute of Physics Inc. 2016 Conference or Workshop Item PeerReviewed Ariffin, W. N. M. and Salleh, S. (2016) The partitioning technique of directed cyclic graph for task assignment problem. In: 23rd Malaysian National Symposium of Mathematical Sciences: Advances in Industrial and Applied Mathematics, SKSM 2015, 24 November 2015 through 26 November 2015, Johor Bahru; Malaysia. https://www.scopus.com/inward/record.uri?eid=2-s2.0-84984535677&doi=10.1063%2f1.4954523&partnerID=40&md5=dbffdd04f86f3380c7dbb4077e0d391c |
| spellingShingle | QA Mathematics Ariffin, W. N. M. Salleh, S. The partitioning technique of directed cyclic graph for task assignment problem |
| title | The partitioning technique of directed cyclic graph for task assignment problem |
| title_full | The partitioning technique of directed cyclic graph for task assignment problem |
| title_fullStr | The partitioning technique of directed cyclic graph for task assignment problem |
| title_full_unstemmed | The partitioning technique of directed cyclic graph for task assignment problem |
| title_short | The partitioning technique of directed cyclic graph for task assignment problem |
| title_sort | partitioning technique of directed cyclic graph for task assignment problem |
| topic | QA Mathematics |
| work_keys_str_mv | AT ariffinwnm thepartitioningtechniqueofdirectedcyclicgraphfortaskassignmentproblem AT sallehs thepartitioningtechniqueofdirectedcyclicgraphfortaskassignmentproblem AT ariffinwnm partitioningtechniqueofdirectedcyclicgraphfortaskassignmentproblem AT sallehs partitioningtechniqueofdirectedcyclicgraphfortaskassignmentproblem |