Este trabalho tem por objetivo estudar os mecanismos de comunicacao em um sistema de multiprocessamento com memoria compartilhada. O trabalho realiza primeiramente, um estudo das principais variaveis que influenciam no desempenho da comunicacao, tais como sincronizacao, estruturas funcionais, memoria e tecnologia de intercomunicacao.Em seguida um sistema e especificado, modelado e proposto para ser analisado sob simulacoes. Cinco algoritmos de arbitracao de barramento foram selecionados, sendo dois provenientes da literatura e os demais propostos, e analisados seus desempenhos em funcao da variacao de alguns parametros. No final do trabalho os resultados sao pormenorizadamente discutidos sendo apresentados algumas conclusoes, bem como sugestoes de prosseguimento do estudo.

O uso de técnicas de processamento paralelo tem se tornado bastante comum na implementação de sistemas computacionais de alto desempenho. Uma destas técnicas, o uso de múltiplos processadores independentes ligados a um sistema de memória compartilhado(normalmente denominada paralelismo MIMD fortemente acoplado), tem sido pesquisado de maneira especial, devido a sua flexibilidade e facilidade de programação. No entanto, a implementação de sistemas de memória compartilhada apresenta diversos desafios, porque um único sistema deve atender a acessos de diversos processadores rapidamente, e ainda assim apresentar um custo aceitável. Diversas propostas para estes sistemas são apresentadas neste trabalho, com atenção especial para cachês locais com mecanismos dinâmicos de garantia de consistência. Entre os mecanismos de consistência, são abordados os protocolos de posse de blocos(adequados a cachês copy-back), protocolos write-through e protocolos orientados por software (adequado a caches write-through)Este trabalho envolve simulações de algumas arquiteturas básicas, através de um simulador de multiprocessadores alimentado com programas de álgebra linear. Da-se especial atenção a comparação entre sistemas baseados em cachês copy-back e nos baseados em cachês write-through, considerando mecanismos de consistência baseados em hardware. Mostra-se que, apesar de exigirem uma largura de faixamaior para a memória principal, sistemas de cachês write-through são menos sensíveis a codificação dos programas do que os sistemas com cachês copy-back, apresentando desempenho melhor quando ha muito compartilhamento de dados.

Este trabalho apresenta o projeto, a implementação e a aplicação em tempo real de uma arquitetura multiprocessadora de baixo custo e com alta capacidade para processamentonumérico. Dois processadores digitais de sinais TMS320C30 são empregados para processamento numérico intensivo, em microcontrolador PCB80C552 faz a interface de arquitetura com sistemas analógico/digitais. Um microcomputador IBM PC é empregado como hospedeiro, plataforma de desenvolvimento de aplicativos e interface eficiente com o usuário. Os processadores se comunicam via memória SRAM de duplo acesso através de um protocolo dirigido por interrupções. Além de flexível, a arquitetura pode ser expandida para implementação em hipercubo.Aplicações em tempo real de filtragem e controle adaptativo são apresentadas e discutidas. Uma metodologia baseada em heurística para a paralelização de algoritmos seriais em equivalente paralelos mapeados na arquitetura é proposta.

Neste trabalho é feito um estudo de desempenho de um núcleo de processamento, baseado em uma arquitetura multiprocessada composta de quatro processadores TMS32010 (texas instruments), adequado ao processamento digital de sinais. A comunicação entre os processadores é feita através de blocos de memória compartilhada. Um simulador deste sistema foi desenvolvido com uma interface de fácil utilização. Dois exemplos de aplicação foram implementados e simulados: 1) histograma de imagens com múltiplos níveis de cinza; 2) distribuição de temperatura na superfície de uma placa condutora de calor. Os resultados obtidos nas simulações, permitiram uma análise do desempenho da arquitetura discutida em diversos casos.

