Table of Contents
Learning Outcomes
The goals of this assignment are to:
 Familiarize yourself with graph algorithms that are most applicable to HLS techniques, namely topological sorting and identifying the critical path.
 Observe the structure of commercial HLS data flow graphs.
 Practice C++ skills.
Preliminary
This assignent is located in the asst_graphs folder. All commands shown assume you are located in that folder in your terminal.
Install Packages
You will need the following packages:
sudo apt install cmake graphviz
Extract Graphs
Due to size contraints on Github, the graphs are in a zip files and need to be extracted. Run the following to extract the graphs:
make unzip_graphs
Inspect the code
niGraphs/
– This folder contains 2333 graphs of customer designs from National Instrument’s HLS tool (LabVIEW Communications System Design Suite – http://www.ni.com/labviewcommunications/). Feel free to look at these files. You will see each file defines a set of nodes and edges with associated properties. As we progress through the class material you will learn more about these properties, but you can ignore most of them for now, aside from a few that are specifically mentioned in this assignment.src/niGraphReader/
– This contains the NIGraphReader class, which will parse the graph files into NIGraph* data structures.src/niGraph/
– This contains the NIGraph class, as well as NIGraphNode and NIGraphEdge classes, which are the data structures for the graphs.src/main.cpp
– You will need to implement several functions in this file. You are free to split your code into additional files if you desire.
Build the code
The project uses cmake
as a build manager. Cmake is a tool that will automatically create necessary makefiles for use with the make
tool. The code can be built using the following commands:
cd build
cmake ../src
make
This will produce an executable located in build/main
. If you change any file contents, you only need to rerun make
to recompile. If you add new files, you will need to edit the src/CMakeLists.txt file.
Requirements
The goal of this lab is to perform a topological sort of a dataflow graph, identify the longest delay path, and create a graph visualization. Graph 0 shows a the graph for DelayGraph\_0.graphml
.
Your graphs should have the following properties:
 Show all nodes and edges. Some nodes don’t have edges.
 Nodes should be labeled with the node
id
, and the longest delay path to reach the node.  Edges should be labeled with the edge
delay
.  Edges along the longest delay path (ie, the critical path), should be colored red.
 The provided graphs are almost directed acyclic graphs (DAGs), except for a few feedback edges, which create cycles. These feedback edges should be colored in blue.
main()
The provided main function can be run in two modes:
 Mode 1: Selective graphs: You can provide a list of graph numbers as arguments to main:
./main 1 7 1300
For each graph this will perform topological sorting and print the sorted list of nodes, find the longest path, and generate a DOT file and PDF. Statistics are printed to a
results.txt
file. Note: Generating PDF files may not be possible for large graphs, and the program will stall.  Mode 2: All graphs: If you provide no arguments, all graphs will be processed. The sorted graph nodes won’t be printed, and no DOT files will be generated.
Part 1: Visualizing Graphs
You must write code to output an NIGraph
structure in DOT language. The code should be added to the following function:
void createDOT(const NIGraph &graph, const std::string outputPath,
NIGraphNodeList &longestPath,
std::map<NIGraphNode *, int> &nodeDelays) {
}
See http://www.graphviz.org/content/dotlanguage for the specification of the DOT language. For example, a simple DAG with two nodes (a
and b
) and one edge (delay = 3
) may have a DOT file like this:
strict digraph {
a [label="a\n0"];
b [label="b\n3"];
a > b [label=3; color=red];
}
Although the graph visualization relies on the longest path data, it is included first in this document as visualizing the graphs can sometimes be helpful in debugging your sorting or longest path analysis code. So, I suggest you complete the graph visualization without the longest path data first, then return and finish this step once you have the longest path analysis working.
Part 2: Topological Sorting
You will write code to perform a topological sort of a graph. See lecture slides or https://en.wikipedia.org/wiki/Topological_sorting.
The code should be added here:
NIGraphNodeList topologicalSort(const NIGraph &graph) {
NIGraphNodeList q;
// add code here
return q;
}
The function has a single input, an NIGraph
, and returns a topologically sorted list of nodes (NIGraphNode*
). Topological order is such that for every directed edge $uv$ from node $u$ to node $v$, $u$ comes before $v$ in the ordering. Since a topological sort is only possible for directed acyclic graphs (DAGs), you will need to ignore the feedback edges.
Part 3: Longest Path
In this last section you will write code to find the longest delay path in the graph, using the topologically sorted nodes from Part 2. This code should be written in this function:
int longestDelayPath(const NIGraphNodeList &topolSortedNodes,
NIGraphNodeList &longestPath,
std::map<NIGraphNode *, int> &nodeDelays) {
// add code here
}
The first arugment to this function is the topologically sorted list of nodes in the graph. The function populates two data structures: longestPath
should be populated with a list of nodes that make up the longest path, from start to finish, and nodeDelays
provides a map indicating the longest delay to each node in the graph. The delay of the longest path is returned from the function.
See lecture slides, wikipedia, or search on the web for how to determine the longest path from a topological sort. For a DAG, the longest delay path is also known as the critical path. This term is likely familiar to you in the circuit domain, as combinational logic can be represented using a DAG, and the critical path restricts the maximum frequency of the circuit.
Again, to ensure the graph is a DAG, you will \uline{need to ignore feedback edges}. Remember to ignore these edges when finding the longest back, and during the backtracking portion.
Deliverables

Make sure your code is pushed up to your Github repo.

Add a 1 page report, that includes a short paragraph about how your topological sorting algorithm works. Include a scatter plot, which plots the runtime for your topological sort code for ALL 2333 of the provided graphs. The plot should be of the following format:
 The xaxis should show the size of the graph ($V + E$)
 The yaxis should show the runtime of the topological sorting.
 Both the x and y axis should be in logarithmic scale, with appropriate ranges to fit your data points.
There are many ways to do a topological sort. For full marks, your chart data should show that your algorithm complexity is approximately O(V+E)
. Please don’t spend extra time performing analysis to show this; a visual inspection of the scatter plot is fine.
 Include the following data using your longest path code:
Graph  size (V+E)  Delay 

DelayGraph_0  197  8077 
DelayGraph_1  
DelayGraph_2  
DelayGraph_3  
DelayGraph_4  
DelayGraph_5  
DelayGraph_6  
DelayGraph_7  
DelayGraph_8  
DelayGraph_9  
DelayGraph_10 
 Include the longest path for DelayGraph_3. For example, the longest path for DelayGraph_0 is:
n0 > n14 > n15 > n19 > n21 > n23 > n24 > n25 > n26 > n27 > n29 > n43 > n44 > n50 > n51 > n56 > n60 > n70 > n71 > n74 > n75 > n78 > n76 > n77 > n79 > n80 > n81 > n82 > n83 > n84 > n88
Submission Instructions
Submit your code using a Github tag: lab1_submission
Instructions are provided here