Esse trabalho apresenta a arquitetura a fluxo de dados Wolf. Essa arquitetura foi proposta considerando-se alguns problemas conhecidos em execução de código em arquiteturas a fluxo de dados tais como tratamento de código seqüencial e tratamento de estruturas de dados (vetores e matrizes). Wolf é baseado no modelo de fluxo de dados dinâmico e explora granulosidade variável, sendo a mais fina a nível de instrução. Alguns conceitos explorados por outras arquiteturas a fluxo de dados guiaram o desenvolvimento do Wolf. Entre esses estão o conceito de macro-dataflow e multithreading. Para o estudo da arquitetura Wolf foi desenvolvido um simulador dirigido a tempo que implementa suas características. O simulador Saw foi escrito na linguagem orientada a objetos C++ e pode ser compilado em qualquer plataforma que use um compilador padrão ANSI de 32 bits. O código do simulador foi exaustivamente testado e os resultados numéricos dos programas executados estão de acordo com resultados apresentados por uma arquitetura Von Neumann padrão. Após o estudo dos resultados obtidos com as simulações, foram identificados alguns problemas com a arquitetura Wolf. Algumas hipóteses foram testadas para solucionar tais problemas. Os resultados desses testes levaram à alteração da arquitetura. Desta alteração originou-se a arquitetura Wolf II que será apresentada também nesse trabalho. Por se tratar de uma conseqüência dos estudos realizados com a arquitetura Wolf, não serão feitos experimentos com o Wolf II. / This work presents the dataflow architecture Wolf. Wolf has been proposed in the focus of some known problems identified in previous works: the execution of data structures (vectors and matrices) and sequential code: to name a few. Wolf is based in the dynamic dataflow model and explores variable granularity (the thinnest is at instruction level). Some concepts developed in the designing of other hybrid architectures: guided the Wolf implementation. The macro-dataflow and multithreading were two of them. Focusing the study of the Wolf architecture: it has been developed a time driven simulator (Saw). The object oriented language C++ was used for this implementation. The code can be compiled on any ANSI standard 32 bits compiler. This code was exhaustively tested and the numeric results obtained with the experiments were equal to the ones obtained with Von Neumann architecture. This study identified some problems with the Wolf architecture. Some proposals were implemented in the simulator to try to identify the causes for the problems. The results led to an alteration in the Wolf architecture. The new proposed architecture (Wolf II) is described in the last chapter: but it was not submitted to experiments as Wolf was.

La complexité et le nombre toujours plus grandissant des applications, notamment les standards vidéo, nécessite d’étudier des méthodes et outils pour leur déploiement sur des architectures elles aussi toujours plus complexes. En effet, afin d’atteindre les performances requises en matière de temps d’exécution ou consommation énergétique, les architectures modernes proposent des éléments de calculs hétérogènes, où chacun est spécialisé pour une fonction précise. Cette thèse s’appuie sur le modèle flot de données pour la spécification de l’application. Ce modèle permet d’exposer explicitement le parallélisme spatial et temporel de l’application à travers un réseau d’acteurs interconnectés par des canaux de type FIFO. Les acteurs, en charge du calcul, peuvent exhiber un comportement statique ou dynamique. Les derniers standards vidéo contraignent à s’appuyer sur les modèles dynamiques pour obtenir une spécification fonctionnelle. Les besoins de calcul sont alors dépendants des données à traiter. Le déploiement d’une application dynamique ne peut donc se faire à l’aide des approches statiques existantes dans la littérature. L’objectif de cette thèse est de proposer des algorithmes efficaces permettant de déployer à la volée une application flot de données dynamique sur une architecture multiprocesseurs hétérogène. La première contribution est un algorithme qui permet de trouver rapidement une solution de déploiement de l’application. La deuxième contribution est un algorithme basé sur les mouvements pour adapter en cours d’exécution le déploiement en réponse aux aspects dynamiques de l’application. / Modern multimedia applications are subject to an increasing complexity with widespread standards. This has led to the interest in dataflow approach that offers a powerful perspective on parallel com- putations at high level. In the meantime, the emergence of massively parallel architectures has revealed the trend towards heterogeneous Multi-Processor System-on-Chips (MPSoCs) to offer a better perfor- mance and energy tradeoff than their homogeneous counterparts. However, this also imposes challenges to the mapping of multimedia applications on such complex architectures. This thesis presents an adaptive methodology for mapping dataflow applications on heterogeneous MPSoCs. This thesis focuses on video decoders specified in RVC-CAL language, a dedicated dataflow language for video applications. Existing static approaches cannot capture all behaviors in dynamic dataflow applications. Thus, this requires to adapt the mapping according to the input data. The algorithm offers some adaptive parameters combined with our analyt- ical communication model to improve a performance while consider- ing load balancing. We evaluate our algorithms on a set of randomly generated benchmarks and real video decoders like MPEG4-SP and HEVC. Experimental results reveal that our mapping methodology is fast enough (in milliseconds) and the runtime remapping signifi- cantly improves the initial mapping. In the remapping process, we take the migration cost into account because the reconfiguration time also contributes to the overall performance.

