Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

Este trabalho descreve o projeto lógico de três meios alternativos de interconexão entre processadores e módulos de memória para um sistema multimicroprocessador: barramento multiplexado, múltiplos barramentos dedicados/memórias multiporta e matriz de barramentos cruzados. Com vistas ao projeto, são analisadas as características operacionais de multiprocessadores e identificadas algumas de suas funções de controle. O problema de interconexão em sistemas compostos de múltiplas unidades de processamento é abordado hierarquicamente. São mostradas as formas de se realizar a estrutura de interconexão, dando-se maior atenção aos barramentos digitais são apresentados os protocolos de arbitração e protocolos de comunicação mais utilizados neste tipo de estrutura. / This work describes the logical project of three alternative ways of interconnecting processors and memory modules in a multimicro processor system: multi p lexed bus, multi ple dedicated buses/multi-port memories, and cross-bar matrix. Aiming the project, the o perational features of multiprocessors are analysed and some control functions identified. The interconnection problem in multiple processing units systems is hierarchichally approached, em phasizing digital buses. The arbitration protocols and communication Protocols mostly used in this kind of structure are shown.

Este trabalho descreve a área de processamento matricial, mostrando os principais compromissos existentes na obtenção de arquiteturas paralelas a partir de algoritmos, para que haja um ganho real na avaliação destes. São feitas, ainda, considerações sobre ferramentas de programação para arquiteturas paralelas. Os principais compromissos que influenciam as arquiteturas SIMD, objeto de estudo deste trabalho, são abordados analisando-se uma áera de aplicação de arquiteturas SIMD: tratamento de imagens. Como uma caso prático de estudo e exemplo destes compromissos, é proposta uma arquitetura SIMD para um processador matricial empregando um chip matricial disponível comercialmente - o GAPP (Geometric Arithmetic Parallel Processor). É proposto, ainda, um ambiente para o desenvolvimento de programas nesta arquitetura. Este ambiente é baseado na utilização da lingaugem GAL (GAPP Algorithm Language), criada especificamente para elaboração de programas para o GAPP. / This work describes the array processing area, discussing the main tradeoffs in the design of parallel architecture from algorithms. The algorithm to architecture transformation is called a mapping problem. Some considerations about progamming tools for parallel architectures are also made. The relationship between algorithms and architectures is covered by studying a specific case for SIMD architectures: digital image processing. A SIMD architecture proposal, using a commercially available chip array - GAPP (Geometric Arithmetic Parallel Processor) is made. This architecture is used on a practical case to study and analyze those tradeoffs. An environment for program development for this architecture is also proposed. This environment is based on the use of GAL language (GAPP Algorithm Language), which was created specificaly for GAPP program development.

Orientadores: Jose Alberto Cuminato, Maria Cristina de Castro Cunha / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-23T19:43:09Z (GMT). No. of bitstreams: 1 Boaventura_Maurilio_D.pdf: 2491219 bytes, checksum: 867f05e9f0a13670568238a19f88b98d (MD5) Previous issue date: 1998 / Resumo: Apresentamos, neste trabalho, uma técnica paralela baseada em uma decomposição de domínio para resolver as equações de Navier-Stokes com superfícies livres em coordenadas cartesianas e cilíndricas em duas dimensões. Essa técnica é baseada no código apresentado por Tomé [1993] e Tomé e co-autores [1996], a qual por sua vez é baseada no método SMAC apresentado por Amsden e Harlow [1971], que resolve as equações de Navier-Stokes em três passos: a equação de momento, a equação de Poisson e o movimento das partículas. A primeira equação é discretizada por diferenças finitas explícitas. A paralelização é realizada dividindo-se o domínio original de cálculo em vários subdomínios verticais e atribuindo cada um deles a um processador. Todos os cálculos podem ser realizados usando comunicação somente com o processador vizinho mais próximo. No final, apresentamos testes comparando a performance do código paralelo com o seqüencial e discutimos a questão do balanceamento de carga. / Abstract: A parallel technique "Qased on domain decomposition for solving free surface Navier-Stokes equations in cartesian and cylindrical coordinates in two dimensions is described. It is based on the code by Tomé [1993] and Tomé et.al. [1996], which in turn is based on the SMAC method by Amsden & Harlow [1971], which solves the Navier-Stokes equations in three steps: the momentum equation and Poisson solvers and particle movement. The first equation is discretized by explicit finite differences. The paralIelization is performed by splitting the computation domain into vertical strips and assigning each of these to a processor. All the computation can then be performed using nearest neighbour communication. We present run tests comparing the performance of the parallel with the serial code, and discuss the load balancing question. / Doutorado / Doutor em Matemática Aplicada

