Orientadores: Guido Costa Souza de Araújo, José Nelson Amaral / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T10:12:59Z (GMT). No. of bitstreams: 1 Pereira_MarcioMachado_D.pdf: 2922376 bytes, checksum: 9775914667eadf354d7e256fb2835859 (MD5) Previous issue date: 2015 / Resumo: Nos últimos anos, Memórias Transacionais (Transactional Memories ¿ TMs) têm-se mostrado um modelo de programação paralela que combina, de forma eficaz, a melhoria de desempenho com a facilidade de programação. Além disso, a recente introdução de extensões para suporte a TM por grandes fabricantes de microprocessadores, também parece endossá-la como um modelo de programação para aplicações paralelas. Uma das questões centrais na concepção de sistemas de TM em Software (STM) é identificar mecanismos ou heurísticas que possam minimizar a contenção decorrente dos conflitos entre transações. Apesar de já terem sido propostos vários mecanismos para reduzir a contenção, essas técnicas têm um alcance limitado, uma vez que o conflito é evitado por interrupção ou serialização da execução da transação, impactando consideravelmente o desempenho do programa. Este trabalho explora uma abordagem complementar para melhorar o desempenho de STM através da utilização de escalonadores. Um escalonador de TM é um componente de software que decide quando uma determinada transação deve ser executada ou não. Sua eficácia é muito sensível às métricas usadas para prever o comportamento das transações, especialmente em cenários de alta contenção. Este trabalho propõe um novo escalonador, Dynamic Transaction Scheduler ¿ DTS, para selecionar a próxima transação a ser executada. DTS é baseada em uma política de "recompensa pelo sucesso" e utiliza uma métrica que mede com melhor precisão o trabalho realizado por uma transação. Memórias Transacionais em Hardware (HTMs) são mecanismos interessante para implementar TM porque integram o suporte a transações no nível da arquitetura. Por outro lado, aplicações que usam HTM podem ter o seu desempenho dificultado pela falta de escalabilidade e transbordamento da cache de dados. Este trabalho apresenta um extenso estudo de desempenho de aplicações que usam HTM na arquitetura Haswell da Intel. Ele avalia os pontos fortes e fracos desta nova arquitetura, realizando uma exploração das várias características das aplicações de TM. Este estudo detalhado revela as restrições impostas pela nova arquitetura e introduz uma política de serialização simples, porém eficaz, para garantir o progresso das transações, além de proporcionar melhor desempenho / Abstract: In the last few years, Transactional Memories (TMs) have been shown to be a parallel programming model that can effectively combine performance improvement with ease of programming. Moreover, the recent introduction of (H)TM-based ISA extensions, by major microprocessor manufacturers, also seems to endorse TM as a programming model for today¿s parallel applications. One of the central issues in designing Software TM (STM) systems is to identify mechanisms or heuristics that can minimize contention arising from conflicting transactions. Although a number of mechanisms have been proposed to tackle contention, such techniques have a limited scope, because conflict is avoided by either interrupting or serializing transaction execution, thus considerably impacting performance. This work explores a complementary approach to boost the performance of STM through the use of schedulers. A TM scheduler is a software component that decides when a particular transaction should be executed. Their effectiveness is very sensitive to the accuracy of the metrics used to predict transaction behaviour, particularly in high-contention scenarios. This work proposes a new Dynamic Transaction Scheduler ¿ DTS to select a transaction to execute next, based on a new policy that rewards success and an improved metric that measures the amount of effective work performed by a transaction. Hardware TMs (HTM) are an interesting mechanism to implement TM as they integrate the support for transactions at the lowest, most efficient, architectural level. On the other hand, for some applications, HTMs can have their performance hindered by the lack of scalability and by limitations in cache store capacity. This work presents an extensive performance study of the implementation of HTM in the Haswell generation of Intel x86 core processors. It evaluates the strengths and weaknesses of this new architecture by exploring several dimensions in the space of TM application characteristics. This detailed performance study provides insights on the constraints imposed by the Intel¿s Transaction Synchronization Extension (Intel¿s TSX) and introduces a simple, but efficient, serialization policy for guaranteeing forward progress on top of the best-effort Intel¿s HTM which was critical to achieving performance / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Nesta tese é apresentado um novo workflow de simulação para avaliar o desempenho do balanceamento de carga dinâmico baseado em sobre-decomposição aplicado a aplicações paralelas iterativas. Seus objetivos são realizar essa avaliação com modificações mínimas da aplicação e a baixo custo em termos de tempo e de sua necessidade de recursos computacionais. Muitas aplicações paralelas sofrem com desbalanceamento de carga dinâmico (temporal) que não pode ser tratado a nível de aplicação. Este pode ser causado por características intrínsecas da aplicação ou por fatores externos de hardware ou software. Como demonstrado nesta tese, tal desbalanceamento é encontrado mesmo em aplicações cujo código não aparenta qualquer dinamismo. Portanto, faz-se necessário utilizar mecanismo de balanceamento de carga dinâmico a nível de runtime. Este trabalho foca no balanceamento de carga dinâmico baseado em sobre-decomposição. No entanto, avaliar e ajustar o desempenho de tal técnica pode ser custoso. Isso geralmente requer modificações na aplicação e uma grande quantidade de execuções para obter resultados estatisticamente significativos com diferentes combinações de parâmetros de balanceamento de carga Além disso, para que essas medidas sejam úteis, são usualmente necessárias grandes alocações de recursos em um sistema de produção. Simulated Adaptive MPI (SAMPI), nosso workflow de simulação, emprega uma combinação de emulação sequencial e replay de rastros para reduzir os custos dessa avaliação. Tanto emulação sequencial como replay de rastros requerem um único nó computacional. Além disso, o replay demora apenas uma pequena fração do tempo de uma execução paralela real da aplicação. Adicionalmente à simulação de balanceamento de carga, foram desenvolvidas técnicas de agregação espacial e rescaling a nível de aplicação, as quais aceleram o processo de emulação. Para demonstrar os potenciais benefícios do balanceamento de carga dinâmico com sobre-decomposição, foram avaliados os ganhos de desempenho empregando essa técnica a uma aplicação iterativa paralela da área de geofísica (Ondes3D). Adaptive MPI (AMPI) foi utilizado para prover o suporte a balanceamento de carga dinâmico, resultando em ganhos de desempenho de até 36.58% em 288 cores de um cluster Essa avaliação também é usada pra ilustrar as dificuldades encontradas nesse processo, assim justificando o uso de simulação para facilitá-la. Para implementar o workflow SAMPI, foi utilizada a interface SMPI do simulador SimGrid, tanto no modo de emulação, como no de replay de rastros. Para validar esse simulador, foram comparadas execuções simuladas (SAMPI) e reais (AMPI) da aplicação Ondes3D. As simulações apresentaram uma evolução do balanceamento de carga bastante similar às execuções reais. Adicionalmente, SAMPI estimou com sucesso a melhor heurística de balanceamento de carga para os cenários testados. Além dessa validação, nesta tese é demonstrado o uso de SAMPI para exploração de parâmetros de balanceamento de carga e para planejamento de capacidade computacional. Quanto ao desempenho da simulação, estimamos que o workflow completo é capaz de simular a execução do Ondes3D com 24 combinações de parâmetros de balanceamento de carga em 5 horas para o nosso cenário de terremoto mais pesado e 3 horas para o mais leve. / In this thesis we present a novel simulation workflow to evaluate the performance of dynamic load balancing with over-decomposition applied to iterative parallel applications at low-cost. Its goals are to perform such evaluation with minimal application modification and at a low cost in terms of time and of resource requirements. Many parallel applications suffer from dynamic (temporal) load imbalance that can not be treated at the application level. It may be caused by intrinsic characteristics of the application or by external software and hardware factors. As demonstrated in this thesis, such dynamic imbalance can be found even in applications whose codes do not hint at any dynamism. Therefore, we need to rely on runtime dynamic load balancing mechanisms, such as dynamic load balancing based on over-decomposition. The problem is that evaluating and tuning the performance of such technique can be costly. This usually entails modifications to the application and a large number of executions to get statistically sound performance measurements with different load balancing parameter combinations. Moreover, useful and accurate measurements often require big resource allocations on a production cluster. Our simulation workflow, dubbed Simulated Adaptive MPI (SAMPI), employs a combined sequential emulation and trace-replay simulation approach to reduce the cost of such an evaluation Both sequential emulation and trace-replay require a single computer node. Additionally, the trace-replay simulation lasts a small fraction of the real-life parallel execution time of the application. Besides the basic SAMPI simulation, we developed spatial aggregation and applicationlevel rescaling techniques to speed-up the emulation process. To demonstrate the real-life performance benefits of dynamic load balance with over-decomposition, we evaluated the performance gains obtained by employing this technique on a iterative parallel geophysics application, called Ondes3D. Dynamic load balancing support was provided by Adaptive MPI (AMPI). This resulted in up to 36.58% performance improvement, on 288 cores of a cluster. This real-life evaluation also illustrates the difficulties found in this process, thus justifying the use of simulation. To implement the SAMPI workflow, we relied on SimGrid’s Simulated MPI (SMPI) interface in both emulation and trace-replay modes.To validate our simulator, we compared simulated (SAMPI) and real-life (AMPI) executions of Ondes3D. The simulations presented a load balance evolution very similar to real-life and were also successful in choosing the best load balancing heuristic for each scenario. Besides the validation, we demonstrate the use of SAMPI for load balancing parameter exploration and for computational capacity planning. As for the performance of the simulation itself, we roughly estimate that our full workflow can simulate the execution of Ondes3D with 24 different load balancing parameter combinations in 5 hours for our heavier earthquake scenario and in 3 hours for the lighter one.

