Scheduling series-parallel task graphs to minimize peak memory

DOI10.1016/J.TCS.2017.09.037MaRDI QIDQ1685958zbMATH OpenOpenAlexFDO

Authors Enver Kayaaslan, Thomas Lambert, Loris Marchal, Bora Uçar

Publication date 20 December 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01891937/file/seriesElsevierSecondSubmission.pdf

zbMATH Keywords

schedulingseries-parallel graphspeak memory minimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• scientific article; zbMATH DE number 1560506
• Minimum Linear Arrangement of Series-Parallel Graphs
• A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
• Minimum flow time graph ordering.
• Parallel algorithms for the minimum cut and the minimum length tree layout problems

Cites work

• scientific article; zbMATH DE number 3483542 (Why is no real title available?)
• scientific article; zbMATH DE number 1953316 (Why is no real title available?)
• scientific article; zbMATH DE number 1875430 (Why is no real title available?)
• scientific article; zbMATH DE number 6131601 (Why is no real title available?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• An Adaptive General Sparse Out-Of-Core Cholesky Factorization Scheme
• An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
• Cutwidth I: A linear time fixed parameter algorithm
• Encyclopedia of parallel computing.
• Inapproximability of treewidth and related problems
• Memory-optimal evaluation of expression trees involving large objects
• Min Cut is NP-complete for edge weighted trees
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On scheduling series-parallel DAGs to maximize area
• On the storage requirement in the out-of-core multifrontal method for sparse factorization
• Parallel recognition of series-parallel graphs
• Scheduling UET-UCT series-parallel graphs on two processors
• Sequencing with Series-Parallel Precedence Constraints
• The Generation of Optimal Code for Arithmetic Expressions
• The Pebbling Problem is Complete in Polynomial Space
• The Recognition of Series Parallel Digraphs

Cited in

(5)

• scientific article; zbMATH DE number 1948448 (Why is no real title available?)
• scientific article; zbMATH DE number 7593805 (Why is no real title available?)
• Optimal memory-aware backpropagation of deep join networks
• Static Scheduling with Load Balancing for Solving Triangular Band Linear Systems on Multicore Processors
• Ant colony algorithm for single processor scheduling with minimization of peak resource usage

This page was built for publication: Scheduling series-parallel task graphs to minimize peak memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685958)