Página 1 dos resultados de 118 itens digitais encontrados em 0.023 segundos

Modelagem e simulação de algoritmos paralelos baseados em operações com DNA; DNA-Based modelling and simulation of parallel algorithms

Cervo, Leonardo Vieira
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Dissertação Formato: application/pdf
Português
Relevância na Pesquisa
56.67%
A área de biologia computacional está vivendo um crescimento rápido causado pela revolução no estudo de genômas e pelo avanço das técnicas de manipulação do material genético. Com essas novas tecnologias para manipulação de seqüências, a importância de achar uma solução eficiente para os problemas chamados de intratáveis também cresceu, pois muitos problemas envolvidos na análise de DNA pertencem a essa classe de problemas. Uma abordagem para achar essas soluções é usar o próprio DNA para realizar computação, aproveitando o paralelismo massivo utilizado em operações que manipulam seqüências de DNA. Isto é estudado na área de computação com DNA. Esse trabalho propõe um modelo formal para representar a estrutura da molécula de DNA e das operações que são realizadas com ela em laboratório. Este modelo ajuda a preencher a necessidade de uma descrição matemática que possa ser usada para analisar algoritmos baseados em DNA, assim como possibilitar a simulaç~o desses algoritmos em um computador. Foi utilizada a teoria de gramáticas de grafos, uma linguagem de especificação formal, para modelar as seqüências de DNA e suas I operações. O trabalho apresenta um estudo da estrutura da molécula de DNA...

Algoritmos de Thinning e suas aplicações

Prates, Jorge Marques
Fonte: Universidade Estadual Paulista (UNESP) Publicador: Universidade Estadual Paulista (UNESP)
Tipo: Trabalho de Conclusão de Curso
Português
Relevância na Pesquisa
46.55%
This monograph aims to study the problem of thinning, also known by Image Skeletonization, to explore their applications in areas such as, Biometrics, Medicine, Engineering and Cartography. The algorithms of thinning can be classi ed into two major groups: iterative algorithms and non-iterative algorithms. Iterative are sub-divided into sequential algorithms and parallel algorithms. In order to develop a computer system able to extract the skeleton of an image, were studied, analyzed and implemented di erent algorithms for this problem, precisely those of Stentiford, Zhang Suen, and Holt; A presente monografia tem como propósito estudar o problema de thinning, conhecido também por Afinamento ou Esqueletonização de Imagens, explorar suas aplicações em areas, como, por exemplo, Biometria, Medicina, Engenharia e Cartografia. Os algoritmos de thinning podem ser classificados em dois grandes grupos: algoritmos iterativos e algoritmos não-iterativos. Os iterativos são sub-divididos em algoritmos sequenciais e algoritmos paralelos. Visando o desenvolvimento de um sistema capaz de extrair o esqueleto de uma imagem foram pesquisados, analisados e implementados diferentes tipos de algoritmos para esse problema, mais precisamente os de Stentiford...

Processamento paralelo de algoritmos de controle hierarquico

Jose Tarcisio Costa Filho
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 29/07/1988 Português
Relevância na Pesquisa
46.51%
Neste trabalho estudamos e alteramos a estrutura de cálculo de algorítimos de controle hierárquico com a finalidade de obter procedimentos de parelização que permitam implementação eficiente em arquiteturas de múltiplos processadores, bem como realizamos experimentos em processamento paralelos destes algoritimos; In this work we have studied and chaged the calculation structure of hierarchical control algorithms with the objective of developing parallelizacion produres allowing the efficient implementation in multiprocessors architecture, as well as we made experiments the parallel processing of these algorithms

Avaliação de algoritmos de ordenação em sistemas paralelos

Anna Catharina da Costa Dantas
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 19/12/1997 Português
Relevância na Pesquisa
57.02%
A classificação ou ordenação de dados tem assumido grandes proporções no âmbito do processamento de informações, tanto devido a sua importância na análise de desempenho quanto pelo fato de ser utilizado como processo intermediário em diversas aplicações. Os primeiros estudos sobre ordenação se deram a partir dos algoritmos seqüenciais. Entretanto, o tamanho crescente das aplicações tratadas vem impondo maior demanda de tempo de execução e memória, provocando uma necessidade de evolução. Para tentar minimizar os efeitos de complexidade dos algoritmos seqüenciais de ordenação, diversos algoritmos paralelos vêm sendo propostos. A combinação entre a tecnologia disponibilizada pelo processamento paralelo e a eficiência dos algoritmos de ordenação produz algoritmos paralelos de ordenação com alto poder de computação. Esse trabalho avalia alguns dos algoritmos paralelos de ordenação interna disponíveis na literatura, aplicáveis ou adaptados a multicomputadores MIMD de memória distribuída, interconectados por redes locais. Alguns benchmarks com diferentes características de distribuição de probabilidade foram implementados para validar os resultados apresentados, obtidos a partir da execução paralela suportada por bibliotecas de comunicação por troca de mensagens; Data sorting has assumed large proportions in the field of information processing...

