Teoría de colas - dagoquevedo/parallelr GitHub Wiki

La teoría de colas es una área de las matemáticas dentro de la investigación de operaciones que estudia el comportamiento de las líneas de espera. En el campo computacional de nuestro interés, se relaciona con la asignación y el ordenamiento de las tareas a un determinado núcleo del CPU de tal manera de minimizar el tiempo total de ejecución de las tareas, este problema de ordenamiento se denomina programación de tareas (scheduling), teniendo la particularidad de ser en tiempo real (Real-time scheduling problem)[1,2].

El objetivo principal de esta práctica es el análisis sistemático de las diferencias en los tiempos de ejecución dada una ordenación de tareas y un número de núcleos disponibles. En específico:

1. Analizar las diferencias en los tiempos de ejecución cuando varia el ordenamientos de las tareas y el número de núcleos habilitados en el cluster; argumentar con un sustento gráfico las posibles causas de estas diferencias.

2. Diseñar una prueba estadísticas para determinar: (a) si las diferencias observadas respecto al número de núcleos habilitados en el cluster son significativas; (b) si las diferencias observadas respecto los ordenamiento de las tareas son significativas.

La operación a evaluar es la determinación de si un número entero , es o no un número primo. El algoritmo base [5] codificado en R es el siguiente:

is_prime = function(n) {
    if (n == 1 || n == 2) {
    	return(T)
    }
    if (n %% 2 == 0) {
    	return(F)
    }
    for (i in seq(3, max(3, ceiling(sqrt(n))), 2)) {
        if ((n %% i) == 0) {
            return(F)
	}
    }
    return(T)
}

Como puede deducirse, el número de operaciones requeridas esta en función . Para determinar la primalidad de , el mayor factor primo que se necesita no es mayor que , por lo cual el número de candidatos a factor primo es aproximadamente:

,

esta expresión crece cada vez más lentamente en función de . Para el experimento, se establecen diferentes ordenamientos de números enteros a partir de un conjunto ordenado inicial , definido por:

,

donde y son el inicio y el final del conjunto ordenado respectivamente, y , . En este caso se utilizo una muestra a evaluar de 5,000 números enteros, entre los rangos 10,000 y 15,000. La siguiente tabla muestra los cinco conjuntos creados a partir de realizar variaciones en el ordenamiento del conjunto inicial .

El experimento consiste en determinar para cada número entero (en el orden de cada conjunto) si es o no un número primo, usando el algoritmo is_prime, variando en cada ejecución el número de núcleos habilitados en el cluster y realizando 30 repeticiones de la totalidad del experimento. En cada ejecución, se genera una tupla con la siguiente estructura (core, conjunto, tiempo).

Se hace uso de una instancia SO Linux (Ubuntu 16.04) 64-bits, con procesador Intel (R) Core (TM) i7-5600U CPU @ 2.60 GHz y 12 GB de memoria RAM con 2 núcleos y 4 procesadores lógicos. La aplicación se ha codificado en R, haciendo uso del paquete doParallel [4] que incluye la función foreach, la cual permite la ejecución paralela de los procesos a partir de la declaración de un cluster con núcleos activos.

La Figura 1 representa el resultado de la ejecución con 30 repeticiones, divido por el número de núcleos disponibles. La tendencia que se muestra es la de un decrecimiento en los tiempo de computo conforme se incrementa el número de núcleos disponibles en el cluster, siendo esta tendencia menor entre el incremento de 3 a 4.

Figura 1. Variación del tiempo en función de los núcleos habilitados y el ordenamiento del conjunto.

Sin embargo, no se visualiza un efecto relevante en el tiempo de computo entre los diferentes conjuntos de prueba. La Figura 2(a) despliega una comparación del tiempo en función del número de núcleos habilitados. Se aprecia nuevamente el efecto positivo que tiene el incremento de núcleos durante el procesamiento de tareas. La Figura 2(b) despliega una comparación del tiempo en función de los conjuntos de prueba, se aprecia como el tipo de ordenamiento no tiene un efecto relevante en el tiempo de computo.

Figura 2. Variación del tiempo en función de los núcleos habilitados y el ordenamiento del conjunto.

La Figura 3 muestra la actividad de los núcleos durante la ejecución de la experimentación. La lectura de las estadísticas del CPU fue posible usando el comando mpstat. Conforme se agregan más núcleos al cluster la actividad del CPU se incrementa, pero logra mantener un balanceo de cargas entre los núcleos habilitados.

Figura 3. Actividad de los núcleos del CPU durante la ejecución del experimento.

Para confirmar las conclusiones del análisis gráfico se procede a realizar un análisis estadístico, formulando las siguientes hipótesis alternativas, : El número de núcleos disponibles tiene un efecto significativo en el tiempo de computo. : El ordenamiento del conjunto de números enteros tiene un efecto significativo en el tiempo de computo. Bajo la posibilidad de que la distribución de la muestra no cumpla con las condiciones de normalidad, se opta por usar una prueba no paramétrica de Kruskal-Wallis [3]. Se establece un nivel de significancia . La siguiente tabla muestra el resultado de este análisis.

Hipótesis	p-value
	2.45e-16
	0.148234

En el caso de la hipótesis alternativa , el p-value que se obtiene es lo suficientemente menor respecto el nivel de significancia , por lo que se rechaza la hipótesis nula y se acepta la hipótesis alternativa. Por el contrario la hipótesis alternativa se rechaza, al obtener un valor de p-value mayor al nivel de significancia. Por lo anterior, los resultados estadísticos confirman el análisis gráfico del experimento.

A partir de la evidencia empírica y estadística mostrada en los resultados, se puede concluir lo siguiente:

1. El número de núcleos habilitados en el cluster afecta de manera positiva el tiempo de procesamiento de las tareas. Esto tiene perfecto sentido en una instancia con procesador multinúcleo dado que los trabajos se asignan entre el número de núcleos habilitados, por lo cual el CPU realiza un balanceo de las asignaciones, minimizando así el tiempo de cómputo. Una vez asignadas las tareas, cada núcleo ejecuta la actividad en un orden FIFO (first in, first out), este aspecto queda en evidencia en la Figura 1, notesé el escenario de un sólo núcleo habilitado, siendo este el más lento en concretar las tareas.

2. El ordenamiento de los conjuntos no tiene una afectación significativa en el tiempo de procesamiento de las tareas. Cabe señalar, que el ligero aumento en el tiempo cuando el ordenamiento es descendente, es debido a que los números más grandes (que requiere un mayor orden de operaciones) son inicialmente computados por el algoritmo is_prime, bloqueando por un mayor tiempo el uso de los núcleos para operaciones subsecuentes. Sin embargo la evidencia gráfica y estadística determina que tal afectación en el tiempo no logra ser lo suficientemente significativa.

1. S.K. Dhall y C.L. Liu, On a Real-Time Scheduling Problem, Operations Research, 26:127-140, 1978.
2. A. Burchard, J. Liebeherr, Y. Oh, S.H. Son. New Strategies for Assigning Real-Time Tasks to Multiprocessor. Systems IEEE Transactions on Computers, 44(12):1429-1442, 1995.
3. W.H. Kruskal y W.A. Wallis. Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association, 47(260): 583-621, 1952.
4. R. Calaway, S. Weston, D. Tenenbaum. Foreach Parallel Adaptor for the 'parallel' Package. R Package, https://cran.r-project.org/web/packages/doParallel/doParallel.pdf.
5. S.E. Schaeffer. Práctica 3: teoría de colas, R paralelo: simulación & análisis de datos, http://elisa.dyndns-web.com/teaching/comp/par/p3.html.