Dynamic Subtask Dispersion Reduction in Heterogeneous Parallel Queueing Systems
File(s)pesu-knottenbelt-entcs-2015.pdf (371.74 KB) 1-s2.0-S157106611500064X-main.pdf (291.09 KB)
Accepted version
Published version
Author(s)
Pesu, T
Knottenbelt, WJ
Type
Journal Article
Abstract
Fork-join and split-merge queueing systems are mathematical abstractions of parallel task processing systems in which entering tasks are split into N subtasks which are served by a set of heterogeneous servers. The original task is considered completed once all the subtasks associated with it have been serviced. Performance of split-merge and fork-join systems are often quantified with respect to two metrics: task response time and subtask dispersion. Recent research effort has been focused on ways to reduce subtask dispersion, or the product of task response time and subtask dispersion, by applying delays to selected subtasks. Such delays may be pre-computed statically, or varied dynamically. Dynamic in our context refers to the ability to vary the delay applied to a subtask according to the state of the system, at any time before the service of that subtask has begun. We assume that subtasks in service cannot be preempted. A key dynamic optimisation that benefits both metrics of interest is to remove delays on any subtask with a sibling that has already completed service. This paper incorporates such a policy into existing methods for computing optimal subtask delays in split-merge and fork-join systems. In the context of two case studies, we show that doing so affects the optimal delays computed, and leads to improved subtask dispersion values when compared with existing techniques. Indeed, in some cases, it turns out to be beneficial to initially postpone the processing of non-bottleneck subtasks until the bottleneck subtask has completed service.
Date Issued
2015-11-25
Date Acceptance
2015-11-18
Citation
Electronic Notes in Theoretical Computer Science, 2015, 318, pp.129-142
ISSN
1571-0661
Publisher
Elsevier
Start Page
129
End Page
142
Journal / Book Title
Electronic Notes in Theoretical Computer Science
Volume
318
Copyright Statement
This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Subjects
Science & Technology
Technology
Computer Science, Theory & Methods
Computer Science
dynamic dispersion reduction
fork-join
split merge
queueing networks
RAID SYSTEMS
MODELS
Publication Status
Published