Neste trabalho, a resposta dinâmica de um riser marítimo devido à geração e desprendimento alternado de vórtices é investigada numericamente. O riser é dividido em seções bidimensionais ao longo de seu comprimento. O Método dos Vórtices Discretos é empregado para a determinação das forças hidrodinâmicas que agem nestas seções bidimensionais. As seções hidrodinâmicas são resolvidas independentemente, e o acoplamento entre as mesmas é feito através da solução da estrutura no domínio do tempo pelo Método dos Elementos Finitos. Os resultados numéricos são comparados com resultados obtidos experimentalmente. Processamento paralelo é empregado para melhorar a performance do método. As simulações são realizadas através de uma metodologia mestre-escravo, utilizando MPI Message Passing Interface para explorar o paralelismo. A escalabilidade do algoritmo é mostrada e discutida. Este trabalho representa o desenvolvimento de um simulador que permite, efetivamente, a análise dinâmica de um riser com características e dimensões representativas das condições reais encontradas em campo, a um custo computacional factível para seu uso como uma ferramenta de engenharia. Isto é obtido por meio da técnica de processamento paralelo, aliada à solução do escoamento através de um método eficiente de CFD Método dos Vórtices Discretos e à solução da estrutura através do Método dos Elementos Finitos. / In this work the dy6namic response of a marine riser due to vortex shedding is numerically investigated. The riser is divided in two-dimensional sections along the riser length. The Discrete Vortex Method is employed for the assessment of the hydrodynamic forces acting on these two-dimensional sections. The hydrodynamic sections are solved independently, and the coupling among the sections is taken into account by the solution of the structure in the time domain by the Finite Element Method. The numerical results are compared with results obtained experimentally. Parallel processing is employed to improve the performance of the method. The simulations are carried out through a master-slave approach using MPI Message Passing Interface to exploit the parallelism. Scalability of the algorithm is shown and discussed. This work represents the development of a simulator that effectively allows the dynamic analysis of a riser with representative characteristics and dimensions of real field conditions, with a feasible computational cost for its use as an engineering tool. This is obtained by means of the parallel processing technique, together with an efficient CFD solution of the flow with de Discrete Vortex Method and the solution of the structure with the Finite Element Method.

