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

DOI: https://doi.org/10.5753/wscad.2002.20771

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.