METIS

Publish in

Documents

5 views

Please download to get full document.

View again

of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
METIS. Three Phases Coarsening Partitioning Uncoarsening. G. Karypis , V. Kumar , “A fast and high quality multilevel scheme for partitioning irregular graphs , ” International Conference on Parallel Processing, 1995. METIS - Coarsening. Maximal Matching
Transcript
METIS
  • Three Phases
  • Coarsening
  • Partitioning
  • Uncoarsening
  • G. Karypis, V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” International Conference on Parallel Processing, 1995.METIS - Coarsening
  • Maximal Matching
  • A set of edges without common vertices
  • An NP-Complete problem
  • METIS - Partitioning
  • Two Steps
  • Randomly Choose a root
  • BFS to include the vertex leading less edge-cuts
  • RootMETIS - Uncoarsening
  • Key Idea
  • Each super-node comprises a set of nodes
  • Decrease the edge-cuts by moving a vertex to one partition to another
  • Parallel METIS
  • Five Phases
  • Initial Partition
  • Coloring
  • Coarsening
  • Partitioning
  • Uncoarsening
  • Each processor keeps two pieces of Information: 1. Sub-graph 2. Adjacency List G. Karypis, V. Kumar, “Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs,” IEEE/ACM Conference on Supercomputing, 1996.Parallel METIS
  • Coloring
  • Adjacent vertices have different colors [Luby’s Algorithm]
  • The number of distinct colors used is to be minimized
  • Parallel METIS
  • Coarsening Phase
  • Unilateral Matching
  • Matching Conflicts?
  • Why do we need coloring?
  • Node.MatchRemote EdgeParallel METIS
  • Partitioning Phase
  • Since the coarsened graph has been relatively small, partition can be done
  • Further parallelization is also possible
  • G. Karypis, V. Kumar, “Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs,” IEEE/ACM Conference on Supercomputing, 1996.Parallel METIS
  • Uncoarsening Phase
  • This phase is broken up into c sub-phases, where cis the number of colors
  • During the cthphase, all the vertices of color c are considered for movement
  • G. Karypis, V. Kumar, “Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs,” IEEE/ACM Conference on Supercomputing, 1996.
    Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks