Algoritmos de escalonamento de lista em ambientes multithread dinâmicos: análise de estudos de caso teóricos e práticos

Abstract

The popularization of multicore architectures made parallel-processing available in sereval personal computing devices such as laptops, tablets and smartphones. However, for an application to benefit from the parallel hardware, we need the support of concurrent programming tools that provide a clean and abstract interface, that hides from the programmer the complexities of the underlying platform. The multithreaded model is the most suitable for the execution mode of multicore architectures. Several widely used concurrent programming tools, such as OpenMP, Intel Cilk Plus, and Intel Threading Building Blocks, provide multithread programming interfaces and abstract thread scheduling at the application level, using strategies based on list algorithms. Once list algorithms were originally designed to schedule DAGs (Directed Acyclic task Graphs) statically, this study aims to analyze the impact of applying list algorithms in the core of dynamic multithreaded environments. In order to this, we implemented a simulation tool and a real multithreaded environment that we called Anahy3. Simulation results indicate that, given an application, list schedules can provide, in multithreaded environments, execution times very close to those obtained when scheduling the application DAG statically, even when the thread graph is generated at runtime. In real executions with Anahy3, we could show that list algorithms can generate efficient schedules, providing execution performances equivalent to the ones obtained using the most prominent multithreaded tools in academy and industry. However, some results showed that the an efficient implementation of the execution environment is as important as the execution order of threads.