API Reference

Effect

Abstract supertype for task access effects.

Effects describe how a task interacts with a region of an object and are used to derive dependency edges in the DAG.

Read() <: Effect
Write() <: Effect
ReadWrite() <: Effect

Effect markers used in access declarations.

• Read() means the task only reads a region.
• Write() means the task overwrites or mutates a region.
• ReadWrite() means the task both reads and mutates a region.

Reduce(op) <: Effect

Reduction effect carrying the operator op.

Arguments

• op: Associative reduction operator, commonly + or *.

Notes

• Parallel reduction behavior depends on execution strategy.
• When using privatized reduction execution, task bodies should update through reduce_add!.

is_reduce(eff::Effect) -> Bool

Predicate that returns true only for Reduce(...) effects.

is_writeish(eff::Effect) -> Bool

Return whether eff should be treated as mutating for conflict analysis.

Returns

• false for Read()
• true for Write(), ReadWrite(), and Reduce(...)

reduce_op(r::Reduce)

Return the reduction operator stored in r.

Block(r::UnitRange{Int}) <: Region

One-dimensional contiguous index range.

IndexSet(idxs::AbstractVector{Int}) <: Region

Sparse set of explicit indices.

Key(k) <: Region

Region representing a single logical key k, typically used for map-like containers or keyed partitions.

Region

Abstract supertype for region descriptors used by access declarations.

A region scopes an effect to a subset of an object so Parables can distinguish independent accesses from conflicting ones.

Tile(I::UnitRange{Int}, J::UnitRange{Int}) <: Region

Two-dimensional rectangular tile defined by row range I and column range J.

Whole() <: Region

Region representing an entire object.

overlaps(a::IndexSet, b::IndexSet) -> Bool

Conservative overlap check for sparse index sets.

Currently returns true to avoid missed dependencies.

overlaps(a::Region, b::Region) -> Bool

Return whether regions a and b may overlap.

Semantics

• Whole() overlaps everything.
• Key(k1) overlaps Key(k2) only when k1 == k2.
• Block and Tile use range intersection checks.
• IndexSet currently uses a conservative overlap policy for IndexSet pairs.
• Unknown region combinations default to conservative true.

ranges_overlap(a::UnitRange{Int}, b::UnitRange{Int}) -> Bool

Return true when integer ranges a and b intersect.

Access

Access metadata used for dependency analysis.

Fields

• objid::UInt64: Stable object identity (objectid(obj)).
• obj::Any: Original object reference (kept for diagnostics).
• eff::Effect: Access effect (Read, Write, ReadWrite, Reduce).
• reg::Region: Region descriptor over the object.

access(obj, eff::Effect, reg::Region) -> Access

Construct an Access record from an object, effect, and region.

objkey(obj) -> (UInt64, Any)

Return (objectid(obj), obj) for reuse in access construction and debugging.

TaskSpec

Executable task plus declarative access metadata.

Fields

• name::String: Human-readable task label.
• accesses::Vector{Access}: Access declarations used for dependency analysis.
• thunk::Function: Zero-argument function containing task work.

TaskSpec(name::String, thunk::Function) -> TaskSpec

Construct a task with an empty access list.

add_access!(task::TaskSpec, obj, eff::Effect, reg::Region) -> TaskSpec

Append one access declaration to task and return the same task.

conflicts(a::Access, b::Access; can_parallel_reduce::Bool=false) -> Bool

Return whether two accesses require an ordering dependency.

Arguments

• a, b: Access declarations to compare.
• can_parallel_reduce: If true, allows Reduce(op) pairs with identical op to proceed in parallel.

Rules

• Different objects never conflict.
• Non-overlapping regions never conflict.
• Any write-like effect conflicts, except optional compatible reductions.

task_conflicts(ti::TaskSpec, tj::TaskSpec; can_parallel_reduce::Bool=false) -> Bool

Return true if any access pair across ti and tj conflicts.

DAG

Dependency graph over TaskSpec nodes.

Fields

• tasks::Vector{TaskSpec}: Tasks in insertion order.
• edges::Vector{Vector{Int}}: Adjacency list (i -> successors).
• indeg::Vector{Int}: Indegree count for each task.

