Imperial College London
Alternate

ProfessorWilliamKnottenbelt

Faculty of Engineering, Department of Computing

Professor of Applied Quantitative Analysis
 
 
 
//

Contact

 

+44 (0)20 7594 8331w.knottenbelt Website

 
 
//

Location

 

E363ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Pesu:2015:10.1016/j.entcs.2015.10.023,
author = {Pesu, T and Knottenbelt, WJ},
doi = {10.1016/j.entcs.2015.10.023},
journal = {Electronic Notes in Theoretical Computer Science},
pages = {129--142},
title = {Dynamic Subtask Dispersion Reduction in Heterogeneous Parallel Queueing Systems},
url = {http://dx.doi.org/10.1016/j.entcs.2015.10.023},
volume = {318},
year = {2015}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Pesu,T
AU  - Knottenbelt,WJ
DO  - 10.1016/j.entcs.2015.10.023
EP  - 142
PY  - 2015///
SN  - 1571-0661
SP  - 129
TI  - Dynamic Subtask Dispersion Reduction in Heterogeneous Parallel Queueing Systems
T2  - Electronic Notes in Theoretical Computer Science
UR  - http://dx.doi.org/10.1016/j.entcs.2015.10.023
UR  - http://hdl.handle.net/10044/1/52107
VL  - 318
ER  -
Download