Produtos de kronecker, simetrizadoras e algoritmos paralelos e sequenciais na algebra linear

Karabi Datta
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 01/08/1982 Português
Relevância na Pesquisa
46.51%
Não informado.; Not informed.

Algoritmos paralelos para árvores de cortes e medidas de centralidade em grafos

Cohen, Jaime
Fonte: Universidade Federal do Paraná Publicador: Universidade Federal do Paraná
Tipo: Tese de Doutorado Formato: application/pdf
Português
Relevância na Pesquisa
56.76%
Resumo: Uma árvore de cortes é uma representação compacta da aresta-conectividade de um grafo não orientado. As árvores de cortes resolvem de maneira eficiente o problema de calcular a arestaconectividade entre todos os pares de vértices do grafo. As árvores de cortes têm muitas aplicações como, por exemplo, no projeto de redes confiáveis, na partição de grafos, no agrupamento em grafos, na análise de redes sociais, dentre outras. Dois algoritmos para a construção de árvores de cortes de grafos não orientados e capacitados são bem conhecidos: o algoritmo de Gomory-Hu e o algoritmo de Gusfield. Este trabalho apresenta propostas de implementações paralelas de três algoritmos para encontrar uma árvore de cortes. Versões paralelas para os algoritmos de Gusfield e de Gomory-Hu são descritas e avaliadas experimentalmente. Um algoritmo híbrido que combina esses dois algoritmos e que busca tirar proveito das vantagens de cada um deles também é apresentado. Resultados experimentais mostram que os três algoritmos apresentam boas acelerações nos tempos de execução. Os experimentos também mostram que o algoritmo híbrido é quase sempre mais rápido do que o algoritmo de Gomory-Hu e em certas instâncias ele é muito mais rápido do que o algoritmo de Gusfield. Heurísticas para a melhoria do algoritmo de Gomory-Hu e do algoritmo híbrido são propostas e analisadas. Na segunda parte desta tese...

Proposta de uma linguagem específica de domínio de programação paralela orientada a padrões paralelos: um estudo de caso baseado no padrão mestre/escravo para arquiteturas multi-core

Griebler, Dalvan Jair
Fonte: Pontifícia Universidade Católica do Rio Grande do Sul; Porto Alegre Publicador: Pontifícia Universidade Católica do Rio Grande do Sul; Porto Alegre
Tipo: Dissertação de Mestrado
Português
Relevância na Pesquisa
36.8%
Este trabalho propôs uma Linguagem Específica de Domínio de Programação Paralela Orientada a Padrões Paralelos (LED-PPOPP). O principal objetivo é reduzir o esforço e induzir o programador a desenvolver algoritmos paralelos guiando-se através de padrões que são implementados pela interface da linguagem, evitando que ocorram grandes perdas de desempenho nas aplicações. Anteriormente estudados, os padrões são soluções especializadas e utilizadas para resolver um problema frequente. Assim, padrões paralelos são descritos em um alto nível de abstração para organizar os algoritmos na exploração do paralelismo, podendo ser facilmente interpretados por programadores inexperientes e engenheiros de software. Como ponto de partida, este trabalho realizou um estudo de caso baseandose no padrão Mestre/Escravo, focando na paralelização de algoritmos para arquiteturas multi-core. Através de experimentos para medição de esforço e desempenho, a implementação de estudo de caso foi avaliada obtendo bons resultados. Os resultados obtidos mostram que houve uma redução no esforço de programação paralela em relação a utilização da biblioteca Pthreads. Já com relação ao desempenho final das aplicações paralelizadas...

Uma implementação paralela híbrida para o problema do caixeiro viajante usando algoritmos genéticos, GRASP e aprendizagem por reforço