Made available in DSpace on 2016-03-22T17:26:24Z (GMT). No. of bitstreams: 1 Wagner Guimaraes Al-Alam.pdf: 2995290 bytes, checksum: 9902eafe02c0b5318a99f1e796dc399f (MD5) Previous issue date: 2010-01-15 / Companies working with bulk materials have appropriate locations for storage during the development of the production and storage of the final product, known as warehouses or storehouses. The values of stocks need to be periodically validated by comparing the control of receipts the and the physical situation (removal of the volume stored in the company). In this context, the calculation of physical inventory as the volume of bulk present in the warehouses is usually done manually with low credibility and prone to errors. The current audit procedures on the contents of warehouses involve inaccurate estimates, and often require emptying the warehouse. Considering the use of technologies which enable the electronic measurement of distances, angles, and automatic controls on actuators enabling mechanical movements on the supporting structures, we sought to develop a system capable of providing both computing solutions, and technology for the problem of calculation of irregular relief (products stocked in warehouses). The Automated Auditing Warehouse SisA3 intends to make this process automatic, fast and precise, without the need for emptying warehouses or having contact the products. To achieve this goal, we developed an integrated system composed of: (i) a scanner equipment, consoling the hybrid prototype of hardware and software called DigSisA3, in order to the measurement of points of relief non-uniform, formed by the products in stock, and (ii) a method for calculating the volume iCone, which combines techniques of scientific visualization, numerical interpolation points and iterative calculation of volume. The parallelization of the prototype iCone was also developed in order to satisfy the test of agility and performance of the method iCone in the audit process. The development for multiprocessor, multi-core, and distributed architectures was done over the DGM (Geometric Distributed Machine), which provides the formalities to ensure creation, management and application processing parallel and / or distributed scientific computing, with emphasis on the exploitation of data parallelism and synchronization steps. The prototype of software iCone was functionally validated, including analysis of error in the method. The analysis of performance in the prototype p-iCone showed satisfactory results. The development of this work strengthens the system SisA3, enabling automatic and reliable measurement of inventories, including broad market application / Empresas que trabalham com produtos a granel possuem locais para estocagem, durante o desenvolvimento do processo produtivo e no armazenamento do produto final, denominados armaz´ens ou silos. Os valores dos estoques devem ser validados periodicamente atrav´es da comparac¸ ao dos estoques fiscal (controle das notas fiscais) e f´ısico (levantamento do volume estocado na empresa). Neste contexto, o c´alculo do estoque f´ısico, ou seja, o volume de gran´eis presentes nos armaz´ens, ´e geralmente efetuado de forma manual e com baixa credibilidade, desta forma com propens ao a erros. Os atuais processos de auditoria no conte´udo de silos, al´em de envolverem estimativas inexatas, est ao frequentemente baseados no esvaziamento do silo. Considerando o uso de tecnologias que viabilizam a medic¸ ao eletr onica de dist ancias, angulos, e controles autom´aticos sobre atuadores que possibilitam movimentos mec anicos sobre estruturas de suporte, buscou-se o desenvolvimento de um sistema capaz de prover tanto soluc¸ oes computacionais, quanto tecnol´ogicas para o problema de c´alculo do volume de relevos irregulares, no caso dos produtos estocados nos armaz´ens. O Sistema Automatizado de Auditoria em Armaz´ens (SisA3) pretende tornar este processo autom´atico, r´apido e preciso, sem a necessidade de esvaziamento ou contato com os produtos. Para alcanc¸ar este objetivo, tem-se um sistema integrado composto de: (i) um equipamento digitalizador, consolidando o prot´otipo h´ıbrido de hardware e software denominado Dig-SisA3 , para a medic¸ ao de pontos do relevo n ao-uniforme, formado pelos produtos estocados; e (ii) m´etodo para o c´alculo do volume (iCone), que combina t´ecnicas de visualizac¸ ao cient´ıfica, interpolac¸ ao num´erica de pontos e c´alculo iterativo de volume. Al´em disto, introduz-se a paralelizac¸ ao do prot´otipo iCone, para diminuir o tempo da obtenc¸ ao dos resultados do m´etodo iCone no processo de auditoria. A an´alise sobre as perspectivas em arquiteturas multiprocessadas, multi-core e paralela distribu´ıda, utiliza o ambiente D-GM (Distributed Geometric Machine), a qual prov e os formalismos para garantir criac¸ ao, gerenciamento e processamento de aplicac¸ oes paralelas e/ou distribu´ıdas da computac¸ ao cient´ıfica, com enfase na explorac¸ ao do paralelismo de dados e nas etapas de sincronizac¸ oes. O prot´otipo de software iCone apresenta-se funcionalmente validado, incluindo an´alise de erro na execuc¸ ao do m´etodo. As an´alises de desempenho no prot´otipo p-iCone apresentaram resultados satisfat´orios. O desenvolvimento deste trabalho consolida o sistema SisA3, viabilizando aferic¸ ao autom´atica e confi´avel de estoques, incluindo ampla aplicac¸ ao no mercado

Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-07-08T01:19:32Z No. of bitstreams: 1 VladimirGuerreiro.pdf: 5547701 bytes, checksum: b807e1f8091b49a5ee1e0b36e2ae4286 (MD5) / Made available in DSpace on 2015-07-08T01:19:32Z (GMT). No. of bitstreams: 1 VladimirGuerreiro.pdf: 5547701 bytes, checksum: b807e1f8091b49a5ee1e0b36e2ae4286 (MD5) Previous issue date: 2014 / Nenhuma / Em ambientes paralelos, uma das alternativas para tratar o dinamismo, tanto em nível de infraestrutura quanto de aplicação é o uso de migração, principalmente em aplicações que executam em fases utilizando BSP (Bulk Synchronous Parallel). Neste contexto, o modelo de reescalonamento MigBSP foi desenvolvido para tratar da realocação de processos em aplica- ções paralelas. Assim como o modelo BSP, ele considera as três fases de execução de uma superetapa: (i) computação local, (ii) comunicação global e (iii) uma barreira de sincroniza- ção; coletando dados localmente durante a computação para efetuar o cálculo do Potencial de Migração (PM) do processo. Com o PM e parâmetros adicionais fornecidos no inicio da execução da aplicação, o MigBSP tem condições de escolher processos candidatos a migração em uma aplicação paralela executando em um ambiente distribuído. Entretanto, as duas heurísticas possíveis de serem utilizadas hoje, dependem de informações fornecidas pelo usuário e/ou podem não selecionar uma quantidade eficiente de processos no momento do reescalonamento, podendo ser necessário várias chamadas para balancear o ambiente. Desta forma, esta disserta- ção apresenta duas novas heurísticas, MigCube e MigHull. Elas utilizam o MigBSP e efetuam a seleção automática de processos candidatos à migração sem a interferência do programador. As informações fornecidas pelo MigBSP são utilizadas nas heurísticas, a combinação das três métricas mensurados, posicionadas em um plano tridimensional, define cada processo como um ponto no espaço que possui as coordenadas x, y e z, onde cada eixo representa uma mé- trica para tomada de decisão. A heurística MigCube monta um cubo a partir das médias das distâncias entre os pontos, utilizando o processo com o maior PM como centro do cubo. A heurística MigHull segue a definição da Envoltória Convexa, tentando envolver todos os pontos, porém utilizando duas adaptações que se fazem necessárias para a aplicação neste trabalho. O MigBSP foi desenvolvido no simulador SimGrid, e este segue sendo utilizado para a criação das duas heurísticas apresentadas nesta dissertação. Nos testes realizados neste simulador, foi possível verificar um ganho de até 45% no tempo de execução da aplicação utilizando a heurística MigHull, e até 42% utilizando a MigCube, quando comparado a aplicação sem o modelo de migração. Porém, em simulações com um maior número de processos, este ganho tende a cair, já que um dos maiores problemas do BSP e aplicações que executam em grades é o tempo de sincronização de tarefas, ou seja, quanto mais processos, maior a necessidade de sincronização, e mesmo o balanceamento dos processos acaba tendo um resultado prejudicado. / In a parallel environment, one of the alternatives to address the dynamism, both at the infrastructure and application levels, is the use of migration, mostly with applications that execute in steps using BSP (Bulk Synchronous Parallel). In this context, the rescheduling model MigBSP was developed to deal with processes reallocation in parallel applications. As BSP model, MigBSP uses the three steps of a superstep: (i) computation, (ii) communication and (iii) a synchronization barrier; collecting local data during the computation step, to compute the processes’ Potential of Migration (PM). With the PM and additional parameters provided in the beginning of the application’s execution, MigBSP have conditions to choose the processes candidate to migrate in a parallel application running in a distributed system. However, the two heuristics possible to be used today depend of information provided by the user and/or may not select the proper quantity of processes in the rescheduling moment, being necessary many executions to balance the environment. This way, this dissertation present two new heuristics, MigCube and MigHull. They make use of MigBSP, and automatically will choose the processes to migrate without user interference. The information provided by MigBSP are used in the heuristics, the combination of the three measured metrics, positioned in a three-dimensional space, defines each process as a point in space and has the coordinates x, y e z, where each axis represents a metric for decision making. The MigCube heuristic build a cube from the average of the distances between points, using the process with the highest PM as the center of the cube. The MigHull follows the definition of a Convex Hull, trying to involve all points, but using two adaptations that are necessary to implement this work. The MigBSP was developed using SimGrid simulator, and it keeps being used to creation of the two heuristics presented in this dissertation. In the conducted tests in this simulator, was possible to achieve a gain of until 45% on application execution time using MigHull, and until 42% using MigCube, when compared with the application without the migration model. However, simulations with a bigger number of processes, this gain tends to fall, since one of the bigger problems of BSP and applications that run in grid is the time of tasks synchronization, that is, as more processes, more need of synchronization, and even the processes balancing ends up having an impaired outcome.