Due to close coupling to hardware and lack of software engineering technologies, the control software in digitally controlled power conversion systems is difficult to design and maintain. This is a natural consequence of a topology- or application-driven design approach. This research work proposes a distributed, modular, open control architecture for power conversion systems to reduce control design complexity, encapsulate and localize design dependencies, reduce unnecessary redesign effort and improve software quality. Dataflow style is chosen as the architectural style for the proposed control architecture based on comparative analysis. The detailed implementation of the dataflow architecture is presented. The resulting dataflow control software is evaluated in comparison to the legacy approach to control design used in industry and academia. The dataflow control software for a 3-phase voltage source inverter is also tested on a real PEBB-based converter system. To further explore the flexibility of control composition that is brought by the dataflow approach, the feasibility of dynamic control reconfiguration is also presented as an important future research direction. / Ph. D.

Avec l'augmentation de l'utilisation des smartphones, des objets connectés et des véhicules automatiques, le domaine des systèmes embarqués est devenu omniprésent dans notre environnement. Ces systèmes sont souvent contraints en terme de consommation et de taille. L'utilisation des processeurs many-cores dans des systèmes embarqués permet une conception rapide tout en respectant des contraintes temps-réels et en conservant une consommation énergétique basse.Exécuter une application sur un processeur many-core requiert un dispatching des tâches appelé problème de mapping et est connu comme étant NP-complet.Les contributions de cette thèse sont divisées en trois parties :Tout d'abord, nous étendons d'importantes propriétés dataflow au modèle Phased Computation Graph.Ensuite, nous présentons un générateur de graphe dataflow capable de générer des Synchonous Dataflow Graphs, Cyclo-Static Dataflow Graphs et Phased Computation Graphs vivant avec plus de 10000 tâches en moins de 30 secondes. Le générateur est comparé à SDF3 et PREESM.Enfin, la contribution majeure de cette thèse propose une nouvelle méthode d'évaluation d'un mapping en utilisant les modèles Synchonous Dataflow Graphe et Cyclo-Static Dataflow Graphe. La méthode évalue efficacement la mémoire consommée par les communications d'un dataflow mappé sur une architecture à mémoire distribuée. L'évaluation est déclinée en deux versions, la première garantit la vivacité alors que la seconde ajoute une contrainte de débit. La méthode d'évaluation est expérimentée avec des dataflow générés par Turbine et avec des applications réelles. / With the increasing use of smart-phones, connected objects or automated vehicles, embedded systems have become ubiquitous in our living environment. These systems are often highly constrained in terms of power consumption and size. They are more and more implemented with many-core processor array that allow, rapid design to meet stringent real-time constraints while operating at relatively low frequency, with reduced power consumption.Running an application on a processor array requires dispatching its tasks on the processors in order to meet capacity and performance constraints. This mapping problem is known to be NP-complete.The contributions of this thesis are threefold:First we extend important notions from the Cyclo-Static Dataflow Graph to the Phased Computation Graph model and two equivalent sufficient conditions of liveness.Second, we present a random dataflow graph generator able to generate Synchonous Dataflow Graphs, Cyclo-Static Dataflow Graphs and Phased Computation Graphs. The Generator, is able to generate live dataflow of up to 10,000 tasks in less than 30 seconds. It is compared with SDF3 and PREESM.Third and most important, we propose a new method of evaluation of a mapping using the Synchonous Dataflow Graph and the Cyclo-Static Dataflow Graph models. The method evaluates efficiently the memory footprint of the communications of a dataflow graph mapped on a distributed architecture. The evaluation is declined in two versions, the first guarantees a live mapping while the second accounts for a constraint on throughput.The evaluation method is experimented on dataflow graphs from Turbine and on real-life applications.