Esta tese melhora o upper bound de tempo e de espaço da resolução paralela do Subset-Sum Problem (SSP) - que é uma variante do Problema da Mochila - numa máquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura científica, isto é, tanto na abordagem através das listas como por programação dinâmica. Com relação ao primeiro paradigma, é apresentada uma paralelização ótima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaço O(2n/2), onde 1 p < 2n/2/n2. Como esse algoritmo seqüencial tem até hoje a melhor complexidade de tempo para a resolução do Problema da Mochila, então nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teórico de toda a literatura. Além disso, são apresentados três algoritmos paralelos adaptativos baseados no paradigma da programação dinâmica, que são os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaço O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaço do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente até o momento.

O algoritmo que resolve o método de advecção proposto por Walcek tem como principais características a conservação dos valores de picos, tanto de máximo quanto de mínimo, e a baixa difusão numérica. Entretanto este algoritmo possui também uma característica intrínseca que limita a implementação de paralelismo por cooperação de tarefas: exige dependências de fluxo no cálculo das células do domínio. O presente trabalho propõe a mudança no paradigma de programação do algoritmo original para torná-lo aderente ao processamento a fluxo de dados. Nesse tipo de processamento a computação ocorre em forma de tarefas que são definidas de acordo com os valores/estado dos dados de entrada. Essas tarefas podem ou não conter dependências e permitem ainda uma organização não sequencial do processamento. Quando tarefas independentes surgem, a obtenção de paralelismo passa a ser trivial. Experimentos realizados sobre domínios unidimensionais mostram que a abordagem a fluxo de dados expõe situações propícias ao processamento paralelo outrora desconhecidas, além de obter um tempo total de processamento inferior ao algoritmo original. Quando considerando domínios multidimensionais, a nova abordagem consegue um desempenho paralelo equivalente e um tempo total de processamento até 2,5 mais rápido do que a abordagem original.

O principal objetivo deste trabalho é apresentar uma análise de desempenho de algoritmos de compressão de imagens, levando em consideração a energia demandada por eles. Em outras palavras, além dos critérios comumente utilizados para avaliar o desempenho de algoritmos de compressão de imagens (e.g., taxa-distorção), este trabalho também irá considerar uma variável custo em termos de energia (i.e., taxa-distorção-energia). Uma avaliação desse tipo pode permitir que a escolha de um algoritmo de compressão de imagens para operar em sistemas com restrição de energia (e.g., satélites de sensoriamento remoto) seja mais apropriada. Sabe-se que uma análise envolvendo o gasto de energia de um algoritmo apresentará resultados que dependerão do hardware que o executa. Por isso, o estudo feito por esse trabalho irá abordar o assunto considerando questões importantes da esfera da computação, onde alguns experimentos irão envolver plataformas de processamento com características distintas. Também é sabido que os processadores mais recentes permitem o processamento paralelo de operações. Quando utilizado, esse recurso é capaz de aumentar a eficiência do algoritmo em termos de tempo de processamento e gasto de energia. Por outro lado, os algoritmos de compressão de imagens mais utilizados, foram desenvolvidos sob a óptica do processamento sequencial de operações (assim como suas implementações mais usuais). Dito isso, este trabalho também irá avaliar o ganho de desempenho que é possível alcançar ao se perseguir a criação de algoritmos de compressão que façam uso do recurso de processamento paralelo. Os resultados das análises apontam para um aumento significativo do desempenho dos algoritmos analisados, em termos de tempo de processamento e gasto de energia, quando utilizado o recurso de processamento paralelo. Além disso, será possível analisar de que forma as estratégias de compressão adotadas pelos algoritmos que serão analisados irão impactar no consumo de energia do sistema.

