Algoritmos multihebrados adaptativos en sistemas no dedicados.

Resumen

El incipiente aumento de microprocesadores con una arquitectura donde se combina un elevado número de procesadores en el mismo chip, más conocido como MIC, de tal forma que el número de nucleos por chip/nodo se está incrementando enormemente en los últimos años. Las principales dicultades que experimentan las aplicaciones cuando se ejecutan en los multiprocesadores actuales se acentúan conforme aumenta el número de procesadores integrados en el sistema. Existen aplicaciones multihebradas que no son eficientes cuando intentan usar todos los recursos de este tipo de sistemas. Las APIs ofrecen soporte a este tipo de aplicaciones para que obtengan un buen rendimiento, sin embargo, el paralelismo de tareas no funciona bien para todas las aplicaciones multihebradas, desafortunadamente los códigos paralelos B&B son un claro ejemplo, por las irregularidades que surgen en la resolución de distintos tipos de problemas. La computación paralela está ayudada por librerías y herramientas que facilitán la programación paralela, sin embargo, estas librerías no terminan de resolver correctamente el problema que plantean las aplicaciones multihebradas en sistemas no dedicados, dejando toda la responsabilidad al sistema operativo (SO). Esta tesis pretende avanzar en el ámbito de las APIs auto-configurables centradas en la programación multicore. Para ello, se estudian métodos que permita al SO cooperar con las aplicaciones multihebradas informandoles periódicamente del mejor número de hebras a utilizar según su rendimiento. Las aplicaciones deben adaptar su nivel de paralelismo para mantener un buen rendimiento, teniendo en cuenta la disponibilidad de recursos en tiempo de ejecución, especialmente en sistema no dedicados. Uno de los factores que inciden directamente en el tiempo total de ejecución de la aplicación en un sistema multicore es el número de hebras. Tradicionalmente, el número de hebras es establecido por el usuario al inicio de la ejecución de la aplicación. Generalmente, el comportamiento de la aplicación depende directamente del número de hebras, que se mantiene invariable durante todo el tiempo de ejecución. La finalidad de este trabajo de tesis es reducir el tiempo de computación de las aplicaciones multihebradas, para lo cual se propone que el algoritmo multihebrado pueda crear nuevas hebras, o incluso detener alguna hebra activa, de tal forma que el número de hebras activas se adapte dinámicanente a los recursos disponibles en cada momento. Sin embargo, la aplicación debe conocer el número óptimo de hebras en cada instante de tiempo que ofrece el mejor rendimiento posible. El gestor del nivel de paralelismo (GP) determinará periodicamente el número de hebras óptimo e informará a la aplicación para que pueda adaptarse durante la ejecución haciendo frente a las variaciones de las cargas computacionales en el sistema producidas por la propia aplicación, o incluso por otras aplicaciones que se ejecutan en el sistema no dedicado. Los GPs propuestos analizan el comportamiento de las aplicaciones multihebradas en ejecución y adaptan el número de hebras automáticamente, manteniendo el máximo rendimiento posible. Esta cooperación entre el GP, la aplicacióny el SO sería beneficiosa para una amplia variedad de aplicaciones, entre ellas, aquellas que utilizan técnicas de B&B. En esta tesis se proponen distintos tipos de GP a nivel de usuario y a nivel de Kernel. Los GPs a nivel de usuario se caracterizan por su fácil implementación, pero poseen ciertas limitaciones respecto a los criterios de decisión que pueden utilizar para estimar el número óptimo de hebras. Los GPs a nivel de kernel ofrecen diseños de mayor complejidad, ofreciendo diferentes versiones en función de la entidad encargada de estimar el número óptimo de hebras. También se ha diseñado la librería IGP que facilita al programador la implementación de aplicaciones multihebradas que interactuan con los distintos GPs. Todas las experimentaciones han sido realizadas directamente sobre sistemas reales con el SO Linux, tanto dedicados como no dedicados, sin utilizar ningún tipo de simulador. El algoritmo Ray Tracing ha sido utilizado para verificar el comportamiento de los distintos GPs en sistemas dedicados, mientras que la aplicación B&B Local-PAMIGO ha permitido analizar distintos criterios de decisión integrados en los diferentes GPs utilizando sistemas dedicados y no dedicados. Esta tesis se compone de cinco capítulos, comenzando con el Capítulo 1 donde se realiza una breve introducción sobre la adaptabilidad de los algoritmos multihebrados en arquitecturas multicore y analizando las APIs disponibles. También se detallan las características de las aplicaciones multihebradas, centrándonos en las distintas estrategias de creación de hebras y su comportamiento en sistemas no dedicados. Finalmente se detalla la aplicación B&B Local-PAMIGO que permite al usuario adaptar el número de hebras gracias a la estrategia de creación dinámica de hebras implementada. El Capítulo 2 se centra en las etapas que integran un GP, y el procedimiento seguido para la implementación de las distintos tipos de GPs. Un benchmark basado en el algoritmo Ray Tracing diseñado especialmente para analizar el comportamiento de los diferentes GPs a nivel de usuario (ACW y AST) y a nivel de kernel (KST, SST y KITST) en sistemas dedicados. Se han realizado varios experimentos para estudiar diferentes características que inciden en la adaptabilidad de la aplicación, tales como, la duración de las secciones críticas de la aplicación, el impacto de la reserva dinámica de memoria sobre el rendimiento de la aplicación, la frecuencia de ejecución del GP para reducir su coste, y el mecanismo de detención de hebras. El Capítulo 3 estudia la selección del mejor criterio de decisión que estima de forma precisa el número óptimo de hebras. Entre los distintos criterios de decisión analizados, resaltamos, el número de procesadores ociosos, rendimiento parcial de la aplicación, minimizar los retardos de la aplicación y estimación del número óptimo de hebras en función de los tiempos de bloqueo de las hebras. Todos los experimentos se han realizado en sistemas dedicados sobre una aplicación real de B&B con los distintos GPs usando diferentes criterios de decisión. El comportamiento irregular de la aplicación B&B ha incidido directamente en la adaptabilidad con diferentes GPs y criterios de decisión, de tal forma que la mejor adaptabilidad de la aplicación multihebrada B&B resolviendo distintos problemas irregulares se ha conseguido habilitando la detención de hebras en el GP El Capítulo 4 evalúa el comportamiento de la aplicación B&B y su adaptabilidad utilizando distintos GP (ACW, KST y KITST) en un sistema no dedicado. Finalmente, en el Capítulo 5 se exponen las conclusiones finales de la tesis, y el trabajo futuro.