Some models for scheduling parallel programs with communication delays

DOI10.1016/S0166-218X(96)00034-0MaRDI QIDQ5961603zbMATH OpenFDO

Authors Evripidis Bampis, Frédéric Guinand, Denis Trystram

Publication date 22 May 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

schedulinggridscommunication delaysparallel programscomplete trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of software (68N99)

Recommendations

• Multiprocessor scheduling with communication delays
• Scheduling tasks with communication delays on parallel processors
• Parallel processor scheduling with delay constraints

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 278827 (Why is no real title available?)
• A Communication-Time Tradeoff
• C.P.M. Scheduling with Small Communication Delays and Task Duplication
• Communication complexity of PRAMs
• Impact of communications of the complexity of the parallel Gaussian elimination
• Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays
• Minimizing the schedule length for a parallel 3D-grid precedence graph
• Multiprocessor scheduling with communication delays
• Optimal parallel execution of complete binary trees and grids into most popular interconnection networks
• Optimal schedules for d-D grid graphs with communication delays
• The complexity of scheduling problems with communication delays for trees
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• UET scheduling with unit interprocessor communication delays

Cited in

(6)

• An optimal schedule for Gaussian elimination on an MIMD architecture
• Scheduling 2-dimensional grids with large communication delays
• Minimizing the overhead for some tree-scheduling problems
• Complexity and approximation results for scheduling multiprocessor tasks on a ring.
• scientific article; zbMATH DE number 2099401 (Why is no real title available?)
• Parallel Machine Scheduling with Uncertain Communication Delays

This page was built for publication: Some models for scheduling parallel programs with communication delays

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