Evaluating the Impacts of Applying List Scheduling Algorithms on Dynamic Multithreaded Environments in Theory and Practice

Autor: Camargo, Cícero Augusto de Souza
Přispěvatelé: Cavalheiro, Gerson Geraldo Homrich
Jazyk: portugalština
Rok vydání: 2013
Předmět:
Zdroj: Repositório Institucional da UFPEL
Universidade Federal de Pelotas (UFPEL)
instacron:UFPEL
Popis: Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2020-05-22T02:16:40Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Cicero_Augusto_de_Souza_Camargo.pdf: 1452499 bytes, checksum: ea68c2e21f2ef68467eb12351685ed6a (MD5) Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2020-05-22T02:18:36Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Cicero_Augusto_de_Souza_Camargo.pdf: 1452499 bytes, checksum: ea68c2e21f2ef68467eb12351685ed6a (MD5) Made available in DSpace on 2020-05-22T02:18:52Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Cicero_Augusto_de_Souza_Camargo.pdf: 1452499 bytes, checksum: ea68c2e21f2ef68467eb12351685ed6a (MD5) Previous issue date: 2013-11-10 Sem bolsa A popularização das arquiteturas multicore trouxe a capacidade de processamento paralelo para diversos dispositivos de computação pessoal, como laptops, tablets e smartphones. No entanto, para que uma aplicação se beneficie do hardware paralelo, precisamos do suporte de ferramentas de programação concorrente que forneçam uma interface simples e abstrata, a qual esconda do programador as complexidades do hardware e do sistema operacional. O modelo multithread é o que mais se adequa ao modo de execução das arquiteturas multicore. Diversas ferramentas de programação concorrente amplamente utilizadas como OpenMP, Intel R Cilk Plus e Intel R Threading Building Blocks, oferecem interfaces de programação multithread e abstraem o escalonamento de threads em nível de aplicação, empregando estratégias baseadas em algoritmos de lista. Uma vez que algoritmos de lista foram originalmente concebidos para o escalonamento estático de Grafos Dirigidos Acíclicos de tarefas (DAG – Directed Acyclic Graph), este trabalho se dedica a analisar o impacto gerado ao empregar tais algoritmos no núcleo de escalonamento de ambientes multithread dinâmicos. Para tanto, foram implementadas uma ferramenta de simulação e um ambiente real de execução multithread, este batizado de Anahy3. Os resultados obtidos nas simulações indicam que escalonamentos de lista em ambientes multithread podem fornecer, para uma dada aplicação, tempos de execução muito próximos daqueles obtidos no escalonamento estático do DAG que descreve a mesma aplicação, mesmo que o grafo de threads seja gerado em tempo de execução. Nas execuções reais com Anahy3 foi possível constatar que algoritmos de lista podem gerar escalonamentos eficientes, resultando em desempenhos semelhantes àqueles fornecidos pelas principais ferramentas multithread da academia e da indústria. Contudo, alguns resultados demonstram que a eficiência das técnicas utilizadas na implementação do ambiente de execução é tão importante quanto a ordem de execução dos threads. 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.
Databáze: OpenAIRE
Externí odkaz: