Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Julien Herrmann Connect in order to contact the contributor
Submitted on : Friday, March 22, 2013 - 5:25:59 PM
Last modification on : Friday, November 18, 2022 - 9:25:28 AM
Long-term archiving on: : Monday, June 24, 2013 - 11:35:24 AM


Files produced by the author(s)


  • HAL Id : hal-00787753, version 1



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



Record views


Files downloads