Orientador: Mauricio Ferreira Magalhães / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T04:53:14Z (GMT). No. of bitstreams: 1 MeloJunior_Alencarde_M.pdf: 4501788 bytes, checksum: f5cab8a6e5f02e4b01c0e349c47e542e (MD5) Previous issue date: 1993 / Resumo: Em sistemas de tempo real crítico os processos a serem escalonados estão sujeitos a um grande número de restrições: tempo de pronto, "deadline", e relações de exclusão mútua. O problema de escalonar um conjunto de processos em um sistema monoprocessador sujeito a estas restrições é conhecido ser "NP-hard", o que efetivamente impede o escalonamento destes em modo totalmente "on-line". Para os processos periódicos, utiliza-se um algoritmo já existente, projetado para ser usado por um escalonador "off-line", que resolve o problema citado anteriormente. Os processos esporádicos possuem tempo de pronto não determinístico, e desta forma, não podem ser escalonados "off-line", fazendo-se necessário uma abordagem "on-line" . Este trabalho mostra que a implementação do escalonador "off-line" é factível e complementa este, propondo um procedimento eficiente para o atendimento "on-line" de processos esporádicos de modo a não comprometer o escalonamento gerado em modo "off-line" para os processos periódicos / Abstract: Not informed. / Mestrado / Mestre em Engenharia Elétrica

Orientador: Ricardo O. Anido / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T10:55:10Z (GMT). No. of bitstreams: 1 Rosa_ThiersonCouto_M.pdf: 7086241 bytes, checksum: f7617659cfaa4add0e67a31718cada39 (MD5) Previous issue date: 1994 / Resumo: Neste trabalho estudamos o problema de validação de ações atômicas distribuídas e de protocolos de validação que visam resolvê-lo. Além do estudo de protocolos de validação existentes na literatura, propomos uma variação do protocolo de duas fases, denominada protocolo semibloqueante. No Capítulo 1 são apresentados o conceito de ação atômica distribuída e uma motivação para sua utilização. Também são descritas as funções básicas de um sistema gerenciador genérico de ações atômicas. No Capítulo 2 é definido um modelo de sistema distribuído. Com base neste modelo, é definido o problema de validação de ações atômicas distribuídas e são apresentados formalism?s para descrição do funcionamento de protocolos de validação em geral. São ta.mbém estudadas as condições necessárias para a existência de protocolos não-bloqueantes e de recuperação independente de processos falhos. No Capítulo 3 são estudados protocolos de validação de duas fases que visam a eficiência quanto à finalização da ação. F:stes protocolos são descritos com base em um conjunto de parâmetros definidos no início do capítulo. No Capítulo 4 são estudados protocolos de validação de duas fases que visam ser tolerantes a falhas. No início do capítulo é adotado um padrão para descrição desses protocolos: O Capítulo 5 descreve um conjunto de protocolos que não se enquadram na categoria de protocolos de duas fases. No Capítulo 6 apresentamos o protocolo semibloqueante, um protocolo intermediário entre os protocolos de duas fases e os protocolos não-bloqueantes. Durante uma execução sem falhas, o protocolo comporta-se como um protocolo bloqueante. Quando surgem falhas no sistema, o protocolo passa a funcionar como um protocolo de três fases não-bloqueante.. A Capítulo 7 finaliza o texto com alguns comentários e sugestões de trabalhos futuros / Abstract: In this work we studythe atomic actions commit problem and a set of commit protocols which aim to solve this problem. We also propose a new two-phase commit protocol, the scmiblocking commit protocol. In Chapter, 1 we give the definition of distributed atomk actions. We also present the basic definitions of a generic atomic action management system. In Chapter 2, we define a model of distributed system which is used to define the atomic action commit problem and the formalism used to describe the operation of generic commit protocols. In Chapter 3, we describe several efficient two-phase commit protocols from the literature. The. description of these protocols are based on a set of parameters which are defined at the beginning of the chapter. In Chapter 4, we describe a series of published fault-tolerant commit protocols. At the beginning of the chapter, we define a set of parameters which are used for the desQri'ptions of these protocols. Chapter 5 contains a set of protocols which do not belong to the two-phase category of commit protocols. In Chapter 6, we introduce the semiblocking commit protocol which stands between the cIass of two-phase commit protocols and that of nonblocking commit protocols. During a failure-free execution, t,he protocol behaves like a blocking commit protocol. When,ever a fault occurs in the system, the semiblocking commit protocol begins to act like a nonblocking . three-phase commit protocol. Chapter 7 cIoses the text with some comments and suggestions for future work / Mestrado / Mestre em Ciência da Computação