Santos, João Paulo Queiroz dos
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia Elétrica; Automação e Sistemas; Engenharia de Computação; Telecomunicações Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia Elétrica; Automação e Sistemas; Engenharia de Computação; Telecomunicações
Tipo: Dissertação Formato: application/pdf
Português
Relevância na Pesquisa
36.74%
The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed; As metaheurísticas são técnicas conhecidas para a resolução de problemas de otimização...

Algoritmos CGM para Busca Uni e Bidimensional de Padrões com e sem Escala

Mongelli, Henrique
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
46.74%
Dados um texto e um padrão, o problema de busca de padrões em textos consiste em determinar as posições do texto onde existe uma ocorrência do padrão. Quando o texto e padrão são cadeias de caracteres, a busca é dita unidimensional. Quando ambos são matrizes, a busca é dita ser bidimensional. Existem variações deste problema onde se permite a busca do padrão, de alguma maneira, modificado. A modificação que permitiremos ao nosso padrão é que ele possa estar escalado. Descrevemos algoritmos seqüencias lineares para estes problemas, uni ou bidimensionais, com e sem escala, presentes na literatura. Para o caso bidimensional sem escala é apresentado, ainda, um algoritmo de tempo sublinear sob determinadas condições nas matrizes de entrada. Para estes problemas propomos novos algoritmos paralelos, utilizando o modelo CGM (Coarse Grained Multicomputers), cujos tempos de computação local são lineares na entrada (local), consomem memória também linear e utilizam apenas uma rodada de comunicação em que são trocados, no máximo, uma quantidade também linear de dados. As condições do modelo são, assim, respeitadas. Do nosso conhecimento, não há na literatura outros algoritmos paralelos em modelos de granularidade grossa para o problema de busca unidimensional com escala e para os problemas de busca bidimensional com ou sem escala. Estes algoritmos propostos foram implementados em linguagem C...

Algoritmos BSP/CGM para programação dinâmica

Loureiro, Leonardo Vinicius Rolan
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Dissertação de Mestrado
Português
Relevância na Pesquisa
46.74%
À medida que a computação paralela vem deixando de ser um tópico a parte e isolado no mundo da computação para ser um tópico essencial e presente em todas as máquinas recentes, o estudo dos modelos e algoritmos paralelos passa a ser uma obrigação para os futuros cientistas da computação. Neste trabalho abordaremos os principais modelos de computação paralela, desde os modelos teóricos (PRAM) até os modelos reais (BSP, CGM, LogP) mostrando suas principais características, seus pontos de acerto e suas falhas ao modelar as arquiteturas paralelas reais. Dois problemas de grande importância em Programação Dinâmica foram estudados: o problema do Alinhamento Local e o problema do Produto da Cadeia de Matrizes. Para cada um dos problemas apresentados, estudamos e desenvolvemos algoritmos paralelos BSP/CGM usando o paradigma de frente de onda, os algoritmos foram implementados num cluster usando a biblioteca LAM-MPI e numa grid usando o middleware InteGrade. Os tempos obtidos foram os esperados de acordo com a análise de complexidade do modelo BSP/CGM e os resultados mostram que o overhead da computação em grid é satisfatório considerando as facilidades da mesma.; As parallel computing are no longer an apart and isolated topic in the world of computing to be an essential and present topic in all recent machines...

Comparação de Algoritmos Paralelos para a Extração de Regras de Associação no Modelo de Memória Distribuída

Mariano, Marcos Alves
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Dissertação de Mestrado
Português
Relevância na Pesquisa
66.95%
Nos ultimos anos, a extra c~ao de conhecimento a partir de grandes volumes de dados t^em sido o objeto de estudo em muitas pesquisas. Com isso, diversas t ecnicas de minera c~ao de dados foram desenvolvidas com o prop osito de descobrir informa c~oes para auxiliar os gestores de empresas e organiza c~oes na tomada de decis~oes. Uma das t ecnicas mais predominantes na minera c~ao de dados e a de extra c~ao de regras de associa c~ao, devido a sua e ci^encia e simplicidade no tratamento das informa c~oes. Com a utiliza c~ao do paralelismo em diversos problemas computacionais, algoritmos paralelos para a minera c~ao de dados foram constru dos utilizando a t ecnica de extra c~ao de regras de associa c~ao. Dentre os algoritmos paralelos mais conhecidos, utilizando o modelo de mem oria distribu da, est a o Apriori, o Eclat e o FP-Growth. Assim, o objetivo deste trabalho e implementar e comparar o desempenho dos algoritmos paralelos Apriori, Eclat e FP-Growth com diferentes n umeros de processadores e tamanhos de bases de dados de entrada.; In the last years, the extraction of knowledge from large amount of data have been the object of study in many surveys. Then, many data mining techniques have been developed in order to discover information to assist managers of companies and organizations in decision-making. One of the most prevalent techniques in data mining is the extraction of association rules...

