Some models for scheduling parallel programs with communication delays

DOI10.1016/S0166-218X(96)00034-0zbMath0863.68015MaRDI QIDQ5961603

Frédéric Guinand, Evripidis Bampis, 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

schedulinggridsparallel programscommunication delayscomplete 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)

Related Items (5)

Parallel Machine Scheduling with Uncertain Communication Delays ⋮ Complexity and approximation results for scheduling multiprocessor tasks on a ring. ⋮ Minimizing the overhead for some tree-scheduling problems ⋮ Scheduling 2-dimensional grids with large communication delays ⋮ An optimal schedule for Gaussian elimination on an MIMD architecture

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal parallel execution of complete binary trees and grids into most popular interconnection networks
• Communication complexity of PRAMs
• Multiprocessor scheduling with communication delays
• UET scheduling with unit interprocessor communication delays
• 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
• Impact of communications of the complexity of the parallel Gaussian elimination
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• A Communication-Time Tradeoff
• C.P.M. Scheduling with Small Communication Delays and Task Duplication
• Optimal schedules for d-D grid graphs with communication delays
• The complexity of scheduling problems with communication delays for trees

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