A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization
A complex computing problem can be solved efficiently on a system with multiple computing nodes by dividing its implementation code into several parallel processing modules or tasks that can be formulated as directed acyclic graph (DAG) problems. The DAG jobs may be mapped to and scheduled on the co...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/404375 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559794391613440 |
|---|---|
| author | Yuyi Jiang Zhiqing Shao Yi Guo |
| author_facet | Yuyi Jiang Zhiqing Shao Yi Guo |
| author_sort | Yuyi Jiang |
| collection | DOAJ |
| description | A complex computing problem can be solved efficiently on a system with multiple computing nodes by dividing its implementation code into several parallel processing modules or tasks that can be formulated as directed acyclic graph (DAG) problems. The DAG jobs may be mapped to and scheduled on the computing nodes to minimize the total execution time. Searching an optimal DAG scheduling solution is considered to be NP-complete. This paper proposed a tuple molecular structure-based chemical reaction optimization (TMSCRO) method for DAG scheduling on heterogeneous computing systems, based on a very recently proposed metaheuristic method, chemical reaction optimization (CRO). Comparing with other CRO-based algorithms for DAG scheduling, the design of tuple reaction molecular structure and four elementary reaction operators of TMSCRO is more reasonable. TMSCRO also applies the concept of constrained critical paths (CCPs), constrained-critical-path directed acyclic graph (CCPDAG) and super molecule for accelerating convergence. In this paper, we have also conducted simulation experiments to verify the effectiveness and efficiency of TMSCRO upon a large set of randomly generated graphs and the graphs for real world problems. |
| format | Article |
| id | doaj-art-d69a05d81d964423bd3583467740957f |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-d69a05d81d964423bd3583467740957f2025-02-03T01:29:18ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/404375404375A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction OptimizationYuyi Jiang0Zhiqing Shao1Yi Guo2College of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, ChinaCollege of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, ChinaCollege of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, ChinaA complex computing problem can be solved efficiently on a system with multiple computing nodes by dividing its implementation code into several parallel processing modules or tasks that can be formulated as directed acyclic graph (DAG) problems. The DAG jobs may be mapped to and scheduled on the computing nodes to minimize the total execution time. Searching an optimal DAG scheduling solution is considered to be NP-complete. This paper proposed a tuple molecular structure-based chemical reaction optimization (TMSCRO) method for DAG scheduling on heterogeneous computing systems, based on a very recently proposed metaheuristic method, chemical reaction optimization (CRO). Comparing with other CRO-based algorithms for DAG scheduling, the design of tuple reaction molecular structure and four elementary reaction operators of TMSCRO is more reasonable. TMSCRO also applies the concept of constrained critical paths (CCPs), constrained-critical-path directed acyclic graph (CCPDAG) and super molecule for accelerating convergence. In this paper, we have also conducted simulation experiments to verify the effectiveness and efficiency of TMSCRO upon a large set of randomly generated graphs and the graphs for real world problems.http://dx.doi.org/10.1155/2014/404375 |
| spellingShingle | Yuyi Jiang Zhiqing Shao Yi Guo A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization The Scientific World Journal |
| title | A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization |
| title_full | A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization |
| title_fullStr | A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization |
| title_full_unstemmed | A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization |
| title_short | A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Tuple-Based Chemical Reaction Optimization |
| title_sort | dag scheduling scheme on heterogeneous computing systems using tuple based chemical reaction optimization |
| url | http://dx.doi.org/10.1155/2014/404375 |
| work_keys_str_mv | AT yuyijiang adagschedulingschemeonheterogeneouscomputingsystemsusingtuplebasedchemicalreactionoptimization AT zhiqingshao adagschedulingschemeonheterogeneouscomputingsystemsusingtuplebasedchemicalreactionoptimization AT yiguo adagschedulingschemeonheterogeneouscomputingsystemsusingtuplebasedchemicalreactionoptimization AT yuyijiang dagschedulingschemeonheterogeneouscomputingsystemsusingtuplebasedchemicalreactionoptimization AT zhiqingshao dagschedulingschemeonheterogeneouscomputingsystemsusingtuplebasedchemicalreactionoptimization AT yiguo dagschedulingschemeonheterogeneouscomputingsystemsusingtuplebasedchemicalreactionoptimization |