Made available in DSpace on 2013-08-07T18:42:26Z (GMT). No. of bitstreams: 1 000409163-Texto+Completo-0.pdf: 1281906 bytes, checksum: a8189d2aee06ad9ac115ad10de30a322 (MD5) Previous issue date: 2008 / The demand for computer processing power has increased in the past years, resulting in computers that provide such capacity. Sometimes different approaches have also being developed to improve computing power by joining together a set of computers, for example in clusters of computers. Currently we have access to this type of solutions but we do not use all their computing power the best way we could. This may lead to a situation in which resources are being wasted. In order to avoid the waste of computing resources, lately the use of virtual machines have been widely used. A virtual machines is a software layer that creates an environment in which several systems can be executed as if they had their own private computer. One solution that allows this approach is Xen. Xen is a paravirtualizer that allows several different operating systems to run as if they were using different computers. The scheduling of the different operating systems that are running in the same computer is performed by one of three possible strategies provided by Xen. The standard scheduler is called "SMP Credit Scheduler", which is recommended when running Xen on multiprocessing computers because it allows load balancing among virtual and real processors. Despite being the best current Xen scheduler, the SMP Credit Scheduler still does not fully use the computing power of a machine. This work proposes to improve the use of the machine by the operating systems (virtual machines) that are running on Xen. We propose a system that dynamically changes the configuration of the virtual machines. Our system will reallocate resources that are not being used by a virtual machine to a virtual machine that needs more resources. / A demanda por poder computacional é cada vez maior, e conseqüentemente leva ao desenvolvimento de equipamentos com capacidades de processamento cada vez maiores para suprí-la. Hoje em dia temos acesso a computadores com poder computacional cada vez maior, porém em sua grande maioria, esse poder computacional é apenas parcialmente utilizado, causando uma ociosidade dos recursos disponíveis, o que pode acarretar aumento de custos. Ao analisarmos a situação do aumento do poder computacional, a idéia de ociosidade de processamento da maioria dos computadores e em contrapartida, a possibilidade de uma melhor utilização de recursos, podemos explicar a renovação de tecnologias que podem vir a suprir essas necessidades. Entre várias destas tecnologias podemos citar clusters e grades computacionais, e entre outras, uma das tecnologias em ascensão são as máquinas virtuais. Uma máquina virtual consiste em um software que cria um ambiente sobre um sistema operacional, possibilitando uma execução abstraída do hardware de vários outros sistemas, sendo transparente para o usuário essa interação. Dentre vários ambientes que suportam o uso de máquinas virtuais, utilizamos o Xen que proporciona a portabilidade de sistemas operacionais sobre um sistema operacional Linux e permite compartilhar uma simples máquina para vários clientes rodando sistemas operacionais distintos. O Xen pode utilizar um de três escalonadores, onde o SMP Credit Scheduler é o escalonador padrão, recomendado para máquinas multiprocessadas por permitir balanceamento de processadores virtuais entre os processadores reais. Porém, o SMP Credit Scheduler ainda tem algumas limitações referentes a uma utilização melhor dos recursos da máquina. Com o objetivo de superar algumas dessas limitações, este trabalho apresenta a proposta e implementação de um subsistema que altera dinamicamente configurações do escalonador SMP Credit, realocando recursos destinados a máquinas virtuais que não estejam utilizando todo o processamento disponível, direcionado-as às máquinas virtuais que necessitem desse processamento. Por fim, apresentamos uma avaliação do uso desse subsistema frente ao escalonador SMP Credit em diversas configurações possíveis.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-05-06T16:17:35Z No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Rejected by Raquel Viana(raquelviana@bce.unb.br), reason: A pedido do cliente. on 2016-05-12T17:27:55Z (GMT) / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-05-12T17:33:17Z No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-16T17:20:02Z (GMT) No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Made available in DSpace on 2016-05-16T17:20:02Z (GMT). No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / A comparação de sequências biológicas é uma operação importante na Bioinformática, que é realizada frequentemente. Os algoritmos exatos para comparação de sequências obtêm o resultado ótimo calculando uma ou mais matrizes de programação dinâmica.Estes algoritmos têm complexidade de tempo O(mn), onde m e n são os tamanhos das sequências. Fickettpropôs um algoritmo que é capaz de reduzir a complexidade paraO(kn), onde k é a faixa decomputação e representa a quantidade de diagonais da matrizefetivamente calculadas. Nessa dissertação de mestrado, propomos e avaliamos oFickett-CUDAlign, uma estratégia paralela que divide a comparação de sequências emmúltiplas comparações de subsequências e calcula uma faixa de Fickett apropriada paracada comparação de sequência (bloco). Com estaabordagem, nós reduzimos potencialmenteo número de células calculadas, quando comparada ao Fickett, que usa uma únicafaixa para toda a comparação. Nossa estratégia multi-bloco ajustável foi programada emC/C++ e pthreadse foi integrada ao estágio 4 do CUDAlign, uma ferramenta do estadoda arte para comparações ótimas de sequências biológicas. O Fickett-CUDAlign foi usadopara comparar sequências reais de DNA cujo tamanho variou de 10KBP (Milhares dePares de Base) a 47MBP (Milhões de Pares de Base),alcançando um speedup de 59,60xna comparação 10MBP x 10MBP, quando comparado aoestágio 4 do CUDAlign. Nestecaso, o tempo de execução foi reduzido de 53,56 segundos para 0,90 segundo. ________________________________________________________________________________________________ ABSTRACT / Biological sequence comparison is an important task in Bioinformatics, which is frequently performed. The exact algorithms for sequence comparison obtain the optimal result by calculating one or more dynamic programming matrices. These algorithms have O(mn) time complexity, where m and n are the sizes of the sequences. Fickett proposed an algorithm which is able to reduce time complexity to O(kn), where k is the computation band and represents the amount of matrix diagonals actually calculated. In this MSc Dissertation, we propose and evaluate Fickett-CUDAlign, a parallel strategy that splits a pairwise sequence comparison in multiple comparisons of subsequences and calculates an appropriate Fickett band to each subsequence comparison (block). With this approach, we potentially reduce the number of cells calculated, when compared to Fickett, which uses a unique band to the whole comparison. Our adjustable multi-block strategy was programmed in C/C++ and pthreads and was integrated to the stage 4 of CUDAlign, a state-of-the-art tool for optimal biological sequence comparison. Fickett-CUDAlign was used to compare real DNA sequences whose sizes ranged from 10KBP (Thousands of Base Pairs) to 47MBP (Millions of Base Pairs), reaching a speedup of 59.60x in the 10MBP x 10MBP comparison, when compared to CUDAlign’s stage 4. In this case, the execution time was reduced from 53.56 seconds to 0.90 second.

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.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnologico / Made available in DSpace on 2012-10-17T02:39:58Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-08T22:20:53Z : No. of bitstreams: 1 109014.pdf: 2393890 bytes, checksum: 2354242494078046fbd1a7ae16dfce4a (MD5) / Nesta dissertação foram implementadas redes neurais artificiais visando a resolução de um fenômeno lingüístico conhecido como referência anafórica. Foram resolvidas referências anafóricas pronominais com apenas dois pronomes pessoais, a saber: ele e ela. Foram realizados dois experimentos. No primeiro utilizou-se uma rede recorrente simples para determinar a referência corretamente. No segundo foi implementado um modelo composto de duas redes neurais: uma rede recorrente simples (Parser) e uma rede direta (Segmentador). Com este modelo é possível resolver o mesmo problema do primeiro experimento com segmentos de texto compostos de um número arbitrário de sentenças.

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-17T08:10:53Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-09T00:43:22Z : No. of bitstreams: 1 143019.pdf: 2160119 bytes, checksum: 511d1dc89700ee50e9b160ac7d4072ba (MD5)

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-17T13:13:39Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-25T18:11:15Z : No. of bitstreams: 1 171570.pdf: 2365219 bytes, checksum: fe91d55c1bc48aa78c96f8bb65c51d10 (MD5) / A finalidade deste trabalho é a implementação em alto nível de uma rede de interconexão do tipo crossbar, customizada, para ser utilizada no Multicomputador Nó //. Para a implementação lógica utiliza-se a Linguagem de Descrição de Hardware - VHDL e para a implementação física, é previsto a utilização de Dispositivos Lógicos Programáveis (FPGA). Para o desenvolvimento utiliza-se o software MAX+PLUS II fornecido pela ALTERA, como Ambiente de Programação, depuração e simulação fornecidos pela ALTERA

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Ciência da Computação / Made available in DSpace on 2012-10-23T18:35:15Z (GMT). No. of bitstreams: 1 255525.pdf: 4153224 bytes, checksum: 0da857a4e789da15dbeca83bb199a295 (MD5) / Este trabalho de disserta»c~ao concentra seu esfor»co no estudo emp¶³rico de tr^es casos com ambientes de cluster distintos e homog^eneos, sendo que dois deles s~ao ambientes operacionais de empresas. Tais agregados s~ao compostos por computadores multiprocessados com processadores mono-core e multi-core (dual-core e quad-core), interconectados por redes Gigabit Ethernet, e outro ambiente interconectado por uma rede Myrinet. O primeiro estudo de caso foi realizado em um ambiente experimental como um exerc¶³cio emp¶³rico sobre a rela»c~ao entre tecnologias de rede de interconex~ao e carac- ter¶³sticas inerentes a aplica»c~oes paralelas. Com isso, pretendeu-se entrar em contato com a realidade da computa»c~ao paralela por meio de arquiteturas paralelas distribu¶³das como os agregados de computadores. Al¶em disso, pode-se conhecer e analisar as diferen»cas em desempenho oferecido por sistemas de comunica»c~ao distintos, como a tecnologia de rede Myrinet face µa tecnologia Ethernet, diante de aplica»c~oes de granularidades distintas, bem como compreender as m¶etricas comumente adotadas em avalia»c~oes de desempenho. Dentre as contribui»c~oes do trabalho de pesquisa e experimenta»c~ao desenvolvido est¶a a redu»c~ao do tempo de execu»c~ao de aplica»c~oes cient¶³¯cas grand challenge, como a modelagem num¶erica de previs~ao meteorol¶ogica. Sendo assim, busca-se como resultado a otimiza»c~ao de desempenho do ambiente de cluster em compara»c~ao µa sua condi»c~ao anterior, sem nenhuma especializa»c~ao µa aplica»c~ao em foco. Nesse sentido, dois estudos de casos foram realizados em agregados de computadores pertencentes a organiza»c~oes, em uma aproxima»c~ao com a realidade da computa»c~ao de alto desempenho em ambientes de produ»c~ao. Com a realiza»c~ao deste estudo emp¶³rico como um todo, pode-se contrastar na pr¶atica os pontos estudados durante a revis~ao bibliogr¶a¯ca. Foi poss¶³vel compreender melhor as vantagens e desvantangens envolvidas nesses ambientes enquanto sistemas paralelos distribu¶³dos, com o foco voltado µa modelagem de sistemas de alto desempenho em ambientes de produ»c~ao. Durante o processo de otimiza»c~ao do desempenho, entrou-se em contato com os mecanismos de intera»c~ao entre processos e os modelos de programa»c~ao paralela envolvidos ao mesmo tempo em que investigou-se o impacto da tend^encia atual no que diz respeito a processadores multi-core, bem como os fatores redutores do desempenho (que resultam em overhead). En¯m, o conhecimento adquirido com os estudos de casos possibilita uma melhor compreens~ao do processo e dos fatores envolvidos na implementa»c~ao de ambientes de cluster adequados a cada aplica»c~ao paralela com demanda por alto desempenho, a ¯m de aproveitar melhor os recursos agregados. Al¶em disso, a import^ancia deste trabalho transcende µa ci^encia da computa»c~ao como disciplina acad^emica, pois a empresa parceira ganha em capacidade e qualidade na previs~ao meteorol¶ogica do tempo, seja para prevenir o impacto de desastres naturais ou para auxiliar na produ»c~ao agr¶³cola, e tamb¶em em potencial de pesquisa no ^ambito daquela ¶area de atua»c~ao. This dissertation concentrates its e®ort on the empirical study of three cases with distinct and homogeneous cluster con¯gurations, two of them operational environments at organizations. Theses clusters are equipped with multiprocessor computers, including multiple single-core and multi-core processors (dual-core and quad-core), interconnected by Gigabit Ethernet networks, and one environment interconnected with a Myrinet device. The ¯rst case study was performed on an experimental environment as an empiri-cal exercise about the relationship between interconnect technologies and characteristics inherent to parallel applications, in order to get in touch with the reality of parallel computing through parallel distributed architectures such as a cluster. Furthermore, we could acknowledge and analyze the di®erences in performance o®ered by di®erent communication systems, opposing Myrinet and Ethernet networking technologies before applications of di®erent granularity, as well as understand common metrics adopted for performance assessments. One of the contributions of this empirical and research work is to reduce the wall clock (or elapsed) time of grand challenge scienti¯c applications, such as numerical weather prediction models. Therefore, it should result in a better performance of the cluster environment compared to its previous condition, with no adaptation for the running application. Based on that, two case studies were conducted on operational clusters belonging to organizations in order to interact with the reality of high performance computing in production environments. Performing this empirical study as a whole confronts the knowledge obtained throughout the literature review putting them into practice. Moreover, we could accomplish a better understanding of the trade-o®s involved in cluster environments as distributed parallel systems for production environments from the point of view of an architectural designer. During this optimization process, we could understand the mechanisms for pro-cesses interaction and parallel programming models as well as the factors for overhead growth and performance reduction. Finally, the knowledge acquired with these case studies allow us to better comprehend the process and the factors involved in the implementation and adaptation of cluster en vironments to a speci¯c high performance application, in order to better employ the aggregated computing resources. Furthermore, the importance of this work transcends computer sciences as an academic subject, because the partner organization gains capacity and quality for predicting weather conditions, either to prevent us from the impact of natural disasters or to enhance agricultural production, as well as gains in research potential within that speci¯c area.

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.

