The increasing demand for energy efficient computing has endorsed the usage of Field-Programmable Gate Arrays to create hardware accelerators for large and complex codes. However, implementing such accelerators involve two complex decisions. The first one lies in deciding which code snippet is the best to create an accelerator, and the second one lies in how to implement the accelerator. When considering both decisions concomitantly, the problem becomes more complicated since the code snippet implementation affects the code snippet choice, creating a combined design space to be explored. As such, a fast design space exploration for the accelerators implementation is crucial to allow the exploration of different code snippets. However, such design space exploration suffers from several time-consuming tasks during the compilation and evaluation steps, making it not a viable option to the snippets exploration. In this work, we focus on the efficient implementation of pipelined hardware accelerators and present our contributions on speeding up the pipelines creation and their design space exploration. Towards loop pipelining, the proposed approaches achieve up to 100× speed-up when compared to the state-uf-the-art methods, leading to 164 hours saving in a full design space exploration with less than 1% impact in the final results quality. Towards design space exploration, the proposed methods achieve up to 9:5× speed-up, keeping less than 1% impact in the results quality. / A demanda crescente por computação energeticamente eficiente tem endossado o uso de Field- Programmable Gate Arrays para a criação de aceleradores de hardware para códigos grandes e complexos. Entretanto, a implementação de tais aceleradores envolve duas decisões complexas. O primeiro reside em decidir qual trecho de código é o melhor para se criar o acelerador, e o segundo reside em como implementar tal acelerador. Quando ambas decisões são consideradas concomitantemente, o problema se torna ainda mais complicado dado que a implementação do trecho de código afeta a seleção dos trechos de código, criando um espaço de projeto combinatorial a ser explorado. Dessa forma, uma exploração do espaço de projeto rápida para a implementação de aceleradores é crucial para habilitar a exploração de diferentes trechos de código. Contudo, tal exploração do espaço de projeto é impedida por várias tarefas que consumem tempo durante os passos de compilação a análise, o que faz da exploração de trechos de códigos inviável. Neste trabalho, focamos na implementação eficiente de aceleradores pipeline em hardware e apresentamos nossas contribuições para o aceleramento da criações de pipelines e de sua exploração do espaço de projeto. Referente à criação de pipelines, as abordagens propostas alcançam uma aceleração de até 100× quando comparadas às abordagens do estado-da-arte, levando à economia de 164 horas em uma exploração de espaço de projeto completa com menos de 1% de impacto na qualidade dos resultados. Referente à exploração do espaço de projeto, as abordagens propostas alcançam uma aceleração de até 9:5×, mantendo menos de 1% de impacto na qualidade dos resultados.

Devido ao grande número de otimizações fornecidas pelos compiladores modernos e à ampla possibilidade de ordenação dessas transformações, uma eficiente Exploração do Espaço de Projeto (DSE) se faz necessária para procurar a melhor sequência de otimização de uma determinada função ou fragmento de código. Como esta exploração é uma tarefa complexa e dispendiosa, apresentamos uma nova abordagem de DSE capaz de reduzir esse tempo de exploração e selecionar sequências de otimização que melhoraram o desempenho dos códigos transformados. Nossa abordagem utiliza um conjunto de funções de referência, para as quais uma representação simbólica do código (DNA) e a melhor sequência de otimização são conhecidas. O DSE de novas funções é baseado em uma abordagem de agrupamento aplicado sobre o código DNA que identifica similaridades entre funções. O agrupamento utiliza três técnicas para a mineração de dados: distância de compressão normalizada, algoritmo de reconstrução de árvores filogenéticas (Neighbor Joining) e identificação de grupos por ambiguidade. As otimizações das funções de referência identificadas como similares formam o espaço que é explorado para encontrar a melhor sequência para a nova função. O DSE pode utilizar o conjunto reduzido de otimizações de duas formas: como o espaço de projeto ou como a configuração inicial do algoritmo. Em ambos os casos, a adoção de uma pré-seleção baseada no agrupamento permite o uso de algoritmos de busca simples e rápidos. Os resultados experimentais revelam que a nova abordagem resulta numa redução significativa no tempo total de exploração, ao mesmo tempo que alcança um desempenho próximo ao obtido através de uma busca mais extensa e dispendiosa baseada em algoritmos genéticos. / Due to the large number of optimizations provided in modern compilers and to compiler optimization specific opportunities, a Design Space Exploration (DSE) is necessary to search for the best sequence of compiler optimizations for a given code fragment (e.g., function). As this exploration is a complex and time consuming task, we present new DSE strategies to reduce the exploration time and still select optimization sequences able to improve the performance of each function. The DSE is based on a clustering approach which groups functions with similarities and then explore the reduced search space provided by the optimizations previously suggested for the functions in each group. The identification of similarities between functions uses a data mining method which is applied to a symbolic representation of the source code. The DSE strategies uses the reduced optimizations set identified by clustering in two ways: as the design space or as the initial configuration of the algorithm. In both ways, the adoption of a pre-selection based on clustering allows the use of simple and fast DSE algorithms. Several experiments for evaluating the effectiveness of the proposed approach address the exploration of compiler optimization sequences. Besides, we investigate the impact of each technique or component employed in the selection process. Experimental results reveal that the use of our new clustering-based DSE approach achieved a significant reduction on the total exploration time of the search space at the same time that obtained performance speedups close to a traditional genetic algorithmbased approach.

