begin
    import Pkg as _Pkg
    haskey(ENV, "PLUTO_PROJECT") && _Pkg.activate(ENV["PLUTO_PROJECT"])
    using Revise, Test
    import PlutoUI
    import Metis
    using ExtendableGrids: simplexgrid, partition, num_partitions, num_pcolors
    using ExtendableGrids: partition_cells, pcolor_partitions, pcolors
    using ExtendableGrids: PlainMetisPartitioning, RecursiveMetisPartitioning
    using ExtendableGrids: PColorPartitions, PartitionNodes, PartitionCells
    using ExtendableGrids: CellVolumes
    using GridVisualize: gridplot, default_plotter!
    import CairoMakie
    isdefined(Main, :PlutoRunner) && default_plotter!(CairoMakie)
end;

Partitioning example

Provide a glance on grid partitioning. This will be made more comprehensive over time.

X = 0:0.25:10
0.0:0.25:10.0
grid = simplexgrid(X, X)
ExtendableGrids.ExtendableGrid{Float64, Int32};
dim: 2 nodes: 1681 cells: 3200 bfaces: 160

gridplot(grid; linewidth = 0.1)

By default, the grid is partitioned in a trivial way.

The partition function returns a differently partitioned grid.

     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.

  • 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.

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.

partition has different backends which can be triggered by alg.

PlainMetisPartitioning

Partition grid using PlainMetisPartitioning

struct PlainMetisPartitioning <: ExtendableGrids.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 controled.

Parameters:

  • npart::Int64: Number of partitions (default: 20)

pgrid1 = partition(grid, PlainMetisPartitioning(; npart = 10))
ExtendableGrids.ExtendableGrid{Float64, Int32};
dim: 2 nodes: 1681 cells: 3200 bfaces: 160, edges: 4880
partitions/color: [3, 2, 3, 2]

This results in the following partitioning of the grid cells:

gridplot(pgrid1; cellcoloring = :partitions, linewidth = 0.1)

The neigborhood graph of the partitions gets colored in such a way that adjacent partitions have different colors. As a result, e.g. FEM assembly threads can run in parallel on partitions with the same color. If we color cells by their partition color, we get the following plot:

gridplot(pgrid1; cellcoloring = :pcolors, linewidth = 0.1)

Partition data are stored in a number of fields:

Accessing partitioning data

PColorPartitions

abstract type PColorPartitions <: ExtendableGrids.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.

pgrid1[PColorPartitions]
5-element Vector{Int32}:
  1
  4
  6
  9
 11

This means that partitions 1:3 have color 1, partitions 4:5 have color 2 etc.

See also:

pcolor_partitions(grid, color)

Return range of partitions for given pcolor based on grid[PColorPartitions].

PartitionCells

abstract type PartitionCells <: ExtendableGrids.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.

pgrid1[PartitionCells]
11-element Vector{Int32}:
    1
  320
  642
  962
 1286
 1604
 1929
 2248
 2562
 2879
 3201

This means that cells 1:319 belong to partition 1, cells 320:641 belong to partition 2 etc. See also:

partition_cells(grid, part)

Return range of cells belonging to a given partition grid[PartitionCells].

PartitionNodes

abstract type PartitionNodes <: ExtendableGrids.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.

2-element Vector{Int32}:
    1
 1682

Here, we see, that there is just one trivial node partition. If there is a need for a partition of the nodes, the node kwarg in partition needs to be set to true:

pgrid2 = partition(grid, PlainMetisPartitioning(; npart = 10); nodes = true)
ExtendableGrids.ExtendableGrid{Float64, Int32};
dim: 2 nodes: 1681 cells: 3200 bfaces: 160, edges: 4880
partitions/color: [3, 2, 3, 2]

pgrid2[PartitionNodes]
11-element Vector{Int32}:
    1
  134
  299
  440
  606
  769
  951
 1123
 1309
 1494
 1682

After partitioning, the PartitionNodes entry has the information on node partition numbers.

Assembly loops

Assembly loops can be run in parallel on for partitions of the same color.

begin
    cvol = pgrid1[CellVolumes]
    pvol = zeros(num_partitions(pgrid1))
    for color in pcolors(pgrid1)
        Threads.@threads for part in pcolor_partitions(pgrid1, color)
            for cell in partition_cells(pgrid1, part)
                pvol[part] += cvol[cell]
            end
        end
        @info "Area of partitions of color $color: $(sum(pvol[pcolor_partitions(pgrid1, color)]))"
    end
end
@test sum(pvol)-sum(cvol) ≈ 0.0
Test Passed

RecursiveMetisPartitioning

This is another partitioning algrorithm which recursively creates colored partitions.

struct RecursiveMetisPartitioning <: ExtendableGrids.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.

This algorithm allows to control the number of partitions in color 1 which coorespond to the bulk of the work.

Parameters:

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

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

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

pgrid3 = partition(grid, RecursiveMetisPartitioning(; npart = 5))
ExtendableGrids.ExtendableGrid{Float64, Int32};
dim: 2 nodes: 1681 cells: 3200 bfaces: 160, edges: 4880
partitions/color: [5, 5, 4]

Built with Julia 1.10.4 and

CairoMakie 0.12.5
ExtendableGrids 1.9.1
GridVisualize 1.7.0
Metis 1.4.1
Pkg 1.10.0
PlutoUI 0.7.59
Revise 3.5.15