Parallel

This section of the manual describes the parallel implementation of some algorithms in the LazySets library. These algorithms are implemented in the LazySets.Parallel module.

Box approximations

LazySets.Parallel.box_approximationFunction
box_approximation(S::ConvexSet{N}) where {N<:Real}

Overapproximation a convex set by a tight hyperrectangle using a parallel algorithm.

Input

  • S – convex set

Output

A tight hyperrectangle.

Algorithm

The center of the hyperrectangle is obtained by averaging the support function of the given set in the canonical directions, and the lengths of the sides can be recovered from the distance among support functions in the same directions.

source
LazySets.Parallel.box_approximation_symmetricFunction
box_approximation_symmetric(S::ConvexSet{N}) where {N<:Real}

Overapproximate a convex set by a tight hyperrectangle centered in the origin, using a parallel algorithm.

Input

  • S – convex set

Output

A tight hyperrectangle centered in the origin.

Algorithm

The center of the box is the origin, and the radius is obtained by computing the maximum value of the support function evaluated at the canonical directions.

source
LazySets.Parallel.box_approximation_helper_parallelFunction
box_approximation_helper_parallel(S::ConvexSet{N}) where {N<:Real}

Parallel implementation for the common code of box_approximation and box_approximation_symmetric.

Input

  • S – convex set

Output

A tuple containing the data that is needed to construct a tightly overapproximating hyperrectangle.

  • c – center
  • r – radius

Algorithm

The center of the hyperrectangle is obtained by averaging the support function of the given convex set in the canonical directions. The lengths of the sides can be recovered from the distance among support functions in the same directions.

The same load is distributed among all available workers, see distribute_task!.

source
LazySets.Parallel.process_chunk!Function
process_chunk!(S::ConvexSet{N},
               irange::UnitRange{Int},
               c::SharedVector{N}, r::SharedVector{N}) where {N<:Real}

Kernel to process a given chunk

Input

  • c – shared vector with the center of the hyperrectangle
  • r – shared vector with the center of the hyperrectangle
  • S – set
  • irange – indices range of the given worker

Algorithm

The center of the hyperrectangle is obtained by averaging the support function of the given convex set in the canonical directions. The lengths of the sides can be recovered from the distance among support functions in the same directions.

The load for each worker is passed through the irange argument. By default, the same load is distributed among all available workers. For details see distribute_task!.

source

Distributed functions

LazySets.Parallel.assign_chunk!Function
assign_chunk!(S::ConvexSet{N}, v::SharedVector{N}...) where {N<:Real}

Return the function that assigns the work for each process.

Input

  • S – convex set
  • v – variable number of shared vectors

Output

The function process_chunk! that equally distributes the load for each worker.

Notes

Use this function to distribute a given task acting on a set S and a pool v of shared vectors. The tasks are equally distributed among the number of processes.

See also distribute_task!.

source
LazySets.Parallel.distribute_task!Function
distribute_task!(S::ConvexSet{N}, v::SharedVector{N}...) where {N<:Real}

Distribute the assignment of each chunk among the available processes.

Input

  • S – convex set
  • v – variable number of shared vectors

Output

Nothing.

Notes

Use this function to distribute a given task acting on a set S and a pool v of shared vectors.

The task for each processor is distributed through remotecall_wait using a function assign_chunk! that should be defined elsewhere. The vectors v contain one or more shared vectors in which the values of the task are written.

Typically, the function assign_chunk! is a wrapper around some problem-specific process_chunk! function.

source
LazySets.Parallel._prangeFunction
_prange(v::SharedVector{N}) where {N<:Real}

Returns the indexes assigned to a process.

Input

  • v – shared vector of length n

Output

The indices range assigned to each process.

Notes

The indices are assigned such that the vector is equally distributed among the processes. If the worker is not assigned a piece, the unit range 1:0 is returned.

source