Parallel

Module Parallel.jl – LazySets algorithms that are parallelized.

interval_hull

Alias for box_approximation.

box_approximation(S::LazySet)::Hyperrectangle

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.

symmetric_interval_hull

Alias for box_approximation_symmetric.

box_approximation_symmetric(S::LazySet{N}
                           )::Union{Hyperrectangle{N}, EmptySet{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.

box_approximation_helper_parallel(S::LazySet{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!.

process_chunk!(S::LazySet{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!.

assign_chunk!(S::LazySet{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!.

distribute_task!(S::LazySet{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.

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