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.

Nos últimos anos, uma das alternativas adotadas para aumentar o desempenho de sistemas de processamento de alto desempenho têm sido o uso de arquiteturas híbridas. Essas arquiteturas são constituídas de processadores multicore e coprocessadores especializados, como GPUs. Esses coprocessadores atuam como aceleradores em alguns tipos de operações. Por outro lado, as ferramentas e modelos de programação paralela atuais não são adequados para cenários híbridos, produzindo aplicações pouco portáveis. O paralelismo de tarefas considerado um paradigma de programação genérico e de alto nível pode ser adotado neste cenário. Porém, exige o uso de algoritmos de escalonamento dinâmicos, como o algoritmo de roubo de tarefas. Neste contexto, este trabalho apresenta um middleware (WORMS) que oferece suporte ao paralelismo de tarefas com escalonamento por roubo de tarefas em sistemas híbridos multi-CPU e multi-GPU. Esse middleware permite que as tarefas tenham implementação tanto para execução em CPUs quanto em GPUs, decidindo em tempo de execução qual das implementações será executada de acordo com os recursos de hardware disponíveis. Os resultados obtidos com o WORMS mostram ser possível superar, em algumas aplicações, tanto o desempenho de ferramentas de referência para execução em CPU quanto de ferramentas para execução em GPUs. / In the last years, one of alternatives adopted to increase performance in high performance computing systems have been the use of hybrid architectures. These architectures consist of multicore processors and specialized coprocessors, like GPUs. Coprocessors act as accelerators in some types of operations. On the other hand, current parallel programming models and tools are not suitable for hybrid scenarios, generating less portable applications. Task parallelism, considered a generic and high level programming paradigm, can be used in this scenario. However, it requires the use of dynamic scheduling algorithms, such as work stealing. In this context, this work presents a middleware (WORMS) that supports task parallelism with work stealing scheduling in multi-CPU and multi-GPU systems. This middleware allows task implementations for both CPU and GPU, deciding at runtime which implementation will run according to the available hardware resources. The performance results obtained with WORMS showed that is possible to outperform both CPU and GPU reference tools in some applications.

