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.

Neste trabalho, é apresentado um novo modelo de reconstrução tridimensional (3D) para amostras agrícolas com filtragem de Wiener em processamento paralelo, o qual é obtido a partir de reconstruções tomográficas bidimensionais (2D). No desenvolvimento, foram modelados algoritmos paralelos de retroprojeção filtrada e reconstrução tridimensional, baseando-se na inserção de um conjunto de planos virtuais entre pares de planos reais obtidos em ensaios tomográficos de raios X na faixa de energia de 56 keV a 662 keV. No modelo, os planos virtuais gerados em algoritmo paralelo são implementados com base na técnica de interpolação por B-Spline-Wavelet. Para validação do modelo desenvolvido, foi utilizada uma plataforma paralela composta de 4 processadores DSP, a qual possibilitou a troca de dados entre os processadores DSP e o envio de informações para o host, um computador desktop com processador Pentium III operando em 800 MHz. A extração de medidas de eficiência, de ganho e de precisão dos algoritmos paralelos foi realizada com base em um conjunto de amostras agrícolas (solo, vidro e madeiras) e de phantoms de calibração. Nessa avaliação, observou-se que o algoritmo de reconstrução 2D, utilizado como base para o algoritmo de reconstrução 3D, possibilitou uma alta eficiência para imagens de maior resolução, atingindo um pico de 92% de eficiência na resolução de 181X181 pixels. O algoritmo paralelo de reconstrução 3D foi analisado para um conjunto de amostras, sob diferentes configurações de planos reais e virtuais, organizados de forma a possibilitarem a avaliação do impacto causado pelo aumento da granularidade da comunicação e da carga de trabalho. Um melhor desempenho, com ganho médio igual a 3,4, foi obtido na reconstrução de objetos que demandaram o cálculo de um maior número de planos. Também, buscou-se conhecer a adaptabilidade do modelo para uso em arquitetura convencional, sendo que neste caso o uso de MPI permitiu a comunicação entre as tarefas projetadas em cada algoritmo paralelo. Adicionamente, foram incluídas ferramentas de visualização 2D e 3D para que usuários possam analisar as imagens e as características das amostras agrícolas em ambiente tridimensional. Os resultados obtidos indicam que o modelo de reconstrução 3D paralela trouxe contribuições originais para a área de tomografia agrícola aplicada à física de solos, bem como para a criação de ferramentas que viabilizem explorar recursos computacionais disponíveis em arquiteturas paralelas que demandem elevada capacidade de processamento. / This work presents a new method for three dimensional (3D) image reconstruction dedicated to the investigation in soil physics by means of X-ray tomography which is obtained using two-dimensional (2D) tomographic image reconstructed slices. The conception of the 3D model for reconstruction and visualization was based on the filtered back projection algorithm, operating under parallel environment together the insertion of virtual planes between pairs of real planes obtained by X-Ray tomography under energies varying from 56 keV to 662 keV. In this model, the virtual planes were generated by interpolation with the use of B-Spline-Wavelets. The evaluation of the 3D reconstruction model was established by using a set of agricultural samples (i.e., soil, glass, wood and calibration phantoms) having different configuration for the planes. Such configuration was based on setting not only the sizes and the number of the real but also the virtual planes in the volume. This procedure allows the impact measurements as a function of the increasing in workload and the communication granularity. To validate the reconstruction model, a dedicated parallel architecture composed of 4 DSP processors was used. This board enables data exchange between DSP processors and communication with host computer. A measurement of efficiency with a speed up equal to 3.4 was obtained using the same set of samples and a better performance was observed with a higher number of planes. Also, to understand about its adaptability, the model was implemented in conventional architecture, using MPI library to enable communication between designed tasks. Additionally, 2D and 3D visualization tools based on Vizualization ToolKit were included in order to help users to analyze images and their characteristics. Results have shown that the 3D parallel model reconstruction brought original contributions for the soil science diagnosis by X-Ray tomography, as well as to explore the available computational resources in parallel architectures, which demands great processing capacity.

Este trabalho aborda a utilização de computadores paralelos no processamento de problemas de análise estrutural. Inicialmente apresentam-se peculiaridades dos computadores de arquitetura paralela e do desenvolvimento de programas voltados a tais máquinas. Discute-se então a paralelização de duas etapas típicas da aplicação do método dos elementos finitos em análise estrutural: a montagem da matriz de rigidez da estrutura e a resolução do sistema de equações lineares. São propostos algoritmos alternativos para ambas as etapas. Finalmente é abordada a implementação de um programa de análise não linear de treliças tridimensionais com várias etapas paralelas. / This work is about the use of parallel computers on solving structural analysis problems. Initially, the particular features of parallel computers and the related software development are presented. The parallelization of two typical steps of finite method element are discussed: the assembly of global stiffness matrix and the solution of the linear system of equations. Alternative algorithms are proposed for both steps. Finally, the implementation of a program for nonlinear space truss analysis with several parallel steps is presented.

Orientador: Marconi Kolm Madrid / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T03:57:30Z (GMT). No. of bitstreams: 1 Castro_EbervalOliveira_M.pdf: 4698124 bytes, checksum: 0a0a438cbad7212bdba90f2c96875871 (MD5) Previous issue date: 2007 / Resumo: A solução de modelos dinâmicos de robôs em tempo real é um dos principais desafios da robótica. Este trabalho propõe um multiprocessador de quatro núcleos fortemente acoplados, o SMM-4 (Sistema Multiprocessado Monolítico), consistindo de uma arquitetura de processamento paralelo monolítica sintetizada em FPGA para aplicações em controle de sistemas robóticos. Uma análise quantitativa e qualitativa é realizada em contraste a sistemas uniprocessadores, evidenciando os ganhos obtidos através desta abordagem em FPGA. O SMM-4 foi desenvolvido no Laboratório de Sistemas Modulares Robóticos (LSMR/Unicamp) como uma das alternativas para o cálculo das equações dos modelos de robôs em tempo real / Abstract: The solution of robots¿ dynamic models in real-time is one of major challenges of the robotics. This work presents a strongly coupled quad-core multiprocessor ¿ the MMS-4 (Monolithic Multiprocessor System) ¿ consisting of a monolithical parallel processing architecture synthesized on FPGA for applications on robotic control systems. A quantitative and qualitative analysis is performed in contrast with uniprocessor systems for the purpose of evince the benefits obtained choosing this approach in FPGA. The MMS-4 was developed at Robotic Modular Systems Laboratory (LSMR/Unicamp) as an alternative to calculate the equations systems of robots¿ models on real-time / Mestrado / Automação / Mestre em Engenharia Elétrica

Weather forecasting models are computationally intensive applications and traditionally they are executed in parallel machines. However, some issues prevent these models from fully exploiting the available computing power. One of such issues is load imbalance, i.e., the uneven distribution of load across the processors of the parallel machine. Since weather models are typically synchronous applications, that is, all tasks synchronize at every time-step, the execution time is determined by the slowest task. The causes of such imbalance are either static (e.g. topography) or dynamic (e.g. shortwave radiation, moving thunderstorms). Various techniques, often embedded in the application’s source code, have been used to address both sources. However, these techniques are inflexible and hard to use in legacy codes. In this thesis, we explore the concept of processor virtualization for dynamically balancing the load in weather models. This means that the domain is over-decomposed in more tasks than the available processors. Assuming that many tasks can be safely executed in a single processor, each processor is put in charge of a set of tasks. In addition, the system can migrate some of them from overloaded processors to underloaded ones when it detects load imbalance. This approach has the advantage of decoupling the application from the load balancing strategy. Our objective is to show that processor virtualization can be applied to weather models as long as an appropriate strategy for migrations is used. Our proposal takes into account the communication pattern of the application in addition to the load of each processor. In this text, we present the techniques used to minimize the amount of change needed in order to apply processor virtualization to a real-world application. Furthermore, we analyze the effects caused by the frequency at which the load balancer is invoked and a threshold that activates rebalancing. We propose an automatic strategy to find an optimal threshold to trigger load balancing. These strategies are centralized and work well for moderately large machines. For larger machines, we present a fully distributed algorithm and analyze its performance. As a study case, we demonstrate the effectiveness of our approach for dynamically balancing the load in Brams, a mesoscale weather forecasting model based on MPI parallelization. We choose this model because it presents a considerable load imbalance caused by localized thunderstorms. In addition, we analyze how other effects of processor virtualization can improve performance.

