Optimal Scheduling for a Distributed Parallel Processing Model
| dc.contributor.author | Makowski, Armand M. | en_US |
| dc.contributor.author | Nelson, R. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:50:27Z | |
| dc.date.available | 2007-05-23T09:50:27Z | |
| dc.date.issued | 1992 | en_US |
| dc.description.abstract | We consider a model of a parallel processing system consisting of K distributed homogeneous processors each with private memory in which tasks queue before being served. Jobs arriving to the system consist of a set of tasks which can be executed independently of each other and we consider a job to be completed only after all of its component tasks have finished execution. A central dispatcher schedules the tasks on the processors at job arrival instants using information on the number of tasks currently scheduled on each processor. We model this system as a distributed fork/join queueing system and derive the structure of the individually optimal scheduling policy. Our results show that the individually optimal policy is a mixture of policies corresponding to sequential job execution (all tasks are scheduled on a single processor) and parallel scheduling (tasks are distributed among several processors in a manner that tends to equalize queue lengths). We show that, under conditions that include the case of moderate to heavy loads, the individually optimal scheduler schedules tasks according to the sequential policy which runs counter to the intuition that parallel processing is desirable. Because we do not include certain overheads associated with executing jobs in parallel in our model, our results are biased towards parallel rather than sequential processing. Thus our results strongly suggest that for actual distributed memory systems the benefits of parallel processing can be achieved only in conditions of light load. Response time properties of the individually optimal scheduler are derived and compared by simulation to other scheduling policies. | en_US |
| dc.format.extent | 1669729 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5218 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1992-36 | en_US |
| dc.subject | queuing networks | en_US |
| dc.subject | parallel architectures | en_US |
| dc.subject | scheduling | en_US |
| dc.subject | performance evaluation | en_US |
| dc.subject | Communication | en_US |
| dc.subject | Signal Processing Systems | en_US |
| dc.title | Optimal Scheduling for a Distributed Parallel Processing Model | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1