Nos últimos anos, máquinas maciçamente paralelas, compostas de centenas de processadores, vem sendo estudadas como uma alternativa para a construção de supercomputadores. Neste novo conceito de processamento de dados, grandes velocidades são alcançadas através da cooperação entre os diversos elementos processadores na resolução de um problema. Grande parte das máquinas maciçamente paralelas encontradas no mercado utilizam-se da topologia hipercúbica para a interconexão de seus múltiplos processadores, ou podem ser configuradas como tal. Uma alternativa interessante para o compartilhamento da capacidade de processamento destas máquinas é sua utilização como computador agregado a uma rede, servindo a diversos usuários [DUT 91]. Desta forma, a máquina hipercúbica se comporta como um banco de processadores, que permite que cada usuário aloque parte de seus processadores para seu uso pessoal. Isto resulta em um aumento no desempenho da rede ao nível de supercomputadores com um custo relativamente baixo e viabiliza a construção de máquinas hipercúbicas com altas dimensões, evitando que estas sejam sub-utilizadas. Neste tipo de contexto, cabe ao sistema operacional atender as requisições dos usuários do hipercubo compartilhado de forma eficiente, a fim de evitar uma rápida fragmentação do cubo e de não exceder o tempo máximo de espera de uma determinada aplicação. A partir dos algoritmos propostos é apresentada a definição de um servidor de processadores para o compartilhamento de uma máquina multiprocessadora hipercúbica em uma rede de estações de trabalho. Algumas funções deste servidor são implementadas por um protótipo denominado Sub-Cube RPC. Com o objetivo de analisar o comportamento da rede de estações em relação a inclusão de um novo recurso a ser compartilhado, foi desenvolvido, juntamente com o grupo de Avaliação de Desempenho ADMP, um simulador para o ambiente SUN/UNIX. Através desta ferramenta e dos tempos de resposta obtidos pelo protótipo do servidor desenvolvido é possível avaliar o custo que o tráfego gerado pelo servidor adiciona à rede, sendo possível a manipulação de parâmetros da rede e do servidor. Os resultados obtidos nas versões paralelas implementadas são comparados com o desempenho das versões seqüenciais. Para viabilizar esta comparação, todos os algoritmos seqüenciais encontrados na literatura também foram implementados na linguagem "C" no ambiente alvo UNIX e encontram-se em anexo. As versões paralelas foram implementadas utilizando-se recursos da própria rede de estações, através de diretivas socket, e também em Transputers na linguagem C paralela. O protótipo do servidor de processadores foi implementado como um servidor RPC para uma rede de estações UNIX também na linguagem "C". A ferramenta de simulação para o funcionamento do servidor foi implementada na linguagem "C" e seu sistema de entrada de dados e visualização utiliza a interface X-Windows. Com os resultados deste trabalho se pode ter uma boa idéia dos efeitos e das dificuldades encontradas na paralelização dos algoritmos de alocação e gerência de processadores para máquinas Hipercúbicas. As informações contidas no trabalho auxiliam na melhoria do tempo de resposta dos algoritmos seqüenciais atuais e no desenvolvimento de novos algoritmos com mais recursos e ainda assim viáveis em ambientes interativos, graças a utilização de paralelismo. O protótipo Sub-Cube RPC demonstra como os algoritmos estudados neste trabalho podem ser aplicados na construção de um servidor de processadores para máquinas multiprocessadas. O protótipo servirá como base para a implementação de um servidor semelhante no CPGCC/UFRGS, que colocará uma placa de Transputers à disposição da rede de estações do grupo de processamento paralelo. / In the last years massively parallel machines, build with hundreds of processors, are becoming an alternative for the construction of supercomputers. In this new concept of data processing, high performance is achieved by processor cooperation in the resolution of a problem. A great part of the commercial massively parallel machines utilizes the hypercubic topology to interconnect their multiple processors, or may be configured as hypercubes. A very interesting alternative for sharing the processing power of this machines is their utilization as aggregated computer in a network, serving various users [DUT 91]. In such environment, the hypercube behaves like a processor server, permitting the users to allocate part of its processors for local use. This result in a enhancement in the performance of workstation networks to the level of supercomputers and allow higher dimension hypercubes to be better utilized. In such environment the operating system is responsible for serving the users of a shared multiprocessor in a efficient way, not allowing a quick fragmentation of the hypercube and observing the maximal waiting time for the applications. The algorithms for processor allocation and management are responsible for obtention and control of one or more processors of the shared machine for the user's task execution. In this study, parallel versions of the most important algorithms for processor allocation and management in hypercubes found in the literature are proposed. The intention with this paralelization is to achieved a better response time of the more complex algorithms, making their use possible in a real time sharing environment. Because the allocation is considered the most important part of the processor server, the utilization of more complex algorithms allows a better utilization of the shared processors, resulting in a performance increase of the parallel machine. Based on the proposed algorithms, a processor server is defined for sharing a hypercubic multiprocessor in a workstation network. Some functions of this server are implemented in a prototype called Sub-Cube RPC. To analyze the behavior of the network, in relation to the inclusion of this new shared resource, a simulator for the SUN/UNIX environment has been developed together with the Performance Evaluation Group ADMP. With this tool and with the response times of the developed server prototype, it is possible to evaluate the cost of the additional network traffic generated by the server, with the possibility to change parameters of the server and network. The results obtained in the implemented parallel versions are compared with the performance of the sequential algorithms. To make this comparison possible all the sequential algorithms found in the literature are also implemented in the "C" language and can be found in annex. The parallel versions were implemented using network resources, through the socket directive, and also using Transputers in parallel "C". The processor server prototype was implemented as a RPC server for an UNIX network, also in the "C" language. The simulation tool was coded in "C" and the I/O interface use the X-Windows protocol. The results of this study may give a background about the effects and difficulties found in the pa ralelization of the allocation algorithms for the hypercubic machines. The information found in this study will help the operating system designer to obtain a better response time of the sequential algorithms found in the literature and in the development of new and more complex algorithms that will be still practicable in a real time environment due to parallelism utilization. The Sub-Cube RPC prototype demonstrates how the algorithms studied in this work can be applied in the construction of a processor server for multiprocessors. The prototype is the first step for the implementation of a similar server in the CPGCC/UFRGS that will share a Transputer board in a network of workstations from the parallel processing group.

