New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some dat...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-07-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/12/7/142 |
| _version_ | 1818509179178975232 |
|---|---|
| author | Qinghai Li Chang Wu Yu |
| author_facet | Qinghai Li Chang Wu Yu |
| author_sort | Qinghai Li |
| collection | DOAJ |
| description | For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar. |
| first_indexed | 2024-12-10T22:41:56Z |
| format | Article |
| id | doaj.art-325e22a94bfc483983503ca9ea8df48a |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-10T22:41:56Z |
| publishDate | 2019-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-325e22a94bfc483983503ca9ea8df48a2022-12-22T01:30:41ZengMDPI AGAlgorithms1999-48932019-07-0112714210.3390/a12070142a12070142New Bipartite Graph Techniques for Irregular Data Redistribution SchedulingQinghai Li0Chang Wu Yu1Department of Electronic Engineering, Zhejiang Industry and Trade Vocational College, East Road 717, Wenzhou 325003, ChinaDepartment of Computer Science and Information Engineering, Chung Hua University, No.707, Sec.2, WuFu Road, Hsinchu 30012, TaiwanFor many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar.https://www.mdpi.com/1999-4893/12/7/142data redistributionschedulingedge coloringapproximation algorithmsgraph techniquesbipartite graphsalgorithm design |
| spellingShingle | Qinghai Li Chang Wu Yu New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling Algorithms data redistribution scheduling edge coloring approximation algorithms graph techniques bipartite graphs algorithm design |
| title | New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling |
| title_full | New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling |
| title_fullStr | New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling |
| title_full_unstemmed | New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling |
| title_short | New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling |
| title_sort | new bipartite graph techniques for irregular data redistribution scheduling |
| topic | data redistribution scheduling edge coloring approximation algorithms graph techniques bipartite graphs algorithm design |
| url | https://www.mdpi.com/1999-4893/12/7/142 |
| work_keys_str_mv | AT qinghaili newbipartitegraphtechniquesforirregulardataredistributionscheduling AT changwuyu newbipartitegraphtechniquesforirregulardataredistributionscheduling |