Algoritmos paralelos para o alinhamento de sequências genômicas

Silva, Pedro Henrique Neves da
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Dissertação de Mestrado
Português
Relevância na Pesquisa
46.51%
No estudo da evolução dos organismos, ou das funções biológicas das moléculas, é comum a comparação entre diferentes organismos, ou moléculas, onde, em geral, essas moléculas são DNA, RNA ou proteínas, que são facilmente representadas por sequências de caracteres. A análise dessas várias sequências é um problema que necessita de muito tempo para ser realizada. Visando diminuir esse tempo são desenvolvidos métodos utilizando programação paralela com granulosidade híbrida, sendo essa paralelização necessária para tratar várias sequências com mais de 1000 caracteres. Neste trabalho estudamos o alinhamento de várias sequências e implementamos um algoritmo paralelo para este problema e comparamos o desempenho com o algoritmo sequencial utilizado pelo ClustalW, obtendo speedups que variam entre 61 e 8200, e com o algoritmo paralelo utilizado pelo ClustalWMPI, obtendo speedups que variam entre 44 e 280, quando temos muitas sequências de tamanho pequeno e quando temos um número considerável de sequências de tamanho grande, respectivamente, em ambas as comparações.; ABSTRACT - In the study of evolution and biological functions of molecules is common to compare different organisms or molecules, where...

Metodología basada en Algoritmos Genéticos y Programación en Paralelo para el Diseño Óptimo de Armaduras de Acero

Ramírez Echeverri, Sebastián
Fonte: Pontifícia Universidade Javeriana Publicador: Pontifícia Universidade Javeriana
Tipo: masterThesis; Tesis de Grado Maestría Formato: Pdf
Português
Relevância na Pesquisa
46.44%
La optimización de estructuras mediante la implementación de metodologías metaheurísticas ha sido una temática ampliamente estudiada en las últimas décadas. Los problemas de diseño estructural requieren del análisis de un gran número de variables complejas y por ende demandan un amplio uso de recursos computacionales. Este trabajo propone un algoritmo genético multi-cromosoma paralelo para resolver el problema de optimización de armaduras de acero 3-D, desarrollado en la plataforma JAVA®, el cual utilizó un cromosoma binario para determinar el mejor conjunto de perfiles y un cromosoma real para auto-adaptar los parámetros genéticos durante la optimización. Para el diseño de las armaduras se empleó un programa de elementos finitos desarrollado en MatLab®. El desempeño del algoritmo serial propuesto es evaluado mediante tres armaduras reportadas en la literatura (25, 72 y 112 miembros) y el uso de tres medidas de desempeño: costo final, desviación estándar entre ejecuciones y número de evaluaciones de la función objetivo. Con el fin de mejorar la eficiencia computacional, el algoritmo genético es paralelizado empleando el modelo de islas e hilos y evaluado mediante una armadura de 200 elementos y una de 354 elementos. Se obtiene que con la metodología propuesta los pesos finales son más bajos y con un uso significativamente menor de recursos computacionales en relación a otros algoritmos de optimización...

Modelado y autooptimización de metaheurísticas e hiperheurísticas parametrizadas paralelas aplicadas a problemas de optimización en ciencias e ingeniería