Procedimentos de reconfiguração são usados em diversos sistemas para isolar módulos falhos e recuperar o sistema após a ocorrência de erros. Em ambientes multiprocessadores, onde existe redundância implícita de nodos processadores, vários algoritmos de reconfiguração já foram propostos. Entretanto a maior parte destes algoritmos destina-se a topologias específicas bastante exploradas como, por exemplo, arquiteturas na forma de arrays e árvores. Neste trabalho é apresentada uma estratégia de detecção/reconfiguração para tolerar falhas na máquina T-NODE. Esta máquina possui uma arquitetura multiprocessadora fracamente acoplada, que tem como processador base o transputer. Sua arquitetura de interconexão é definida pelo usuário; a organização de barramentos implementada com base em uma chave crossbar, a qual permite uma variada e fácil gama de opções. Assim, os algoritmos tradicionais de reconfiguração não se aplicam pois são excessivamente restritivos. A análise da arquitetura e do software de baixo nível existentes para a T-NODE revelou recursos praticamente inexistentes a nível de controle de falhas nos processadores e erros no processamento. Mesmo considerando-se que o principal objetivo desta máquina é a obtenção de alto desempenho, é possível implementar procedimentos que melhorem suas características de confiabilidade. Neste estudo é apresentada uma maneira de melhorar o nível de tolerância a falhas da máquina de modo que ela possa ser usada em tarefas mais exigentes do ponto de vista de confiabilidade, sem perda excessiva de desempenho. A estratégia definda usa a técnica de redundância dinâmica com detecção de falhas on-line e recuperação do sistema através do isolamento da falha por reconfiguração e conseqüente reinicialização do sistema. A validação da estratégia foi feita pela construção de um protótipo utilizando a linguagem OCCAM2 e um processador transputer conectado ao barramento de um microcomputador PC. No protótipo foram implementados três processos distintos: o testador, o supervisor e o reconfigurador. Estes processos têm respectivamente, as funções de testar os nodos processadores, supervisionar os resultados dos testes e reconfigurar o sistema quando da ocorrência de uma falha. / In many systems, reconfiguration strategies are used to remove failed components and to recuperate system from the resulting errors. Various reconfiguration algorithms have been proposed with the goal of covering faults in multiprocessing systems, but most of them support only specific architecture styles, as arrays or trees. In this study, a reconfiguration algorithm is proposed whose goal is to tolerate faults in the T-NODE machine. The T-NODE is a loosed coupled, multiprocessor machine based on transputers. The analysis of the architecture and of the system software existing for the T-NODE has shown that, in practice, there were not special resources aiming to control processor faults and processing errors. Even considering that the main goal of this machine is processing with high performance, it is possible to implement alternative procedures which result in better reliability characteristics. By other way, the interconnection architecture of this machine is defined by the user; its bus organization implemented with the aid of a crossbar switch allows choices among several possibilities. Consequently, traditional algorithms do not apply because they are too restrictive. Therefore, the research here related aims to improve the fault-tolerance parameters of this machine without changing significantly its original performance. The strategy here presented uses a dynamic redundancy technique with on-line fault detection; system recovery is get by logically isolating the faulty module, reconfiguring the others and restarting the system. The validation of the strategy has been done with the construction of a prototype using the OCCAM2 language and a transputer processor connected to the bus of a microcomputer (PC). Three different processes have been implemented in the prototype: the tester, the supervisior and the reconfigurator. These processes have respectively the functions of: testing the processing nodes, to supervise tests results and to reconfigure the system under fault occurrence.

