Autores

7136
2673,131,764,2741
7137
2673,131,764,2741
7138
2673,131,764,2741
7139
2673,131,764,2741

Informações:

Publicações do PESC

Título
Explorando a Equivalência Entre Uma Máquina Química Abstrata e Computação Dataflow
Linha de pesquisa
Arquitetura e Sistemas Operacionais
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
23/3/2022
Resumo

Atualmente, a busca por desempenho computacional, tanto em aplicações de computação científica quanto em aplicações de uso geral, aponta para a computação paralela como área de interesse para sobrepor as dificuldades encontradas nos paradigmas computacionais utilizados tradicionalmente. Dentre os modelos computacionais paralelos onde programas podem ser desenvolvidos de maneira natural e transparente, Gamma e Dataflow apresentam uma surpreendente similaridade. Entretanto, a implementação do paradigma computacional Gamma apresenta vários desafios no que diz respeito ao escalonamento decorrente para a adequação às arquiteturas disponíveis. Neste trabalho demonstramos pela primeira vez a equivalência entre os modelos computacionais Gamma e Dataflow, onde além da apresentação da similaridade, apresentamos as provas formais de equivalência entre os modelos. Por ocasião desta equivalência, também propomos a implementação da primeira ferramenta de conversão entre os modelos Dataflow e Gamma, o GFlow. Diante dos desafios relacionados às implementações de Gamma, propomos o GSink. Trata-se da primeira implementação de um ambiente de execução de programas Gamma que permite a execução paralela de instâncias de diversas reações. Para tanto, utilizamos um mecanismo de escalonamento baseado em reversão de arestas de sinks de um grafo dirigido acíclico. Através de resultados experimentais demonstramos a corretude tanto das conversões propostas pelo GFlow, quanto dos resultados de execução do GSink.

Abstract

Currently, the search for computational performance, both in scientific computing applications and general-purpose applications, points to parallel computing as an area of interest to overcome the existing difficulties in traditionally used computational paradigms. Among the parallel computational models where programs can be developed in a natural and transparent way, Gamma and Dataflow present a surprising similarity. However, the implementation of the Gamma computational paradigm presents several challenges with regard to the resulting scheduling to adapt to the available architectures. In this work, we demonstrate for the first time, the equivalence between Gamma and Dataflow computational models, where we present the similarity and the formal equivalence proofs between these two models. Due to this equivalence, we also propose the implementation of the first conversion tool between the Dataflow and Gamma models, called GFlow. Faced with the challenges related to Gamma implementations, we also propose GSink. It consists of the first implementation of a Gamma program execution environment that allows the parallel execution of instances of several reactions. For that, we use a mechanism based on scheduling by edges reversal of an acyclic directed graph. Through experimental results, we demonstrate the correctness of both the conversions proposed by GFlow and the results of GSink execution.

Arquivo
Topo