Cutillas Lozano, José Matías
Fonte: Universidade de Múrcia Publicador: Universidade de Múrcia
Tipo: Tese de Doutorado Formato: application/pdf
Português
Relevância na Pesquisa
36.79%
En este trabajo se estudia la aplicación de esquemas parametrizados paralelos de metaheurísticas e hiperheurísticas a problemas de optimización en ciencias e ingeniería. Un objetivo a conseguir es la aplicación eficiente de estos métodos, por lo que es necesario el uso de modelos que permitan su autooptimización durante la ejecución a través de la selección adecuada de parámetros característicos del sistema computacional y del paradigma de paralelismo empleado. La utilización de un esquema parametrizado de metaheurísticas permite aplicar fácilmente diferentes metaheurísticas a problemas de optimización, simplemente modificando algunos parámetros metaheurísticos. Además, puesto que muchos de estos problemas tienen una elevada carga computacional se hace indispensable la introducción de paralelismo en el esquema. Así, se consideran dos paradigmas que pueden ser complementarios: paralelismo local de memoria compartida y paralelismo global de paso de mensajes. El uso de algoritmos paralelos persigue un objetivo claro: la reducción del tiempo de ejecución, suponiendo un enfoque diferente para la resolución de los problemas de optimización. Debido a que obtener una buena metaheurística para un problema de optimización concreto puede ser un proceso costoso...

Towards efficient exploitation of GPUs : a methodology for mapping index-digit algorithms

Lobeiras Blanco, Jacobo
Fonte: Universidade da Corunha Publicador: Universidade da Corunha
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
36.81%
[Resumen]La computación de propósito general en GPUs supuso un gran paso, llevando la computación de alto rendimiento a los equipos domésticos. Lenguajes de programación de alto nivel como OpenCL y CUDA redujeron en gran medida la complejidad de programación. Sin embargo, para poder explotar totalmente el poder computacional de las GPUs, se requieren algoritmos paralelos especializados. La complejidad en la jerarquía de memoria y su arquitectura masivamente paralela hace que la programación de GPUs sea una tarea compleja incluso para programadores experimentados. Debido a la novedad, las librerías de propósito general son escasas y las versiones paralelas de los algoritmos no siempre están disponibles. En lugar de centrarnos en la paralelización de algoritmos concretos, en esta tesis proponemos una metodología general aplicable a la mayoría de los problemas de tipo divide y vencerás con una estructura de mariposa que puedan formularse a través de la representación Indice-Dígito. En primer lugar, se analizan los diferentes factores que afectan al rendimiento de la arquitectura de las GPUs. A continuación, estudiamos varias técnicas de optimización y diseñamos una serie de bloques constructivos modulares y reutilizables...

Estudo da influência dos parâmetros de algoritmos paralelos da computação evolutiva no seu desempenho em plataformas multicore

Pais, Mônica Sakuray
Fonte: Universidade Federal de Uberlândia Publicador: Universidade Federal de Uberlândia
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
56.9%
A computação paralela é um modo poderoso de reduzir o tempo de processamento e de melhorar a qualidade das soluções dos algoritmos evolutivos (AE). No princípio, os AE paralelos (AEP) eram executados em máquinas paralelas caras e pouco disponíveis. Desde que os processadores multicore tornaram-se largamente disponíveis, sua capacidade de processamento paralelo é um grande incentivo para que os AE, programas exigentes de poder computacional, sejam paralelizados e explorem ao máximo a capacidade de processamento dos multicore. A implementação paralela traz mais fatores que podem influenciar a performance dos AEP e adiciona mais complexidade na avaliação desses algoritmos. A estatística pode ajudar nessa tarefa e garantir conclusões corretas e significativas, com o mínimo de testes, se for aplicado o planejamento de experimentos adequado. Neste trabalho é apresentada uma metodologia de experimentação com AEP. Essa metodologia garante a correta estimação do speedup e aplica ao planejamento fatorial na análise dos fatores que influenciam o desempenho. Como estudo de caso, um algoritmo genético, denominado AGP-I, foi paralelizado segundo o modelo de ilhas. O AGP-I foi executado em plataformas com diferentes processadores multicore na resolução de duas funções de teste. A metodologia de experimentação com AEP foi aplicada para se determinar a influência dos fatores relacionados à migração no desempenho do AGP-I. ______________________________________________________________________________ ABSTRACT; Parallel computing is a powerful way to reduce the computation time and to improve the quality of solutions of evolutionary algorithms (EAs). At first...

Algoritmos Paralelos para Extensão Linear em Digrafos Planares

