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 nnodes = 1681 ncells = 3200 nbfaces = 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 withSparseMatrixCSC
. Nodes are renumbered compared to the original grid. Iffalse
(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 ingrid[
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. Iffalse
(default), a trivial partitioning of the edges is created such that all edges belong to partition 1 and all others are empty.
Access:
pcolors
returns the range of partition colorspcolor_partitions
returns the range of partition numbers for a given colorpartition_cells
provides the range of cell numbers of a given partitionpartition_nodes
provides the range of node numbers of a given partitionpartition_edges
provides the range of edge numbers of a given partition
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.
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 controlled.
Parameters:
npart::Int64
: Number of partitions (default: 20)
pgrid1 = partition(grid, PlainMetisPartitioning(; npart = 10))
ExtendableGrids.ExtendableGrid{Float64, Int32} dim = 2 nnodes = 1681 ncells = 3200 nbfaces = 160 nedges = 4880 npartitions/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 nnodes = 1681 ncells = 3200 nbfaces = 160 nedges = 4880 npartitions/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 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)
pgrid3 = partition(grid, RecursiveMetisPartitioning(; npart = 5))
ExtendableGrids.ExtendableGrid{Float64, Int32} dim = 2 nnodes = 1681 ncells = 3200 nbfaces = 160 nedges = 4880 npartitions/color = [5, 5, 4]
Built with Julia 1.11.1 and
CairoMakie 0.12.16ExtendableGrids 1.10.5
GridVisualize 1.8.2
Metis 1.5.0
Pkg 1.11.0
PlutoUI 0.7.60
Revise 3.6.3
Test 1.11.0