Neste trabalho, a resposta dinâmica de um riser marítimo devido à geração e desprendimento alternado de vórtices é investigada numericamente. O riser é dividido em seções bidimensionais ao longo de seu comprimento. O Método dos Vórtices Discretos é empregado para a determinação das forças hidrodinâmicas que agem nestas seções bidimensionais. As seções hidrodinâmicas são resolvidas independentemente, e o acoplamento entre as mesmas é feito através da solução da estrutura no domínio do tempo pelo Método dos Elementos Finitos. Os resultados numéricos são comparados com resultados obtidos experimentalmente. Processamento paralelo é empregado para melhorar a performance do método. As simulações são realizadas através de uma metodologia mestre-escravo, utilizando MPI Message Passing Interface para explorar o paralelismo. A escalabilidade do algoritmo é mostrada e discutida. Este trabalho representa o desenvolvimento de um simulador que permite, efetivamente, a análise dinâmica de um riser com características e dimensões representativas das condições reais encontradas em campo, a um custo computacional factível para seu uso como uma ferramenta de engenharia. Isto é obtido por meio da técnica de processamento paralelo, aliada à solução do escoamento através de um método eficiente de CFD Método dos Vórtices Discretos e à solução da estrutura através do Método dos Elementos Finitos. / In this work the dy6namic response of a marine riser due to vortex shedding is numerically investigated. The riser is divided in two-dimensional sections along the riser length. The Discrete Vortex Method is employed for the assessment of the hydrodynamic forces acting on these two-dimensional sections. The hydrodynamic sections are solved independently, and the coupling among the sections is taken into account by the solution of the structure in the time domain by the Finite Element Method. The numerical results are compared with results obtained experimentally. Parallel processing is employed to improve the performance of the method. The simulations are carried out through a master-slave approach using MPI Message Passing Interface to exploit the parallelism. Scalability of the algorithm is shown and discussed. This work represents the development of a simulator that effectively allows the dynamic analysis of a riser with representative characteristics and dimensions of real field conditions, with a feasible computational cost for its use as an engineering tool. This is obtained by means of the parallel processing technique, together with an efficient CFD solution of the flow with de Discrete Vortex Method and the solution of the structure with the Finite Element Method.