Há mais de uma década os robôs paralelos têm atraído a atenção das comunidades acadêmica e industrial devido às suas vantagens potenciais sobre as arquiteturas predominantes - as seriais. Dentre estas vantagens, pode-se citar a leveza, as elevadas velocidades e acelerações e a capacidade de carga. A aplicação industrial mais promissora para estas arquiteturas alternativas de robôs são as operações \"pega-e-põe\", necessárias nas indústrias alimentícia, farmacêutica e de componentes eletrônicos. Neste trabalho apresenta-se um robô paralelo, concebido com a finalidade de realizar operações \"pega-e-põe\" no espaço bidimensional (plano). O objetivo principal é a análise dinâmica deste mecanismo, empregando o método de Kane, para a determinação dos torques dos atuadores e das forças de reação, causados pelo efeito dinâmico de sua movimentação, quando a garra esteja sujeita a esforços externos e realizando uma trajetória retilínea ou circular em movimento uniforme ou uniformemente variado. Para tanto, desenvolveu-se nesta dissertação a análise cinemática do robô, um estudo de possíveis trajetórias para a garra, o levantamento do espaço de trabalho, bem como a análise dinâmica correspondente. Incluiu-se também diversas simulações para caracterizar melhor suas propriedades. / For over a decade parallel robots have attracted the interest from academic and industrial communities due to their potential advantages over the predominant serial architecture. Among these advantages are the lighter weight and higher speeds, accelerations, and load capacity. The most promising industrial application for these alternative architectures are the pick-and-place operations, which are needed in food, pharmaceutical and electronics industries. We show here a parallel robot designed to perform pick-and-place operations in two dimensions , i.e., on a plane. The main goal is the dynamical analysis of this mechanism by means of the Kane method. We determine the torques of the actuators and the reaction forces caused by the dynamical effects of its movement, when its end-effector is subject to external load. The cases of uniform and accelerated movements, with either straight or circular trajectory, are considered. Therefore, in this dissertation we present the kinematics analysis of the robot, an analysis of possible end-effector trajectories, the workspace development, and the corresponding dynamical analysis. A few simulations are also included to better describe its properties.

Apresentamos um problema de dinâmica molecular e quatro algoritmos seqüenciais para a implementação do mesmo. Em seguida esses algoritmos são estudados quanto ao tempo de execução e possibilidades de paralelização. É escolhido então dentre os quatro o algoritmo que apresenta melhores características para a paralelização. Introduzimos a seguir uma proposta de implementação do mesmo em um rede de transputers, com a. definição das interligações entre os processadores e da. programação dos mesmos. A seguir é realizado um estudo da eficiência da estrutura proposta quanto a. tempo de execução e características de expansibilidade do número de processadores. Os resultados mostram que conseguem-se velocidades de execução próximas às de supercomputadores para redes com baixos números de elementos. / In the present work, we describe four sequential algorithms for simulating molecular dynamics. The parallelism and execution times of these algorithms are assessed. Using the best suited algorithm for parallelism exploitation a transputer based architecture is suggested including needed link and software. The evaluation of the eficiency regarding execution time and number of processors is analyzed. The results show that speeds dose to those of supercomputers can be achieved with a low number of processors.

Este trabalho aborda alguns conceitos e definições de processamento paralelo, que são aplicados a paralelização automática, e também às análises e condições para as dependências dos dados, de modo a aplicarmos os métodos de paralelização: Hiperplano, Transformação Unimodular, Alocação de Dados Sem Comunicação e Particionamento & Rotulação. Desta forma, transformamos um programa seqüencial em seu equivalente paralelo. Utilizando-os em um sistema de memória distribuída com comunicação através da passagem de mensagem MPI (Message-Passing Interface), e obtemos algumas métricas para efetuarmos as avaliações/comparações entre os métodos. / This work invoke some concepts and definitions about parallel processing, applicable in the automatic parallelization, and also the analysis and conditions for the data dependence, in order to apply the methods for parallelization: Hyperplane, Unimodular Transformation, Communication-Free Data Allocation and Partitioning & Labeling. On this way, transform a sequential program into an equivalent parallel one. Applying these programs on the distributed-memory system with communication through message-passing MPI (Message-Passing Interface), and we obtain some measurements for the evaluations/comparison between those methods.