5. File formats

This page summarizes the file formats used in OSP as inputs and outputs. Note that some example input files are available in the /data folder.

Computational DAG

OSP allows the computational DAGs to be read in $3$ different file formats. The interpretation of the input file in one of thes formats depends on the file extension.

HyperDAG format (.hdag)

This is a custom file format in OSP which represents every computational DAGs as a hyperDAG [1]. That is, for each non-sink vertex $v$, the directed edges going out from $v$ are replaced by a single hyperedge containing $v$ and all its children. Some example files in this format can be found in the /data/spaa folder; these DAGs originate from our hyperDAG database [2, 3]. Note that conversion between the DAG and hyperDAG representation of the same computational DAG is straightforward; OSP also offers a converter between the .hdag hypergraph and the .dot DAG format.

The first few lines of these files can be comment lines, starting with '%'. The first non-comment line contains three integers ' $m$ $n$ $q$', where $m$ is the number of hyperedges (i.e., non-sink vertices in the DAG), $n$ is the number of vertices, and $q$ is the number of pins (i.e., the sum of the sizes of all hyperedges).

This is followed by $m$ lines, each describing a hyperedge, with 1-3 integers separated by spaces, i.e., in the format ' $e$', ' $e$ $w_1$' or ' $e$ $w_1$ $w_2$'. This specifies that hyperedge $e$ has communication weight $w_1$ and memory weight $w_2$; weights that are not present are set to $1$ by default. The usage of these weights is problem-dependent, but internally, they are associated with the source vertex of the hyperedge. The hyperedge indices in these $m$ lines are supposed to be all distinct and between $0$ and $(m-1)$.

This is followed by $n$ lines, each describing a vertex, with 1-3 integers separated by spaces, i.e., in the format ' $v$', ' $v$ $w$' or ' $v$ $w$ $t$'. This specifies that vertex $v$ has compute weight $w$ and type $t$; the default values for $w$ and $t$ are $1$ and $0$, respectively. The vertex indices in these $n$ lines are supposed to be all distinct and between $0$ and $(n-1)$.

This is followed by $q$ lines, each describing a pin, in format ' $e$ $v$' (two integers separated by a space). Here $0 \leq e < m$ is a hyperedge index and $0 \leq v < n$ is a vertex index, and the line indicates that vertex $v$ is contained in hyperedge $e$. If this is the first line where hyperedge $e$ appears, then $v$ is the source vertex of this hyperedge $e$; otherwise, it is a target vertex in $e$. In the DAG representation of the computation, for each hyperedge $e$, we have a separate directed edge from the source vertex of $e$ to every target vertex of $e$.

DOT format (.dot)

In .dot files, the computations are described as DAGs. This format allows to list the properties of each vertex and edge with human-readable labels. Some example files in this format can be found in the /data/dot folder.

The first line here contains 'digraph G {', and the last line contains '}'. Between these, we first have $n$ lines (where $n$ is the number of vertices), each describing a vertex of the DAG. These vertex description lines are best explained with an example:
0[work_weight="5";comm_weight="4";mem_weight="3";type="0";];
Here the first integer ($0$ in this case) is the index of the vertex between $0$ and $(n-1)$, and the square brackets contain optional data for the vertex: its work (compute) weight, its communication weight, its memory weight, and its type. The vertex lines are expected to be sorted by vertex index from $0$ to $(n-1)$.

We then have a separate line for each directed edge of the DAG. An example for an edge description line is:
1->2 [comm_weight="1";];
which specifies that there is a directed edge from vertex $1$ to vertex $2$, with communication weight $1$. The communication weights assigned to the edges are currently only used in a few algorithms in OSP.

Sparse matrix format (.mtx)

Finally, OSP can also construct computational DAGs from a sparse lower triangular matrix, interpreting each row as a vertex, and each non-zero entry as an edge. This coincides with the natural DAG representation of the scheduling problems for SpTRSV tasks [4].

The sparse matrix files are expected in a standard matrixmarket format. They might begin with several comment lines, each starting with the character '%'. The first non-comment line contains three integers: the number of rows and columns in the matrix (which must be equal in our case, let us denote it by $n$), and then the number on non-zero entries $z$. This is followed by $z$ distinct lines of the form ' $v_1$ $v_2$ $l$', i.e., three values separated by spaces. $v_1$ and $v_2$ must be integers with $n > v_1 > v_2 \geq 0$, resulting in a directed edge from vertex $v_2$ to vertex $v_1$. The last number $l$ is a double, it specifies the entry of the matrix in the given cell; this is not required for scheduling, only if we want to run a concrete SpTRSV computation. This format does not allow to specify vertex weights explicitly; they are calculated from the workload in the corresponding SpTRSV problem.

Architecture model

