Esta tesis afronta el problema de la planificación de sistemas de tiempo real utilizando sistemas multiprocesador con memoria compartida. Según laliteratura este problema es NP-Hard. En las aplicaciones de sistemas de tiempo real se imponen unos plazos temporales para la realización de las tareas. Así, lo importante es obtener los resultados a tiempo y no lo es tanto el obtener un rendimiento alto en promedio. La solución al problematradicionalmente ha consistido en repartir las tareas en tiempo de diseño y tratar a losprocesadores como monoprocesadores aislados. La solución alternativa, la planificación global del multiprocesador, tiene una teoría poco desarrollada. Los límites de utilización del sistema con garantías para losplazos son muy bajos, del orden del 50%, y la capacidad sobrante difícilmente se puede usar para dar servicio a las tareas aperiódicas. Así, el objetivoprincipal de la tesis es la planificación global con garantías de los plazos y con buen servicio a las tareas aperiódicas, llegando a usar el 100% de la capacidad de proceso. Primero se estudiaron cuatro posibilidades de distribución: estática o dinámica según las tareas, periódicas o aperiódicas. Para ello se trató el servicioa las tareas aperiódicas con dos métodos distintos: con servidores y sin servidores. En las distribuciones dinámicas, con el método de los servidoresse encontraron dificultades en su dimensionado y en las garantías de los plazos. Los métodos sin servidores probados fueron los planificadores Slack Stealing y Total Bandwidth. Ambos solo se pudieron adaptar para la planificación estática de las tareas periódicas. Las simulaciones mostraron que laplanificación local con Slack Stealing y un distribuidor de las tareas aperiódicas tipo Next-Fit proporcionan los mejores tiempos de respuesta medios para las tareas aperiódicas. Sin embargo, cuando las cargas son muy altas su tiempo de respuesta se dispara. Todos los métodos ensayados hasta elmomento quedaron desestimados para la planificación global. En segundo lugar se adaptó a la planificación global el algoritmo Dual Priority. Primero se analizaron sus características en monoprocesadores y se realizaron diversas mejoras. El algoritmo depende del cálculo off-line del peor tiempo de respuesta de las tareas periódicas y la fórmula paracalcularlos en monoprocesadores no es válida para multiprocesadores. Así, se analizaron tres métodos para su cálculo: un método analítico, unmétodo con simulación y un método con un algoritmo. El primero obtiene valores demasiado pesimistas; el segundo obtiene valores más ajustados pero en ocasiones son demasiado optimistas; el tercero es un método aproximado y obtiene valores tanto optimistas como pesimistas. Así, estemétodo no garantiza los plazos y no se puede usar en sistemas de tiempo real estrictos. En sistemas laxos, con una monitorización on-liney un ajuste dinámico de las promociones, el número de plazos incumplidos es muy bajo y el tiempo de repuesta de las tareas aperiódicas es excelente. Finalmente, se presenta una solución híbrida entre el repartimiento estático de las tareas periódicas y la planificación global. En tiempo de diseño, sereparten las tareas periódicas entre los procesadores y se calculan las promociones para la planificación local. En tiempo de ejecución las tareasperiódicas se pueden ejecutar en cualquier procesador hasta el instante de su promoción, instante en el que deben migrar a su procesador. Así segarantizan los plazos y se permite un cierto grado de balanceo dinámico de la carga. La flexibilidad conferida por las promociones de las tareas y el balanceo de la carga se utiliza para (i) admitir tareas periódicas que de otra forma no serian planificables, (ii) servir tareas aperiódicas y (iii) servirtareas aperiódicas con plazo o esporádicas. Para los tres casos se diseñaron y analizaron distintos métodos de distribución de las tareas periódicas en tiempo de diseño. También se diseño un método para reducir el número de migraciones. Las simulaciones mostraron que con este método se puedenconseguir cargas con solo tareas periódicas muy cercanas al 100%, lejos del 50% de la teoría de la planificación global. Las simulaciones con tareasaperiódicas mostraron que su tiempo de repuesta medio es muy bueno. Se diseño un test de aceptación de las tareas esporádicas, de forma que si una tarea es aceptada entonces su plazo queda garantizado. El porcentaje de aceptación obtenido en los experimentos fue superior al 80%.Finalmente, se diseñó un método de distribución de las tareas periódicas pre-rutime capaz de facilitar en tiempo de ejecución la aceptación de un alto porcentaje de tareas esporádicas y mantener un buen nivel de servicio medio para las tareas aperiódicas. / This thesis takes into consideration the problem of real-time systems scheduling using shared memory multiprocessor systems. According to the literature, this problem is NP-Hard. In real-time systems applications some time limits are imposed to tasks termination. Therefore, the really important thing is to get results on time and it is not so important to achieve high average performances. The solution to the problem traditionally has been to partition the tasks at design time and treat processors as isolated uniprocessors. The alternative solution, the global scheduling, has an undeveloped theory. The limit on the system utilization with deadlines guarantees is very low, around 50%, and spare capacity can hardly be used to service aperiodic tasks. Thus, the main goal of this thesis is to develop global scheduling techniques providing deadlines guarantees and achieving good service for aperiodic tasks, being able to use 100% of the processing capacity.First of all, we explored four possibilities of distribution: static or dynamic depending on the tasks, periodic or aperiodic. We tried to schedule aperiodic tasks with two different methods: with servers and without servers. In dynamic distributions, with the method of servers were found difficulties in its size and guarantees for deadlines. The methods without servers were The Slack Stealing and The Total Bandwidth. Both were adapted only for scheduling the static case. The simulations showed that the local scheduling with Slack Stealing and an allocation of aperiodic tasks kind Next-Fit provides the best mean average response time for the aperiodic tasks. However, when the load is very high response time increases. All methods tested so far were dismissed for the global scheduling.Secondly the Dual Priority algorithm was adapted to global scheduling. First we discussed its characteristics in uniprocessors and various improvements were made. The algorithm depends on the off-line calculation of the worst case response time for the task and the formula to compute them in uniprocessors is not valid for multiprocessors. We have analyzed three methods for its calculation: an analytical method, a simulation method and an algorithmic method. The former gets too pessimistic values, the second gets adjusted values but are sometimes too optimistic, and the third is a method that obtains approximate values. Thus, this method does not guarantee deadlines and may not be used in hard real-time systems. However, it is very suitable for soft real-time systems. In these systems, using an on-line monitoring and dynamic adjustment of promotions, the number of missed deadlines is very low and the response time of aperiodic tasks is excellent.Finally, we present a hybrid solution between static task allocation and global scheduling. At design time, is performed the distribution of periodic tasks among processors and their promotions are calculated for local scheduling. At runtime, the task can be run on any processor until the moment of its promotion, when it has to migrate to its processor. This will ensure deadlines and allowing a certain degree of dynamic load balancing. The flexibility provided by task promotions and load balancing is used (i) to admit task that would otherwise not be scheduled, (ii) to serve aperiodic tasks and (iii) to serve aperiodic tasks with deadlines or sporadic tasks. For the three cases were designed and analyzed various methods of task distribution at design time. We also designed a method to reduce the number of migrations. The simulations showed that this method can achieve with only periodic task loads very close to 100%, far from the 50% of the global scheduling theory. The simulations showed that aperiodic tasks average response time is very good. We designed an acceptance test for sporadic tasks, hence, if a task is accepted then its deadline is guaranteed. The acceptance rate obtained in the experiments was over 80%. Finally, we devised a pre-rutime distribution method of periodic tasks that is able to provide at run time a high acceptance ratio for sporadic tasks and maintain a good level of service for aperiodic tasks