Made available in DSpace on 2014-12-17T15:48:05Z (GMT). No. of bitstreams: 1 ChristianeAN_DISSERT.pdf: 2651034 bytes, checksum: 1c708aec5eba3fd620f2944124931c55 (MD5) Previous issue date: 2012-08-17 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The increasing complexity of integrated circuits has boosted the development of communications architectures like Networks-on-Chip (NoCs), as an architecture; alternative for interconnection of Systems-on-Chip (SoC). Networks-on-Chip complain for component reuse, parallelism and scalability, enhancing reusability in projects of dedicated applications. In the literature, lots of proposals have been made, suggesting different configurations for networks-on-chip architectures. Among all networks-on-chip considered, the architecture of IPNoSys is a non conventional one, since it allows the execution of operations, while the communication process is performed. This study aims to evaluate the execution of data-flow based applications on IPNoSys, focusing on their adaptation against the design constraints. Data-flow based applications are characterized by the flowing of continuous stream of data, on which operations are executed. We expect that these type of applications can be improved when running on IPNoSys, because they have a programming model similar to the execution model of this network. By observing the behavior of these applications when running on IPNoSys, were performed changes in the execution model of the network IPNoSys, allowing the implementation of an instruction level parallelism. For these purposes, analysis of the implementations of dataflow applications were performed and compared / A crescente complexidade dos circuitos integrados impulsionou o surgimento de arquiteturas de comunica??o do tipo Redes em chip ou NoC (do ingl?s, Network-on-Chip), como alternativa de arquitetura de interconex?o para Sistemas-em-Chip (SoC; Systems-on-Chip). As redes em chip possuem capacidade de reuso de componentes, paralelismo e escalabilidade, permitindo a reutiliza??o em projetos diversos. Na literatura, t?m-se uma grande quantidade de propostas com diferentes configura??es de redes em chip. Dentre as redes em chip estudadas, a rede IPNoSys possui arquitetura diferenciada, pois permite a execu??o de opera??es, em conjunto com as atividades de comunica??o. Este trabalho visa avaliar a execu??o de aplica??es orientadas a dados na rede IPNoSys, focando na sua adequa??o frente ?s restri??es de projeto. As aplica??es orientadas a dados s?o caracterizadas pela comunica??o de um fluxo cont?nuo de dados sobre os quais, opera??es s?o executadas. Espera-se ent?o, que estas aplica??es possam ser beneficiadas quando de sua execu??o na rede IPNoSys, devido ao seu elevado grau de paralelismo e por possu?rem modelo de programa??o semelhante ao modelo de execu??o desta rede. Uma vez observadas a execu??o de aplica??es na rede IPNoSys, foram realizadas modifica??es no modelo de execu??o da rede IPNoSys, o que permitiu a explora??o do paralelismo em n?vel de instru??es. Para isso, an?lises das execu??es de aplica??es data flow foram realizadas e comparadas

