.png){kind=icon}
Return
Memory-aware tree traversals with pre-assigned tasks
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2014.10.004.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study the complexity of traversing tree-shaped workflows whose tasks require large I/O files. We target a heterogeneous architecture with two resource types, each with a different memory, such as a multicore node equipped with a dedicated accelerator (FPGA or GPU). The tasks in the workflow are colored according to their type and can be processed if all their input and output files can be stored in the corresponding memory. The amount of used memory of each type at a given execution step strongly depends upon the ordering in which the tasks are executed, and upon when communications between both memories are scheduled. The objective is to determine an efficient traversal that minimizes the maximum amount of memory of each type needed to traverse the whole tree. In this paper, we establish the complexity of this two-memory scheduling problem, and provide inapproximability results. In addition, we design several heuristics, based on both post-order and general traversals, and we evaluate them on a comprehensive set of tree graphs, including random trees as well as assembly trees arising in the context of sparse matrix factorizations. (C) 2014 Elsevier Inc. All rights reserved.
Keywords:
Scheduling
Memory-aware
Sparse matrix factorization
Multifrontal method
Tree traversal
Bi-objective optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
Cited Papers
ShareSaveShareSaveDopamine Modulates Acetylcholine Release via Octopamine and CREB Signaling in Caenorhabditis elegans.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAIShareSaveShareSave
View more