Este trabalho propõe uma nova abordagem para o desenvolvimento de sistemas embarcados, através da combinação da abstração e propriedades de verificação de modelos da linguagem declarativa Alloy com a ampla aceitação de Java na indústria. A abordagem surge no contexto de que a automação de software no domínio embarcado tornou-se extremamente necessária, uma vez que atualmente a maior parte do tempo de desenvolvimento é gasta no projeto de software de produtos tão restritos em termos de recursos. As ferramentas de automação de software embarcado devem atender a demanda por produtividade e manutenibilidade, mas respeitar restrições naturais deste tipo de sistema, tais como espaço de memória, potência e desempenho. As ferramentas de automação de projeto lidam com produtividade e manutenibilidade ao permitir especificações de alto nível, tarefa difícil de atender no domínio embarcado devido ao comportamento misto de muitas aplicações embarcadas. Abordagens que promovem meios para verificação formal também são atrativas, embora geralmente sejam difíceis de usar, e por este motivo não são de grande auxílio na tarefa de reduzir o tempo de chegada ao mercado do produto. Através do uso de Alloy, baseada em lógica de primeira-ordem, é possível obter especificações em altonível e verificação formal de modelos com uma única linguagem. Este trabalho apresenta a poderosa abstração proporcionada pela linguagem Alloy em aplicações embarcadas, assim como regras para obter automaticamente código Java a partir de modelos Alloy. A geração de código Java a partir de modelos Alloy, combinada a uma ferramenta de estimativa, provê exploração de espaço de projeto, atendendo assim as fortes restrições do projeto de software embarcado, o que normalmente não é contemplado pela engenharia de software tradicional. / This work proposes a new approach for embedded software development, by combining the abstraction and model verification properties of the Alloy declarative language with the broad acceptance in industry of Java. The approach comes into play since software automation in the embedded domain has become a major need, as currently most of the development time is spent designing software for such hardconstrained resources products. Design automation tools for embedded systems must meet the demand for productivity and maintainability, but constraints such as memory, power and performance must still be considered. Design automation tools deal with productivity and maintainability by allowing high-level specifications, which is hard to accomplish on the embedded domain due to the mixed behavior nature of many embedded applications. Approaches that provide means for formal verification are also attractive, but their usage is usually not straightforward, and for this reason they are not that helpful in dealing with time-tomarket constraints. By using Alloy, based in first-order logic, it is possible to obtain high-level specifications and formal model verification with a single language. This work shows the powerful abstraction provided by the Alloy language for embedded applications, as well as rules for obtaining automatically Java code from Alloy models. The Java source code generation from Alloy models, combined with an estimation tool, provides design space exploration to match tight embedded software design constraints, what is usually not taken into account by standard software engineering techniques.

