yloc - A Dynamic Topology Information System

Introduction

The goal of yloc is to create a dynamic topology information system that allows for a flexible representation of the hardware topology of modern architectures by incorporating existing open-source and vendor-specific data sources. To offer a more general and widely applicable solution to some of the shortcomings of existing tools for working with system topology, yloc has been designed with these principles in mind:

• Flexible data schema: Instead of relying on a tree data structure, data storage and representation in yloc is based on a flexible (multi-)graph representation. Nodes in this multi-graph represent components in the hardware setup of a machine, edges may represent any labelled relationship between these hardware components.

• Support for multiple data sources: Since our data representation format is very general, the tool has the ability to ingest and combine data from a variety of sources. In terms of our yloc prototype implementation, the ability to support multiple data sources is aided by a module system that makes it comparatively easy to add new data sources, such as vendor-specific tools.

• Basic abstract machine model: To attach semantic meaning to the components of the topology graph (nodes and edges), a simple extensible abstract machine model has been developed. This model covers the most important aspects of current-generation hardware found in high performance computing systems, but is also extensible in order to allow it to evolve to cover future hardware developments.

• Unification and integration of data sources: Since yloc allows data from multiple sources to be integrated into a single graph representation, the data domains of these sources may be overlapping. In order to provide a way to produce a coherently integrated data model, yloc identifies nodes that correspond to each other in different (sub-)graphs generated by different modules.

• Support for dynamic data: In addition to static information (hardware components and their relationship or connection), it may be often useful to augment this static structure with dynamic (time-varying) properties. Dynamic information may arise based on time-varying hardware properties, such as temperature or operating frequency of compute elements, or it may originate from software components, such as an application's dynamic load information.

• Query support: Having a flexible way to represent data in an information system is only a necessary, but not sufficient, condition for a useful and practical approach. What is additionally needed is a way to extract and find relevant data, i.e., a way to formulate and execute queries that can find and filter the data. This approach is supported in yloc by means of operations on the underlying graph, such as predicate-based graph views and support for graph algorithms such as computing shortest paths or performing a breadth-first search.

---

Requirements, Build and Install

Requirements

yloc uses the CMake build system (required CMake version 3.12+).

By default yloc depends on the Boost Graph Library (BGL). For the moment, yloc also depends on hwloc as the primary source of topology information. There are further dependencies for the different modules, although they aren't usually mandatory.

Building

In order to configure the software, create a build folder and run cmake <yloc-root> from within a build folder.

For example:

cd yloc
mkdir -p build ; cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build . -j

CMake will check for dependencies and fail with according messages if they are not met. Otherwise build files are generated that can be executed either with make or cmake --build .

There are CMake options to change the default build of yloc. To list all available options use cmake -L from the build folder.

At the moment there are options to enable or disable specific modules: YLOC_ENABLE_<MODULE>. They can be set using cmake -D, for example to deactivate usage of the NVML module:

cmake -DYLOC_ENABLE_NVML=OFF ..

Installation

cd build
cmake --install-prefix <install folder>
make install
# uninstall:
# xargs rm < install_manifest.txt

API Reference

To generate the full documentation in HTML or PDF format run:

cd build
cmake .. -DBUILD_DOC=ON
# html reference manual created in docs/html/index.html

# to generate the reference manual as pdf:
cd docs/latex
make -j
# generates refman.pdf in docs/latex

Yloc uses the Boost Graph Library (BGL) to represent the hardware topology in a graph data structure.

A topology graph can be created by constructing a yloc::Graph object. Its class is compatible with BGL and can be used with the BGL API and the algorithms.

See the examples in the example folder and the documentation in the build/doc folder for further details.

Vertex and Edge Query API

Iterating over all vertices in the topology graph:

yloc::Graph &graph;
for(auto vertex_id : yloc::vertex_range(graph)) {
  auto &vertex = graph[vertex_id];
}

Iterating over all edges in the topology graph:

for(auto edge_id : yloc::edge_range(graph)) {
  auto &edge = graph[edge_id];
}

Component Types

TODO

Component Properties

TODO

yloc::Graph &graph;

// default type return type of method 'get("property_name")' is std::optional<std::uint64_t>
for(auto vertex : yloc::vertex_range(graph)) {
  // query property (e.g. "memory") of vertex:
  auto val = graph[vertex].get("property_name");
   // access property value of vertex:
  if(val.has_value()) val.get();
}

for(auto edge : yloc::edge_range(graph)) {
  // query property (e.g. "latency") of edge:
  auto val = graph[edge].get("property_name");
   // access property value of edge:
  if(val.has_value()) val.get();
}

Algorithm API

A yloc::Graph is-a BGL graph (bidirectional adjacency list with vectors as containers for vertices and edges) and can be used with the BGL algorithms. However, yloc implements several commonly used graph algorithms (using BGL) for ease of use.

Breath First Search

Determining, for example, the number of hops from a start vertex to other vertices in the graph can be done with yloc::bfs_distance_vector. The default behavior of yloc::bfs_distance_vector is to count the number of hops to other vertices in BFS traversal and return the values in a vector.

yloc::Graph &graph;
yloc::vertex_t start = *boost::vertices(graph).first;
auto distances = yloc::bfs_distance_vector(graph, start);
for (auto v_other : yloc::vertex_range(graph)) {
    // distances[v_other] is the number of hops 
    // from vertex 'start' to 'v_other'
}

Sometimes it might be desireable to take other factors into account, for example the type of edges in the BFS traversal. Therefore, yloc::bfs_distance_vector takes a lambda as a third parameter, that will be executed when a tree edge is traversed during BFS.

The following example adds 10 to the distance each time a network interconnect edge is traversed as a tree edge during BFS in addition to counting the number of hops.

auto distances = yloc::bfs_distance_vector(graph, start, 
    [&](edge<Graph> edge, int val_pre) {
        return val_pre + 1 
               + (graph[edge].is_a<NetworkInterconnect> ? 10 : 0);
        }
    );

Dijkstra Shortest Path

TODO: yloc::dijkstra_path_distance_vector

yloc::Graph &graph;
yloc::vertex_t start = *boost::vertices(graph).first;

std::unordered_map<yloc::edge_t, std::uint64_t> edge_latency_map =
    yloc::make_edge_weight_map(graph, 
        [&](yloc::edge_t edge) { return graph[edge].get(std::string{"latency"}).value_or(0); });

auto pair = yloc::dijkstra_path_distance_vector(graph, start, edge_latency_map);

std::vector<yloc::vertex_t> predecessors = pair.first;  // shortest path information
std::vector<std::uint64_t>  distances    = pair.second; // minimum distances to vertices

Affinity Mask API

TODO

---

Examples

Please see the folder example for further examples.

---

yloc Modules

The yloc topology graph is generated and modified by modules. Yloc can be extended via custom modules. See the Module Readme for how to write a module.

---

Supported Topology Information Systems

Yloc currently implements modules for the following topology information systems:

• hwloc
• ROCm System Management Interface (ROCm SMI) Library
• NVIDIA Management Library (NVML)
• MPI