Conselho Nacional de Desenvolvimento Científico e Tecnológico / A obtenção de imagens usando tomografia computadorizada revolucionou o diagnóstico de doenças na medicina e é usada amplamente em diferentes áreas da pesquisa científica. Como parte do processo de obtenção das imagens tomográficas tridimensionais um conjunto de radiografias são processadas por um algoritmo computacional, o mais usado atualmente é o algoritmo de Feldkamp, David e Kress (FDK). Os usos do processamento paralelo para acelerar os cálculos em algoritmos computacionais usando as diferentes tecnologias disponíveis no mercado têm mostrado sua utilidade para diminuir os tempos de processamento. No presente trabalho é apresentada a paralelização do algoritmo de reconstrução de imagens tridimensionais FDK usando unidades gráficas de processamento (GPU) e a linguagem CUDA-C. São apresentadas as GPUs como uma opção viável para executar computação paralela e abordados os conceitos introdutórios associados à tomografia computadorizada, GPUs, CUDA-C e processamento paralelo. A versão paralela do algoritmo FDK executada na GPU é comparada com uma versão serial do mesmo, mostrando maior velocidade de processamento. Os testes de desempenho foram feitos em duas GPUs de diferentes capacidades: a placa NVIDIA GeForce 9400GT (16 núcleos) e a placa NVIDIA Quadro 2000 (192 núcleos). / The imaging using computed tomography has revolutionized the diagnosis of diseases in medicine and is widely used in different areas of scientific research. As part of the process to obtained three-dimensional tomographic images a set of x-rays are processed by a computer algorithm, the most widely used algorithm is Feldkamp, David and Kress (FDK). The use of parallel processing to speed up calculations on computer algorithms with the different available technologies, showing their usefulness to decrease processing times. In the present paper presents the parallelization of the algorithm for three-dimensional image reconstruction FDK using graphics processing units (GPU) and CUDA-C. GPUs are shown as a viable option to perform parallel computing and addressed the introductory concepts associated with computed tomographic, GPUs, CUDA-C and parallel processing. The parallel version of the FDK algorithm is executed on the GPU and compared to a serial version of the same, showing higher processing speed. Performance tests were made in two GPUs with different capacities, the NVIDIA GeForce 9400GT (16 cores) and NVIDIA GeForce 2000 (192 cores).