This work introduces a data model, compiler and runtime interpreter to drive the logic of animation graphs in game engines. The primary purpose of an animation graph is to allow for animation logic to be evaluated in a data driven way, which enables game programmers and animators to work iteratively and in parallel. The combination of animation blend trees and hierarchical state machines serves to empower animators to break down the complexity into simpler units with precise and predictable control over animation sampling and the transitions between them. Additionally, the system also serves as a synchronization point between game play elements and animation with input parameters and output events which can potentially trigger other systems such as audio and visual effects. The result is a standalone library which can be used as a foundation in a project and expanded with additional functionality as required. / Detta arbete introducerar en data model, kompilator och körmiljö för att driva logiken av  animationsgrafer i spelmotorer. Huvudsyftet av en animationsgraf är att tillåta datadrivet animationslogik vilket möjliggör spelprogrammerare och animerare att arbeta iterativt och parallellt. Kombinationen av animationblandningsträd och hierarkiska statmaskiner ger animerare ett sätt att bryta ner komplexa problem till mindre enheter med exakt och förutsägbar kontroll av animationer och övergångar mellan dem. Systemet verkar också som en synkroniseringspunkt mellan spelelement och animation med inmatningsparameterar och utgående händelser som potentiellt kan utlösa andra system som ljud- och visuella effekter. Resultatet är ett fristående programbibliotek som kan användas som en startpunkt i ett projekt och vars funktionalitet kan utökas vid behov.

O modelo a fluxo de dados tem grande destaque em pesquisas em arquiteturas de alto desempenho. Neste modelo, o controle de execução é feito apenas pela disponibilidade dos dados, permitindo que seja explorado o máximo de paralelismo implícito em um programa. As propostas que serão expostas neste trabalho visam solucionar um particular problema da máquina de fluxo de dados de Manchester. Esta arquitetura para tratar código reentrante, impõe que as fichas de dados, além da indicação da instrução destino, possuam um rótulo. Estas informações extras, que formam 70% da ficha de dado, fazem com que a implantação da máquina seja complexa. Assim, o hardware impõe um sério limite a velocidade de processamento, impedindo a plena utilização do modelo. Neste trabalho, serão apresentadas propostas para a redução do número de informações necessárias para o correto funcionamento da máquina, possibilitando uma implementação mais simples e mais eficiente. / The dataflow model is specially relevant you research in high-performance architectures. In this model, the execution control is done by taking into account only the dates availability, thus allowing maximum exploitation of the paralelism implicit in programs. The present work is based on the Manchester dataflow machine, which, in to order you handle the reentran code, imposes the dates token you have, in addition you the destination instruction Field, albel. Additional This information, which corresponds you 70% of the dates token, compounds the machine implementation it substantially bounds the execution speed and prevents the full model utilization. This work presents approaches will be reducing the amount of information needed will be to proper machine operation in to order you achieve to simpler and lives effective implementation.

Neste trabalho é apresentada a arquitetura SEED, proposta a partir das experiências adquiridas com as arquiteturas baseadas no modelo a fluxo de dados que foram estudadas até o presente. A arquitetura SEED utiliza o modelo a fluxo de dados para escalonar e executar blocos de instruções, visando aproveitar a principal qualidade apresentada pelo modelo, que consiste em expor o máximo de paralelismo existente nos programas. No entanto, a arquitetura explora paralelismo de granularidade mais grossa que as arquiteturas a fluxo de dados, a fim de reduzir o trafego de fichas de dados na arquitetura. Esta redução tenta resolver ou amenizar problemas como a excessiva ocupação de memória e a grande complexidade exigida do hardware. Além da especificação da funcionalidade de toda a arquitetura SEED, este trabalho apresenta uma proposta para o particionamento do código. A utilização desta proposta permite a geração de blocos de códigos que podem ser executados corretamente pela arquitetura SEED. Alguns benchmarks foram gerados utilizando essa proposta de particionamento de código. Estes benchmarks foram executados no simulador da arquitetura SEED, visando analisar e avaliar o comportamento da arquitetura com diversas configurações de hardware. / In this work is presented the SEED architecture. This architecture was proposed considering the experiences obtained with existing architectures based on dataflow model. The SEED architecture uses dataflow model to schedule and execute sets of instructions, called code blocks. This approach tries to make use of the main quality of the dataflow model that is to expose the maximum parallelism of the programs. However, this architecture explores coarser granularity than the one usually considered in dataflow architectures in order to reduce the data token traffic in the architecture. This type of reduction tries to solve problems like excessive occupation of memory and high complexity of the hardware. Besides the specification of all units that compose the SEED architecture, this work also proposes a way of partitioning programs, creating code blocks that may be executed by SEED architecture. Some benchmarks were generated using this proposal for partitioning programs. These benchmarks were executed in the SEED architecture simulator, in order to analyze the behavior of the proposed architecture under special configurations.