The second vital part of the input is the architecture or machine model for the scheduling; we often used the .arch extension for these files.

The first line of the file must contain 3-6 on-negative integers, separated by spaces. The first three integers are the main parameters of the BSP model: 1) the number of available processing units $P$ (cores/processors/devices) for the scheduling problem, 2) the cost $g$ of sending a single unit of data (describing the network bandwidth), and 3) the synchronization cost $L$ incurred by each superstep [2, 5]. These numbers must be present in all architecture files. The 4th number specifies the memory constraint type: the values 0, 1, 2 and 3 mean 'none', 'local', 'global' and 'persistent and transient', respectively. The 5th number specifies the memory constraint; it is ignored if the constraint type is 'none'. Finally, if we have a 6th number, it must be 0 or 1; this is an indicator bit for whether processor types are given in the architecture file.

If the first line contains 6 numbers, and the last number is 1, then we have a heterogeneous problem instance. In this case, the next line must contain $P$ non-negative integers, separated by spaces; the $i$-th integer specifies the type of the $i$-th processor. The app interface of OSP assumes by default that vertex type $i$ can only be executed on processor type $i$ (if the number of vertex and processor types is equal).

Finally, the next $P^2$ lines each have three integers, separated by spaces, describing the communication cost multiplier between a given pair of processors (for NUMA effects). Each line must contain the identifiers of the source and target processors (between $0$ and $P-1$), and the non-negative communication cost multiplier for the pair of processors. For instance, the line '0 2 7' describes that the cost of sending any data from processor 0 to processor 2 is multiplied by 7. For an example of uniform communication costs, consider the example file /data/machine_params/p3.arch.

The file might also have comment lines between the different blocks, starting with the '%' character; these lines are ignored.

Output file

OSP can output the BSP schedule into a text file if desired.

The first line of this text file starts with '%%', and textually describes the number of processors and supersteps.

This is followed by a line with 4 distinct integers, separated by spaces. The first three of these numbers is the number of vertices $n$ in the DAG, the number of processors in the architecture, and the number of supersteps in the schedule, respectively. The last number is 1 if the file also contains an explicit communication schedule description, and 0 otherwise.

This is followed by $n$ distinct lines, each with three different integers ' $v$ $p$ $s$' separated by spaces, meaning that vertex $v$ is assigned to processor $p$ and to superstep $s$.

If we have an explicit communication schedule, then this is followed by several further lines, each with four different integers ' $v$ $p_1$ $p_2$ $s$' separated by spaces, meaning that the output data of vertex $v$ is communicated from processor $p_1$ to processor $p_2$ in the communication phase of superstep $s$.

Further problem variants

Note that there are also several other problem variants in OSP.

In pebbling problems, the input is the same as in a scheduling problem. The output file here is a textual description of the schedules, describing which vertices are computed, loaded and saved in each step.

In hypergraph partitioning problems, the input can be read in several different ways. If the input is a computational DAG file with '.hdag' extension, then a hypergraph is created from its hyperDAG interpretation [1]. There is also an alternative read function for computational DAGs from '.hdag' files, which instead interprets each directed edge as a hyperedge of size 2. Finally, one can also read a sparse matrix from an '.mtx' file, and form a hypergraph from this based on the fine-grained model [6].

The output in partitioning problems is again a text file. The first line of this is a comment line starting with '%%', specifying the number of parts in text. This is followed by $n$ lines (where $n$ is the number of vertices), each with two integers ' $v$ $p$' separated by spaces, meaning that vertex $v$ is assigned to partition $p$.

References

• [1] Pal Andras Papp, Georg Anegg, and Albert-Jan N. Yzelman. Partitioning hypergraphs is hard: Models, inapproximability, and applications. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 415–425, 2023. (full preprint)
• [2] Pal Andras Papp, Georg Anegg, Aikaterini Karanasiou, and Albert-Jan N. Yzelman. Efficient multiprocessor scheduling in increasingly realistic models. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 463–474, 2024. (full preprint)
• [3] HyperDAG_DB: database of computational DAGs in hyperDAG format, available on GitHub.
• [4] Toni Boehnlein, Pal Andras Papp, Raphael S. Steiner, Christos K. Matzoros, and Albert-Jan N. Yzelman. Efficient parallel scheduling for sparse triangular solvers. In 2025 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 2025. (full preprint)
• [5] Pal Andras Papp, Georg Anegg, and Albert-Jan N. Yzelman. DAG scheduling in the BSP model. In Proceedings of the 50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 238–253, 2025. (full preprint)
• [6] Timon E. Knigge, and Rob H. Bisseling. An improved exact algorithm and an NP-completeness proof for sparse matrix bipartitioning. In Parallel Computing 96, 102640. 2020.