Les travaux de cette thèse s'inscrivent dans une collaboration avec l'entreprise Berger-Levrault, acteur majeur du développement de logiciels de gestion administrative pour les services publics. Ces travaux s'appuient sur deux constats. D'une part, la politique de numérisation des services publics induit la nécessité de disposer de logiciels adaptés aux métiers de l'ensemble des établissements publics. Ces logiciels sont complexes et particulièrement riches comparativement aux logiciels de bureautique classiquement utilisés. D'autre part, on observe que les dispositifs utilisés pour interagir avec ces logiciels n'évoluent que très peu. Depuis plusieurs décennies, la souris et le clavier restent la norme dans un environnement fixe. Or, ces dispositifs ne possèdent que peu de degrés de libertés en entrée. La manipulation de données multidimensionnelles avec ceux-ci induit un plus grand nombre d'étapes pour réaliser une tâche, rallongeant ainsi le chemin d'interaction. Dans ce contexte, l'objectif de ces travaux de thèse est de contribuer à la fluidification de l'interaction avec des données multidimensionnelles, contenues dans les logiciels du service public, au travers de l'augmentation des degrés de libertés en entrée proposés par les dispositifs. En effet, une plus grande quantité de degrés de libertés en entrée réduirait le nombre d'étapes nécessaires à la réalisation d'une tâche donnée, fluidifiant ainsi l'interaction. Nous proposons 3 contributions majeures : un dispositif à multiples degrés de libertés, la Roly-Poly Mouse ; un espace de conception, DECO ; ainsi qu'un ensemble de techniques d'interaction avec dispositifs mobiles basées sur le principe du stacking. Une première contribution de nos travaux consiste en la conception d'un nouveau dispositif à multiples degrés de liberté : la Roly-Poly Mouse (RPM). Ce dispositif, dont la base est arrondie, vise à remplacer la souris traditionnelle. Il possède 6 degrés de libertés (3 translations dont 2 exploitées et 3 rotations). Nous avons évalué ses performances et l'avons comparé à d'autres dispositifs pour une tâche nécessitant 6 degrés de libertés (manipulation d'objet 3D). Une seconde contribution de nos travaux consiste en la définition d'un espace de conception se focalisant sur l'aspect physique de la composition de dispositifs : DECO. DECO s'appuie sur deux axes : l'arrangement physique et la manipulation physique. À partir de cet espace de conception, nous avons conçu un dispositif composé : la Roly-Poly Mouse 2, un dispositif composé d'une Roly-Poly Mouse et d'une souris traditionnelle. Nous avons évalué ses performances et l'avons comparé à d'autres dispositifs au travers d'une tâche de RST (Rotate-Scale-Translate, tâche 5D). [...] / The work of this thesis is part of a collaboration with the company Berger-Levrault, a major actor in the development of administrative management software for public services. This work is based on two observations. On the first hand, the policy of digitization of public services induces the need for software adapted to the professions of all public institutions. These software are complex and particularly rich compared to classically used office software (Office, mailbox, etc.). On the other hand, we observe that the devices used to interact with these software did not evolve. Since several decades, the mouse and the keyboard remain the norm in a fixed environment. However, these devices have only few input degrees of freedom. The manipulation of multidimensional data with these devices induces a greater number of steps to perform a task, thus lengthening the interaction path. In this context, the objective of these thesis work is to improve the interaction flow with multidimensional data contained in the software of the public service through the increase of the input degrees of freedom proposed by the devices. Indeed, a larger amount of input degrees of freedom would reduce the number of steps necessary to the accomplishment of a given task, thus improving the interaction flow. We propose three major contributions: a device with multiple degrees of freedom, the Roly-Poly Mouse; a design space, DECO; as well as a set of interaction techniques with mobile devices based on the principle of stacking. A first contribution of our work is the design of a new device with multiple degrees of freedom: the Roly-Poly Mouse (RPM). This device, whose base is rounded, aims to replace the traditional mouse. It has 6 degrees of freedom (3 translations of which 2 exploited and 3 rotations). We evaluated its performance and compared it to other devices for a task requiring 6 degrees of freedom (3D object manipulation). A second contribution of our work is the definition of a design space focusing on the physical aspect of the composition of devices: DECO. DECO relies on two axes: physical arrangement and physical manipulation. From this design space, we designed a compound device: the Roly-Poly Mouse 2, a device consisting of the combination of a Roly-Poly Mouse and a traditional mouse. We evaluated its performance and compared it to other devices through a RST task (Rotate-Scale-Translate, 5D task). [...]

Dans le cadre de la synthèse de haut niveau (SHN), qui permet d'extraire un modèle structural à partir d'un modèle algorithmique, nous proposons des solutions pour opti- miser l'accès et le transfert de données du matériel cible. Une méthodologie d'exploration de l'espace des architectures mémoire possibles a été mise au point. Cette méthodologie trouve un compromis entre la quantité de mémoire interne utilisée et les performances temporelles du matériel généré. Deux niveau d'optimisation existe : 1. Une optimisation architecturale, qui consiste à créer une hiérarchie mémoire, 2. Une optimisation algorithmique, qui consiste à partitionner la totalité des données manipulées pour stocker en interne seulement celles qui sont utiles dans l'immédiat. Pour chaque répartition possible, nous résolvons le problème de l'ordonnancement des calculs et de mapping des données. À la fin, nous choisissons la ou les solutions pareto. Nous proposons un outil, front-end de la SHN, qui est capable d'appliquer l'optimisation algorithmique du point 2 à un algorithme de traitement d'image spécifié par l'utilisateur. L'outil produit en sortie un modèle algorithmique optimisé pour la SHN, en customisant une architecture générique.

Ride and handling are important areas for safety and improved vehicle control during driving. To meet the demands on ride and handling a number of measures can be taken. This master thesis work has focused on the early design phase. At the early phases of design, the level of details is low and the design freedom is big. By introducing a tool to support the early vehicle body design, the potential of finding more efficient structures increases. In this study, topology optimization of a vehicle front structure has been performed using OptiStruct by Altair Engineering. The objective has been to find the optimal topology of beams and rods to achieve high stiffness of the front structure for improved ride and handling. Based on topology optimization a proposal for a beam layout in the front structure area has been identified. A vital part of the project has been to describe how to use topology optimization as a tool in the design process. During the project different approaches has been studied to come from a large design space to a low weight architecture based on a beam-like structure. The different approaches will be described and our experience and recommendations will be presented. Also the general result of a topology-optimized architecture for vehicle body stiffness will be presented.

In the design of a multi-processor System-on-a-Chip (SoC), the bus architecture typically comes to the forefront because the system performance is not dependent only on the speed of the Processing Elements (PEs) but also on the bus architecture in the system. An efficient bus architecture with effective arbitration for reducing contention on the bus plays an important role in maximizing performance. Therefore, among many issues of multi-processor SoC research, we focus on two issues related to the bus architecture in this dissertation. One issue is how to quickly and easily design an efficient bus architecture for an SoC. The second issue is how to quickly explore the design space across performance influencing factors to achieve a high performance bus system. The objective of this research is to provide a Computer-Aided Design (CAD) tool with which the user can quickly explore System-on-a-Chip (SoC) bus design space in search of a high performance SoC bus system. From a straightforward description of the numbers and types of Processing Elements (PEs), non-PEs, memories and buses (including, for example, the address and data bus widths of the buses and memories), our Bus Synthesis tool, called BusSynth, generates a Register-Transfer Level (RTL) Verilog Hardware Description Language (HDL) description of the specified bus system. The user can utilize this RTL Verilog in bus-accurate simulations to more quickly arrive at an efficient bus architecture for a multi-processor SoC. The methodology we propose gives designers a great benefit in fast design space exploration of bus systems across a variety of performance influencing factors such as bus types, PE types and software programming styles (e.g., pipelined parallel fashion or functional parallel fashion). We also show that BusSynth can efficiently generate bus systems in a matter of seconds as opposed to weeks of design effort to integrate together each system component by hand. Moreover, unlike the previous related work, BusSynth can support a wide variety of PEs, memory types and bus architectures (including a hybrid bus architecture) in search of a high performance SoC.

Often, design problems are strongly coupled and their concurrent resolution by interacting (though decentralized) stakeholders is required. The ensuing interactions are characterized predominantly by degree of interdependence and level of cooperation. Since tradeoffs, made within and among sub-systems, inherently contribute to system level performance, bridging the associated gaps is crucial. With this in mind, effective collaboration, centered on continued communication, concise coordination, and non-biased achievement of system level objectives, is becoming increasingly important. Thus far, research in distributed and decentralized decision-making has focused primarily on conflict resolution. Game theoretic protocols and negotiation tactics have been used extensively as a means of making the required tradeoffs, often in a manner that emphasizes the maximization of stakeholder payoff over system level performance. More importantly, virtually all of the currently instantiated mechanisms are based upon the a priori assumption of the existence of solutions that are acceptable to all interacting parties. No explicit consideration has been given thus far to ensuring the convergence of stakeholder design activities leading up to the coupled decision and the associated determination of values for uncoupled and coupled design parameters. Consequently, unnecessary and costly iteration is almost certain to result from mismatched and potentially irreconcilable objectives. In this dissertation, an alternative coordination mechanism, centered on sharing key pieces of information throughout the process of determining a solution to a coupled system is presented. Specifically, the focus is on (1) establishing and assessing collaborative design spaces, (2) identifying and exploring regions of acceptable performance, and (3) preserving stakeholder dominion over design sub-system resolution throughout the duration of a given design process. The fundamental goal is to establish a consistent framework for agile collaboration that more accurately represents the mechanics underlying product development and supports interacting stakeholders in achieving their respective objectives in light of system level priorities. This aim is accomplished via improved resource management and design space exploration, augmented awareness of system level implications emanating from sub-system decisions, and increased modularity of decentralized design processes. Stakeholder synergy in design processes is enhanced via stakeholder focalization, based on the systematic communication of decision-critical information content.

Recent years have witnessed the emergence of microprocessors that are embedded within a plethora of devices used in everyday life. Embedded architectures are customized through a meticulous and time consuming design process to satisfy stringent constraints with respect to performance, area, power, and cost. In embedded systems, the cost of the memory hierarchy limits its ability to play as central a role. This is due to stringent constraints that fundamentally limit the physical size and complexity of the memory system. Ultimately, application developers and system engineers are charged with the heavy burden of reducing the memory requirements of an application. This thesis offers the intriguing possibility that compilers can play a significant role in the automatic design space exploration and optimization of embedded memory systems. This insight is founded upon a new analytical model and novel compiler optimizations that are specifically designed to increase the synergy between the processor and the memory system. The analytical models serve to characterize intrinsic program properties, quantify the impact of compiler optimizations on the memory systems, and provide deep insight into the trade-offs that affect memory system design.

Bildverarbeitungsanwendungen stellen besondere Ansprüche an das ausführende Rechensystem. Einerseits ist eine hohe Rechenleistung erforderlich. Andererseits ist eine hohe Flexibilität von Vorteil, da die Entwicklung tendentiell ein experimenteller und interaktiver Prozess ist. Für neue Anwendungen tendieren Entwickler dazu, eine Rechenarchitektur zu wählen, die sie gut kennen, anstatt eine Architektur einzusetzen, die am besten zur Anwendung passt. Bildverarbeitungsalgorithmen sind inhärent parallel, doch herkömmliche bildverarbeitende eingebettete Systeme basieren meist auf sequentiell arbeitenden Prozessoren. Im Gegensatz zu dieser "Unstimmigkeit" können hocheffiziente Systeme aus einer gezielten Synergie aus Software- und Hardwarekomponenten aufgebaut werden. Die Konstruktion solcher System ist jedoch komplex und viele Lösungen, wie zum Beispiel grobgranulare Architekturen oder anwendungsspezifische Programmiersprachen, sind oft zu akademisch für einen Einsatz in der Wirtschaft. Die vorliegende Arbeit soll ein Beitrag dazu leisten, die Komplexität von Hardware-Software-Systemen zu reduzieren und damit die Entwicklung hochperformanter on-Chip-Systeme im Bereich Bildverarbeitung zu vereinfachen und wirtschaftlicher zu machen. Dabei wurde Wert darauf gelegt, den Aufwand für Einarbeitung, Entwicklung als auch Erweiterungen gering zu halten. Es wurde ein Entwurfsfluss konzipiert und umgesetzt, welcher es dem Softwareentwickler ermöglicht, Berechnungen durch Hardwarekomponenten zu beschleunigen und das zu Grunde liegende eingebettete System komplett zu prototypisieren. Hierbei werden komplexe Bildverarbeitungsanwendungen betrachtet, welche ein Betriebssystem erfordern, wie zum Beispiel verteilte Kamerasensornetzwerke. Die eingesetzte Software basiert auf Linux und der Bildverarbeitungsbibliothek OpenCV. Die Verteilung der Berechnungen auf Software- und Hardwarekomponenten und die daraus resultierende Ablaufplanung und Generierung der Rechenarchitektur erfolgt automatisch. Mittels einer auf der Antwortmengenprogrammierung basierten Entwurfsraumexploration ergeben sich Vorteile bei der Modellierung und Erweiterung. Die Systemsoftware wird mit OpenEmbedded/Bitbake synthetisiert und die erzeugten on-Chip-Architekturen auf FPGAs realisiert. / Image processing applications have special requirements to the executing computational system. On the one hand a high computational power is necessary. On the other hand a high flexibility is an advantage because the development tends to be an experimental and interactive process. For new applications the developer tend to choose a computational architecture which they know well instead of using that one which fits best to the application. Image processing algorithms are inherently parallel while common image processing systems are mostly based on sequentially operating processors. In contrast to this "mismatch", highly efficient systems can be setup of a directed synergy of software and hardware components. However, the construction of such systems is complex and lots of solutions, like gross-grained architectures or application specific programming languages, are often too academic for the usage in commerce. The present work should contribute to reduce the complexity of hardware-software-systems and thus increase the economy of and simplify the development of high-performance on-chip systems in the domain of image processing. In doing so, a value was set on keeping the effort low on making familiar to the topic, on development and also extensions. A design flow was developed and implemented which allows the software developer to accelerate calculations with hardware components and to prototype the whole embedded system. Here complex image processing systems, like distributed camera sensor networks, are examined which need an operating system. The used software is based upon Linux and the image processing library OpenCV. The distribution of the calculations to software and hardware components and the resulting scheduling and generation of architectures is done automatically. The design space exploration is based on answer set programming which involves advantages for modelling in terms of simplicity and extensions. The software is synthesized with the help of OpenEmbedded/Bitbake and the generated on-chip architectures are implemented on FPGAs.