Skip to content

AGENTS.MD

Latest commit

 

History

History
71 lines (56 loc) · 7.31 KB

AGENTS.MD

File metadata and controls

71 lines (56 loc) · 7.31 KB

Framework API Notes

Graph Representation

  • VertexId/EdgeId are uint64_t aliases used across the codebase; Weight is an int64_t for weighted edges.
  • VertexEdgeMapping stores the [edge_start_index, edge_end_index) interval for a vertex in the global edge array.
  • CSRGraph is the sequential graph view with vertex_array (prefix sums) and edge_array (adjacency list).
  • DistributedCSRGraph wraps distributed vertex/edge arrays plus a matching array of edge weights. The vertex distribution (std::shared_ptr<DistributionStrategy>) defines ownership for vertices and, by extension, component roots in distributed algorithms.

Distribution Strategies (primitives/distribution_strategy.hpp)

  • DistributionStrategy is the abstract interface; every strategy must implement owner, local_size, to_local_index, to_global_index, and total_elements.
  • BlockDistribution is constructed from a prefix-sum array over workers. Rank k owns indices [_distribution[k], _distribution[k+1]); all conversions between global/local indices use this array.
  • RoundRobinDistribution owns every num_ranks-th element. to_local_index throws if invoked on a rank that does not own the element.

Distributed Containers

distributed::DistributedArray<T> (primitives/distributed_array.hpp)

  • Constructed with a DistributionStrategy and a kamping::Communicator. Optional third argument fills the local slice with a constant.
  • initialize_local(elements, rank) swaps in a pre-built local slice; it asserts the input matches the strategy’s local_size(rank).
  • set(global_index, value) queues remote writes that are flushed via exchange(sub_comm); local indices are written immediately.
  • set(global_index, value, OperationType) merges values with OperationType::{IDENTITY, MIN, MAX} locally or after exchange.
  • get(global_index) is only valid on the owning rank; it throws if called elsewhere.
  • local_data() exposes the mutable local vector for in-place updates. print_local()/print_local_vertex() are debugging helpers.
  • gather() exists for debugging/inspection only; production code must not rely on it because it materializes the entire array on one rank.

distributed::DistributedSet<T> (primitives/distributed_set.hpp)

  • Wraps a std::vector<T> owned by a communicator; inserts append, remove erases the first match, and contains performs a linear scan.
  • deduplicate() sorts the local vector and removes duplicates; use it before communications when uniqueness matters.
  • filter(predicate) removes all elements for which predicate(element) returns true.
  • redistribute(mapping) prepares an all-to-all exchange based on a user-supplied ownership function. Elements mapped to the current rank remain local; the rest are sent and replaced with the received buffer. max_send_buffer_size tracks the peak send volume for diagnostics.
  • redistribute(mapping, join_communication) temporarily splits the communicator (with MPI_Comm_split through kamping) when a subset should participate.
  • updateCommunicator(new_comm) swaps the communicator in-place so the container aligns with externally split communicators.
  • SortedDistributedSet<T> maintains the sorted invariant by inserting with lower_bound and reusing the base class utilities.

Frontier Abstractions (algorithms/distributed)

  • SetBasedDistributedFrontier wraps a DistributedSet<VertexId> for BFS-style waves. Construction seeds the frontier with vertices whose owner matches the local rank. It exposes:

    • add(vertex) and clear() for local staging.
    • exchange(mapping) to move vertices to their owning rank (typically graph->vertex_dist->owner).
    • deduplicate() and filter(predicate) to prune duplicates or already-processed vertices.
    • local_frontier() for the current slice, plus max_send_buffer_size() and updateCommunicator() passthroughs.

  • TraditionalDistributedFrontier<T> is an alternative queue built on std::unordered_set. Key methods:

    • Constructors accept a DistributionStrategy and communicator, optionally with an initial frontier vector.
    • add queues local or remote vertices while preventing duplicates with _visited.
    • exchange() performs an all-to-all, merges _next_frontier with received vertices, assigns BFS levels in _distances, clears staging buffers, and returns true when all ranks report an empty frontier (via logical AND).
    • visited(element) queries _visited; local_frontier() and distances() expose the current frontier and per-vertex depth map.

Distributed Algorithms

  • DistributedBFS consumes a DistributedCSRGraph, communicator, and initial frontier. Internals:

    • Maintains _distances as a DistributedArray<uint64_t> initialized to std::numeric_limits<uint64_t>::max().
    • The BFS loop: visit every vertex in the current local frontier, set its distance with OperationType::MIN, collect neighbors, rebuild the frontier, exchange() to send non-local vertices home, deduplicate(), and filter() away already-reached vertices. global_active is derived from a logical-OR allreduce over local_active.
    • Accessors: distances(), frontier(), get_current_distance(), and updateCommunicator().

  • TraditionalDistributedBFS uses TraditionalDistributedFrontier to propagate frontiers level by level until exchange() signals global quiescence. Useful for comparisons with the set-based variant.

  • BFSBasedDistributedConnectedComponent iterates over the block of vertices owned by each rank (block distribution expected). Whenever _bfs_runner.distances().get(vertex) is still ∞, the vertex seeds a new BFS, and the component count increments. The final count is reduced via plus allreduce.

  • BFSBasedDistributedConnectedComponentWithSubCommOptimization extends the above by splitting communicators once ranks exhaust their local vertex range, shrinking the active communicator for later BFS waves.

  • LabelPropagation and MinLabelPropagation prototypes demonstrate how DistributedArray can be reused for iterative label relaxation, but the current implementations are incomplete/commented out.

Executable Entry Points

  • src/main.cpp exposes a CLI (--generator, --start, --print-graph, --algorithm). It builds distributed vertex/edge arrays from KaGen output, constructs a DistributedCSRGraph, and runs either DistributedBFS or BFSBasedDistributedConnectedComponent. Timers are gathered and printed as JSON.
  • src/run_bfs.cpp mirrors the setup but selects a random global source vertex, runs an initial warm-up BFS to amortize MPI startup, and then measures a second BFS.
  • src/run_cc.cpp is the connected-components driver; it prints summary statistics (component count, rank count) after execution.

Operational Notes

  • Avoid DistributedArray::gather in production logic; it is intended for debugging small cases only.
  • DistributedArray::initialize_local currently throws if the element count mismatches the strategy; a TODO suggests a known bug, so be cautious when reusing it with different distributions.
  • Many algorithms assume BlockDistribution for vertex ownership; ensure alternative strategies provide equivalent invariants before reuse.
  • Kamping collectives (alltoallv, allgatherv, allreduce, barrier) are used to coordinate distributed state; synchronize timers before measurements when reproducibility matters.