The partition module. More...

Functions/Subroutines
subroutine, public	prg_metispartition (gp, ngroups, nnodes, xadj, adjncy, nparts, part, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm)
	Create graph partitions minizing number of cut edges. More...

subroutine, public	prg_costpartition (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm)
	Compute cost of a partition. More...

subroutine, public	update_prg_costpartition (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm, node, new_part)
	Update cost of partition and the different parameters node is moves into new_part For each neighbor of node, the following cases hold: Case 1: neighbor is in old_part Case 2: neighbor is in new_part Case 3: neighbor is neither in old_ or new_part. More...

subroutine	prg_accept_prob (it, prg_delta, r)
	Compute acceptance probability for simulated annealing. More...

subroutine	prg_costindex (cost, sumCubes, maxCH, smooth_maxCH, obj_fun)
	Choose objective function to work with. More...

subroutine	prg_rand_node (gp, node, seed)
	Pick a random node. More...

subroutine, public	prg_simannealing (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm, niter, seed)
	Graph partitioning based on Simulated Annealing. More...

subroutine, public	prg_kernlin (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm, nconverg, seed)
	Graph partitioning based on inspired by Kernighan-Lin Review METiS manual for description of k-way implementation of KL Pick a core together with its halos Place free vertices on a priority queue with (key, value) =(prg_delta, best_part),with prg_delta = change in obj_value Dequeue and allow hill climbing. More...

subroutine, public	prg_update_gp (gp, partNumber, core_count)

subroutine	prg_rand_shuffle (array, seed)
	Randomly shuffle array. More...

subroutine, public	prg_check_arrays (gp, core_count, CH_count, Halo_count)
	Error checking Checking that core_count, CH_count, Halo_count match. More...

subroutine, public	prg_kernlin_queue (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm)
	Greedy algorithm. At each step it chooses the (vertex, new_part) pair with highest gain Currently implementation is very slow. More...

subroutine	prg_find_best_move (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm, best_node, best_part)
	For kerlin_queue to find (vertex, new_part) pair with highest gain. More...

subroutine, public	prg_kernlin2 (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm)

subroutine	prg_get_largest_hedge_in_part (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm, search_part, largest_Hedge)

subroutine, public	prg_simannealing_old (gp, xadj, adjncy, partNumber, core_count, CH_count, Halo_count, sumCubes, maxCH, smooth_maxCH, pnorm, niter, seed)

Variables
integer, parameter	dp = kind(1.0d0)

integer, parameter	metis_index_kind = METIS_INDEX_KIND
	From /usr/include/metis.h. More...

integer, parameter	metis_real_kind = kind(METIS_REAL_KIND)
	From /usr/include/metis.h. More...

Detailed Description

The partition module.

Contains different partitioning algorihms such as Metis, Simulated Annealing etc. Also contains optimization routines to improve upon existing partitioning, such as simulated annealing, etc.

Function/Subroutine Documentation

◆ prg_accept_prob()

subroutine prg_partition_mod::prg_accept_prob	(	integer, intent(in)	it,
		real(dp), intent(in)	prg_delta,
		real, intent(inout)	r
	)

private

Compute acceptance probability for simulated annealing.

Parameters

it	iteration
prg_delta	(new_obj_value - old_obj_value)
r	acceptance probability

Definition at line 488 of file prg_partition_mod.F90.

◆ prg_check_arrays()

subroutine, public prg_partition_mod::prg_check_arrays	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count
	)

Error checking Checking that core_count, CH_count, Halo_count match.

Definition at line 1167 of file prg_partition_mod.F90.

◆ prg_costindex()

subroutine prg_partition_mod::prg_costindex	(	real(dp), intent(inout)	cost,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		integer, intent(inout)	obj_fun
	)

private

Choose objective function to work with.

Parameters

cost	output according to chosen obj_fun
sumCubes	Sum of cubes obj value
maxCH	maximum core-halo part size obective value
obj_fun	0=sumcubes, 1=maxCH

Definition at line 506 of file prg_partition_mod.F90.

◆ prg_costpartition()

subroutine, public prg_partition_mod::prg_costpartition	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(in), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm
	)

Compute cost of a partition.

Parameters

gp	Graph partitioning
xadj	CSR array of graph nodes
adjncy	CSR array of graph neighbors
nparts	Number of Parts
partNumber	Partition vector
core_count	Array: number of core vertices in each part
CH_count	Array: number of core+halo vertices in each part
Halo_count	2D Array of size nparts by totalNodes: Halo_count(i,j) = k, node j is a halo of part i\ with k connections
sumCubes	Sum of cubes objective value
maxCh	maximum core-halo part size obective value

prg_initialize

Definition at line 326 of file prg_partition_mod.F90.

◆ prg_find_best_move()

subroutine prg_partition_mod::prg_find_best_move	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm,
		integer, intent(inout)	best_node,
		integer, intent(inout)	best_part
	)

private

For kerlin_queue to find (vertex, new_part) pair with highest gain.

Definition at line 1230 of file prg_partition_mod.F90.

