Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-08-22T17:39:55Z No. of bitstreams: 1 ADRIANO_JOS?_VOGEL_DIS.pdf: 2344216 bytes, checksum: e0dd6229d4a98c039e793851290beab0 (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-08-24T14:50:33Z (GMT) No. of bitstreams: 1 ADRIANO_JOS?_VOGEL_DIS.pdf: 2344216 bytes, checksum: e0dd6229d4a98c039e793851290beab0 (MD5) / Made available in DSpace on 2018-08-24T17:31:58Z (GMT). No. of bitstreams: 1 ADRIANO_JOS?_VOGEL_DIS.pdf: 2344216 bytes, checksum: e0dd6229d4a98c039e793851290beab0 (MD5) Previous issue date: 2018-03-28 / As aplica??es de stream se tornaram cargas de trabalho representativas nos sistemas computacionais. Diversos dom?nios de aplica??es representam stream, como v?deo, ?udio, processamento de gr?ficos e imagens. Uma parcela significativa dessas aplica??es demanda paralelismo para aumentar o desempenho. Por?m, programadores frequentemente enfrentam desafios entre produtividade de c?digo e desempenho devido ?s complexidades decorrentes do paralelismo. Buscando facilitar a paraleliza??o, a DSL SPar foi criada usando atributos (stage, input, output, and replicate) do C++-11 para representar paralelismo. O compilador reconhece os atributos da SPar e gera c?digo paralelo automaticamente. Um desafio relevante que ocorre em est?gios paralelos da SPar ? a demanda pela defini??o manual do grau de paralelismo, o que consome tempo e pode induzir a erros. O grau de paralelismo ? definido atrav?s do n?mero de r?plicas em est?gios paralelos. Por?m, a execu??o de diversas aplica??es pode ser pouco eficiente se executadas com um n?mero de r?plicas inadequado ou usando um n?mero est?tico que ignora a natureza din?mica de algumas aplica??es. Para resolver esse problema, ? introduzido o conceito de um n?mero de r?plicas transparente e adaptativo para a SPar. Al?m disso, os mecanismos implementados e as regras de transforma??o s?o descritos para possibilitar a gera??o de c?digo paralelo na SPar com um n?mero adaptativo de r?plicas. Os mecanismos adaptativos foram avaliados demonstrando a sua efic?cia. Ainda, aplica??es reais foram usadas para demonstrar que os mecanismos adaptativos propostos podem oferecer abstra??es de alto n?vel sem significativas perdas de desempenho. / In recent years, stream processing applications have become a traditional workload in computing systems. They are traditionally found in video, audio, graphic and image processing. Many of these applications demand parallelism to increase performance. However, programmers must often face the trade-off between coding productivity and performance that introducing parallelism creates. SPar Domain-Specific Language (DSL) was created to achieve the optimal balance for programmers, with the C++-11 attribute annotation mechanism to ensure that essential properties of stream parallelism could be represented (stage, input, output, and replicate). The compiler recognizes the SPar attributes and generates parallel code automatically. The need to manually define parallelism is one crucial challenge for increasing SPAR?s abstraction level, because it is time consuming and error prone. Also, executing several applications can fail to be efficient when running a non suitable number of replicas. This occurs when the defined number of replicas in a parallel region is not optimal or when a static number is used, which ignores the dynamic nature of stream processing applications. In order to solve this problem, we introduced the concept of the abstracted and adaptive number of replicas for SPar. Moreover, we described our implemented strategy as well as transformation rules that enable SPar to generate parallel code with the adaptive degree of parallelism support. We experimentally evaluated the implemented adaptive strategies regarding their effectiveness. Thus, we used real-world applications to demonstrate that our adaptive strategy implementations can provide higher abstraction levels without significant performance degradation.

Este trabalho tem o intuito de fazer uso do processamento paralelo na análise não linear de cascas pelo método dos elementos finitos. O elemento finito de casca é obtido com o acoplamento de um elemento de placa e um de chapa. O elemento de placa utiliza formulação de Kirchhof (DKT) para placas delgadas e o elemento de chapa faz uso da formulação livre (FF), introduzindo um grau de liberdade rotacional nos vértices. A análise não-linear com plasticidade utiliza o modelo de plasticidade associada com algoritmo de integração explícito, modelo de escoamento de von Mises com integração em camadas (modelo estratificado), para materiais isotrópicos. A implementação em paralelo é realizada em um sistema com memória distribuída e biblioteca de troca de mensagens PVM (Parallel Virtual Machine). O procedimento não-linear é completamente paralelizado, excetuando a impressão final de resultados. As etapas que constituem o método dos elementos finitos, matriz de rigidez da estrutura e resolução do sistema de equações lineares são paralelizadas. Para o cálculo da matriz de rigidez utiliza-se um algoritmo com decomposição de domínio explícito. Para resolução do sistema de equações lineares utiliza-se o método dos gradientes conjugados com implementação em paralelo. É apresentada uma breve revisão bibliográfica sobre o paralelismo, com comentários sobre perspectivas em análise estrutural / This work aims at using parallel processing for nonlinear analysis of shells through finite element method. The shell finite element is obtained by coupling a plate element with a membrane one. The plate element uses Kirchhoff’s formulation (DKT) for thin plates and the membrane element makes use of the free formulation (FF), introducing a rotational degree of freedom at the vertexes. Nonlinear plastic analysis uses associated plasticity model with explicit integration algorithm, von Mises yelding model with layer integration (stratified model) for isotropic materials. Parallel implementation is done on a distributed memory system and message exchange library PVM (Parallel Virtual Machine). Nonlinear procedure is completely parallelised, but final printing of results. The finite element method steps, structural stifness matrix and solution of the linear equation system are parallelised. An explicit domain decomposition algorithm is used for the stifness matrix evaluation. To solve the linear equation system, one uses conjugated gradients method, with parallel implementation. A brief bibliography about parallelism is presented, with comments on structural analysis perspectives

Este trabalho teve como finalidade a implementação de um método para a paralelização parcial de programas, escritos na linguagem funcional, SISAL utilizando as bibliotecas do padrão MPI (Message Passing Interface). Para tal, propusemos a transformação dos programas SISAL através do particionamento do loop paralelo forall, através do método de particionamento slice e a utilização do modelo de implementação do paralelismo SPMD (Single Program Multiple Data) no estilo de programas mestre/escravo. A validação de nossa proposta foi obtida através da realização de testes onde foram comparados os resultados obtidos com os programas originais e os programas com as alterações propostas / This work describes a method for the partial parallelization of SISAL programs into programs with calls to MPI routines. We focused on the parallelization of the forall loop (through slicing of the index range). The generated code is a master/slave SPMD program. The work was validated through the compilation of some simple SISAL programs and comparison of the results with an unmodified version

Made available in DSpace on 2014-06-12T17:36:05Z (GMT). No. of bitstreams: 2 arquivo7119_1.pdf: 2897021 bytes, checksum: 6c54b56dbdc59f5e101d0042be325a2b (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / O gerenciamento automático da memória dinâmica, conhecido como coleta de lixo (garbage collection), se tornou uma necessidade na maioria das linguagens de programação em uso atualmente. Dentre as técnicas para realizar o gerenciamento automático da memória, a contagem de referências se mostra vantajosa por uma série de razões, dentre elas o fato de ser uma técnica naturalmente incremental, o que evita a parada completa do processo do usuário para realizar tarefas de administração da memória. A natureza incremental da contagem de referências indica que o algoritmo pode ser adaptado para uma versão em sistemas multiprocessados, mantendo sua característica não suspensiva no programa do usuário. Entretanto, os problemas causados pela necessidade de sincronização entre threads pode anular os ganhos de eficiência obtidos com essa extensão, inviabilizando o uso de um coletor de lixo baseado em contagem de referências em um ambiente multiprocessado. Nesta tese apresenta-se um conjunto de algoritmos eficientes para utilizar a contagem de referências em sistemas com vários processadores, tendo como foco principal o algoritmo para contagem de referências para vários mutadores e um coletor. Este algoritmo foi implementado na máquina virtual Java Jikes RVM e seu desempenho testado em relação a coletores alternativos; os resultados de tais testes indicam que o algoritmo proposto tem desempenho competitivo com outros coletores similares, mas impõe tempos de pausa muito menores ao programa do usuário. A presente tese também apresenta uma prova informal da corretude do algoritmo proposto

Made available in DSpace on 2014-06-12T17:36:54Z (GMT). No. of bitstreams: 2 arquivo2635_1.pdf: 1615049 bytes, checksum: 0bfad898b05e2327f8bd4385c52f1fb8 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / O gerenciamento automático da memória utilizada por um programa se tornou uma necessidade na maioria das linguagens de programação em uso atualmente, cujas implementações incluem em sua maioria um coletor de lixo para administrar a memória utilizada. Dentre as técnicas para realizar o gerenciamento automático da memória, a contagem de referências se mostra popular por uma série de vantagens, dentre elas o fato de ser uma técnica naturalmente incremental, o que evita a parada completa da computação para realizar tarefas de administração da memória. Esta natureza incremental da contagem de referências indica que o algoritmo pode ser extendido para uma versão concorrente, em sistemas multiprocessados, com facilidade. Entretanto, o problema da sincronização pode anular os ganhos de eficiência obtidos com essa extensão, inviabilizando o uso de um coletor de lixo concorrente. Nesta dissertação apresenta-se uma nova arquitetura para implementar concorrentemente o gerenciamento automático da memória baseado na contagem de referências; esta proposta está baseada em versões anteriores do algoritmo seqüencial para contagem de referências e da arquitetura para contagem de referências concorrentes, mas tem como diferencial o uso de sincronização bastante eficiente. Os resultados de testes realizados com uma implementação desta nova arquitetura indicam que, de fato, a eficiência obtida compensa o seu uso em sistemas multiprocessados

Made available in DSpace on 2015-04-22T22:10:46Z (GMT). No. of bitstreams: 1 leand.pdf: 1294573 bytes, checksum: d10eb21cbecb9685945b11331d660860 (MD5) Previous issue date: 2010-02-08 / The production line concept introduction by Henry Ford, brought a great enhancement in the resource usage efficiency and transformation during the industrial process. Afterwards Ohno (1988) presented that during the industrial process all the waste should be removed from the process. Ohno also explains that waste is any activity that do not aggregate value in the final product. As a production test do not aggregate value, it simply ensure the product reliability, this paper has the purpose to develop a methodology to evaluate, identify and reduce the longest tests time of an electronic test sequence without decrease the product quality. Based on the instrument driver s utilization is possible to identify opportunities points to be executed concurrently (parallelism). The execution of two or more tests in parallel make possible the time reduction of the whole product test. One baseline of times and results were created to act as a benchmark and based on statistical process control indexes such as result mean and standard deviation and also the test acceptance limits cpk index, it will be possible to confirm the methodology efficacy and efficiency. Besides the methodology, the paper also refers the analysis and automation tools that were created during the time optimization project. / A introdução do conceito de linha de montagem por Henry Ford, trouxe um grande avanço à eficiência do uso dos recursos e transformações durante o processo fabril. Mais tarde com Ohno (1988), mostrou-se que durante o processo fabril, todo o desperdício deve ser removido do processo. Ohno ainda explica que desperdício é toda atividade que não agrega valor ao produto final. Como o teste de produção não agrega valor ao produto final, apenas garante a confiabilidade do mesmo, o presente trabalho tem como objetivo desenvolver uma metodologia para identificar e reduzir os tempos de testes mais demorados de uma sequência de testes de produtos eletrônicos sem que seja diminuída a qualidade dos produtos. Baseado na análise da utilização dos instrumentos dos testes é possível a identificação dos pontos candidatos a serem executados concorrentemente (paralelismo). A execução de dois ou mais testes em paralelo nas sequências torna possível a redução do tempo total de testes do produto. Um histórico dos tempos e resultados foi catalogado para através da utilização de índices estatísticos como a média e o desvio padrão dos resultados, juntamente com o índice Cpk dos limites dos testes, poder comprovar não só a eficiência, mas também a eficácia da metodologia. Além da metodologia, o trabalho também cita as ferramentas de análise e automação de redução de tempos de testes que foram desenvolvidas ao longo do projeto. A metodologia se mostrou eficaz e não apenas os tempos de testes foram reduzidos, mas, também, os resultados se mostraram igualmente confiáveis.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A construÃÃo de novas aplicaÃÃes voltadas à ComputaÃÃo de Alto Desempenho (CAD) tÃm exigido ferramentas que conciliem um alto poder de abstraÃÃo e integraÃÃo de software. Dentre as soluÃÃes apresentadas pela comunidade cientÃfica estamos particularmente interessados naquelas baseadas em tecnologia de componentes. Os componentes tÃm sido usados para abordar novos requisitos de aplicaÃÃes de alto desempenho, entre as quais destacamos: interoperabilidade, reusabilidade, manutenibilidade e produtividade. As abordagens das aplicaÃÃes atuais baseadas em tecnologia de componentes, no entanto, nÃo conseguem abstrair formas mais gerais de paralelismo de maneira eficiente, tornando ainda o processo de desenvolvimento difÃcil, principalmente se o usuÃrio for leigo no conhecimento das peculiaridades de arquiteturas de computaÃÃo paralela. Um tempo precioso, o qual deveria ser utilizado para a soluÃÃo do problema, à perdido na implementaÃÃo eficiente do cÃdigo de paralelizaÃÃo. Diante desse contexto, esta dissertaÃÃo apresenta o HPE (Hash Programming Environment), uma soluÃÃo baseada no modelo # de componentes paralelos e na arquitetura Hash. O HPE define um conjunto de espÃcies de componentes responsÃveis pela construÃÃo, implantaÃÃo e execuÃÃo de programas paralelos sobre clusters de multiprocessadores. A arquitetura Hash à constituÃda de trÃs mÃdulos distintos: o Front-End, o Back-End e o Core. A contribuiÃÃo principal deste trabalho reside na implementaÃÃo de um Back-End, como uma plataforma de componentes paralelos que estende o Mono, plataforma de componentes de cÃdigo aberto baseado no padrÃo CLI (Common Language Interface). Feito isso, unimos o back-End Ãs implementaÃÃes jà existentes do Front-End e do Core, ambos em java e sobre a plataforma de desenvolvimento Eclipse, atravÃs de serviÃos web (web service). Ao final, apresentaremos um pequeno teste de conceito, construÃdo por um programa paralelo construÃdo a partir de componentes #, segundo as premissas e conceitos apresentados neste trabalho. / The development of new High Performance Computing (HPC) application has demanded a set of tools for reconciling high level of a abstraction with software integration. In particular, we are interested in component-based solutions presented by the scientific community in the last years. Components have been applied to meet new requirements of high performance application such as: interoperability, reusability, maintainability and productivity. Recent approaches for component based development time in HPC context, however, have not reconciled more expressive ways for parallel programming and efficiency. Unfortunately, this issue increases the software development time and gets worse when user have poor knowledge of architectural details of parallel computers and of requirements of applications. Precious time is lost optimizing parallel code, probably with non-portable results, instead of being applied to the solutions of the problem. This dissertation presents the Hash Programming Environment (HPE), a solution based on the # (reads "Hash") Component Model and on the Hash Framework Architecture. HPE defines a set of component kinds for building, deploying and executing parallel programs targeted at clusters of multiprocessors. The Hash Framework Architecture has three loosely coupled modules: the Front-End, the Back-End and the Core. The main contribution of this work is the implementation of the Back-End and the Core. The main contribution of this work is the implementation of the Back-End, since we have an early version of the Front-End and Core, both developed in Java on top of the Eclipse Platform. The Back-End was implemented as a parallel extension of a Mono, an open source component platform based on CLI (Common Language Interface) standard. Once independently done, we bound all the modules together, using web services technology. For evaluating the proposed Back-End, we have developed a small conceptual test application, composed by # components.

Entre todas las ideas esparcidas por la Ciencia de la Computación en los últimos años, pocas han transformado el área de manera tan profunda como la computación paralela. Virtualmente todos los aspectos se vieron afectados, y se generó un gran número de conceptos nuevos. Desde la Arquitectura de Computadoras hasta los Sistemas Operativos, desde los Lenguajes de Programación y Compiladores hasta Bases de Datos e Inteligencia Artificial, y desde la Computación numérica hasta las Combinatorias, cada rama sufrió un renacimiento. / Tesis doctoral de la Facultad de Informática (UNLP). Grado alcanzado: Doctor en Ciencias Informáticas. Director de tesis: Guillermo Simari; co-director de tesis: Emilio Luque y Marcelo Naiouf.

La evaluación de yacimientos mineros tiene por objetivo estimar, con el menor error posible, la calidad y cantidad de un recurso mineral, que tiene potencial de ser explotado. Una de las principales herramientas utilizadas es la Geoestadística, la cual pone énfasis en el contexto geológico y la relación espacial entre los datos a estudiar. Los métodos de estimación tradicionales, llamados Kriging, calculan el mejor estimador lineal insesgado de una variable en base a los valores de datos vecinos. Para representar de mejor manera la variabilidad espacial de los datos, se recurre a la Simulación Convencional, que consiste en añadir un factor aleatorio a Kriging para obtener una distribución de escenarios, que sirven como medida de la respuesta ante la incerteza. El inconveniente de esta técnica es que no permite correlacionar diversos puntos al mismo tiempo, sólo se pueden correlacionar dos puntos a la vez (se basa en la covarianza de 2 puntos). Este hecho representa una potencial pérdida de información en la construcción del modelo que se utilizará para realizar estimaciones o simulaciones. Al correlacionar dos puntos a la vez, se induce una suavización sobre las estimaciones, lo cual puede entregar resultados sobreestimados o subestimados. Para solucionar el problema anterior, se propone utilizar métodos que contemplan estadísticas de múltiples puntos, representadas por patrones. Se espera que la utilización de patrones junto a un método de simulación no convencional llamado Recocido Simulado (Simulated Annealing) puedan tener un mejor desempeño al evaluar un proceso que la simulación convencional. Los principales problemas del método propuesto son el tiempo de cálculo del Recocido Simulado y el manejo de patrones grandes. Se optó por resolver el primero de ellos y dejar abierta la puerta para posibles trabajos a futuro en la optimización de las estructuras de datos para el manejo de patrones grandes. El tiempo de cálculo del Recocido Simulado aumenta exponencialmente al incrementar el tamaño de los patrones a estudiar. Para solucionar esto, se realizó una implementación utilizando múltiples procesos, configurados según una técnica llamada Computación Especulativa, la cual permite realizar varios pasos de la simulación a la vez. Se estudió el speedup teórico de la paralelización y se realizaron pruebas numéricas, las cuales entregaron resultados satisfactorios en tiempo y en calidad de la imagen simulada.

Com o crescente aumento das funcionalidades dos circuitos integrados, existe um aumento consequente da complexidade do projeto dos mesmos. O fluxo de projeto de circuitos integrados inclui em um de seus passos o roteamento, que consiste em criar fios que interconectam as células do circuito. Devido à complexidade, o roteamento é dividido em global e detalhado. O roteamento global de circuitos VLSI é uma das tarefas mais complexas do fluxo de síntese física, sendo classificado como um problema NP-completo. Neste trabalho, além de realizar um levantamento de trabalhos que utilizam as principais técnicas de paralelismo com o objetivo de acelerar o processamento do roteamento global, foram realizadas análises nos arquivos de benchmark do ISPD 2007/08. Com base nestas análises foi proposto um método que agrupa as redes para então verificar a existência de dependência de dados em cada grupo. Esta verificação de dependência de dados, que chamamos neste trabalho de colisor, tem por objetivo, criar fluxos de redes independentes umas das outras para o processamento em paralelo, ou seja, ajudar a implementação do roteamento independente de redes. Os resultados demonstram que esta separação em grupos, aliada com a comparação concorrente dos grupos, podem reduzir em 67x o tempo de execução do colisor de redes se comparada com a versão sequencial e sem a utilização de grupos. Também foi obtido um ganho de 10x ao comparar a versão com agrupamentos sequencial com a versão paralela. / With the increasing of the functionality of integrated circuits, there is a consequent increase in the complexity of the design. The IC design flow includes the routing in one of its steps, which is to create wires that interconnect the circuit cells. Because of the complexity, routing is divided into global and detailed. The global routing of VLSI circuits is one of the most complex tasks in the flow of physical synthesis and it's classified as an NP-complete problem. In this work, a parallel computing techniques survey was applied to the VLSI global routing in order to accelerate the global routing processing analyzes. This analyzes was performed on the ISPD 2007/08 benchmark files. We proposed a method that groups the networks and then check for data dependence in each group based on these analyzes. This data dependency checking, we call this checking of collider, aims to create flow nets independent of each other for processing in parallel, or help implement the independent routing networks. The results demonstrate that this separation into groups, together with the competitor comparison of groups, can reduce 67x in the collider networks runtime compared with the sequential release and without the use of groups. It was also obtained a gain of 10x when comparing the version with sequential clusters with the parallel version.