Many digital signal processing and real-time streaming systems are modeled using dataflow graphs, such as Synchronous Dataflow (SDF) and Cyclo-static Dataflow (CSDF) graphs that allow static analysis and optimization techniques. However, mapping of such descriptions into tightly constrained real-time implementations requires optimization of resource sharing, buffering and scheduling across a multi-dimensional latency-throughput-area objective space. This requires techniques that can find the Pareto-optimal set of implementations for the designer to choose from. In this work, we address the problem of multi-objective mapping and scheduling of SDF and CSDF graphs onto heterogeneous multi-processor platforms. Building on previous work, this thesis extends existing two-stage hybrid heuristics that combine an evolutionary algorithm with an integer linear programming (ILP) model to jointly optimize throughput, area and latency for SDF graphs. The primary contributions of this work include: (1) extension of the ILP model to support CSDFGs with additional buffer size optimizations; (2) a further optimization in the ILP-based scheduling model to achieve a runtime speedup of almost a factor of 10 compared to the existing SDFG formulation; (3) a list scheduling heuristic that replaces the ILP model in the hybrid heuristic to generate Pareto-optimal solutions at significantly decreased runtime while maintaining near-optimality of the solutions within an acceptable gap of 10% when compared to its ILP counterparts. The list scheduling heuristic presented in this work is based on existing modulo scheduling approaches for software pipelining in the compiler domain, but has been extended by introducing a new concept of mobility-based rescheduling before resorting to backtracking. It has been proved in this work that if mobility-based rescheduling is performed, the number of required backtrackings and hence overall complexity and runtime is less. / text

[pt] Muitas aplicações são tornadas programáveis para usuários finais avançados adicionando recursos como scripting e macros. Outras aplicações dão a uma linguagem de programação um papel central na sua interface com o usuário. Esse é o caso, por exemplo, da linguagem de fórmulas de planilhas de cálculo. Enquanto a área de scripting se beneficiou dos avanços das pesquisas em linguagens de programação, produzindo linguagens maduras e reusáveis, o estado das linguagens em nível de interface não teve o mesmo grau de desenvolvimento. Argumentamos que um melhor entendimento desta classe de linguagens se faz necessário. Neste trabalho, modelamos semânticas de linguagens de usuário final existentes, em três diferentes domínios: multimídia, planilhas e engenharia. Nosso foco é em linguagens de dataflow, um paradigma representativo em aplicações programáveis por usuários finais. Com base nessa análise, temos como objetivo prover um melhor entendimento do design de linguagens de dataflow no contexto de programação de usuários finais e propor linhas-guia para o projeto de linguagens de nível de interface baseadas neste paradigma para aplicações programáveis. / [en] Many applications are made programmable for advanced end-users by adding facilities such as scripting and macros. Other applications take a programming language to the center stage of its UI. That is the case, for example, of the spreadsheet formula language. While scripting has benefited from the advances of programming language research, producing mature and reusable languages, the state of UI-level languages lags behind. We claim that a better understanding of such languages is necessary. In this work, we model the semantics of existing end-user programming languages in three different domains: multimedia, spreadsheets and engineering. Our focus is on dataflow languages, a representative paradigm for end-user programmable applications. Based on this analysis, we aim to provide a better understanding of dataflow semantics as used in the context of end-user programming and propose guidelines for the design of UI-level languages for end-user programmable applications.

O modelo a fluxo de dados tem grande destaque em pesquisas em arquiteturas de alto desempenho. Neste modelo, o controle de execução é feito apenas pela disponibilidade dos dados, permitindo que seja explorado o máximo de paralelismo implícito em um programa. As propostas que serão expostas neste trabalho visam solucionar um particular problema da máquina de fluxo de dados de Manchester. Esta arquitetura para tratar código reentrante, impõe que as fichas de dados, além da indicação da instrução destino, possuam um rótulo. Estas informações extras, que formam 70% da ficha de dado, fazem com que a implantação da máquina seja complexa. Assim, o hardware impõe um sério limite a velocidade de processamento, impedindo a plena utilização do modelo. Neste trabalho, serão apresentadas propostas para a redução do número de informações necessárias para o correto funcionamento da máquina, possibilitando uma implementação mais simples e mais eficiente. / The dataflow model is specially relevant you research in high-performance architectures. In this model, the execution control is done by taking into account only the dates availability, thus allowing maximum exploitation of the paralelism implicit in programs. The present work is based on the Manchester dataflow machine, which, in to order you handle the reentran code, imposes the dates token you have, in addition you the destination instruction Field, albel. Additional This information, which corresponds you 70% of the dates token, compounds the machine implementation it substantially bounds the execution speed and prevents the full model utilization. This work presents approaches will be reducing the amount of information needed will be to proper machine operation in to order you achieve to simpler and lives effective implementation.