As threads de aplicações paralelas cooperam a fim de cumprir suas tarefas, dessa forma, comunicação é realizada entre elas. A latência de comunicação entre os núcleos em arquiteturas multiprocessadas diferem dependendo da hierarquia de memória e das interconexões. Com o aumento do número de núcleos por chip e número de threads por núcleo, esta diferença entre as latências de comunicação está aumentando. Portanto, é importante mapear as threads de aplicações paralelas levando em conta a comunicação entre elas. Em aplicações paralelas baseadas no paradigma de memória compartilhada, a comunicação é implícita e ocorre através de acessos à variáveis compartilhadas, o que torna difícil a descoberta do padrão de comunicação entre as threads. Mecanismos tradicionais usam simulação para monitorar os acessos à memória realizados pela aplicação, requerendo modificações no código fonte e aumentando drasticamente a sobrecarga. Nesta dissertação de mestrado, são introduzidos dois mecanismos inovadores com uma baixa sobrecarga para se detectar o padrão de comunicação entre threads. O primeiro mecanismo faz uso de informações sobre linhas compartilhadas de caches providas por protocolos de coerência de cache. O segundo mecanismo utiliza a Translation Lookaside Buffer (TLB) para detectar quais páginas de memória cada núcleo está acessando. Ambos os mecanismos dependem totalmente do hardware, o que torna o mapeamento de threads transparente aos programadores e permite que ele seja realizado dinamicamente pelo sistema operacional. Além disto, nenhuma tarefa de alta sobrecarga, como simulação, é requerida. As propostas foram avaliadas com o NAS Parallel Benchmarks (NPB), obtendo representações precisas dos padrões de comunicação. Mapeamentos para as threads foram gerados utilizando os padrões de comunicação descobertos e um algoritmo de mapeamento. O problema do mapeamento é NP-Difícil. Portanto, de forma a se atingir uma complexidade polinomial, o algoritmo empregado é heurístico, baseado no algoritmo de emparelhamento de grafos de Edmonds. Executando as aplicações com o mapeamento resultou em um ganho de desempenho de até 15; 3%. O número de faltas na cache, invalidações em linhas de cache e transações de espionagem foram reduzidos em até 31; 9%, 41% e 65; 4%, respectivamente. / The threads of parallel applications cooperate in order to fulfill their tasks, thereby communication is performed among themselves. The communication latency between the cores in a multiprocessor architecture differs depending on the memory hierarchy and the interconnections. With the increase in the number of cores per chip and the number of threads per core, this difference between the communication latencies is increasing. Therefore, it is important to map the threads of parallel applications taking into account the communication between them. In parallel applications based on the shared memory paradigm, the communication is implicit and occurs through accesses to shared variables, which makes difficult to detect the communication pattern between the threads. Traditional approaches use simulation to monitor the memory accesses performed by the application, requiring modifications to the source code and drastically increasing the overhead. In this master thesis, we introduce two novel light-weight mechanisms to find the communication pattern of threads. The first mechanism makes use of the information about shared cache lines provided by cache coherence protocols. The second mechanism makes use of the Translation Lookaside Buffer (TLB) to detect which memory pages each core is accessing. Both our mechanisms rely entirely on hardware features, which makes the thread mapping transparent to the programmer and allows it to be performed dynamically by the operating system. Moreover, no time consuming task, such as simulation, is required. We evaluated our mechanisms with the NAS Parallel Benchmarks (NPB) and obtained accurate representations of the communication patterns. We generated thread mappings from the detected communication patterns using a mapping algorithm. Mapping is a NP-Hard problem. Therefore, in order to achieve a polynomial complexity, we designed a heuristic method based on the Edmonds graph matching algorithm. Running the applications with these mappings resulted in performance improvements of up to 15.3% compared to the original scheduler of the operating system. The number of cache misses, cache line invalidations and snoop transactions were reduced by up to 31.9%, 41% and 65.4%, respectively.

As próximas gerações de processadores many-core exigem que novas abordagens no projeto de arquitetura de processadores sejam propostas. Neste novo contexto, as redes de comunicação intra-chip são importantes para garantir o desempenho dos programas. Soluções tradicionais de interconexão possuem limites físicos que comprometem a escalabilidade e o desempenho no processamento de aplicações paralelas de diversos tipos. A alternativa apontada pelo estado da arte é a Network-on-Chip (NoC) composta por roteadores e outros elementos de rede capazes de prover comunicação escalável e de alto desempenho. No entanto, as cargas de trabalho geram padrões de comunicação diferentes que podem influenciar no desempenho da rede. Existem pesquisas que abordam metodologias de projeto dedicado de NoCs em função de domínios de aplicações específicos. Apesar de uma NoC dedicada possuir um alto desempenho, cargas de trabalho paralelas geram padrões de comunicação coletiva que mudam dinamicamente. Com o objetivo de aumentar a flexibilidade de redes-em-chip, trabalhos correlatos utilizam conceitos de computação reconfigurável para aumentar a capacidade da arquitetura da NoC se adaptar em função de padrões de comunicação. Alguns trabalhos focam na programação de FPGAs e outros em ASICs polimórficos. O objetivo desta tese é propor uma arquitetura de Network-on-Chip que suporte múltiplos clusters de núcleos de processamento através de roteadores programáveis e de topologias reconfiguráveis. Cada roteador é composto por uma chave crossbar reconfigurável capaz de implementar topologias dinamicamente através do uso de um segundo nível de reconfiguração. Os roteadores possuem processadores de rede que aumentam a flexibilidade e a capacidade da NoC se adaptar ao padrão de comunicação através de programas que monitoram e gerenciam a rede. Portanto, a contribuição da tese é a Arquitetura de NoC Programável Baseada em Múltiplos Clusters de Cores. Os resultados baseados em modelos analíticos e de simulação, e cargas de trabalho artificiais e naturais, mostram que a arquitetura da NoC possui um alto desempenho e vazão de pacotes, proporcionados pela adaptação de topologias e redução da influência da rede na comunicação. A ocupação em FPGA mostra que os roteadores programáveis possuem tamanho similares a NoCs com arquiteturas tradicionais para gerenciamento de mesma quantidade de núcleos. A menor utilização de buffers de entrada resulta em uma melhor eficiência no consumo de potência e energia. Portanto, através dos modelos de projeto e avaliação foi possível verificar através dos resultados que a arquitetura da MCNoC é uma alternativa para suportar padrões de comunicações coletivas. / For the next generation of many-core processors, new design methodologies must be proposed. In this context, on-chip interconnections are important to assure the program performance. Traditional approaches of interconnections have physical constraints that reduce the scalability and performance to process parallel applications. The state-of-theart points out to the Network-on-Chip (NoC), which consists of routers and other network devices capable of increasing the communication scalability and performance. However, workloads produce different types of communication patterns, which can influence the network performance. There are research works that explore applicationspecific NoC design to response the demand on specific workloads. Although a dedicated NoC has a high performance, parallel workloads have different collective communication patterns. In order to increase the flexibility of NoCs, related works use concepts of reconfigurable computing to add architecture adaptability to support dynamic communication patterns. Some works focus on FPGA-based reconfiguration and others on polymorphic ASICs. The goal of this thesis is to propose an alternative Programmable Multi-Cluster NoC architecture. Each router consists of a reconfigurable crossbar switch capable of implementing dynamic topologies through a second reconfiguration level. The routers have network processors that increase the flexibility and the NoC adaptability through management programs in order to support different workloads. Therefore, the contribution of this thesis is the following: A Programmable Multi-Cluster NoC (MCNoC) architecture. Based on analytical and simulation models, and artificial and natural workloads, results show the high performance and throughput for the proposed NoC architecture, due to the adaptable topologies and low network latency impact. Results based on FPGA shows a similar component utilization considering the proposed programmable NoC relative to conventional NoC architectures for the same number of processing cores. The low utilization of input buffers improves the efficiency of power and energy consumption. Therefore, through design and evaluation models, the NoC proposal was verified and the results point out the MCNoC as an alternative architecture to support collective communication patterns.

Procedimentos de teste para dispositivos eletrônicos tem sido construídos de forma a lidar com problemas, tais como geração de padrões de teste, cobertura de falhas e outros parâmetros tais como custo e tempo. Com o surgimento dos circuitos VLSI (Very Large Scale Integration), tais como os processadores, os problemas do teste tem aumentado. Com relação aos processadores, sua complexidade é um convite para o uso de procedimentos de teste funcionais, ignorando a estrutura física dos circuitos. Adicionalmente, informações sobre a estrutura do processador são geralmente desconhecidas por parte do usuário. No nível funcional, um processador é tratado como um sistema composto por blocos funcionais, cuja descrição pode ser obtida no manual do usuário. Cada bloco e caracterizado pela sua função, como por exemplo, a unidade lógica e aritmética, registradores, memória, etc... Testar o processador consiste em exercitar cada bloco com padrões de teste determinados. A utilização do processador transputer em situações onde se faz necessário um certo nível de confiabilidade depende da utilização de técnicas para detecção on-line. No presente trabalho é proposto um procedimento para o teste funcional do transputer. O teste funcional aqui proposto permite detecção de falhas on-line, em um contexto de aplicação periódica (pela suspensão temporária mas sem alteração do contexto da aplicação do usuário), com baixa degradação no desempenho global do sistema. Hipóteses e procedimentos relacionados a fabricação de circuitos não são considerados. Para possibilitar o uso de técnicas de teste convencionais, o transputer IMS T800 é particionado em blocos funcionais e um modelo para o teste, baseado na organização desse componente, e proposto. Este modelo é apoiado pela similaridade desse processador com um sistema microprocessado. Após o particionamento cada bloco funcional pode ser testado em separado; para os blocos que possuem organização como a de microprocessadores convencionais (tais como parte da CPU e a FPU), utiliza-se como base o método proposto por Robach and Saucier [ROB80]. De acordo com este método de teste funcional, as instruções do processador são modeladas por intermédio de grafos, que formam a base para definição de um conjunto mínimo de instruções. A execução desse conjunto exercita todos os elementos pertencentes ao respectivo bloco funcional do transputer. Entretanto, o procedimento proposto não é uma aplicação direta da metodologia citada, devido a características particulares do transputer, especialmente no que diz respeito ao paralelismo de operações, e sua estrutura de blocos internos. Com relação aos testes on-line, a utilização de um conjunto de instruções reduzido possibilita a realização de um teste rápido, reduzindo perdas de desempenho. Para os blocos restantes, de acordo com suas características, são construídos procedimentos de teste específicos. A freqüência de execução é ajustável para cada bloco. Dependendo das exigências da aplicação, alguns procedimentos podem ser omitidos, reduzindo a carga provocada pelo procedimento de teste no desempenho do sistema. A validação do procedimento de teste é realizada de duas maneiras: injeção de falhas, para verificar a capacidade de detecção: e avaliação de desempenho, para identificar o nível de degradação causado pela utilização do procedimento de teste em um sistema genérico. Apesar desse trabalho ter sido desenvolvido com base na estrutura da maquina TNODE [TEL91] e na abordagem de teste global descrita em [NUN93b], o procedimento de teste proposto pode ser utilizado em qualquer sistema composto por transputers, cujos parâmetros de aplicação se enquadrem nos requisitos usados neste trabalho. / Test procedures for electronic devices have been planned in order to deal with problems as test pattern generation, fault coverage and other parameters as cost and time. With the advent of very large scale integration (VLSI) circuits, such as the microprocessors, the test problems have arised. Concerning processors, their complexity is an invitation to the use of functional test procedures, ignoring the physical structure of the circuit. Further, structural information about the processor is, in general, unknown by users. In a functional level, a processor is seen as a system made up of functional blocks, whose description can be obtained from the user's manual. Each block is characterized by its function, as arithmetic and logic unit, registers, memory, etc... Testing the processor consists of exercising every block with specified test patterns. The use of the transputer processor in situations where reliability is needed depends on the use of on-line detection techniques. In this work, a functional test procedure for the transputer is proposed. The functional test here proposed intends to allow on-line fault detection, in a context of periodical application, with low degradation in global system performance. Hypotheses and procedures related to the fabrication process are not concerned. In order to make possible the use of conventional test techniques, the IMS T800 transputer is partitioned in functional blocks and a test model, based on the architecture of this component, is proposed. This model is supported by the similarity of this processor with a microprocessor system. Then each functional block may be tested in separate; for the blocks that have conventional microprocessor architecture (as part of the CPU and the FPU), the method proposed by Robach and Saucier [ROB80] is used. According to this functional test method, processor instructions are modeled by means of graphs which are the basis to find a minimal instruction set. The execution of this set exercises all elements that belong to the respective functional block of the transputer. Therefore, it is not a straight application of that methodology due to particular characteristics of the transputer, specially concerning the parallelism of operation and its internal blocks structure. Concerning on-line tests, the use of a reduced instruction set allows a fast test realization, reducing the overhead over system performance. For the remainder blocks, specific test procedures are built according to their features. The frequency of execution is adjustable to each block. Depending on the application constraints, some procedures may be omitted, reducing the overhead produced by the test procedure over the system performance. The validation of the test procedure may be done by means of: fault injection, to verify the faults coverage parameters; and performance evaluation, to identify degradation level caused by the inclusion of test procedure in a generic system. Although this work has been developed with basis in the structure of the T-NODE machine [TEL91] and the global test approach described in [NUN93b], it can be used in other transputer systems whose application parameters are similar to those here used.

A exploração do paralelismo na programação em lógica e considerada uma alternativa para simplificação da programação de maquinas paralelas e para aumento do desempenho de programas em lógica. Desta forma, a integração da programação em lógica e sistemas paralelos tornou-se nos últimos anos um centro de atenções da comunidade ciêntifica. Dentre os problemas que devem ser solucionados para exploração adequada do paralelismo, encontra-se a analise de granulosidade. A análise de granulosidade determina o tamanho dos grãos, ou seja, a complexidade dos módulos que devendo ser executados seqüencialmente num único processador. Basicamente, esta analise consiste de uma refinada identificação dos grãos, visando a máxima eficiência na exploração do paralelismo. Neste sentido, devem ser realizadas considerações sobre dependências, complexidade dos grãos e custos envolvidos na paralelização. Recentemente, a analise de granulosidade na programação em lógica tem recebido atenção especial por parte dos pesquisadores. Os grãos podem ser identificados pelo programador através de primitivas de programação ou podem ser detectados automaticamente pelo sistema paralelo. Na programação em lógica, a exploração automática do paralelismo é estimulada, devido ao paralelismo implícito existente na avaliação das expressões lógicas. Além disso, a programação em lógica permite uma clara distinção entre a semântica e o controle da linguagem, proporcionando uma abordagem distinta entre a descrição do problema e o caminho para obtenção das soluções. A detecção automática do paralelismo permite o aproveitamento de programas já existentes, alem de liberar o programador do encargo de paralelizar o problema. Este trabalho dedica-se ao estudo da analise automática de granulosidade na programação em lógica. O texto propõe um modelo para geração de informações de granulosidade, denominado GRANLOG (GRanularty ANalyzer for LOGic Programming). O GRANLOG realiza uma analise estática de um programa em 16aica. Dessa analise resulta o programa granulado, ou seja, o programa original acrescido da anotação de granulosidade. Esta anotação contem diversas informações que contribuem de forma significativa com a exploração adequada do paralelismo na programação em lógica. Durante o desenvolvimento do GRANLOG foram exploradas diversas áreas de pesquisa da programação em lógica, dentre as quais destacam-se: analise de modos, analise de tipos, análise de medidas para mensuração do tamanho de termos, interpretação abstrata, analise de dependências e analise de complexidade. A integração destes t6picos torna o GRANLOG uma rica fonte de pesquisa. Além disso, a organização modular da proposta permite o aprimoramento independente de suas partes, tornando a estrutura do modelo uma base para o desenvolvimento de novos trabalhos. Além do modelo, o texto descreve a implementação de um protótipo e propõe duas aplicações para as informações de granulosidade, ou seja, auxilio a decisões de escalonamento e simulação da execução de programas. O texto apresenta ainda uma proposta para integração do GRANLOG a um modelo para execução paralela de programas em lógica, denominado OPERA. O OPERA dedica-se a exploração do paralelismo na programação em lógica e possui atualmente um protótipo para execução paralela de programas em lógica em redes de computadores. Os bons resultados obtidos com a integração OPERA-GRANLOG demonstram a relevância das informações geradas pelo modelo proposto neste trabalho. Encontra-se ainda neste texto uma proposta para inclusão do GRANLOG numa interface gráfica, denominada XOPERA. Esta interface permite a execução do protótipo OPERA e, a partir deste trabalho, gerencia também o protótipo GRANLOG. A inclusão da gerencia do GRANLOG na interface XOPERA, contribui de forma substancial para a integração OPERA-GRANLOG. / The exploitation of parallelism in logic programming is considered an alternative for simplifying the task of programming parallel machines. Also, it provides a way to increase the performance of logic programs. Because of this, integrating parallel systems with parallel programmin g has been a topic of much interest in the scientific comunity, in the last years. Among the problems that must be solved for the adequate exploitation of parallelism, there is the granularity analysis. Granularity analysis determines the size of the grains, that is, the complexity of the modules that must be sequentially executed in a single processor. Basically, this analysis consists of a refined identification of the grains, aiming the maximum efficiency in the parallelism exploitation. In this sense, considerations must be taken about dependencies, grain complexity and costs involved in the parallelizing process. Recently, many researchers have given special attention to the granularity analysis of logic programming. The grains may be identified by the programmer via programming primitives, or they may be automatically detected by the parallel system. In logic programming, the automatic exploitation of parallelism is stimulated, because of the implicit parallelism that exists in the evaluation of the logic expressions. Besides, logic programming allows a clear distinction between the semantics and the control of the language, providing a distinct approach between the problem description and the way to obtain the results. The automatic detection of parallelism permits the utilization of already written programs, also freeing the programmer from parallelizing the program by hand. This work is dedicated to the study of automatic granularity analysis in logic programming. The text proposes a model for generating granularity informations, called GRANLOG (GRanularity Analyzer for LOGic Programming). GRANLOG performs a static analysis of a logic program. From this analysis, it results a granulated program, that is, the original program increased by the granularity annotation. This annotation has several informations that contribute in a significant way to the adequate exploitation of parallelism in logic programming. During the development of GRANLOG, several research areas have been explored, namely, mode analysis, type analysis, measure analysis for measuring the size of terms, abstract interpretation, dependencies analysis and complexity analysis. The integration of these topics makes GRANLOG a good source for researchs. Besides, the modular organization proposed permits the independent improvement of its parts, making of the model structure, a base for the development of new works. Besides the model, the text describes the implementation of a prototype and proposes two applications for the granularity informations, namely, help in scheduling decisions and program execution simulation. It also presents a proposal for integrating GRANLOG to a parallel logic execution model for logic programming, called OPERA. OPERA is dedicated to the exploitation of parallelism in logic programming and, at the present time, has a prototype for parallel execution of logic programming in computer networks. The good results obtained by integrating OPERA and GRANLOG show the importance of the information generated by the model proposed in this work. There is, also, in this work, a proposal for including GRANLOG in a graphical interface, called XOPERA. This interface allows the execution of the OPERA prototype and, from now on, also manaaes the GRANLOG prototype. The inclusion of GRANLOG in the XOPERA interfaces substantially contributes to the OPERAGRANLOG intearation.

