Beyond the mean in fork-join queues: Efficient approximation for response-time tails

Título traducido de la contribución: Más allá de la media en las colas de unión de horquillas: Aproximación eficiente para colas de tiempo de respuesta

Zhan Qiu, Juan F. Pérez, Peter G. Harrison

Resultado de la investigación: Contribución a RevistaArtículo

11 Citas (Scopus)

Resumen

Las colas de unión de horquillas son modelos naturales para diversos sistemas informáticos y de comunicaciones que implican la multitarea paralela y la división y resincronización de datos, como la computación paralela, el procesamiento de consultas en bases de datos distribuidas y el acceso a discos paralelos. El tiempo de respuesta del trabajo en una cola de unión de horquillas es un indicador de rendimiento crítico, pero su análisis exacto es un reto. Introducimos un modelo estocástico para colas de unión de horquillas homogéneas de nodos () que se centra en la diferencia de longitud entre cualquier cola de nodos y la más corta, truncando el espacio de estado de forma que la diferencia máxima sea como máximo una constante . Mientras que la mayoría de los métodos anteriores se centran en el tiempo de respuesta medio, nuestro modelo también es capaz de evaluar la distribución del tiempo de respuesta, así como los tiempos de procesamiento de tipo fase y los procesos de llegada de Markovian. Para hacer frente a escenarios con cargas elevadas, que requieren un gran valor de precisión suficiente, desarrollamos un algoritmo eficiente utilizando métodos analíticos matriciales. Las pruebas contra la simulación muestran que el modelo propuesto produce resultados precisos para colas de unión de horquillas de 2 nodos. A medida que el modelo se vuelve numéricamente intratable para grandes valores de , proponemos además un enfoque aproximado, basado en las propiedades de las estadísticas de los pedidos y los valores extremos. La aproximación proporciona un alto grado de precisión en los tiempos de respuesta de las colas, y tiene la ventaja de ser eficiente y escalable, requiriendo únicamente los resultados analíticos de las colas de unión de horquillas de un solo nodo y dos nodos, que se obtienen con el modelo matricial-analítico antes mencionado. La comparación con los resultados de la simulación muestra que nuestra aproximación produce buenos ajustes para las colas, incluso en casos muy grandes con tiempos generales de procesamiento y entre llegadas.
Idioma originalEnglish (US)
Número de artículo1822
Páginas (desde-hasta)99-116
Número de páginas18
PublicaciónPerformance Evaluation
Volumen91
DOI
EstadoPublished - sep 1 2015
Publicado de forma externa

Huella dactilar

Response Time
Join
Queue
Tail
Approximation
Vertex of a graph
Multitasking
Matrix Analytic Methods
Query processing
Markovian Arrival Process
Stochastic models
Parallel processing systems
Distributed Databases
Processing
Performance Indicators
Model
Arrival Time
Extreme Values
Query Processing
Parallel Computing

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software
  • Modeling and Simulation

Citar esto

@article{4c317fa2900c4bb8bc9140096b8d6cf0,
title = "Beyond the mean in fork-join queues: Efficient approximation for response-time tails",
abstract = "Abstract Fork-join queues are natural models for various computer and communications systems that involve parallel multitasking and the splitting and resynchronizing of data, such as parallel computing, query processing in distributed databases, and parallel disk access. Job response time in a fork-join queue is a critical performance indicator but its exact analysis is challenging. We introduce a stochastic model for K-node homogeneous fork-join queues (K≥2) that focuses on the difference in length between any node-queue and the shortest one, truncating the state space such that the maximum difference is at most a constant C. Whilst most previous methods focus on the mean response time, our model is also able to evaluate the response time distribution, as well as accommodating phase-type processing times and Markovian arrival processes. In order to tackle scenarios with high loads, which require a large value of C to provide sufficient accuracy, we develop an efficient algorithm using matrix-analytic methods. Tests against simulation show that the proposed model yields accurate results for 2-node fork-join queues. As the model becomes numerically intractable for large values of K, we further propose an approximate approach, based on properties of order statistics and extreme values. The approximation gives a high degree of accuracy on response time tails, and has the advantage of being efficient and scalable, requiring only the analytical results for a single-node and 2-node fork-join queues, which we obtain with the aforementioned matrix-analytic model. Comparison with simulation results shows that our approximation yields good fits for the tails, even in very large cases with general processing and inter-arrival times.",
author = "Zhan Qiu and P{\'e}rez, {Juan F.} and Harrison, {Peter G.}",
year = "2015",
month = "9",
day = "1",
doi = "10.1016/j.peva.2015.06.007",
language = "English (US)",
volume = "91",
pages = "99--116",
journal = "Performance Evaluation",
issn = "0166-5316",
publisher = "Elsevier",

}

