Advanced digital signal processing systems require specialized high-performance embedded computer architectures. The term high-performance translates to large amounts of data and computations per time unit. The term embedded further implies requirements on physical size and power efficiency. Thus the requirements are of both functional and non-functional nature. This thesis addresses the development of high-performance digital signal processing systems relying on manycore technology. We propose building two-level hierarchical computer architectures for this domain of applications. Further, we outline a tool flow based on methods and analysis techniques for automated, multi-objective mapping of such applications on distributed memory manycore processors. In particular, the focus is put on how to provide a means for tunable strategies for mapping of task graphs on array structured distributed memory manycores, with respect to given application constraints. We argue for code mapping strategies based on predicted execution performance, which can be used in an auto-tuning feedback loop or to guide manual tuning directed by the programmer. Automated parallelization, optimisation and mapping to a manycore processor benefits from the use of a concurrent programming model as the starting point. Such a model allows the programmer to express different types and granularities of parallelism as well as computation characteristics of importance in the addressed class of applications. The programming model should also abstract away machine dependent hardware details. The analytical study of WCDMA baseband processing in radio base stations, presented in this thesis, suggests dataflow models as a good match to the characteristics of the application and as execution model abstracting computations on a manycore. Construction of portable tools further requires a manycore machine model and an intermediate representation. The models are needed in order to decouple algorithms, used to transform and map application software, from hardware. We propose a manycore machine model that captures common hardware resources, as well as resource dependent performance metrics for parallel computation and communication. Further, we have developed a multifunctional intermediate representation, which can be used as source for code generation and for dynamic execution analysis. Finally, we demonstrate how we can dynamically analyse execution using abstract interpretation on the intermediate representation. It is shown that the performance predictions can be used to accurately rank different mappings by best throughput or shortest end-to-end computation latency.

No description available.

[pt] Este trabalho tem como objetivo propor uma metaheurística Iterated Local Search para minimizar o tempo de término ponderado de jobs em problemas de escalonamento de máquinas idênticas paralelas. O objetivo secundário do trabalho é propor uma solução prática para um problema real da companhia estudada em questão. A motivação para o trabalho consiste em uma aplicação prática na indústria de óleo e gás, onde os navios PLSV realizam operações em poços de forma ordenada e visando a antecipação dos poços de petróleo mais produtivos. As características do problema, tais quais: elegibilidade entre navio e operações, tempos de setup relativos à família de atividades, associações entre operações e poços e setups que dependem da chegada de material se adequam a modelagem baseada em escalonamento de máquinas paralelas idênticas. No trabalho uma introdução à respeito do tema é apresentada, em seguida é feita uma revisão da literatura sobre problemas de máquinas paralelas idênticas, a formulação matemática com a descrição do problema é apresentada, a metodologia contemplando representação da solução, heuristica construtiva, vizinhanças exploradas, busca local e Iterated Local Search é exposta, por fim são apresentados os resultados do método e as conclusões sobre o trabalho. / [en] This work objective is to propose an Iterated Local Search metaheuristic to minimize the weighted completion time of jobs on identical parallel machines scheduling problems. The secondary objective of this work is to propose a practical solution to the real problem of the studied company. The motivation of this work consists on a practical application in the Oil and Gas industry, where the PLSV vessels perform ordered operations in a set of wells aiming to maximize the oil production. The characteristics of the problem such as: eligibility between vessels and operations, setup times related to the family of activities, association between operations and wells and setup times depending on the material arrival fit well the identical parallel machine schedule modelling. In this work, an introduction about the theme is presented, followed by a literature review on identical parallel machine scheduling problems, the mathematical formulation with the problem description is presented, the methodology, including the solution representation, constructive heuristic, neighborhood structures, local search and Iterated Local Search is exposed, at last, the method results and conclusions of the work are summarized.

No description available.

[pt] A dissertação aborda um problema real de reprogramação de uma frota de embarcações do tipo PLSV (Pipe Laying Support Vessel), responsáveis pelas interligações de poços petrolíferos submarinos. O cronograma de curto prazo dessas embarcações está sujeito à inúmeras incertezas inerentes às operações realizadas, acarretando em ociosidade nas embarcações ou postergações na produção de petróleo, que podem resultar em prejuízo de milhões de reais. Uma metaheurística ILS (Iterated Local Search) é proposta para atender a frequente demanda por reprogramações dos PLSVs. O método é composto de uma fase inicial de viabilização, para tratar potenciais inconsistências nas programações. Na sequência, iterativamente, são realizadas perturbações na solução por meio de movimentos de swap e aplicada uma busca local baseada na vizinhança insert, a fim de fugir de ótimos locais e encontrar soluções que aprimorem o cronograma. Foram feitos experimentos com diferentes parâmetros e critérios do ILS, sendo definidas duas abordagens aplicadas a dez instâncias oriundas de uma programação real de PLSVs. A partir de uma função de avaliação, capaz de medir o impacto operacional na programação, o ILS proporcionou uma melhoria média nos cronogramas acima de 91 por cento, quando comparados aos cronogramas originais. As soluções foram obtidas em um tempo computacional médio de 30 minutos, aderente ao processo da companhia. Em função dos resultados alcançados, o método provou ser uma boa base para uma ferramenta de apoio à decisão para a reprogramação dos PLSVs. / [en] This dissertation addresses a real-life rescheduling problem of a Pipe Laying Support Vessels (PLSVs) fleet, in charge of subsea oil wells interconnections. The short-term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production, which may lead to losses of millions of Brazilian Reais. A method based on the ILS (Iterated Local Search) metaheuristic is proposed to meet the frequent demand of PLSVs rescheduling. The first step of this method aims to find a feasible initial solution from an incoming schedule with potencial inconsistencies. The following steps consists in, iteratively, performing a perturbation on a solution through swap movements and applying a local search based on the insertion neighborhood, in order to escape from local optimal and find better solutions. Extensive preliminary experiments were conducted considering different ILS parameters setups. The two most performing setups were selected and applied to ten instances of a real PLSV schedule. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91 percent in schedules when compared to the original planning. These solutions were obtained in an average computational time of 30 minutes, which fits in the company process. The obtained results showed that the proposed method might be a basis for a decision support tool for the PLSVs rescheduling problem.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.

[pt] A programação de máquinas é um processo de tomada de decisão que desempenha um importante papel na maioria das indústrias de manufatura e serviços. Esta dissertação aborda o problema de programação de máquinas paralelas idênticas sem preempção, considerando características da programação de data de liberação e data limite para execução do início das tarefas, restrição de precedência entre pares de tarefas, elegibilidade e disponibilidade de máquinas. Para resolver este problema, uma formulação de programação linear inteira mista é proposta. O novo modelo, chamado de bucket-indexed (BI), particiona o horizonte de planejamento em períodos de tempos de mesmo tamanho (buckets). O tamanho dos buckets é um par âmetro que varia de acordo com a instância e influencia o porte do modelo, podendo assumir valores entre 1 e o menor tempo de processamento das tarefas. Quanto maior o tamanho do bucket, menor é o número de buckets criados e, consequentemente, menor o porte do modelo. A formulação proposta é testada em instâncias reais referentes ao problema de programação de sondas para construção de poços de petróleo de uma indústria brasileira de óleo e gás. A fim de avaliar os resultados obtidos pela formulação BI, a formulação clássica time-indexed (TI) foi também implementada para comparação dos tempos computacionais e qualidade da solução. Os resultados da formulação proposta apontam um melhor desempenho nas instâncias testadas, reduzindo o tempo computacional em todos os casos e resolvendo instâncias de grande porte não resolvidas pela formulação TI. / [en] Machine scheduling is a decision-making process that plays an important role in most manufacturing and service industries. This dissertation tackles a nonpreemptive identical parallel machine scheduling problem, considering release dates, deadlines, precedences, eligibility, and machine availability constraints. To solve this problem, a mixed-integer linear programming formulation is proposed. The new model, called bucketindexed, partitions the planning horizon in periods of equal length (buckets). The bucket size is a parameter which varies according to instances and influences the model size, assuming values between 1 and the shortest processing time of jobs. The larger the bucket size, the smaller is the number of buckets created and, consequently, the smaller the model size. The proposed formulation is tested in real instances of the rig scheduling problem for a Brazilian oil and gas industry. To evaluate the results obtained by the BI formulation, the classical time-indexed (TI) formulation was also implemented for comparison of computational times and solution quality. The results of the proposed formulation highlight a better performance in all the tested instances, reducing computational time in all cases and solving large instances unsolvable by the TI formulation.

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.

Cette thèse est consacrée à l'etude de l'implantation du parallélisme OU en Prolog sur des machines sans mémoire commune. Nous présentons le modèle multi-séquentiel OU Opera, implanté par compilation (machine abstraite de Warren - WAM), en préservant la sémantique de Prolog. Les deux problèmes principaux d'un tel système, la gestion de contextes multiples et l'ordonnancement, sont détaillés. La gestion des contextes multiples s'effectue par copie incrémentale, en parallèle au calcul. Pour que ceci reste efficace et cohérent, le traitement des variables conditionnelles a été inclus dans la WAM. Notre méthode introduit une nouvelle pile pour ces variables dont l'initialisation, la déliaison été modifiées. Le coût des opérations séquentielles de la WAM est constant et indépendent du nombre de processus. Nous proposons encore une méthode simple et efficace pour la réalisation de la coupure. Un prototype Opera a été implanté sur un réseau de Transputers. Dans ce prototype, l'ordonnancement a été résolu par une méthode basée sur des heuristiques d'évaluation de charge. Cet ordonnancement est mis en ocuvre par une architecture centralisée où un processus ordonnanceur unique régule la charge des autres processus. L'ordonnanceur utilise une répresentation approximative de l'état du système. La partie séquentielle du prototype Opera constitue l'un des systèmes Prolog les plus efficaces existant actuellement sur le Transputer. Ses gains de performance en parallèle sont aussi effectifs. / This thesis is dedicated to the study of the implementation of Or-parallel Prolog over distributed memory machines. The Opera Or multi-sequential model is presented. It uses compiling techniques (Warren Abstract Machine) and preserves the Prolog semantics. Multienvironment management and scheduling, the two major problems of Opera, are described. Multi-environment management is realized by incremental copying, in parallel to the computation. The treatment of conditional variables is included in the WAM, in order to allow an efficient and coherent cooperation. Our method introduces a new pile for these variables, initialization, binding and unbinding of which are adapted. The cost of WAM sequential operations is constant and independent of the number of processes. We also propose a simple and efficient method for implementing cut in parallel. An Opera prototype has been implemented over a Transputer array. In the current prototype, scheduling is resolved by heuristics of load evaluation. This scheduling is centralized, a unique process balancing the load of the other Prolog workers, and using an approximate representation of the state of the system. The Opera prototype is one of the most efficient Prolog implementations on the Transputer, and reaches effective speed-ups in parallel.

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.