L'accroissement d'efficacite des réseaux d'interconnexion et la vulgarisation des machines multiprocesseurs permettent la réalisation de machines parallèles a mémoire distribuée de faible coût: les grappes de multiprocesseurs. Elles nécessitent l'exploitation à la fois du parallélismeà grain fin, interne à un multiprocesseur offert par la multiprogrammation légère, et du parallélisme à gros grain entre les différents multiprocesseurs. L'exploitation simultanée de ces deux types de parallélisme exige une méthode de communication entre les processus légers qui ne partagent pas le mêmme espace d'adressage. Le travail de cette thèse porte sur le problème de l'Intégration de la multiprogrammation légère et des communications sur grappes de multiprocesseurs symétriques (SMP). II porte plus précisément sur evaluation et le reglage du noyau exécutif ATHAPASCAN-0 sur ce type d'architecture. ATHAPASCAN-0 est un noyau exécutif, portable, développé au sein du projet APACHE (CNRS-INPG-INRIA-UJF), qui combine la multiprogrammation légère et la communication par échange de messages. La portabilité est assurée par une organisation en couches basée sur les standards POSIX threads et MPI largement répandus. ATHAPASCAN-0 étend le modèle de réseau statique de processus «lourds» communicants tel que MPI, PVM, etc,à celui d'un réseau dynamique de processus légers communicants. La technique de base est la multiprogrammation lègere des communications et des calculs. La progression des communications exige la scrutation de état du reseau et l'enchainement des opérations de transferts. L'efficacité repose sur la minimisation de ces opérations. De plus, l'emploi de multiprocesseurs ajoute des problèmes spécifiques dus à l'apparition d'un parallélisme réel entre calcul et communication. Ces problèmes sont présentés et des solutions sont proposées pour l'environnement ATHAPASCAN-0. Ces solutions sont évaluées sur des grappes de multiprocesseurs. / The continuous price reduction for commodity PC multiprocessors and the availability of fast network interfaces have made cluster of multiprocessors an attractive low-price alternative to build parallel systems. Multiprocessor clusters offer two levels of parallelism: a fine grain parallelism inside a single multiprocessor and a coarse grain among them. A mechanism must be provided to exploit both levels of parallelism simultaneously. This requires to provide communications between threads belonging to different addresses spaces. This dissertation addresses the problem of integrating threads and communications on ATHAPASCAN-0 run time system. ATHAPASCAN-0 is a portable run time for cluster of multiprocessors developed as part of the APACHE project (CNRS-INPG-INRIA-UJF). Portability is achieved by a layered organization based on standards like POSIX threads and MPI. The ATHAPASCAN-0 run time system extends the heavy-weight process communication model of message passing libraries such as MPI, PVM, etc, into a lighter dynamic network of communicating threads. Multiprogramming is the key concept used. Communication progress is based on a network polling basis to handle incoming messages and to deliver outgoing communications requests. Performance is strongly dependent on the way these operations are implemented. Additionally, multiprocessors introduce some programming problems like overhead of cache coherency mechanisms, method of managing concurrent accesses and efficient mutex locking to avoid unnecessary context switching. These problems are analyzed and solutions are implemented in the ATHAPASCAN-0 run time system. An evaluation of these solutions is performed on a cluster of multiprocessors.

