Grid partitioning

All grids created from ExtendableGrids can be considered to be partitioned such that the neighborhood graph of the partitions is colored so that operations (FEM/FVM assembly, sparse matrix-vector multiplication with SparseMatrixCSC, ILU preconditioners) on different partitions of the same color can be performed in parallel without write conflicts in a multithreading environment.

The default partitioning is trivial: all cells and nodes belong to one partition, and the resulting trivial neighborhood graph is colored with one color.

API calls

ExtendableGrids.partition — Function
     partition(grid::ExtendableGrid,
               alg::AbstractPartitioningAlgorithm;
               nodes = false,
               keep_nodepermutation = false,
               edges = false )

Partition cells of grid according to alg, such that the neigborhood graph of partitions is colored in such a way, that all partitions with a given color can be worked on in parallel. Cells are renumbered such that cell numbers for a given partition are numbered contiguously.

Return the resulting grid.

Useful for parallel FEM assembly and cellwise FVM assembly.

Keyword arguments:

  • nodes: if true, induce node partitioning from cell partitioning. Used for node/edgewise FVM assembly. In addition the resulting partitioning supports parallel matrix-vector products with SparseMatrixCSC. Nodes are renumbered compared to the original grid. If false (default), a trivial partitioning of the nodes is created such that all nodes belong to partition 1 and all others are empty.
  • keep_nodepermutation: if true, keep the node permutation with respect to the original grid in grid[NodePermutation].
  • edges: if true, induce partitioning of edges from cell partitioning. Used for node/edgewise FVM assembly. This step creates a number of relatively expensive additional adjacencies. If false (default), a trivial partitioning of the edges is created such that all edges belong to partition 1 and all others are empty.

Access:

A parallel loop over grid cells thus looks like

for color in pcolors(grid)
    @threads for part in pcolor_partitions(grid, color)
                for cell in partition_cells(grid, part)
                 ...
                end
             end
end

Without a call to partition, all these functions return trivial data such that the above sample code stays valid.

Note

partition must be called before obtaining any other adjacencies of a grid.

Currently, partitioning does not cover the boundary, boundary cells belong to one big trivial partition.

source
ExtendableGrids.num_partitions_per_color — Function
num_partitions_per_color(grid)

Return a vector containing the number of partitions for each of the colors of the grid partitioning. These define the maximum number of parallel threads for each color.

source
ExtendableGrids.check_partitioning — Function
check_partitioning(grid; 
                   verbose=true, 
                   cellpartonly=false)

Check correctness of cell partitioning, necessesary for parallel assembly:

  • Check if every node belongs to one of the cell partitions
  • Check if no node belongs to two cell partitions of the same color at once

If cellpartonly==false check correctness of node partitioning necessary for parallel sparse matrix multiplication and ILU preconditioning

  • Check if no node belongs to two node partitions of the same color at once
  • Check if no node is a neighbor of nodes from two node partitions of the same color
source

Partitioning algorithms

ExtendableGrids.PlainMetisPartitioning — Type
struct PlainMetisPartitioning <: AbstractPartitioningAlgorithm

Subdivide grid into npart partitions using Metis.partition and color the resulting partition neigborhood graph. This requires to import Metis.jl in order to trigger the corresponding extension.

This algorithm allows to control the overall number of partitions. The number of partitions per color comes from the subsequent partition graph coloring and in the moment cannot be controlled.

Parameters:

  • npart::Int64: Number of partitions (default: 20)
source
ExtendableGrids.RecursiveMetisPartitioning — Type
struct RecursiveMetisPartitioning <: AbstractPartitioningAlgorithm

Subdivide grid into npart partitions using Metis.partition and calculate cell separators from this partitioning. The initial partitions get color 1, and the separator gets color 2. This is continued recursively with partitioning of the separator into npart partitions and calculating the spearator of the separator, giving it color 3.

This algorithm allows to control the number of partitions in color 1 which correspond to the bulk of the work. The overall number of partitions will be in the range of 3*npart.

If the grid is too coarse for that many partitions, several of them may be just empty.

Parameters:

  • npart::Int64: Number of color 1 partitions (default: 4)

  • maxdepth::Int64: Recursion depth (default: 1)

  • separatorwidth::Int64: Separator width (default: 2)

source

Key types for grid access

ExtendableGrids.PColorPartitions — Type
abstract type PColorPartitions <: AbstractGridIntegerArray1D

Key type describing colors of partitions. These correspond to a coloring of the neigborhood graphs of partitions such that operations (e.g. FEM assembly) on partitions of a given color can be performed in parallel.