◆ prg_get_largest_hedge_in_part()

subroutine prg_partition_mod::prg_get_largest_hedge_in_part	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm,
		integer, intent(inout)	search_part,
		integer, intent(inout)	largest_Hedge
	)

private

i can be viewed as a hyperedge for all hyperedges in search_part, pick the one with largest size

Definition at line 1442 of file prg_partition_mod.F90.

◆ prg_kernlin()

subroutine, public prg_partition_mod::prg_kernlin	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm,
		integer, intent(in)	nconverg,
		integer, intent(inout)	seed
	)

Graph partitioning based on inspired by Kernighan-Lin Review METiS manual for description of k-way implementation of KL Pick a core together with its halos Place free vertices on a priority queue with (key, value) =(prg_delta, best_part),with prg_delta = change in obj_value Dequeue and allow hill climbing.

Parameters

gp	Graph partitioning
xadj	CSR array of graph nodes
adjncy	CSR array of graph neighbors
nparts	Number of Parts
partNumber	Partition vector
core_count	Array: number of core vertices in each part
CH_count	Array: number of core+halo vertices in each part
Halo_count	2D Array of size nparts by totalNodes: Halo_count(i,j) = k, node j is a halo of part i\ with k connections
sumCubes	Sum of cubes objective value
maxCh	maximum core-halo part size obective value
nconverg	number of before convergence
seed	random number generator seed

Allocate arrays

Initialize variables

Initialize array of nodes

Randomize nodes

Compute current cost of partition

Choose objective function to minimize

iterate over the columns of the matrix, ie the hyperedges

KL iteration

let min_part be the smallest CH_part

Try and move free nodes to min_part

lock vertices (climb_counter) vertices have been accepted need to lock (climb_counter) vertices Last vertex to be moved is node_backup(climb_counter)

reset

If all vertices locked, go to next iteration

If empty parts exit, place a vertex in max_part there

Place j and it's neighbors that are in the max part into the empty part

Check Convergence

Check empty part exist move nodes from maxpart to empty part

move it neighbor in the max parts to the newpart

Update graph structure

Allocate subgraph structure

Assign node ids to sgraph

Definition at line 772 of file prg_partition_mod.F90.

◆ prg_kernlin2()

subroutine, public prg_partition_mod::prg_kernlin2	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm
	)

Allocate arrays

Pick hyperedge with largest size or random hyperedge with probability 0.5 We wiil change it to pick hyperedge with highest priority, where priority will be defined according to different metrics

Find part with smalles size (should be included in update_prg_costPartition

if current part is max, move to min_part then move subsets (neighbors)

Move hyperedges to minCH part

Try and move intersecting hyperedges

Move k number of vertices. k should be small i.e k <=20, k set in prg_Kernlin_queue Only use this for small systems

Check empty part exist move nodes from maxpart to empty part

move it neighbor in the max parts to the newpart

Update graph structure

Allocate subgraph structure

Assign node ids to sgraph

Definition at line 1278 of file prg_partition_mod.F90.

◆ prg_kernlin_queue()

subroutine, public prg_partition_mod::prg_kernlin_queue	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm
	)

Greedy algorithm. At each step it chooses the (vertex, new_part) pair with highest gain Currently implementation is very slow.

Definition at line 1194 of file prg_partition_mod.F90.

◆ prg_metispartition()

subroutine, public prg_partition_mod::prg_metispartition	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, intent(in)	ngroups,
		integer, intent(in)	nnodes,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, intent(inout)	nparts,
		integer, dimension(:), intent(inout), allocatable	part,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm
	)

Create graph partitions minizing number of cut edges.

Parameters