A Microscopia de Força Atômica é uma técnica que permite a aquisição de imagens em escalas nanométricas da superfície de quase todo tipo de material. Nessa escala, porém, as imagens podem apresentar uma relação sinal/ruído pobre, causado por efeitos degenerativos em sua qualidade. Para recuperar essas imagens ou minimizar os efeitos da degradação, técnicas de restauração de imagens são empregadas. Nas últimas décadas, diversas técnicas têm sido desenvolvidas e aplicadas com essa finalidade. Dentre elas, uma técnica de restauração, descrita aqui nesta tese, baseada na minimização de um funcional de Tikhonov com termos de regularização a um parâmetro, tem sido usada há alguns anos com resultados bastante satisfatórios no tratamento de imagens obtidas com o Microscópio de Força Atômica. O uso dessa técnica, entretanto, exige um grande esforço computacional que resulta em um tempo de execução elevado quando o programa que implementa o algoritmo de restauração é processado serialmente. Além disso, à medida que os equipamentos eletrônicos aumentam as suas capacidades, as imagens obtidas por esses equipamentos aumentam de resolução, assim como o esforço computacional e o tempo gasto para analisá-las e restaurálas. Assim, com o passar do tempo, o aumento da velocidade de processamento e do desempenho do programa de restauração tem-se tornado um problema cada vez mais crítico. Com o intuito de obter uma velocidade maior de processamento, nesta tese é descrita uma estratégia de implementação do algoritmo de restauração que faz uso de técnicas de computação paralela para se desenvolver uma nova versão paralela do programa de restauração. Os resultados obtidos com essa nova versão do programa mostram que a estratégia paralela adotada reduziu os tempos de execução e produziu bons desempenhos computacionais quando comparado com outras implementações feitas do mesmo algoritmo. Além disso, a nova estratégia apresenta níveis de desempenho maiores à medida que as resoluções das imagens restauradas aumentam, possibilitando a restauração de imagens maiores num tempo proporcionalmente mais curto.