Skip to Main content Skip to Navigation
Reports

Tree traversals with task-memory affinities

Abstract : 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.
Complete list of metadatas

https://hal.inria.fr/hal-00787753
Contributor : Julien Herrmann <>
Submitted on : Friday, March 22, 2013 - 5:25:59 PM
Last modification on : Wednesday, November 20, 2019 - 3:20:58 AM
Long-term archiving on: : Monday, June 24, 2013 - 11:35:24 AM

File

RR-8226.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00787753, version 1

Collections

Citation

Julien Herrmann, Loris Marchal, Yves Robert. Tree traversals with task-memory affinities. [Research Report] RR-8226, INRIA. 2013, pp.31. ⟨hal-00787753⟩

Share

Metrics

Record views

306

Files downloads

337