Notes

• A newly created DAG() contains tasks only after push!.
• Call finalize! to construct edges and indeg.

DAG() -> DAG

Create an empty DAG builder with no tasks and no computed edges.

push!(dag::DAG, task::TaskSpec) -> DAG

Append task to dag and return the same DAG.

Notes

• This does not recompute dependencies. Call finalize! after appending tasks.

finalize!(dag::DAG; can_parallel_reduce::Bool=false) -> DAG

Build dependency edges and indegrees for dag using pairwise task conflict checks while preserving insertion order.

Arguments

• can_parallel_reduce: If true, compatible Reduce(op) tasks may execute concurrently.

Complexity

• O(T^2) over number of tasks.

execute!(
    dag::DAG;
    backend=:threads,
    nworkers::Integer=Threads.nthreads(),
    reduce_strategy=:serialize,
) -> DAG

Execute a finalized DAG with the selected backend and reduction strategy.

Arguments

• backend: :threads or :serial.
• nworkers: Number of worker tasks when backend=:threads.
• reduce_strategy: :serialize (default) or :privatize.

Returns

• The executed dag.

execute_serial!(dag::DAG) -> DAG

Execute dag in topological order on the current thread.

Useful for debugging and correctness baselines.

execute_threads!(dag::DAG; nworkers::Integer=Threads.nthreads()) -> DAG

Execute dag using Julia threads with a ready-queue scheduler.

Arguments

• nworkers: Number of worker tasks spawned to process ready nodes.

Notes

• Assumes dag has valid edges/indeg from finalize!.
• Rethrows the first task error after workers complete.

ReducerKey(objid, reg, op)

Internal key identifying a reduction target by object identity, region, and operator.

_reduce_identity(op::Function, ::Type{T}) where {T}

Internal helper that returns identity elements for supported operators.

alloc_reducers(dag::DAG; nthreads::Integer=Threads.maxthreadid()) -> ReduceContext

Allocate per-thread reduction buffers for all Reduce(...) accesses in dag.

Supported targets

• AbstractVector with regions Whole() and Block(...).

combine!(ctx::ReduceContext)

Internal helper that folds thread-local reduction buffers into destination objects.

execute_privatize!(
    dag::DAG;
    backend=:threads,
    nworkers::Integer=Threads.nthreads(),
) -> DAG

Execute dag with reduction privatization enabled.

Arguments

• backend: :threads or :serial.
• nworkers: Worker count for threaded backend.

Behavior

• Re-finalizes with can_parallel_reduce=true.
• Allocates reducer buffers for declared Reduce accesses.
• Executes the DAG.
• Combines per-thread buffers into real reduction targets.

reduce_add!(
    obj::AbstractVector,
    op::Function,
    reg::Region,
    idx::Int,
    value,
) -> AbstractVector

Accumulate value into obj[idx] using reduction operator op.

Arguments

• obj: Destination vector being reduced into.
• op: Reduction operator (for example +).
• reg: Declared reduction region (Whole() or Block(...)).
• idx: Global index in obj to update.
• value: Contribution to combine at idx.

Behavior

• In normal execution, updates obj directly.
• In privatized execution, updates a thread-local reduction buffer.

Notes

• reg and op must match a declared Reduce(op) access for the task.

@access obj eff reg

Declare one access inside a @task body.

Arguments

• obj: Object being accessed.
• eff: Effect instance (Read(), Write(), ReadWrite(), Reduce(op)).
• reg: Region instance (Whole(), Block(...), Key(...), ...).

Notes

• Valid only inside @task.

@accesses begin
    (obj1, eff1, reg1)
    (obj2, eff2, reg2)
    ...
end

Declare multiple accesses inside a @task body.

Each entry must be a 3-tuple (obj, eff, reg).

@dag begin
    ...
end

Create a DAG builder context, collect tasks appended via @spawn, and return a finalized DAG.

Example

dag = Parables.@dag begin
    Parables.@spawn Parables.@task "t1" begin
        ...
    end
end

@spawn expr

Append task expression expr to the current @dag builder.

Notes

