No description available.

With the failure of Dennard's scaling, which stated that shrinking transistors will be more power-efficient, computer hardware has today become very divergent. Initially the change only concerned the number of processor on a chip (multicores), but has today further escalated into complex heterogeneous system with non-intuitive properties -- properties that can improve performance and power consumption but also strain the programmer expected to develop on them. Answering these challenges is the OpenMP task-parallel model -- a programming model that simplifies writing parallel software. Our focus in the thesis has been to explore performance and quality-of-service directions of the OpenMP task-parallel model, particularly by taking architectural features into account. The first question tackled is: what capabilities does existing state of the art runtime-systems have and how do they perform? We empirically evaluated the performance of several modern task-parallel runtime-systems. Performance and power-consumption was measured through the use of benchmarks and we show that the two primary causes for bottlenecks in modern runtime-systems lies in either the task management overheads or how tasks are being distributed across processors. Next, we consider quality-of-service improvements in task-parallel runtime-systems. Striving to improve execution performance, current state of the art runtime-systems seldom take dynamic architectural features such as temperature into account when deciding how work should be distributed across the processors, which can lead to overheating. We developed and evaluated two strategies for thermal-awareness in task-parallel runtime-systems. The first improves performance when the computer system is constrained by temperature while the second strategy strives to reduce temperature while meeting soft real-time objectives. We end the thesis by focusing on performance. Here we introduce our original contribution called BLYSK -- a prototype OpenMP framework created exclusively for performance research. We found that overheads in current runtime-systems can be expensive, which often lead to performance degradation. We introduce a novel way of preserving task-graphs throughout application runs: task-graphs are recorded, identified and optimized the first time an OpenMP application is executed and are later re-used in following executions, removing unnecessary overheads. Our proposed solution can nearly double the performance compared with other state of the art runtime-systems. Performance can also be improved through heterogeneity. Today, manufacturers are placing processors with different capabilities on the same chip. Because they are different, their power-consuming characteristics and performance differ. Heterogeneity adds another dimension to the multiprocessing problem: how should work be distributed across the heterogeneous processors?We evaluated the performance of existing, homogeneous scheduling algorithms and found them to be an ill-match for heterogeneous systems. We proposed a novel scheduling algorithm that dynamically adjusts itself to the heterogeneous system in order to improve performance. The thesis ends with a high-level synthesis approach to improve performance in task-parallel applications. Rather than limiting ourselves to off-the-shelf processors -- which often contains a large amount of unused logic -- our approach is to automatically generate the processors ourselves. Our method allows us to generate application-specific hardware from the OpenMP task-parallel source code. Evaluated using FPGAs, the performance of our System-on-Chips outperformed other soft-cores such as the NiosII processor and were also comparable in performance with modern state of the art processors such as the Xeon PHI and the AMD Opteron. / <p>QC 20151016</p>

No description available.

No description available.

No description available.

No description available.

No description available.

This thesis presents the LiquiMedia operating system architecture. LiquiMedia is specialized to schedule multimedia applications. Because they generate output for a human observer, multimedia applications such as video games, video conferencing and video players have both unique scheduling requirements and unique allowances: a multimedia stream must synchronize sub-streams generated for different sensory modalities within 20 milliseconds, it is not successfully segregated until it has existed for over 200 milliseconds and tolerates occasional scheduling failures. LiquiMedia is specialized around these requirements and allowances. First, LiquiMedia synchronizes multimedia tasks by invoking them from a shared realtime timer interrupt. Second, owing to multimedia's tolerance of scheduling failures, LiquiMedia schedules tasks based on a probabilistic model of their running times. Third, LiquiMedia can infer per-task models while a user is segregating the streams that the tasks generate. These specializations provide novel capabilities: up to 2. 5 times higher utilization than RMS scheduling, use of an atomic task primitive 9. 5 times more efficient than preemptive threading, and most importantly, the ability to schedule arbitrary tasks to a known probability of realtime execution without a priori knowledge of their running times.

Ingeniero Civil Matemático / El objetivo principal del presente trabajo de memoria de título es el cálculo de cotas para precio de la anarquía de algunos juegos asociados a problemas de scheduling. Se comienza realizando una revisión general de lo que son los problemas de scheduling, un algoritmo de aproximación y la relación que existe entre teoría de juegos y los problemas de scheduling. Ahí se identifica el cuociente de aproximación del algoritmo de Smith para problemas de scheduling, con el precio de la anarquía de un juego asociado. Se realiza también una revisión de los principales resultados conocidos útiles para el presente trabajo. Más adelante se calcula el precio de la anarquía para ciertos juegos de scheduling donde la función objetivo es la suma ponderada de los tiempos de completación. Se demuestra que en el caso de máquinas idénticas, el precio de la anarquía en estrategias mixtas es 3/2. Se demuestra también que en máquinas paralelas con velocidades, el precio de la anarquía es mayor o igual a 2. Por último, se prueba acá que en el caso en que todos los trabajos tienen el mismo tamaño, el precio de la anarquía del juego de scheduling en máquinas paralelas con velocidades y suma ponderada de los tiempos de completación como función objetivo es 1. Para seguir se estudia el juego asociado al problema de scheduling en el cual la función objetivo es la suma de los tiempos de completación, y las máquinas son todas excepto una idénticas entre sí, la máquina restante es de velocidad mayor a las demás, y las máquinas que son más lentas son una cantidad suficientemente grande. Para este juego de scheduling se demuestra que el precio de la anarquía es e/(e-1). Después se estudia el juego mencionado anteriormente en su caso más general, en el cual la cantidad de máquinas lentas no está restringida a ser suficientemente grande. Para este problema se demuestra que el precio de la anarquía está acotado superiormente por 5/3. Se muestra además un problema de programación lineal cuyo óptimo acota superiormente el precio de la anarquía del juego de scheduling de máquinas paralelas con velocidades y suma de los tiempos de completación como función objetivo. Finalmente, se plantea como conjetura que el precio de la anarquía del juego asociado al problema de scheduling más general antes mencionado es efectivamente e/(e-1), y se muestran pruebas computacionales que fueron realizadas, con las cuales se justifica el plantear esta conjetura.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd Easton / Heuristics are often implemented to find better solutions to computationally challenging problems. Heuristics use varying techniques to search for quality solutions. Several optimization heuristics have drawn inspiration from real world practices. Ant colony optimization mimics ants in search of food. Genetic algorithms emulate traits being passed from a parent to a child. Simulated annealing imitates annealing metal. This thesis presents a new variable neighborhood search optimization heuristic, fútbol Strategies applied to Optimize Combinatorial problems to Create Efficient Results, which is called the SOCCER heuristic. This heuristic mimics fútbol and the closest player to the ball performs his neighborhood search and players are assigned different neighborhoods. The SOCCER heuristic is the first application of variable neighborhood search heuristic that uses a complex structure to select neighborhoods. The SOCCER heuristic can be applied to a variety of optimization problems. This research implemented the SOCCER heuristic for job shop scheduling problems. This implementation focused on creating a quality schedule for a local limestone company. A small computational study shows that the SOCCER heuristic can quickly solve complex job shop scheduling problems with most instances finishing in under an half an hour. The optimized schedules reduced the average production time by 7.27%. This is roughly a 2 day decrease in the number of days required to produce a month’s worth of orders. Thus, the SOCCER heuristic is a new optimization tool that can aid companies and researchers find better solutions to complex problems.