Orientadores: Nelson C. Machado, Celio C. Guimarães / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-19T11:11:43Z (GMT). No. of bitstreams: 1 MartinezCarrazana_Ivone_M.pdf: 2485359 bytes, checksum: 940d798281420b928ccef25b9a47978f (MD5) Previous issue date: 1993 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Ciência da Computação

Orientador: Gerson Francisco / Mestre

Desempenho e consumo energético são requisitos fundamentais em sistemas de computação. Um desafio comumente encontrado é conciliar esses dois aspectos, buscando manter o mesmo desempenho, consumindo cada vez menos energia. Muitas técnicas possibilitam a redução do consumo de energia em aplicações paralelas, mas na maioria das vezes elas envolvem recursos encontrados apenas em processadores modernos ou um conhecimento amplo das características da aplicação e da plataforma alvo. Nesse trabalho propomos uma abordagem em formato de Workflow. Na primeira fase, o comportamento da aplicação paralela é investigado. A partir dessa investigação, a segunda fase realiza a execução da aplicação paralela com diferentes frequências (mínima e máxima) de processador, utilizando a caracterização das regiões, obtida na primeira fase da abordagem. Esse Workflow foi implementado em formato de biblioteca dinâmica, a fim de que ela possa ser utilizada em qualquer aplicação OpenMP. A biblioteca possui suporte as duas fases do Workflow, na primeira fase é gerado um arquivo que descreve as assinaturas comportamentais das regiões paralelas da aplicação. Esse arquivo é posteriormente utilizado na segunda fase, quando a biblioteca vai alterar dinamicamente a frequência de processador. O benchmark Lulesh é utilizado como cenário de testes da biblioteca, com isso o maior ganho obtido é a redução de 1,89% do consumo de energia. Esse ganho acarretou uma sobrecarga de 0,09% no tempo de execução. Ao comparar nossa técnica com a política de troca de frequência adotada pelo governor Ondemand do Sistema Operacional Linux, o ganho de 1,89% é significativo em relação ao benchmark utilizado, pois nele existem regiões paralelas de curta duração, o que impacta negativamente no overhead da operação de troca de frequência. / Performance and energy consumption are fundamental requirements in computer systems. A very frequent challenge is to combine both aspects, searching to keep the high performance computing while consuming less energy. There are a lot of techniques to reduce energy consumption, but in general, they use modern processors resources or they require specific knowledge about application and platform used. In this work, we propose a performance analysis workflow strategy divided into two steps. In the first step, we analyze the parallel application behavior through the use of hardware counters that reflect CPU and memory usage. The goal is to obtain a per-region computing signature. The result of this first step is a configuration file that describes the duration of each region, their hardware counters, and source code identification. The second step runs the parallel application with different frequencies (low or high) according to the characterization obtained in the previous step. The results show a reduction of 1,89% in energy consumption for the Lulesh benchmark with an increase of 0,09% in runtime when we compare our approach against the governor Ondemand of the Linux Operating System.

Moore’s law reaching its physical limitations has pushed the industry to produce multicore processors. However, programming those processors with an imperative language is not easy since it requires developers to create and synchronize threads. A pure functional language is an adequate tool for this task both from the architectural point of view and from the developer’s. We will show that an architecture can benefit from the implicit parallelism present on functional programs and from the lack of side effects making it easier to parallelize. The developer benefits from functional languages from the superior expressiveness of the language to avoid bugs. In this dissertation, we present the ACQuA architecture, a multicore accelerator created to explore parallelism available in function calls from a pure functional program. ACQuA uses hardware support and a specificallytailored memory organization to minimize the overheads of scheduling, communication, and synchronization. Function calls are placed into a queue and are scheduled to different processing units. The processing units are interconnected and exchange results from function applications. In this work we defined a high level model of the accelerator and how to compile a functional program to it. We also simulated the accelerator and evaluated results, such as speedup, memory usage, and communication overhead of the proposed architecture. We defined the necessary traits of a program to achieve a good speedup on the architecture. On the ideal use case, we can increase the speed up at the same rate we increase the number of processing units in the architecture.