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

`LazySets.Parallel`

— ModuleModule `Parallel.jl`

– LazySets algorithms that are parallelized.

## Box approximations

`LazySets.Parallel.interval_hull`

— Function`interval_hull`

Alias for `box_approximation`

.

`LazySets.Parallel.box_approximation`

— Function`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.

`LazySets.Parallel.symmetric_interval_hull`

— Function`symmetric_interval_hull`

Alias for `box_approximation_symmetric`

.

`LazySets.Parallel.box_approximation_symmetric`

— Function`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.

`LazySets.Parallel.box_approximation_helper_parallel`

— Function`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!`

.

`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!`

.

## 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!`

.

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

`LazySets.Parallel._prange`

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