Coordenador: Siang Wun Song
Phylogeny from whole genome comparison
(palestra dada em português)
Nalvo Franco Almeira Jr.
Resumo:
In this work we propose and compare several distance-based phylogenetic
measures from whole genome comparison, which take into account gene
content and gene order conservation. We show that it is possible to
infer phylogenetic issues from whole genome comparison, since gene
content and gene order are conserved between closely related species.
Implementação paralela do LCS (ancestral comum mais baixo) usando
MPI e CGM/BSP
Henrique Mongelli
Resumo:
O LCA (Lowest Common Ancestor - Ancestral Comum Mais Baixo) de dois
vértices u e v em uma árvore T com raiz é o vértice w que é ancestral
de u e de v e está mais distante da raiz. O problema do LCA consiste
em pré-processar uma árvore T, obtendo uma estrutura de dados de forma
que qualquer consulta LCA(u,v), para quaisquer u e v, possa ser
respondida em tempo constante. Se a árvore T é um caminho ou uma
árvore binária completa, o pré-processamento é bastante simples.
Apresentaremos um algoritmo paralelo CGM/BSP, baseado no algoritmo
PRAM desenvolvido por Schieber e Vishkin que utiliza um mapeamento da
árvore dada em uma árvore binária completa. Será apresentada também
uma proposta de implementação utilizando a plataforma MPI (Message
Passing Interface).
Computação em grade: uma introdução
Rogério Seiji Ueda
Resumo:
Com o avanço tecnológico do poder de processamento dos computadores e na
popularização da Internet vem ganhando destaque a idéia da computação
em grade ("Grid Computing"). Esta apresentação tem o objetivo de
introduzir algumas características por trás da computação em grade.
Será apresentado o cenário atual e aplicações e projetos em andamento.
Um algoritmo BSP/CGM para o Conjunto Independente Máximo em grafos
bipartidos convexos
Marco Aurélio Stefanes
Resumo: (Este trabalho foi apresentado na conferencia PDPTA 2001).
Um grafo bipartido $G=(V,W,E)$ é convexo se há uma ordenação
dos vértices de $W$ de modo que: se
$(v,w')\in E$ e $(v,w'')\in E$, com $w'\leq w''$, então $(v,w)\in E$,
$w' \leq w \leq w''$. Sendo $|V|=n$ e $|W|=m$, tal grafo pode ser
representado em uma forma compacta que requer espaço $O(n)$.
Neste semimário trataremos do problema de encontrar um Conjunto
Independente Máximo em um grafo bipartido
convexo. Considerando $m=O(n^c)$, dado um grafo $G$ bipartido convexo
na forma compacta
e um emparelhamento máximo $M$ de $G$ descrevemos um novo algoritmo
seqüencial de complexidade $O(n)$. Baseado nesse algoritmo descrevemos
um algoritmo paralelo BSP/CGM que gasta computação local $O(n/p)$ e rodadas de
comunicação $O(1)$, com $n/p \geq p$, onde $p$ é o número de processadores.
Metodologia para obtenção de uma plataforma de alto desempenho
baseada em Clusters de PCs
Martha Ximena Torres Delgado
Resumo:
Nesta palestra serão explicados os principais passos que
devem ser considerados para a obtenção de uma plataforma para
processamento paralelo baseada em Clusters de PCs, desde a compra
dos componentes até seu funcionamento. Também serão
abordados alguns itens referentes a configuração, administração
e segurança.
Um algoritmo de aproximação paralelo para
transversal mínima com aplicação em análise de expressão gênica
Danielle Passos de Ruchkys
Resumo: (O trabalho será apresentado no SBAC 2002 - Simpósio Brasileiro
de Arquiteturas de Computadores da SBC no final de outubro.
Segue-se o resumo
em inglês.)
With the recent DNA-microarray technology, it is possible to
measure the expression levels
of thousands of genes simultaneously in the same experiment.
A genetic network is a model that describes how the expression
level of each gene is affected by the expression levels of other
genes in the network.
Given the results of
an experiment with $n$ genes and $m$ measures over time
($m << n$),
we consider the problem of
finding a subset of genes ($k$ genes, where $k << n$) that
explain the expression level of a given target gene under study.
We consider the coarse-grained multicomputer (CGM) model,
with $p$ processors.
In this paper we first
present a sequential approximation algorithm of
$O(m^{4} n)$ time and $O(m^2 n)$ space.
The main result is a new parallel approximation
algorithm that determines the $k$ genes in
$O(m^{4} n / p)$ local computing time
plus $O(k)$ communication rounds,
% with $O(p+m^2)$ amount of data
% transmitted in each communication round,
and with space requirement of $O(m^2 n /p)$.
The $p$ factor in the parallel time and space complexities
indicates a good parallelization.
We also show preliminary promising experimental
results on a Beowulf machine.
To our knowledge there are no
CGM algorithms for the problem considered in this paper.
Lista TOP500 - os 500 computadores mais velozes do mundo
Siang Wun Song
Resumo: TOP500 é uma lista dos 500 computadores mais velozes no mundo (em termo de números de operações aritméticas por segundo) divulgada em junho e em novembro de cada ano. Apresentamos neste seminário a última lista TOP500 (junho de 2002). Discutimos as características dessa lista e as tendências quanto a arquitetura, tecnologia de fabricação dos componentes e outros aspectos importantes. Em particular, nota-se a recente introdução na lista TOP500 computadores do tipo Beowulf e cluster de clusters (denominado constelação).
Programação dinâmica paralela para resolver o problema
de edição de cadeias em um CGM/BSP
Carlos Eduardo Rodrigues Alves
Resumo:
(Este trabalho foi apresentado no SPAA 2002 de agosto passado. Segue-se
o resumo em inglês.)
In this paper we present a coarse-grained parallel algorithm
for solving the
string edit distance problem for a string $A$ and all substrings
of a string $C$. Our method is based on a novel CGM/BSP parallel
dynamic programming technique for computing all highest scoring paths
in a weighted grid graph.
The algorithm requires $\log p$ rounds/supersteps and
$O(\frac{n^2}{p}\log m)$ local computation,
where $p$ is the number of processors, $p^2 \leq m \leq n$.
To our knowledge, this is the first efficient CGM/BSP algorithm
for the alignment of all substrings of $C$ with $A$. Furthermore, the
CGM/BSP parallel dynamic programming technique presented is of
interest in its own right and we expect it to lead to other
parallel dynamic programming methods for the CGM/BSP.
Consideraçõs sobre Implementação de Algoritmos CGM
Rogério Seiji Ueda
Resumo:
Considere a resolução de um problema de tamanho de entrada n
num multicomputador com p processadores cada um com memória
local O(n/p). Num algoritmo CGM o objetivo é minimizar o
número de rodadas de comunicação. Em cada rodada de
comunicação cada processador pode enviar/receber um total
de O(n/p) dados. Neste seminário discutimos dois
pontos importantes para a implementação de um algoritmo CGM:
1) A importância de minimizar a quantidade de dados
transimitidos em cada rodada e
2) O compromisso entre o número de rodadas de comunicação
e a carga de trabalho do processador.
Como exemplo para ilustrar esses dois pontos, será usado
o algoritmo paralelo de seleção proposto por Saukas
(mestrado no IMEUSP).
Implementando algoritmos de Similaridade de Strings
em um Beowulf
Edson Norberto Cáceres
Resumo: Apresentamos um algoritmo CGM/BSP para computar um alinhamento entre duas cadeias A e C, com |A|=m e |C|=n. Mostramos as complexidades do algoritmo e discutimos as implementaçõs realizadas em uma máquina paralela do tipo Beowulf com 64 processadores.
Algoritmos Paralelos para Numerar Combinações
Martha Ximena Torres Delgado
Resumo: A numeração de combinações é necessária em diferentes tipos de aplicações, em particular está presente em aplicações de bioinformática onde se estuda a interação de gens. Numerar combinações de maneira sequencial demanda muito tempo de processamento. Portanto uma implementação paralela é interessante para este tipo de problema. No seminário serão discutidos 2 algoritmos paralelos para numerar combinações. Serão explicadas vantagens e desvantagens dos dois algoritmos e serão mostrados alguns resultados de desempenho destes algoritmos.