grid[PColorPartitions] returns an integer vector describing the partition colors ("pcolors") of a grid. Let p=grid[PColorPartitions]. Then all partitions with numbers i ∈ p[c]:p[c+1]-1 have "color" c. See also pcolors.

source
ExtendableGrids.PartitionCells — Type
abstract type PartitionCells <: AbstractGridIntegerArray1D

Key type describing the cells of a given partition.

grid[PartitionCells] returns an integer vector describing the cells of a partition given by its number. Let pc=grid[PartitionCells]. Then all cells with index i ∈ pc[p]:pc[p+1]-1 belong to partition p.

source
ExtendableGrids.PartitionBFaces — Type
abstract type PartitionBFaces <: AbstractGridIntegerArray1D

Key type describing the bondary faces of a given partition.

grid[PartitionBFaces] returns an integer vector describing the boundary faces of a partition given by its number. Let pc=grid[PartitionCells]. Then all cells with index i ∈ pc[p]:pc[p+1]-1 belong to partition p.

source
ExtendableGrids.PartitionNodes — Type
abstract type PartitionNodes <: AbstractGridIntegerArray1D

Key type describing the nodes of a given partition.

grid[PartitionNodes] returns an integer vector describing the nodes of a partition given by its number. Let pn=grid[PartitionNodes]. Then all nodes with index i ∈ pn[p]:pn[p+1]-1 belong to partition p.

source
ExtendableGrids.PartitionEdges — Type
abstract type PartitionEdges <: AbstractGridIntegerArray1D

Key type describing the edges of a given partition.

grid[PartitionEdges] returns an integer vector describing the edges of a partition given by its number. Let pe=grid[PartitionEdges]. Then all edges with index i ∈ pe[p]:pe[p+1]-1 belong to partition p.

source
ExtendableGrids.NodePermutation — Type
abstract type NodePermutation <: AbstractGridIntegerArray1D

Key type describing the permutation of the nodes of a partitioned grid with respect to the unpartitioned origin.

If pgrid is the partitioned grid and grid is the unpartitioned origin, then

pgrid[Coordinates][:,pgrid[NodePermutation]]==grid[Coordinates]

source

Internal API

These functions & methods are neither exported nor public.

ExtendableGrids.instantiate — Method
instantiate(grid::ExtendableGrid, ::Type{PColorPartitions})

If not given otherwise, instantiate partition data with trivial partitioning.

source
ExtendableGrids.instantiate — Method
instantiate(grid::ExtendableGrid, ::Type{PartitionCells})

If not given otherwise, instantiate partition data with trivial partitioning.

source
ExtendableGrids.instantiate — Method
instantiate(grid::ExtendableGrid, ::Type{PartitionBFaces})

If not given otherwise, instantiate partition data with trivial partitioning.

source
ExtendableGrids.instantiate — Method
instantiate(grid::ExtendableGrid, ::Type{PartitionNodes})

If not given otherwise, instantiate partition data with trivial partitioning.

source
ExtendableGrids.partgraph — Function
partgraph(cellpartitions, ncellpartitions, cellcelladj)

(internal) Create neigbourhood graph for given partitioning.

source
ExtendableGrids.dopartition — Function
dopartition(grid, alg)

(Internal utility function) Core function for partitioning grid cells which dispatches over partitioning algorithms. Partitioning extensions should add methods to this function.

source
ExtendableGrids.reorder_cells — Function
reorder_cells(
    grid,
    cellpartitions,
    ncellpartitions,
    colpart
)

(Internal utility function) Create cell permutation such that all cells belonging to one partition are numbered contiguously, return grid with reordered cells.

source
ExtendableGrids.induce_node_partitioning! — Function
induce_node_partitioning!(
    grid,
    cn,
    nc;
    trivial,
    keep_nodepermutation
)

(internal) Induce node partitioning from cell partitioning of grid. The algorithm assumes that nodes get the partition number from the partition numbers of the cells having this node in common. If these are differnt, the highest number is taken.

Node partitioning should support parallel matrix-vector products with SparseMatrixCSC. The current algorithm assumes that nodes get the partition number from the partition numbers of the cells having this node in common. If these are differnt, the highest number is taken.

Simply inducing node partition numbers from cell partition numbers does not always fulfill the condition that there is no node which is neigbour of nodes from two different partition with the same color.

This situation is detected and corrected by joining respective critical partitions, sacrificing a bit of parallel efficiency for correctness.

source
ExtendableGrids.induce_edge_partitioning! — Function
induce_edge_partitioning!(grid; trivial)

(internal) Induce edge partitioning from cell partitioning of grid. The algorithm assumes that nodes get the partition number from the partition numbers of the cells having this node in common. If these are differnt, the highest number is taken.

This method triggers creation of rather complex edge information and should be called only if this information is really necessary.

source