Orientador: Marco Aurelio Amaral Henriques / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T12:56:47Z (GMT). No. of bitstreams: 1 Enomoto_Cristina_M.pdf: 856279 bytes, checksum: ce524a49db0f67734e28d8458d5deb0b (MD5) Previous issue date: 2005 / Resumo: Vários sistemas de grid e computação distribuída existentes só permitem a execução de aplicações com um fluxo de execução de tarefas básico, no qual é feita a distribuição das tarefas executadas em paralelo e depois a coleta de seus resultados. Outros sistemas permitem definir uma relação de dependências entre as tarefas, formando um grafo direcionado acíclico. Porém, mesmo com este modelo de fluxo de execução não é possível executar vários tipos de aplicações que poderiam ser paralelizadas, como, por exemplo, algoritmos genéticos e de cálculo numérico que utilizam algum tipo de processamento iterativo. Nesta dissertação é proposta uma linguagem de especificação para fluxo de execução de aplicações paralelas que permite um controle de fluxo de tarefas mais flexível, viabilizando desvios condicionais e laços com iterações controladas. A linguagem é baseada na notação XML (eXtensible Markup Language), o que lhe confere características importantes tais como flexibilidade e simplicidade. Para avaliar estas e outras características da linguagem proposta, foi feita uma implementação sobre o sistema de processamento paralelo JoiN. Além de viabilizar a criação e execução de novas aplicações paralelas cujos fluxos de tarefas contêm laços e/ou desvios condicionais, a linguagem se mostrou simples de usar e não causou sobrecarga perceptível ao sistema paralelo / Abstract: Many distributed and parallel systems allow only a basic task flow, in which the parallel tasks are distributed and their results collected. In some systems the application execution flow gives support to a dependence relationship among tasks, represented by a directed acyclic graph. Even with this model it is not possible to execute in parallel some important applications as, for example, genetic algorithms. Therefore, there is a need for a new specification model with more sophisticated flow controls that allow some kind of iterative processing at the level of task management. The purpose of this work is to present a proposal for a specification language for parallel application execution workflow, which provides new types of control structures and allows the implementation of a broader range of applications. This language is based on XML (eXtensible Markup Language) notation, which provides characteristics like simplicity and flexibility to the proposed language. To evaluate these and other characteristics of the language, it was implemented on the JoiN parallel processing system. Besides allowing the creation and execution of new parallel applications containing task flows with loops and conditional branches, the proposedlanguage was easy to use and did not cause any significant overhead to the parallel system / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica