On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929500538798080 |
|---|---|
| author | Liu, Wei Chen, Jian-Jia Yang, Yongjie |
| author_facet | Liu, Wei Chen, Jian-Jia Yang, Yongjie |
| contents | We study a graph partition problem where we are given a directed acyclic graph (DAG) whose vertices and arcs can be respectively regarded as tasks and dependencies among tasks. The objective of the problem is to minimize the total energy consumed for completing these tasks by assigning the tasks to k heterogeneous machines. We first show that the problem is NP-hard. Then, we present polynomial-time algorithms for two special cases where there are only two machines and where the input DAG is a directed path. Finally, we study a natural variant where there are only two machines with one of them being capable of executing a limited number of tasks. We show that this special case remains computationally hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_01022 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks Liu, Wei Chen, Jian-Jia Yang, Yongjie Data Structures and Algorithms Computational Complexity We study a graph partition problem where we are given a directed acyclic graph (DAG) whose vertices and arcs can be respectively regarded as tasks and dependencies among tasks. The objective of the problem is to minimize the total energy consumed for completing these tasks by assigning the tasks to k heterogeneous machines. We first show that the problem is NP-hard. Then, we present polynomial-time algorithms for two special cases where there are only two machines and where the input DAG is a directed path. Finally, we study a natural variant where there are only two machines with one of them being capable of executing a limited number of tasks. We show that this special case remains computationally hard. |
| title | On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2404.01022 |