El rendimiento de los actuales sistemas multiprocesador de memoria compartida depende tanto de la utilización eficiente de todos los componentes del sistema (procesadores, memoria, etc), como de las características del conjunto de aplicaciones a ejecutar. Esta Tesis tiene como principal objetivo mejorar la ejecución de conjuntos de aplicaciones paralelas en sistemas multiprocesador de memoria compartida mediante la utilización de información sobre el rendimiento de las aplicaciones para la planificación de los procesadores.Es una práctica común de los usuarios de un sistema multiprocesador reservar muchos procesadores para ejecutar sus aplicaciones asumiendo que cuantos más procesadores utilicen mejor rendimiento sacarán sus aplicaciones. Sin embargo, normalmente esto no es cierto. Las aplicaciones paralelas tienen diferentes características respecto a su escalabilidad. Su rendimiento depende además de parámetros que sólo son conocidos en tiempo de ejecución, como por ejemplo el conjunto de datos de entrada o la influencia que pueden ejercer determinadas aplicaciones que se ejecutan de forma concurrente.En esta tesis proponemos que el sistema no base sus decisiones solamente en las peticiones de recursos de los usuarios sino que él, dinámicamente, mida el rendimiento que están consiguiendo las aplicaciones y base, o ajuste, sus decisiones teniendo en cuenta esa información.El rendimiento de las aplicaciones paralelas puede ser medido por el sistema de forma dinámica y automática sin introducir una sobrecarga significativa en la ejecución de las aplicaciones. Utilizando esta información, la planificación de procesadores puede ser decidida, o ajustada, siendo mucho más robusta a requerimientos incorrectos por parte de los usuarios, que otras políticas que no consideran este tipo de información. Además de considerar el rendimiento, proponemos imponer una eficiencia objetivo a las aplicaciones paralelas. Esta eficiencia objetivo determinará si la aplicación está consiguiendo un rendimiento aceptable o no, y será usada para ajustar la asignación de procesadores. La eficiencia objetivo de un sistema podrá ser un parámetro ajustable dinámicamente en función del estado del sistema: número de aplicaciones ejecutándose, aplicaciones encoladas, etc.También proponemos coordinar los diferentes niveles de planificación que intervienen en la planificación de procesadores: Nivel librería de usuario, planificador de procesadores (en el S.O), y gestión del sistema de colas. La idea es establecer una interficie entre niveles para enviar y recibir información entre niveles, así como considerar esta información para tomar las decisiones propias de cada nivel.La evaluación de esta Tesis ha sido realizada utilizando un enfoque práctico. Hemos diseñado e implementado un entorno de ejecución completo para ejecutar aplicaciones paralelas que siguen el modelo de programación OpenMP. Hemos introducido nuestras propuestas modificando los tres niveles de planificación mencionados. Los resultados muestran que las ideas propuestas en esta tesis mejoran significativamente el rendimiento del sistema. En aquellos casos en que tanto las aplicaciones como los parámetros del sistema han sido previamente optimizados, las propuestas realizadas introducen una penalización del 5% en el peor de los casos, comparado con el mejor de los resultados obtenidos por otras políticas evaluadas. Sin embargo, en otros casos evaluados, las propuestas realizadas en esta tesis han mejorado el rendimiento del sistema hasta un 400% también comparado con el mejor resultado obtenido por otras políticas evaluadas.Las principales conclusiones que podemos obtener de esta Tesis son las siguientes: - El rendimiento de las aplicaciones paralelas puede ser medido en tiempo de ejecución. Los requisitos para aplicar el mecanismo de medida propuesto en esta Tesis son que las aplicaciones sean maleables y estar en un entorno de ejecución multiprocesador de memoria compartida. - El rendimiento de las aplicaciones paralelas debe ser considerado para decidir la asignación de procesadores a aplicaciones. El sistema debe utilizar la información del rendimiento para auto-ajustar sus decisiones. Además, el sistema debe imponer una eficiencia objetivo para asegurar el uso eficiente de procesadores.- Los diferentes niveles de planificación deben estar coordinados para evitar interferencias entre ellos / The performance of current shared-memory multiprocessor systems depends on both the efficient utilization of all the architectural elements in the system (processors, memory, etc), and the workload characteristics.This Thesis has the main goal of improving the execution of workloads of parallel applications in shared-memory multiprocessor systems by using real performance information in the processor scheduling.It is a typical practice of users in multiprocessor systems to request for a high number of processors assuming that the higher the processor request, the higher the number of processors allocated, and the higher the speedup achieved by their applications. However, this is not true. Parallel applications have different characteristics with respect to their scalability. Their speedup also depends on run-time parameters such as the influence of the rest of running applications.This Thesis proposes that the system should not base its decisions on the users requests only, but the system must decide, or adjust, its decisions based on real performance information calculated at run-time. The performance of parallel applications is information that the system can dynamically measure without introducing a significant penalty in the application execution time. Using this information, the processor allocation can be decided, or modified, being robust to incorrect processor requests given by users. We also propose that the system use a target efficiency to ensure the efficient use of processors. This target efficiency is a system parameter and can be dynamically decided as a function of the characteristics of running applications or the number of queued applications.We also propose to coordinate the different scheduling levels that operate in the processor scheduling: the run-time scheduler, the processor scheduler, and the queueing system. We propose to establish an interface between levels to send and receive information, and to take scheduling decisions considering the information provided by the rest of levels.The evaluation of this Thesis has been done using a practical approach. We have designed and implemented a complete execution environment to execute OpenMP parallel applications. We have introduced our proposals, modifying the three scheduling levels (run-time library, processor scheduler, and queueing system).Results show that the ideas proposed in this Thesis significantly improve the system performance. If the evaluated workload has been previously tuned, in the worst case, we have introduced a slowdown around 5% in the workload execution time compared with the best execution time achieved. However, in some extreme cases, with a workload and a system configuration not previously tuned, we have improved the system performance in a 400%, also compared with the next best time.The main results achieved in this Thesis can be summarized as follows:- The performance of parallel applications can be measured at run-time. The requirements to apply the mechanism proposed in this Thesis are to have malleable applications and shared-memory multiprocessor architectures.- The performance of parallel applications 1must be considered to decide the processor allocation. The system must use this information to self-adjust its decisions based on the achieved performance. Moreover, the system must impose a target efficiency to ensure the efficient use of processors.- The different scheduling levels must be coordinated to avoid interferences between levels.