Lima, Anderson Correa de
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Dissertação de Mestrado
Português
Relevância na Pesquisa
46.38%
O objetivo principal deste trabalho consistiu em estudar e detalhar o algoritmo paralelo PRAM para computar a extensão linear de um digrafo acíclico planar, devido a Kao e Klein [KAO93]. Para digrafos acíclicos gerais, a obtenção de uma extensão linear não é simples. Kao e Klein mostraram que no modelo PRAM ela só pode ser obtida por meio da computação do fecho transitivo do digrafo. Para a classe dos digrafos acíclicos planares, Kao e Klein apresentam um algoritmo paralelo PRAM para computar a extensão linear sem a necessidade de computar o fecho transitivo do digrafo. Esse algoritmo, entretanto, utiliza uma série de estruturas e definições próprias de teoria dos grafos, além de outros algoritmos para resolver problemas chaves em digrafos. Dentre estes, o principal algoritmo estudado foi o algoritmo paralelo PRAM para obtenção de árvores geradoras em digrafos fortemente conexos, denominado algoritmo do CD-PAR, devido a Kao e Shannon [KAO89]. Kao e Klein mostraram que, partindo do resultado do algoritmo do CD-PAR, pode-se obter uma decomposição em orelhas de digrafos acíclicos planares e, a partir desta, alcançar a extensão linear. Essa relação entre árvores geradoras e decomposição em orelhas é a base para o entendimento do algoritmo de extensão linear proposto por Kao e Klein e amplamente discutida neste trabalho.; This work main objective was to study and to detail a PRAM parallel algorithm to compute topological ordering of a planar acyclic digraph...

Algoritmos paralelos realísticos para a maior subsequência comum

Peviani, Claudia Regina Tinós
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Dissertação de Mestrado
Português
Relevância na Pesquisa
56.67%
Neste trabalho estudou-se o problema da Maior Subsequência Comum (Longest Common Subsequence - LCS) que deseja encontrar uma subsequência comum de comprimento máximo de duas sequências. O problema LCS pode ser resolvido em tempo sequencial quadrático usando a técnica de programação dinâmica. Este trabalho consiste em estudar os algoritmos paralelos baseados nos modelos realísticos para resolver o problema LCS. Inicialmente estudou-se um algoritmo sequencial, um algoritmo paralelo no modelo PRAM e um no modelo realístico que encontra a LCS de todas as subcadeias. Fez-se uma implementação paralela realística com O(p) rodadas de comunicação usando p processadores. O resultado desta implementação não obteve speedup satisfatório, o que motivou o estudo mais teórico da paralelização do problema. Neste sentido, a partir do algoritmo PRAM descreveu-se uma solução paralela realística, usando estrutura de dados bem conhecidas como soma prefixa paralela e a técnica de pointer jumping.; In this work, it was studied the problem of the Longest Common Subsequence - LCS that aims to finds a common subsequence of maximum lenght of two sequences. The LCS problem can be solved in quadratic sequential time using the dynamic programmimg technique. This work consists in studying the parallel algorithms based on the realistic models to solve the LCS problem. Initially they studied a sequential algorithm...

Algoritmos para emparelhamento em grafos e uma implementação paralela

Carlos Fernando Bella Cruz
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 17/04/1996 Português
Relevância na Pesquisa
46.38%
Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani; In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor...

Algoritmos paralelos para alocação e gerência de processadores em máquinas multiprocessadoras hipercúbicas; Parallel algorithms for processor allocation in hypercubes

De Rose, Cesar Augusto Fonticielha
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Dissertação Formato: application/pdf
Português
Relevância na Pesquisa
56.78%
Nos últimos anos, máquinas maciçamente paralelas, compostas de centenas de processadores, vem sendo estudadas como uma alternativa para a construção de supercomputadores. Neste novo conceito de processamento de dados, grandes velocidades são alcançadas através da cooperação entre os diversos elementos processadores na resolução de um problema. Grande parte das máquinas maciçamente paralelas encontradas no mercado utilizam-se da topologia hipercúbica para a interconexão de seus múltiplos processadores, ou podem ser configuradas como tal. Uma alternativa interessante para o compartilhamento da capacidade de processamento destas máquinas é sua utilização como computador agregado a uma rede, servindo a diversos usuários [DUT 91]. Desta forma, a máquina hipercúbica se comporta como um banco de processadores, que permite que cada usuário aloque parte de seus processadores para seu uso pessoal. Isto resulta em um aumento no desempenho da rede ao nível de supercomputadores com um custo relativamente baixo e viabiliza a construção de máquinas hipercúbicas com altas dimensões, evitando que estas sejam sub-utilizadas. Neste tipo de contexto, cabe ao sistema operacional atender as requisições dos usuários do hipercubo compartilhado de forma eficiente...