• Due Date: Friday 31 October 2025, before 23:59.
• Team Size: 2 (pair design/programming).
  Note that as of the 2017-2018 Academic Year, each International student should team up with a "local" student (i.e., whose Bachelor degree was obtained at the University of Antwerp).
• Submission Information:
  • Only one member of each team submits a full solution.
  • This must be a compressed archive (ZIP, RAR, TAR.GZ...) that includes your report and all models, images, code and other sources that you have used to create your solution.
  • The report must be in PDF and must be accompanied by all images.
  • Images that are too large to render on one page of the PDF must still be rendered on the PDF (even though unclear), and the image label should mention the appropriate file included in the submission archive.
  • Make sure to mention the names and student IDs of both team members.
  • The other team member must submit a single HTML file containing the coordinates of both team members using this template.
• Submission Medium: BlackBoard Ultra. Beware that BlackBoard's clock may differ slightly from yours. If BlackBoard is not reachable due to an (unpredicted) maintenance, you submit your solution via e-mail to the TA. Make sure all group members are in CC!
• Contact / TA: Rakshit Mittal.

In this assignment, you will learn to create and use Causal-Block Diagrams (CBD) using the pyCBD framework created by our lab. You will learn:

• How to transpile CBD models into standalone executable C code
• About dependency graphs, topological sorting, and algebraic loops
• About the numerical analysis, accuracy and stability of integration methods
• Optimization and comparison of performance between interpreted (Python) and compiled (C) code
• In order to get a better understanding about how tools like OpenModelica and MatLab Simulink work behind the scenes.

You are discouraged but allowed to make use of any GenAI tool in solving the assignment or writing the report (for example, to correct grammatical mistakes) as long as you adhere to the UA Guidelines for students on responsible use of GenAI.

You are required to cite any use of GenAI and describe what portions of the assignment you used it for.
You should also mention all other sources, including collaborations.

Note that a significant part of demonstrating that the learning goals have been achieved, includes being able to

1. explain the relevant concepts in the assignment,
2. explain the design choices in your implementation, and
3. critically discuss your solution.

This will be evaluated in a short (~15 minute) oral evaluation, which will be conducted in the week following the deadline of every assignment.

You will use this Python-based CBD framework for all tasks. The zip-file contains a full Python framework to allow CBD modelling in Python. You can install the Python package within your Python virtual/environment by executing the following command from within the src folder:

pip install .

To view the documentation you can execute the docs.bat or docs.sh scripts. The documentation is already provided in the zip-file. You can view it by opening doc/_build/pyCBD.html in a browser. Additionally, the documentation provides a set of examples which may help you in completing this assignment.

Note: The internal implementation of pyCBD will be much more complicated compared to the algorithms introduced in the lectures. If something is not clear, or if you have found an issue/bug, or if you have a feature request, please contact the TA.

Please read the documentation of everything you use! If the documentation explicitly states you cannot do something, don't! If you use a function or a class in a way that disregards the "warning", "danger", "attention"... labels, you will not receive any points on that task, even if it produces the correct results.

Once the simulator is installed, it works with any IDE, including Jupyter Notebooks.

For creating plots of simulation traces, Bokeh, MatPlotLib and SeaBorn are supported.

DrawioConvert is an additional tool that allows the creation, visualization and code generation of coupled CBDs. The tool may still have small bugs, and its use is optional, however incredibly useful. It uses DrawIO as a front-end. A small tutorial on how to use the tool is provided. Please contact the TA if you experience any problems.

• DrawIO Library
• Download Python Code
• Requires: Jinja2

You should first install DrawIo from this link

Essentially, using this tool, you can define your CBDs in a graphical environment (much like the graphical editor of OMEdit), and then use the DrawioConvert Python code to generate Python code that instantiates a CBD model based on the PyCBD framework. It simplifies the creation of your CBD and you are encouraged to use it.

This assignment consists of three main parts and five additional tasks:

1. CBD to C Code Generation (35%)
2. Integration Methods (25%)
3. LaTeX Equation Generator (15%)
4. Additional Tasks (5 × 5% = 25%)

Note: This task assumes you know the C programming language. A simple tutorial can be found on the W3 Schools Website. You need it to understand and debug the generated C-code from your PyCBD model.

The Python CBD simulator is flexible and easy to use, but its execution is relatively slow due to Python's interpreted nature and the overhead of object-oriented abstractions. In embedded systems, real-time control, or high-performance computing scenarios, we need faster execution.