Este trabalho e dedicado ao estudo da exploração de paralelismo na Programação em Lógica. O aspecto declarativo das linguagens de Programação em Lógica permite uma exploração eficiente do paralelismo implícito no código, de forma mais simples que as linguagens imperativas. Ao mesmo tempo, o paralelismo tem-se mostrado uma forte opção para procura de aumentos significativos do desempenho dos computadores. Como conseqüência, nos últimos anos, diversas maquinas paralelas tem surgido no mercado. No entanto, a sua efetiva utilização ainda ressente-se de uma dificuldade de programação maior que a das maquinas sequênciais. Por outro lado, o alto nível das linguagens de Programação em Lógica permite o desenvolvimento de programas de forma mais rápida e concisa do que as linguagens tradicionais (imperativas). Porem, apesar dos importantes progressos nas técnicas de compilação destas linguagens, elas permanecem menos eficientes que as linguagens imperativas. 0 aumento na eficiência de execução da Programação em Lógica, com o use do paralelismo, certamente estenderá o seu emprego. Em função disto, a unido da Programação em Lógica e maquinas paralelas tem sido proposta como uma alternativa para facilitar a programação das maquinas paralelas, bem como para aumentar o desempenho na Programação em Lógica. O ponto central do trabalho e a concepção de um modelo para exploração do paralelismo E Restrito na execução de Prolog, voltado para arquiteturas multiprocessadoras sem memória comum. Como ponto de partida foi utilizado o modelo já definido para exploração do paralelismo OU do projeto OPERA, do Instituto de Informática da UFRGS, de maneira que o modelo de paralelismo E proposto possa vir a compor, com aquele, uma plataforma que integre a exploração simultânea dos paralelismos E e OU. O modelo concebido compreende uma proposta de compilação e um ambiente de execução. A detecção e o controle do paralelismo é iniciado na compilação. Nesta fase, a gerada uma Expressão Condicional de Execução para cada clausula do programa Prolog, cuja avaliação em tempo de processamento determina a execução, em paralelo ou não, dos literais que compõem a clausula. A Maquina Abstrata Prolog, projetada para o emulador paralelo, é baseada na WAM (Warren Abstract Machine), uma das mais eficientes e difundidas técnicas para compilação Prolog. Isto, dentre outros aspectos, confere uma boa portabilidade ao modelo. O ambiente de execução compreende a concepção de uma arquitetura de processos formada por trabalhadores OPERA, uma filosofia de escalonamento de serviço entre estes trabalhadores, uma política para gerencia de sua memória e uma estratégia para as comunicações. Para validar o modelo proposto para exploração do paralelismo E, o mesmo foi implementado em rede local de estações Unix, obtendo bons resultados. / This work is devoted to the study of the exploration of parallelism in Logic Programming. The declarative aspect of the Logic Programming languages allows an efficient exploration of the implicit parallelism in the code, in a simpler form than the imperative languages. At the same time, parallelism has been shown as a strong option to the search for significant increases in the performance of the computers. As a consequence, in the last years, several parallel machines have been sprung up into the market. Nevertheless, their effective usefulness still undergoes some difficulties in programming which are greater than those of the sequential machines. On the other hand, the high level of Logic Programming languages allows programs development to be faster and concise than in the traditional languages (imperatives). However, despite the important progress in compiling techniques for these languages, they remain less efficient than the imperatives languages. The increase in execution efficiency of logic programs, with the use of parallelism, will probabily extend their use. Having this in mind, the union of the Logic Programming and parallel machines has been proposed as an alternative to make programming of the parallel machines easier, as well as to increase the performance of Logic Programming. The central aspect of the work is the conception of a model to explore the Restricted AND Parallelism in the execution of Prolog, turned to multiprocessing architectures without a common memory. As a starting point, the already defined model for exploring OR parallelism of the OPERA project, from the Instituto de Informatica da UFRGS was used. This happened so that the proposed model of AND parallelism can make up a plataform with that one to integrate the simultaneous exploration of the AND and OR parallelisms. The conceived model holds a proposal of compilation and execution environment. The detection and the control of the parallelism is started in the compilation. A Conditional Expression of Execution to each clause of the Prolog program is generated on this phase. Its evaluation, during the time of processing, determines the execution, whether or not in parallel, of the literals that constitute the clause. The Abstract Prolog Machine, projected for the parallel emulator, is based on the WAM (Warren Abstract Machine) which is one of the most efficient and spread techniques for Prolog compilation. This aspects, among others, gives a good portability to the model. The environmente of execution comprises the conception of an architecture of processes formed by OPERA workers and a philosophy of scheduling service among these workers; it also comprise a policy to manage its memory and a strategy for the communications. So that the proposed model for the exploitation of AND parallelism got validated, it was implemented on a local net of Unix workstations, obtaining good results.

Este trabalho apresenta um modelo de escalonamento hierárquico para exploração do paralelismo E Independente e do paralelismo OU na programação em lógica. O modelo utiliza informações de granulosidade geradas pelo GRANLOG (Granularity Analyzer for Logic Programming) para o auxílio ao escalonamento. Um estudo detalhado de ambientes de programação em lógica explorando o paralelismo é apresentado. A partir deste, é feita uma comparação destacando as principais características de cada um. O escalonamento em linhas gerais também é descrito e uma enfâse maior é dada ao escalonamento dinâmico. As principais vantagens e desvantagens de cada escalonador são mostradas. O modelo proposto recebe o nome de DSLP – Distributed Scheduler for Logic Programming e realiza o escalonamento em duas fases. Inicialmente é executada a Fase OU, na qual todo paralelismo OU é explorado. Em seguida, é iniciada a Fase E onde ocorre a exploração do paralelismo E Independente. A estratégia de escalonamento proposta, utiliza informações de complexidade do GRANLOG para determinar o trabalho a ser exportado, bem como o nível de sobrecarga dos nodos. Para validação do trabalho, um protótipo utilizando o ambiente Parallel Virtual Machine foi implementado. O protótipo é um simulador de programas Prolog e implementa a fase E de escalonamento. / This work presents a hierarchical scheduling model for exploration of the Independent AND parallelism and OR parallelism in logic programming. The model uses granularity information generated by GRANLOG (Granularity Analyzer for Logic Programming) to aid the scheduler. A detailed study of parallel logic programming environments is presented. Starting from this, it is made a comparison highlighting the main characteristics of each one. Scheduling in general is also described and the dynamic scheduling is pointed out. The main advantages and disadvantages of each scheduler are shown. The proposed model receives the name of DSLP – Distributed Scheduler for Logic Programming and it accomplishes the scheduling in two phases. Initially the OR Phase is executed and the whole OR parallelism is explored. Soon after, it is initiate the AND Phase with the exploration of the Independent AND parallelism. The scheduling strategy proposed uses complexity information generated by GRANLOG to determinate the task to be exported, as well as the nodes overloaded level. For work validation, a prototype using the Parallel Virtual Machine was implemented. The prototype is a Prolog simulator and it implements the scheduling AND phase.