Multiple data structures are available to represent a partition, addressing the different needs of the available algorithms.
set_i4: The most simple representation is simply an array of integers denoting the members of one part, an array of set_i4 consequently can represent the partition
partition_assignment denotes for each index (potentially with an indirection map) the partition it's assigned to.
partition_vec is a concise representation of the same information an array of type set_i4 holds, but only uses two allocatables, one to hold the elements of all sets and another to note the division indices in this array.
block_decomposition finally describes block decompositions only, where each division of one dimension is described by one instance of block_decomposition. Therefore, 2D block decomposition would typically use a 2-element array of block_decomposition.
Setting up for Partitioning
To decompose a data structure one first needs to describe the topology of the data structure in question. ScalES-PPM provides for several basic data types to make this step as simple as possible:
n-dimensional rectilinears like e.g. regular grids use use a rank 1 n-dimensional extent array to describe the enumeration of indices in each dimension
i.e. to describe a 2-dimensional grid with indices 1..m in x-direction and indices 1..n in y-direction the corresponding data structure would be declared as:
For repartitioning the input already is a partition. The following types are therefore both input and output argument to some routines.
Given p parts over a set of n elements, arbitrary partitions vary in requirements. To bridge the gap from succinct but rigid to flexible but more redundant data structures the following types are provided by :
partition_vec consists of two tables start(1:p+1) tabulates the sub-array of the second table elements which lists the elements sorted by partition, i.e. elements(start(x):start(x+1)-1) lists the elements of part x
set_i4 lists in its component array elem the elements for one (sub-)set. A vector of set_i4 can accordingly describe a partition.
partition_assignment with component part_range = [1,p], component array assigned tabulates for each element the assignment to partition elem(i) where elem(i) part_range
block_decomposition In a block decomposition, each part only contains one contiguous range of indices per dimension. Each dimension having elements 1..n can therefore be partitioned into parts where part i is partition(i).
basic routines and data structures for handling partitions
Definition ppm_set_partition_base.f90:47
Set partition
If your data has no inherent connectivity, i.e. the problem is embarrassingly parallel, graphs or grids are improper models to use for partitioning. In this case partitioning by weight only is probably the most sensible solution. The library provides a greedy method to partition such data sets.
For an already partitioned set the library offers a routine based on swapping elements such that memory reallocation can be avoided. The example is for the multi-process variant which has MPI collective call semantics.
USE ppm_set_repartition, ONLY: repartition_swap_mp
Based on the part and new_part arrays of above example, the application can then reorganize the data decomposition. If a certain amount of imbalance among partitions is tolerable, it can be beneficial to add an efficiency_threshold argument to the call to repartition_swap_mp.
Das diesem Bericht zugrundeliegende Vorhaben wurde mit Mitteln des Bundesministeriums für Bildung, und Forschung unter dem Förderkennzeichen 01IH08004E gefördert. Die Verantwortung für den Inhalt dieser Veröffentlichung liegt beim Autor.
Generated on Sun Mar 9 2025 00:00:00 for ScalES-PPM by 1.12.0