The solution is code generation or transpilation: automatically converting a high-level CBD model into optimized C code that can be compiled and executed much faster. This is similar to how tools like Modelica (OpenModelica) and Simulink work behind the scenes:

1. Flatten the hierarchical model into a flat structure
2. Analyze dependencies to determine the order of computation
3. Detect algebraic loops (circular dependencies)
4. Generate C code that implements the same computations
5. Compile and execute the C code

Your Task

You will implement a CBD-to-C transpiler that converts a flattened CBD model into standalone C code. We provide you with a template file that contains the overall structure, but with several key functions left incomplete for you to implement.

Sub-task 1.1: Understand the Template

Download and examine the CBD2C_template.py file. The template includes:

• Signal mapping: Maps each block's output to an array index (stored in a Python dictionary)
• State structure: A C struct containing:
  • A 2D array signals[NUM_SIGNALS][HISTORY_SIZE] for storing current and past signal values
  • A ring buffer index to manage history
  • Time, delta_t, and iteration counters
• Code generation functions: Methods to generate C code for headers, initialization, computation, and main loop

Study the template to understand:

1. How signals are accessed using direct array indexing: state.signals[0][state.current_idx]
2. How the ring buffer works to store history efficiently
3. The overall structure of the generated C code

Sub-task 1.2: Implement Dependency Graph and Topological Sort

In the template, the following functions are marked as TODO and need your implementation:

def _build_dependency_graph(self, cbd_model):
    """
    Build a dependency graph for the flattened CBD model.
    
    Args:
        cbd_model: The flattened CBD model
    
    Returns:
        A dependency graph structure (you decide the representation)
    
    TODO: Implement this function
    """
    pass

def _topological_sort(self, dep_graph):
    """
    Perform topological sort on the dependency graph to determine
    the order in which blocks should be computed.
    
    Args:
        dep_graph: The dependency graph from _build_dependency_graph
    
    Returns:
        A list of blocks in topological order
    
    TODO: Implement this function. You may use Tarjan's algorithm,
    Kahn's algorithm, or depth-first search.
    """
    pass

def _detect_algebraic_loops(self, dep_graph):
    """
    Detect algebraic loops (strongly connected components) in the
    dependency graph.
    
    Args:
        dep_graph: The dependency graph
    
    Returns:
        A list of strongly connected components (each is a list of blocks)
    
    TODO: Implement this function
    """
    pass
				

Implementation Requirements:

• You must build a directed graph where:
  • Each node represents a block in the CBD
  • An edge from block A to block B means "B depends on A" (B's input is connected to A's output)
• Implement a topological sorting algorithm (e.g., DFS-based, Kahn's algorithm, or Tarjan's)
• Detect strongly connected components (algebraic loops) - blocks that have circular dependencies
• Your code should handle:
  • Simple linear chains (A → B → C)
  • Fan-out (one block feeding multiple blocks)
  • Feedback loops with delay blocks (which break cycles)
  • Algebraic loops (for now, just detect and warn)

Hints:

• Look at pyCBD.depGraph for reference (but implement your own version)
• DelayBlocks break cycles - they depend on their IC input at iteration 0, nothing at other iterations
• Test with simple models first (constants, adders) before complex ones
• The lectures on dependency graphs and topological sorting will be helpful

Sub-task 1.3: Block Code Generation

Once you have the computation order, complete the _generate_block_computation() function to generate C code for each block type. The template provides examples for common blocks:

• ConstantBlock: state.signals[idx][state.current_idx] = constant_value;
• AdderBlock: state.signals[out_idx][state.current_idx] = state.signals[in1_idx][state.current_idx] + state.signals[in2_idx][state.current_idx];

You need to complete code generation for at least these block types:

• DelayBlock
• ProductBlock, NegatorBlock, InverterBlock
• GenericBlock (for sin, cos)
• LessThanBlock, EqualsBlock

Report and describe your completed CBD2C.py implementation

Sub-task 1.4: Testing and Validation

Test your transpiler with the following CBDs:

1. Two constants added together
2. A counter (adder with delay feedback)

For each test:

• Show the CBD model (graphical or code).
• Show the generated C code.
• Compare Python simulation output vs C code execution output
• Verify they match (or explain any differences)