A paralelização de aplicaçõpes envolvendo a solução de problemas definidos sob o escopo da Dinâmica dos Fluidos Computacional normalmente é obtida via paralelismo de dados, onde o domínio da aplicação é dividido entre os diversos processadores, bem como a manutenção do balancecamento durante a execução é um problema complexo e diversas heurísticas têm sido desenvolvidas. Aplicações onde a simulação é dividida em diversas fases sobre partes diferentes do domínio acrescentam uma dificuldade maior ao particionamento, ao se buscar a distirbuição equlibrada das cargas em todas as fases. este trabalho descreve a implementação de mecanismos de particionamento e balanceamento de carga em problemas multi-fase sobre clusters de PCs. Inicialmente é apresentada a aplicação desenvolvida, um modelo de circulação e transporte de susbtâncias sobre corpos hídricos 2D e 3 D, que pode ser utilizado para modelar qualquer corpo hídrico a partir da descrição de sua geometria, batimetria e condições de contorno. Todo o desenvolvimento e testes do modelo foi feito utilizando como caso de estudo o domínio do Lago Guaíba, em Porto Alegre. Após, são descritas as principais heurísticas de particionamento de domínio de aplicações multi-fase em clusters, bem como mecanismos para balanceamento de carga para este tipo de aplicação. Ao final, é apresentada a solução proposta e desenvolvida, bem como os resultados obtidos com a mesma.