gp	Graph partitioning`
ngroups	Number of groups/nodes
nnodes	Number of nodes
xadj	CSR array of graph nodes
adjncy	CSR array of graph neighbors
nparts	Number of Parts
part	Partition vector
core_count	Array: number of core vertices in each part
CH_count	Array: number of core+halo vertices in each part
Halo_count	2D Array of size nparts by totalNodes: Halo_count(i,j) = k, node j is a halo of part i\ with k connections
sumCubes	Sum of cubes objective value
maxCh	maximum core-halo part size obective value

prg_initialize

Partition graph into nparts'

Compute cost of partition

Definition at line 216 of file prg_partition_mod.F90.

◆ prg_rand_node()

subroutine prg_partition_mod::prg_rand_node	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, intent(inout)	node,
		integer, intent(inout)	seed
	)

private

Pick a random node.

Parameters

gp	graph partitioning structure
node	output node
seed	random seed

Definition at line 526 of file prg_partition_mod.F90.

◆ prg_rand_shuffle()

subroutine prg_partition_mod::prg_rand_shuffle	(	integer, dimension(:), intent(inout)	array,
		integer, intent(inout)	seed
	)

private

Randomly shuffle array.

Random seed

Shuffle array

Definition at line 1137 of file prg_partition_mod.F90.

◆ prg_simannealing()

subroutine, public prg_partition_mod::prg_simannealing	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm,
		integer, intent(in)	niter,
		integer, intent(inout)	seed
	)

Graph partitioning based on Simulated Annealing.

Parameters

gp	Graph partitioning
xadj	CSR array of graph nodes
adjncy	CSR array of graph neighbors
nparts	Number of Parts
partNumber	Partition vector
core_count	Array: number of core vertices in each part
CH_count	Array: number of core+halo vertices in each part
Halo_count	2D Array of size nparts by totalNodes: Halo_count(i,j) = k, node j is a halo of part i\ with k connections
sumCubes	Sum of cubes objective value
maxCh	maximum core-halo part size obective value
niter	Number of iterations
seed	Random seed

Compute current cost of partition

Choose objective function to minimize

Perform SA

Find part with smalles size (should be included in update_prg_costPartition

if part(node) == max_ch_part, try to move node and it's neighbors to min_ch_part else move neighbors to part(node)

Check empty part exist move nodes from maxpart to empty part

move it neighbor in the max parts to the newpart

Update graph structure

For debuging

Definition at line 558 of file prg_partition_mod.F90.

◆ prg_simannealing_old()

subroutine, public prg_partition_mod::prg_simannealing_old	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm,
		integer, intent(in)	niter,
		integer, intent(inout)	seed
	)

Compute current cost of partition

Choose objective function to minimize

Perform SA

Update graph structure

For debuging

Definition at line 1475 of file prg_partition_mod.F90.

◆ prg_update_gp()

subroutine, public prg_partition_mod::prg_update_gp	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count
	)

Update graph structure

Allocate subgraph structure

Assign node ids to sgraph

Definition at line 1096 of file prg_partition_mod.F90.

◆ update_prg_costpartition()

subroutine, public prg_partition_mod::update_prg_costpartition	(	type (graph_partitioning_t), intent(inout)	gp,
		integer, dimension(:), intent(inout), allocatable	xadj,
		integer, dimension(:), intent(inout), allocatable	adjncy,
		integer, dimension(:), intent(inout), allocatable	partNumber,
		integer, dimension(:), intent(inout), allocatable	core_count,
		integer, dimension(:), intent(inout), allocatable	CH_count,
		integer, dimension(:,:), intent(inout), allocatable	Halo_count,
		real(dp), intent(inout)	sumCubes,
		real(dp), intent(inout)	maxCH,
		real(dp), intent(inout)	smooth_maxCH,
		real(dp), intent(inout)	pnorm,
		integer, intent(in)	node,
		integer, intent(in)	new_part
	)

Update cost of partition and the different parameters node is moves into new_part For each neighbor of node, the following cases hold: Case 1: neighbor is in old_part Case 2: neighbor is in new_part Case 3: neighbor is neither in old_ or new_part.

Parameters

gp	Graph partitioning
xadj	CSR array of graph nodes
adjncy	CSR array of 1043365660.0000000graph neighbors
nparts	Number of Parts
partNumber	Partition vector
core_count	Array: number of core vertices in each part
CH_count	Array: number of core+halo vertices in each part
Halo_count	2D Array of size nparts by totalNodes: Halo_count(i,j) = k, node j is a halo of part i\ with k connections
sumCubes	Sum of cubes objective value
maxCh	maximum core-halo part size obective value
node	Vertex that has moved to new_part
new_part	new part that node has moved to

Definition at line 400 of file prg_partition_mod.F90.

Variable Documentation

◆ dp

integer, parameter prg_partition_mod::dp = kind(1.0d0)

private

Definition at line 18 of file prg_partition_mod.F90.

◆ metis_index_kind

integer, parameter prg_partition_mod::metis_index_kind = METIS_INDEX_KIND

private

From /usr/include/metis.h.

IDXTYPEWIDTH = 32 --> metis_index_kind = 4 IDXTYPEWIDTH = 64 --> metis_index_kind = 8

Definition at line 24 of file prg_partition_mod.F90.

◆ metis_real_kind

integer, parameter prg_partition_mod::metis_real_kind = kind(METIS_REAL_KIND)

private

From /usr/include/metis.h.

REALTYPEWIDTH = 32 --> metis_real_kind = kind(0e0) REALTYPEWIDTH = 64 --> metis_real_kind = kind(0d0)

Definition at line 30 of file prg_partition_mod.F90.

Functions/Subroutines

Variables

Detailed Description

Function/Subroutine Documentation

◆ prg_accept_prob()

◆ prg_check_arrays()

◆ prg_costindex()

◆ prg_costpartition()

◆ prg_find_best_move()

◆ prg_get_largest_hedge_in_part()

◆ prg_kernlin()

◆ prg_kernlin2()

◆ prg_kernlin_queue()

◆ prg_metispartition()

◆ prg_rand_node()

◆ prg_rand_shuffle()

◆ prg_simannealing()

◆ prg_simannealing_old()

◆ prg_update_gp()

◆ update_prg_costpartition()

Variable Documentation

◆ dp

◆ metis_index_kind

◆ metis_real_kind