El càlcul de valors i vectors propis és un nucli computacional que forma part de diverses aplicacions de tipus científic i tècnic que requereixen una potència de càlcul molt gran. Aquestes aplicacions no poden resoldre's en sistemes monoprocessadors perquè aquests sistemes no proporcionen la potència de càlcul suficient per resoldre el problema amb un temps raonable. Una solució possible a aquest problema és la utilització de sistemes paral·lels.El contingut d'aquest treball pot dividir-se en quatre parts ben diferenciades; en les tres primeres parts dels valors i vectors propis en sistemes multicomputadors amb diferents topologies: hipercub, malla i torus; en l'última part del treball es proposa una metodologia d'anàlisis de l'escalabilitat de sistemes paral·lels.- En la primera part del treball es proposen un conjunt d'algorismes paral·lels per hipercubs: BR segmentat, alfa-optimal i Grau-4. Tots aquests algorismes es basen en l'algorisme Block Recursive proposat a [42]. Els nous algorismes proposats tenen la capacitat d'utilitzar de forma més eficient el potencial paral·lelisme de comunicacions que ofereix una arquitectura multiple-port amb els que s'aconsegueix una reducció del cost de la comunicació considerable respecte al cost de comunicació de l'algorisme original.- En la segona part del treball es proposa un nou algorisme amb una topologia de comunicació en malla bidimensional (2D). Aquest algorimse l'hem anomenat algorisme 2D. Es veurà que aquest nou algorisme aconsegueix reduir el cost total considerablement respecte als algorismes que han estat proposats per altres autors per malles i torus.- En la tercera part, s'estudia l'eficiència de l'algorisme BR-segmentat (algorisme amb una topologia de comunicació en hipercub proposat en la primera part de la tesi) un cop mapejat en un multicomputador amb una topologia en malla o en torus. A l'hora de realitzar el mapeig s'ha aplicat i ampliat una metodologia desenvolupada en el grup de treball que ens permet realitzar el mapeig de forma eficient i sistemàtic d'una topologia en hipercub a una topologia en malla o torus. El cost de la comunicació del nou algorisme es compara amb el cost de l'algorisme 2D proposat en la segona part del treball.- Finalment, en l'última part d'aquest treball es proposa una metodologia d'anàlisi de l'escalabilitat de sistemes paral·lels orientada a l'usuari final del sistema. S'utilitza l'algorisme 2D mapejat en una línia per mostrar un exemple d'aplicació de la metodologia.