Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints
As more and more parallel programs are migrating to shared computing platforms, bounding their parallel execution times under resource constraints is particularly important for their efficient executions. The parallel program is often modeled as a task graph, which is composed of a collection of con...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8685096/ |
| _version_ | 1818855219045335040 |
|---|---|
| author | Jiangong Song Qinyong Li Shilong Ma |
| author_facet | Jiangong Song Qinyong Li Shilong Ma |
| author_sort | Jiangong Song |
| collection | DOAJ |
| description | As more and more parallel programs are migrating to shared computing platforms, bounding their parallel execution times under resource constraints is particularly important for their efficient executions. The parallel program is often modeled as a task graph, which is composed of a collection of control or data-dependent sub-tasks organized as a directed acyclic graph (DAG) for scheduling. In this paper, we propose a simple yet effective method to bound the parallel execution time of a task graph when the memory resources are constrained. The essence of this method is to extend Brent's theorem by incorporating the memory factor. To this end, we introduce a concept of range of concurrent tasks (RCT) and leverage it to estimate an upper bound on the parallel execution time of task graph with respect to work-conserving scheduling algorithm. And also we exploit the estimated bound to develop a metric to help determine optimal memory capacity for a given task graph. Through an empirical study, we evaluate how good the estimated bound is via a designed scheduling algorithm and demonstrate the effectiveness of the metric in the selection of optimal memory capacity for a task graph. |
| first_indexed | 2024-12-19T08:05:07Z |
| format | Article |
| id | doaj.art-7ee6be50e17d4d0481c6ee7ab4a89670 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-19T08:05:07Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-7ee6be50e17d4d0481c6ee7ab4a896702022-12-21T20:29:46ZengIEEEIEEE Access2169-35362019-01-017527785278910.1109/ACCESS.2019.29099228685096Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory ConstraintsJiangong Song0https://orcid.org/0000-0001-5430-3902Qinyong Li1Shilong Ma2State Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaState Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaState Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaAs more and more parallel programs are migrating to shared computing platforms, bounding their parallel execution times under resource constraints is particularly important for their efficient executions. The parallel program is often modeled as a task graph, which is composed of a collection of control or data-dependent sub-tasks organized as a directed acyclic graph (DAG) for scheduling. In this paper, we propose a simple yet effective method to bound the parallel execution time of a task graph when the memory resources are constrained. The essence of this method is to extend Brent's theorem by incorporating the memory factor. To this end, we introduce a concept of range of concurrent tasks (RCT) and leverage it to estimate an upper bound on the parallel execution time of task graph with respect to work-conserving scheduling algorithm. And also we exploit the estimated bound to develop a metric to help determine optimal memory capacity for a given task graph. Through an empirical study, we evaluate how good the estimated bound is via a designed scheduling algorithm and demonstrate the effectiveness of the metric in the selection of optimal memory capacity for a task graph.https://ieeexplore.ieee.org/document/8685096/Task graph schedulingtime boundsparallel executionmulticoresshared memorymemory constraints |
| spellingShingle | Jiangong Song Qinyong Li Shilong Ma Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints IEEE Access Task graph scheduling time bounds parallel execution multicores shared memory memory constraints |
| title | Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints |
| title_full | Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints |
| title_fullStr | Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints |
| title_full_unstemmed | Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints |
| title_short | Toward Bounds on Parallel Execution Times of Task Graphs on Multicores With Memory Constraints |
| title_sort | toward bounds on parallel execution times of task graphs on multicores with memory constraints |
| topic | Task graph scheduling time bounds parallel execution multicores shared memory memory constraints |
| url | https://ieeexplore.ieee.org/document/8685096/ |
| work_keys_str_mv | AT jiangongsong towardboundsonparallelexecutiontimesoftaskgraphsonmulticoreswithmemoryconstraints AT qinyongli towardboundsonparallelexecutiontimesoftaskgraphsonmulticoreswithmemoryconstraints AT shilongma towardboundsonparallelexecutiontimesoftaskgraphsonmulticoreswithmemoryconstraints |