Title: Scheduling divisible loads in a three-dimensional mesh of processors
Abstract: We study distributed processing of a divisible load in a three-dimensional mesh of communicating processors. The objective is to find distribution of the load among processors which guarantees minimal processing time. We describe a family of load distribution algorithms and obtain closed-form formulae for optimal load shares allocated to processors in each algorithm. Our model takes into consideration communication delays involved in moving load shares from one processor to another. In large meshes our algorithms attain speedup limit of 1+p/ρ, where p is the number of communication ports used simultaneously by each processor in data transfer and ρ is the ratio of processing to communication transfer rate. We also show a matching upper bound on the speedup in this topology.
Publication Year: 1999
Publication Date: 1999-04-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 57
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot