Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation
Task scheduling is the key to the full utilization of heterogeneous cloud capabilities for parallel processing of big graphs. Most graph processing systems adopt single-granularity scheduling mechanisms without considering the heterogeneity of the cloud, leading to poor performance. To alleviate it...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8732339/ |
| _version_ | 1818877592234622976 |
|---|---|
| author | Kekun Hu Guosun Zeng Shuang Ding Huowen Jiang |
| author_facet | Kekun Hu Guosun Zeng Shuang Ding Huowen Jiang |
| author_sort | Kekun Hu |
| collection | DOAJ |
| description | Task scheduling is the key to the full utilization of heterogeneous cloud capabilities for parallel processing of big graphs. Most graph processing systems adopt single-granularity scheduling mechanisms without considering the heterogeneity of the cloud, leading to poor performance. To alleviate it by learning from the excellent directed acyclic graph (DAG)-based scheduling techniques accumulated in traditional parallel computing, we first present a streaming DAG-construction heuristic. It transforms a big graph along with graph traversal algorithms to be carried out into a DAG. We then propose a three-phase heterogeneous-aware cluster-scheduling algorithm to schedule the DAG into a heterogeneous cloud for parallel processing. In the first phase, we design a parallel linear clustering algorithm to cluster the DAG into a series of linear clusters with different granularities. In the second phase, we design a heterogeneous-aware load balancing algorithm to map these clusters to different computational nodes of the cloud. In the last phase, we design a task ordering algorithm to assigns these clusters as-early-as-possible start times. The experimental results show that our scheme can generate high-quality schedules and improve the efficiency and performance of parallel processing of big graphs in the heterogeneous cloud. |
| first_indexed | 2024-12-19T14:00:44Z |
| format | Article |
| id | doaj.art-10b85ec4a5e546779e0f92ec61528e92 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-19T14:00:44Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-10b85ec4a5e546779e0f92ec61528e922022-12-21T20:18:27ZengIEEEIEEE Access2169-35362019-01-017770707708210.1109/ACCESS.2019.29214778732339Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG TransformationKekun Hu0https://orcid.org/0000-0003-3433-9566Guosun Zeng1Shuang Ding2https://orcid.org/0000-0002-1952-5152Huowen Jiang3Department of Computer Science and Technology, Tongji University, Shanghai, ChinaDepartment of Computer Science and Technology, Tongji University, Shanghai, ChinaSchool of Software, Henan University, Kaifeng, ChinaCollage of Mathematics & Computer Science, Jiangxi Science & Technology Normal University, Nanchang, ChinaTask scheduling is the key to the full utilization of heterogeneous cloud capabilities for parallel processing of big graphs. Most graph processing systems adopt single-granularity scheduling mechanisms without considering the heterogeneity of the cloud, leading to poor performance. To alleviate it by learning from the excellent directed acyclic graph (DAG)-based scheduling techniques accumulated in traditional parallel computing, we first present a streaming DAG-construction heuristic. It transforms a big graph along with graph traversal algorithms to be carried out into a DAG. We then propose a three-phase heterogeneous-aware cluster-scheduling algorithm to schedule the DAG into a heterogeneous cloud for parallel processing. In the first phase, we design a parallel linear clustering algorithm to cluster the DAG into a series of linear clusters with different granularities. In the second phase, we design a heterogeneous-aware load balancing algorithm to map these clusters to different computational nodes of the cloud. In the last phase, we design a task ordering algorithm to assigns these clusters as-early-as-possible start times. The experimental results show that our scheme can generate high-quality schedules and improve the efficiency and performance of parallel processing of big graphs in the heterogeneous cloud.https://ieeexplore.ieee.org/document/8732339/Heterogeneous cloudbig graph traversal taskparallel processingDAGcluster-schedulinggranularity |
| spellingShingle | Kekun Hu Guosun Zeng Shuang Ding Huowen Jiang Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation IEEE Access Heterogeneous cloud big graph traversal task parallel processing DAG cluster-scheduling granularity |
| title | Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation |
| title_full | Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation |
| title_fullStr | Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation |
| title_full_unstemmed | Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation |
| title_short | Cluster-Scheduling Big Graph Traversal Task for Parallel Processing in Heterogeneous Cloud Based on DAG Transformation |
| title_sort | cluster scheduling big graph traversal task for parallel processing in heterogeneous cloud based on dag transformation |
| topic | Heterogeneous cloud big graph traversal task parallel processing DAG cluster-scheduling granularity |
| url | https://ieeexplore.ieee.org/document/8732339/ |
| work_keys_str_mv | AT kekunhu clusterschedulingbiggraphtraversaltaskforparallelprocessinginheterogeneouscloudbasedondagtransformation AT guosunzeng clusterschedulingbiggraphtraversaltaskforparallelprocessinginheterogeneouscloudbasedondagtransformation AT shuangding clusterschedulingbiggraphtraversaltaskforparallelprocessinginheterogeneouscloudbasedondagtransformation AT huowenjiang clusterschedulingbiggraphtraversaltaskforparallelprocessinginheterogeneouscloudbasedondagtransformation |