Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
DEVELOPMENTS IN PARALLEL, DISTRIBUTED, GRID AND CLOUD COMPUTING FOR ENGINEERING
Edited by: B.H.V. Topping and P. Iványi
Reducing Subtask Dispersion in Parallel Systems
W.J. Knottenbelt and I. Tsimashenka
Department of Computing, Imperial College London, England
W.J. Knottenbelt, I. Tsimashenka, "Reducing Subtask Dispersion in Parallel Systems", in B.H.V. Topping and P. Iványi, (Editor), "Developments in Parallel, Distributed, Grid and Cloud Computing for Engineering", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 9, pp 203-227, 2013. doi:10.4203/csets.31.9
Keywords: performance optimisation, parallel queueing systems, split-merge, fork-join, subtask dispersion, optimal subtask delays.
In numerous customer and resource processing systems of real-life interest, each incoming high-level task is decomposed into several low-level subtasks that are processed by a set of parallel servers. Only when all low-level subtasks have been served and placed in an output buffer does the corresponding high-level task complete service. Two important classes of such systems are split-merge and fork-join systems. Previous research on split-merge and fork-join systems has regarded high-level task response time as being the primary performance metric of interest. However, in some systems, and especially those with physical output buffers with limited capacity, the primary concern is reducing subtask dispersion - that is, the time between the arrival of the first and the last subtasks in the output buffer. Consequently, here we develop and apply the theory of heterogeneous order statistics to reduce subtask dispersion by adding judiciously-chosen delays to subtask processing at the parallel servers. We describe a methodology for optimising both the mean and given percentiles of subtask dispersion in split-merge systems, and outline how to optimise the mean of subtask dispersion in a class of fork-join systems. We illustrate the application of our techniques using three case studies and quantify the adverse effects of applying our methodologies on system capacity and response time.
purchase the full-text of this chapter (price £20)