• expr should evaluate to a TaskSpec (or compatible value accepted by push! on DAG).
• Valid only within @dag.

@task name begin
    ...
end

Create a TaskSpec from a task body.

Behavior

• Collects @access obj eff reg and @accesses begin ... end declarations into TaskSpec.accesses.
• Removes those access declarations from the runtime thunk so they are metadata only.
• Stores remaining statements as the task's zero-argument thunk.

Arguments

• name: Task name expression that must evaluate to a String.
• begin ... end: Task body containing access declarations and work.

Example

Parables.@task "scale" begin
    Parables.@access x Read() Whole()
    Parables.@access y Write() Whole()
    y .= 2 .* x
end

eachblock(data::AbstractArray, block_size::Integer) -> Vector{UnitRange{Int}}

Convenience overload equivalent to eachblock(length(data), block_size).

eachblock(n::Integer, block_size::Integer) -> Vector{UnitRange{Int}}

Split 1:n into contiguous blocks of size block_size (last block may be shorter).

Arguments

• n: Number of logical elements.
• block_size: Positive block size.

parables_foreach!(dag::DAG, blocks, task_builder::Function) -> DAG

Append tasks produced by task_builder(r, i) directly to an existing DAG.

parables_foreach!(dag::DAG, task_builder::Function, blocks) -> DAG

Do-block friendly overload for parables_foreach!.

parables_foreach(blocks, task_builder::Function; finalize::Bool=true) -> DAG

Build a DAG by applying task_builder(r, i) to each block.

Arguments

• blocks: Block collection (commonly ranges from eachblock).
• task_builder: Function returning a TaskSpec or collection of TaskSpec.
• finalize: If true, calls finalize! before returning.

parables_foreach(task_builder::Function, blocks; finalize::Bool=true) -> DAG

Do-block friendly overload:

parables_foreach(blocks) do r, i
    ...
end

parables_map!(
    dest::AbstractVector,
    data::AbstractVector,
    blocks,
    f::Function;
    finalize::Bool=true,
    name_prefix::String="map",
) -> DAG

Create block tasks that apply f elementwise to data and write into dest.

Arguments

• dest, data: Equal-length vectors.
• blocks: Index ranges defining task partitions.
• f: Elementwise transform.
• finalize: Whether to finalize the returned DAG.
• name_prefix: Task name prefix.

parables_map(
    data::AbstractVector,
    blocks,
    f::Function;
    finalize::Bool=true,
    name_prefix::String="map",
) -> Tuple{DAG, AbstractVector}

Allocate an output vector, build a block map DAG, and return (dag, dest).

parables_mapreduce(
    data::AbstractVector,
    blocks,
    op::Function,
    mapf::Function=identity;
    finalize::Bool=true,
    name_prefix::String="mapreduce",
) -> Tuple{DAG, Vector}

Build a block map-reduce DAG over data.

Arguments

• data: Input vector.
• blocks: Index ranges for per-task work.
• op: Reduction operator used by Reduce(op) and reduce_add!.
• mapf: Per-element transform before reduction.
• finalize: Whether to finalize the returned DAG.
• name_prefix: Task name prefix.

Returns

• (dag, acc) where acc is a length-1 vector storing the reduced value.

task_from_accesses(
    name::String,
    accesses::AbstractVector,
    thunk::Function,
) -> TaskSpec

Build a TaskSpec from a list of access tuples and a zero-arg thunk.

Arguments

• name: Task name.
• accesses: Iterable of (obj, eff, reg) tuples.
• thunk: Task body.

show(io::IO, a::Access)

Render an Access as a compact single-line summary:

Effect object#id region

show(io::IO, t::TaskSpec)

Render a TaskSpec with name and condensed access list.

explain_conflict(
    ti::TaskSpec,
    tj::TaskSpec;
    can_parallel_reduce::Bool=false,
) -> Union{Nothing, Tuple{Access,Access}}

Return the first conflicting access pair between ti and tj, or nothing when no conflict is found.

print_dag(dag::DAG; io::IO=stdout)

Print adjacency and levelized structure for a finalized DAG.

Notes

• If dag is not finalized, prints a message and returns.
• Also warns when remaining indegrees suggest a cycle.