O desenvolvimento de aplicações de forma a atingir níveis de desempenho próximos aos níveis teóricos de uma determinada plataforma é uma tarefa que exige conhecimento técnico do ambiente de hardware, uma vez que o software deve explorar detalhes específicos da plataforma em questão. Pelo fato do software ser específico à plataforma, caso ela evolua ou se altere, as otimizações realizadas podem não explorar a nova arquitetura de forma eficiente. Auto-tuners são sistemas que surgiram como um meio automatizado de adaptar um determinado software a uma arquitetura alvo. Essa adaptação ocorre através de uma busca empírica de valores ótimos para parâmetros específicos de uma aplicação, a fim de ajustá-los às características do hardware, ou ainda através da geração de códigofonte otimizado para a plataforma. Este trabalho propõe um módulo auto-tuner orientado à adaptação parametrizada de uma aplicação paralela, que trabalha variando os fatores da dimensão do domínio bidimensional, o número de processos e a extensão das regiões de sobreposição. Para cada variação dos fatores, o auto-tuner testa a aplicação na arquitetura paralela de forma a buscar a combinação de parâmetros com melhor desempenho. Para possibilitar o auto-tuning, foi desenvolvida uma classe em linguagem C++ denominada Mesh, baseada no padrão MPI. A classe busca abstrair a decomposição de domínios de uma aplicação paralela por meio do uso de Orientação a Objetos, e facilita a variação da extensão das regiões de sobreposição entre os subdomínios. Os resultados experimentais demonstraram que o auto-tuner explora o ganho de desempenho pela variação do número de processos da aplicação, que também é tratado pelo módulo auto-tuner. A arquitetura paralela utilizada na validação não se mostrou ideal para uma otimização através do aumento da extensão das regiões sobrepostas entre subdomínios. / Achieving the peak performance level of a particular platform requires technical knowledge of the hardware environment involved, since the software must explore specific details inherent to the hardware. Once the software is optimized for a target platform, if the hardware evolves or is changed, the software probably would not be as efficient in the new environment. This performance portability problem is addressed by software auto-tuning, which emerged in the past decade as an automated technique to adapt a particular software to an underlying hardware. The software adaptation is performed by an auto-tuner. The auto-tuner is an entity that empirically adjusts specific application parameters in order to improve the overall application performance, or even generates source-code optimized for the target platform. This dissertation proposes an auto-tuner to optimize the domain decomposition of a parallel application that performs stencil computations. The proposed auto-tuner works in a parameterized adaptation fashion, and varies the dimensions of a 2D domain, the number of parallel processes and the extension of the overlapping zones between subdomains. For each combination of parameter values, the auto-tuner probes the application in the parallel architecture in order to seek the best combination of values. In order to make auto-tuning possible, it is proposed a C++ class called Mesh, based on the Message Passing Interface (MPI) standard. The role of this class is to abstract the domain decomposition from the application using the Object Orientation facilities provided by C++, and also to enable the extension of the overlapping zones between subdomain. The experimental results showed that the performance gains were mainly due to the variation of the number of processes, which was one of the application factors dealt by the auto-tuner. The parallel architecture used in the experiments showed itself as not adequate for optimizing the domain decomposition by increasing the overlapping zones extension.