Beyond the mean in fork-join queues : Efficient approximation for response-time tails. / Qiu, Zhan; Pérez, Juan F.; Harrison, Peter G.

En: Performance Evaluation, Vol. 91, 1822, 01.09.2015, p. 99-116.

Resultado de la investigación: Contribución a RevistaArtículo

TY - JOUR

T1 - Beyond the mean in fork-join queues

T2 - Efficient approximation for response-time tails

AU - Qiu, Zhan

AU - Pérez, Juan F.

AU - Harrison, Peter G.

PY - 2015/9/1

Y1 - 2015/9/1

N2 - Abstract Fork-join queues are natural models for various computer and communications systems that involve parallel multitasking and the splitting and resynchronizing of data, such as parallel computing, query processing in distributed databases, and parallel disk access. Job response time in a fork-join queue is a critical performance indicator but its exact analysis is challenging. We introduce a stochastic model for K-node homogeneous fork-join queues (K≥2) that focuses on the difference in length between any node-queue and the shortest one, truncating the state space such that the maximum difference is at most a constant C. Whilst most previous methods focus on the mean response time, our model is also able to evaluate the response time distribution, as well as accommodating phase-type processing times and Markovian arrival processes. In order to tackle scenarios with high loads, which require a large value of C to provide sufficient accuracy, we develop an efficient algorithm using matrix-analytic methods. Tests against simulation show that the proposed model yields accurate results for 2-node fork-join queues. As the model becomes numerically intractable for large values of K, we further propose an approximate approach, based on properties of order statistics and extreme values. The approximation gives a high degree of accuracy on response time tails, and has the advantage of being efficient and scalable, requiring only the analytical results for a single-node and 2-node fork-join queues, which we obtain with the aforementioned matrix-analytic model. Comparison with simulation results shows that our approximation yields good fits for the tails, even in very large cases with general processing and inter-arrival times.

AB - Abstract Fork-join queues are natural models for various computer and communications systems that involve parallel multitasking and the splitting and resynchronizing of data, such as parallel computing, query processing in distributed databases, and parallel disk access. Job response time in a fork-join queue is a critical performance indicator but its exact analysis is challenging. We introduce a stochastic model for K-node homogeneous fork-join queues (K≥2) that focuses on the difference in length between any node-queue and the shortest one, truncating the state space such that the maximum difference is at most a constant C. Whilst most previous methods focus on the mean response time, our model is also able to evaluate the response time distribution, as well as accommodating phase-type processing times and Markovian arrival processes. In order to tackle scenarios with high loads, which require a large value of C to provide sufficient accuracy, we develop an efficient algorithm using matrix-analytic methods. Tests against simulation show that the proposed model yields accurate results for 2-node fork-join queues. As the model becomes numerically intractable for large values of K, we further propose an approximate approach, based on properties of order statistics and extreme values. The approximation gives a high degree of accuracy on response time tails, and has the advantage of being efficient and scalable, requiring only the analytical results for a single-node and 2-node fork-join queues, which we obtain with the aforementioned matrix-analytic model. Comparison with simulation results shows that our approximation yields good fits for the tails, even in very large cases with general processing and inter-arrival times.

UR - http://www.scopus.com/inward/record.url?scp=84938950443&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938950443&partnerID=8YFLogxK

U2 - 10.1016/j.peva.2015.06.007

DO - 10.1016/j.peva.2015.06.007

M3 - Article

AN - SCOPUS:84938950443

VL - 91

SP - 99

EP - 116

JO - Performance Evaluation

JF - Performance Evaluation

SN - 0166-5316

M1 - 1822

ER -