Computing the integral of a function is a common practice in simulation systems. It can be used for specifying time-dependent simulations, constructing (PID) controllers and even identifying accumulative errors. Any complex Cyber-Physical process that happens over a certain period of time makes use of integrators, however their computation is always a numerical approximation. This task will compare two integration methods and their accuracy.

Table 1: Comparison of Euler integration methods.

Backwards Euler Method	Forwards Euler Method
$$I_0 = f(t_0)\cdot \Delta t$$$$I_1 = f(t_1)\cdot \Delta t$$$$I = I_0 + I_1$$	$$I_0 = f(t_1)\cdot \Delta t$$$$I_1 = f(t_2)\cdot \Delta t$$$$I = I_0 + I_1$$
computed over 1 iteration	computed over 1 iteration

Tasks

Your job is to implement and compare two integration methods using DrawioConvert.

Sub-task 2.1: Implement Integrators

1. Using DrawioConvert, create two coupled CBD blocks implementing:
   • Backwards Euler integrator (similar to the built-in IntegratorBlock, but build your own)
   • Forwards Euler integrator
2. Each integrator block should have:
   • An input IN1 for the function to integrate
   • An input IC for the initial condition
   • An output OUT1 for the integrated value
3. Include clear, readable images of your DrawIO diagrams
4. Include the generated Python code for both integrators

Sub-task 2.2: Test Function

For the function $g(t) = \dfrac{t + 2}{(t + 3)^2}$, it is known that the integral over the range $[0, 100]$ is: $$\int_0^{100} g(t) dt = \int_3^{103} \left(\dfrac{1}{u} - \dfrac{1}{u^2}\right) du = \left[\ln(|u|) + \dfrac{1}{u}\right]_3^{103} \approx 3.212492104$$

1. Implement $g(t)$ as a coupled CBD block using DrawioConvert
2. It should have a single input (time $t$) and single output (value of $g(t)$)

Sub-task 2.3: Accuracy Comparison

1. Create a complete simulation model that:
   • Uses your $g(t)$ function block
   • Integrates $g(t)$ using both Backwards and Forwards Euler
   • Simulates for $t \in [0, 100]$
2. Run simulations with three different step sizes:
   • $\Delta t = 0.1$
   • $\Delta t = 0.01$
   • $\Delta t = 0.001$
3. Compare the results against the analytical solution (3.212492104)
4. Create a table showing:
   • Step size
   • Backwards Euler result
   • Forwards Euler result
   • Absolute error for each method
5. Which method is more accurate? Why? How does step size affect accuracy?

Mathematical models are often documented using equations. For CBD models, we can automatically generate LaTeX code that represents the model's denotational semantics - the mathematical equations describing what each signal computes.

This is useful for:

• Documentation and presentations
• Mathematical analysis and verification
• Understanding the model at a glance
• Academic papers and reports

Task: Implement a LaTeX Equation Generator

Create a Python module that takes a CBD model and generates LaTeX code representing its equations in three different forms:

1. CT-CBD (Continuous Time): The original continuous-time model's denotational semantics
2. DT-CBD (Discrete Time): The inlined/discretized model as a set of equations (order doesn't matter)
3. Sorted DT-CBD: The computation order with dependencies resolved (order matters, except for algebraic loops)

Step 1: Generate LaTeX for CT-CBD Model

For the original continuous-time CBD model (before discretization), generate the denotational semantics showing the continuous behavior.

For example, an integrator in continuous time is represented as:

    \[
      \frac{dx}{dt} = f(t, x)
    \]
				

This represents the mathematical intent of the model before discretization.

Step 2: Generate LaTeX for DT-CBD Model (Inlined/Discretized)

After discretization (e.g., using Backwards or Forwards Euler), generate the discrete-time equations. These should be formatted as a set of equations using \left\{, indicating that the order doesn't matter semantically.

Example transformations:

• ConstantBlock("c", 5.0) → c(i) = 5.0
• AdderBlock("sum") with inputs from blocks a and b → sum(i) = a(i) + b(i)
• ProductBlock("mult") → mult(i) = in1(i) \cdot in2(i)
• DelayBlock("delay") with IC from ic and input from x → delay(i) = ic(0) when $i=0$, delay(i) = x(i-1) when $i>0$
• GenericBlock("sine", "sin") → sine(i) = \sin(input(i))
• IntegratorBlock (Backwards Euler) → x(i) = x(i-1) + \Delta t \cdot f(i)

Format as a set of equations:

    \documentclass{article}
    \begin{document}
    \[
      \left\{
        \begin{array}{rcl}
         v(i) & = & w(i) - 2\\
         w(i) & = & w(i-1) + v(i-1) + 3\\
        \end{array}
      \right.
    \]
    \end{document}
				

Which renders as:

The \left\{ notation indicates these are the denotational semantics of the DT-CBD - what the equations mean, regardless of computation order.

Step 3: Generate LaTeX for Sorted DT-CBD Model

After applying topological sort from Part 1, generate the equations in computation order. Use \[ (without the set braces) to show this is a sequential computation where order matters.

    \documentclass{article}
    \begin{document}
    \[
      \begin{array}{rcl}
       w(i) & = & w(i-1) + v(i-1) + 3\\
       v(i) & = & w(i) - 2\\
      \end{array}
    \]
    \end{document}
				

Important: If there are algebraic loops (strongly connected components), they must still be rendered as a set with \left\{ since they need to be solved simultaneously:

    \[
      \begin{array}{rcl}
       a(i) & = & c(i) + 1\\
       \left\{
         \begin{array}{rcl}
          b(i) & = & c(i) \cdot 2\\
          c(i) & = & b(i) + d(i)\\
         \end{array}
       \right. \\
       d(i) & = & a(i) - 3\\
      \end{array}
    \]
				

This sorted representation is very close to the generated C code - it shows the actual execution order.

Hints:

• Use block.getPath() to get full hierarchical names (e.g., "controller.pid.sum")
• Sanitize names for LaTeX (replace underscores with escaped underscores: \_)
• Use the topological sort from Part 1 to order equations for the sorted DT-CBD
• For DelayBlocks, you may want to generate two equations or use piecewise notation
• LaTeX math operators:
  • Addition: +
  • Multiplication: \cdot or \times
  • Division: \frac{a}{b} or a / b
  • Functions: \sin, \cos, \exp, \log
  • Subscripts: x_{i-1}
  • Derivatives: \frac{dx}{dt}

Report your LaTeX generator implementation (CBD2LaTeX.py)

For each of the following models, show all three LaTeX representations (CT-CBD, DT-CBD, and Sorted DT-CBD) with compiled PDF screenshots:

1. The counter model from Part 1
2. Your Backwards Euler integrator from Part 2
3. Your Forwards Euler integrator from Part 2
4. The complete $g(t)$ integration model (function + integrator)

Note: This part of the assignment is optional. You may choose to do some or all of the following tasks.

The following five tasks extend your transpiler with important features and optimizations. Each task is worth 5% of your total grade.

For each task, show that your implementation works with a clear example, including before/after comparisons where applicable.

Task 1: Signal Name Macros (5%)

In the base implementation, signals are accessed using array indices like state.signals[0][state.current_idx]. This is error-prone and hard to read/debug.

Extend your transpiler to generate C preprocessor #define macros for signal names.

Implementation:

1. Map each signal to a unique index: #define C1_OUT1 0, #define C2_OUT1 1, etc.
2. Generate helper macros for accessing signals:

   #define GET(sig) (state.signals[sig][state.current_idx])
   #define GET_PREV(sig) (state.signals[sig][(state.current_idx + HISTORY_SIZE - 1) % HISTORY_SIZE])
   #define SET(sig, val) (state.signals[sig][state.current_idx] = (val))
   						

3. Update your code generation to use these macros: SET(ADD_OUT1, GET(C1_OUT1) + GET(C2_OUT1));
4. Sanitize signal names to valid C identifiers (replace dots, dashes, etc. with underscores)

Task 2: Constant Folding Optimization (5%)

If a block's inputs are all constants, we can compute its output at code generation time instead of runtime.

For example, if c1 = ConstantBlock(5), c2 = ConstantBlock(3), and add = AdderBlock() adds them, we can generate SET(ADD_OUT1, 8.0) directly instead of SET(ADD_OUT1, 5.0 + 3.0).

Implement constant folding optimization for all block types.

Implementation:

1. Add a method to detect if a block's inputs are all constants:

   def _is_constant_block(self, block):
       """Returns True if block is a ConstantBlock or has been folded to constant."""
       return isinstance(block, ConstantBlock) or block in self.folded_constants
   
   def _can_fold(self, block):
       """Returns True if all inputs come from constant blocks."""
       for input_port in block.getInputPorts():
           incoming = input_port.getIncoming()
           if incoming is None:
               return False
           if not self._is_constant_block(incoming.source.block):
               return False
       return True
   						

2. Before generating code, evaluate constant blocks:
   • AdderBlock: sum all constant inputs
   • ProductBlock: multiply all constant inputs
   • NegatorBlock: negate the constant
   • GenericBlock("sin"): compute sin(constant)
   • And so on for all block types
3. Generate SET(output, computed_value) instead of the full computation
4. Track which blocks have been folded to extend folding transitively

Task 3: Initialization vs. Iteration Code Separation (5%)

Some blocks behave differently at iteration 0 (initialization) vs. subsequent iterations. Currently, we check if (iteration == 0) at runtime for every iteration.

Generate separate code for initialization (iteration 0) and steady-state iterations (iteration > 0).

Implementation:

1. Build two separate dependency graphs:
   • init_dep_graph: For iteration 0 (DelayBlocks use IC input)
   • steady_dep_graph: For iterations > 0 (DelayBlocks use previous IN1)
2. Generate two separate computation functions:

   void cbd_step_init(CBDState* state) {
       /* Initialization: blocks that depend on IC */
       SET(DELAY_OUT1, GET(IC_OUT1));
       /* ... other init computations ... */
   }
   
   void cbd_step(CBDState* state) {
       /* Steady state: no IC dependencies */
       SET(DELAY_OUT1, GET_PREV(IN1_OUT1));
       /* ... other computations ... */
   }
   						

3. Modify main simulation loop:

   /* Simulation loop */
   if (iter == 0) {
       cbd_step_init(&state);
   } else {
       cbd_step(&state);
   }
   						

Task 4: Scope-Based Computation & Multi-Rate Scheduling (5%)

Not all signals need to be computed at every iteration. Memory blocks (Delay, Integrator) must be updated every Integration Interval (II), but output signals may only need updating every Communication Interval (CI).

Concepts:

• Integration Interval (II): Time step for numerical integration ($\Delta t$)
• Communication Interval (CI): Time step for output/tracing ($CI = K \times II$)
• "Must-Compute" Part: Blocks feeding into memory blocks (must run every II)
• Scope Block: Special block marking signals to trace (run every CI)

Implement multi-rate scheduling.

Implementation:

1. Create a ScopeBlock that marks signals for tracing (has inputs, no outputs)
2. Identify "must-compute" blocks: find all memory blocks and traverse backwards to find their dependencies
3. Identify "scope-required" blocks: find all blocks feeding into ScopeBlocks
4. Remove unused blocks: any block not in must-compute AND not in scope-required
5. Generate two C functions:
   • cbd_step_ii(): Must-compute schedule (runs every iteration)
   • cbd_step_ci(): Full schedule including scope (runs every K iterations)
6. Show an example where only 10% of blocks are in must-compute, demonstrating significant speedup

Task 5: Performance Benchmarking (5%)

Now that you have a transpiler, measure its performance benefit by comparing Python simulation vs. compiled C execution.

Benchmark and compare execution times.

Implementation:

1. Take g(t) with your Backwards Euler integrator from Part 2
2. Measure Python simulation time using time.time()
3. Generate C code, compile with gcc -O3
4. Measure C execution time (using time command or C's clock())
5. Test with different simulation lengths: 1,000, 10,000, and 100,000 iterations
6. Run each test multiple times and average the results
7. Create a table and plot showing:
   • Simulation length
   • Python time
   • C time
   • Speedup factor
8. Answer: What is the speedup? When does C code generation become worthwhile?

• All parts of this assignment use Python 3.6+. Do not use features from Python 2.7 (discontinued as of January 1, 2020).
• You will need a C compiler (GCC or Clang on Linux/Mac, MinGW on Windows)
• The files for DrawioConvert can be found here:
  • Small Tutorial
  • DrawIO Library
  • Download Python Code
  • Requires: Jinja2
• Template file: CBD2C_template.py
• Useful documentation:
  • The CBD Simulator's documentation
  • CBDs: http://msdl.uantwerpen.be/people/claudio/pub/Gomes2016a.pdf
  • C programming: https://www.w3schools.com/c/index.php
  • Dependency graphs and topological sorting: Lecture slides