Estudo Comparativo de Software para Particionamento e Mapeamento de Grafos

  • Elias C. Carvalho UFRGS
  • Ricardo V. Dorneles UFRGS
  • Rogério L. Rizzi UFRGS
  • Tiarajú A. Diverio UFRGS

Resumo


Aplicações e arquiteturas de computadores podem ser representadas por meio de grafos. O particionamento do grafo de uma aplicação e seu respectivo mapeamento sobre o grafo de uma arquitetura é uma forma de paralelizar o processamento. Nesse contexto, é importante considerar como o grafo da aplicação será particionado, pois uma distribuição desigual sobre um ambiente heterogêneo, certamente reduzirá a eficiência do processamento, pois alguns processadores terminarão sua tarefa antes e permanecerão ociosos até que os outros alcancem o ponto de sincronização para receberem novos dados e executarem novas tarefas. Este artigo apresenta a realização de experimentos de particionamento e mapeamento, representando o problema e a arquitetura através de grafos e utilizando ferramentas específicas para esse fim.

Referências

DORNELES, R. V., Particionamento de Domínio e Balanceamento Dinâmico de Carga em Arquiteturas Heterogêneas: Aplicação a Modelos Hidrodinâmicos e de Transporte de Massa 2-D e 3-D, PPGC da UFRGS, Porto Alegre, 2002.

RIZZI, R. L., Modelo Computacional Paralelo para a Hidrodinâmica e para o Transporte de Massa 2-D e 3D, PPGC da UFRGS, Porto Alegre, 2002.

CANAL, A. P., Paralelização de Métodos de Resolução de Sistemas Lineares Esparsos com o DECK em um Cluster de PCs, PPGC da UFRGS, Porto Alegre, 2002.

ROOSTA, S., Parallel Processing and Parallel Algorithms: theory and computation, Springer, Berlin, 2000. 566p.

ABURTO, A., Flops.c Version 2.0. Disponível em: <ftp://ftn.nosc.mil/pub/aburto>. Acesso em: 12 ago. 2001.

McCALPIN, J. D., STREAM: Sustainable Memory Bandwidth in High Performance Computers, Dept of Computer Science. University of Virgínia, Virgina. Disponível em: <http://www.cs.virginia.edu/stream>. Acesso em: 10 ago. 2001.

Norcott, W. D., IOzone Filesystem Benchmark, lozone Org. Disponível em: <http://www.iozone.org/>. Acesso em: 12 ago. 2001.

Wominger, J., Pingpong - Measure effective bandwidth and latency, Lehrstuhl Fur Betriebssysteme University. Disponível em: <http://www.lfbs.rwth-aachen.de/~joachim/SCI-MPICH/pingpong_src.html>. Acesso em: 09 set. 2001.

GROPP, W., et al. A high-performance, portable implementation of the MPI message passing interface standard, Parallel Computing, n.22, 1996. p.789-828.

YANG, W., MAHESHWARI P., Mapping and Scheduling on Heterogeneous Systems, School of Computer Science and Engineering, University of New South Wales, Sydney, Australia, 1999. Disponível em: [link]. Acesso em: 13 abr. 2002.

HENDRICKSON, B., LELAND, R, The Chaco User's Guide. Version 2.0. Disponível em: < http://www.cs.sandia.gov/CRF/papers_chaco.html>. Acesso em: 22 mar. 2001.

WALSHAW, C., The jostle user manual: Version 2.2. Disponível em: < http://www.gre.ac.ukHjgOI/>. Acesso em: 14 jan. 2001.

PELLEGRINI, F., SCOTCH 3.1 SCOTCH User's Guide, Disponível em: <https://dept-info.labri.u-bordeaux.fr/~pelegrin/scotch/scotchgb.html>. Acesso em: 25 fev. 2001.

DEMMEL, J., Applications of Parallel Computers. Berkeley, UC Berkeley, 1996. Disponível em: <http://www.cs.berkeley.edu/~demmel/cs267/>. Acesso em: 15 jul. 2001.

KERNIGHAN, B., LJN, S., An Efficient Heuristic Procedure for Partitioning Graphs, The Bell System Technical Journal, n.49, v.2, 1970.

FIDUCCIA, C.M., MATTHEYSES, R.M., A Linear Time Heuristic for lmproving Network Partitions, Las Vegas, EUA, IEEE Computer Society, 1982. p. l75-1 81.

WALSHAW, C., CROSS, M., Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm, London: Uni versity of Greenwich, 1998. Disponível em: <http://www.gre.ac.uk/jostle/>. Acesso em: 30 mar. 2001.

SZEWCZYK, R, FERENCZ, A., WEINSTEIN, J., WILKENING, J., Graph Bisection, Disponível em: <http://www.cs.berkeley.edu/_szewczyk/CS270/>. Acesso em: 30 jun. 2001.
Publicado
28/10/2002
CARVALHO, Elias C.; DORNELES, Ricardo V.; RIZZI, Rogério L.; DIVERIO, Tiarajú A.. Estudo Comparativo de Software para Particionamento e Mapeamento de Grafos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 3. , 2002, Vitória. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2002 . p. 126-133. DOI: https://doi.org/10.5753/wscad.2002.20771.