# Automatic Configurable Hardware Code Generation for Software-Defined Radios+
## 3 Analysis of SDF-AP Model  
The key properties of the model are analysed at compile time. This analysis includes checking the boundedness, the ability to avoid the deadlock, finding the schedule and computing the buffer size. A model is bounded if it can be executed infinitely using finite FIFO buffers. Like in the SDF model, the SDF-AP boundedness exists if there is a finite non-zero number of firings for each actor such that executing the model the number of times as specified in the repetition vector (i.e., \(RV\)) takes it back to its original state. The SDF-AP model is deadlock-free if each actor can fire without interruption for the number of times specified in the repetition vector. However, the deadlock-free property for an SDF-AP model is sufficient but not a necessary condition as often times the actor is fired before all the tokens are available in the input FIFO buffer. A bounded schedule which is statically determined at compile time ensures that each actor is eventually executed (ensuring liveness) and that the execution is infinite using finite buffers (ensuring boundedness of FIFOs). To ensure that the SDF-AP graph is free from deadlock and that it has unbounded execution using a bounded buffer, the so-called _Periodic Admissible Schedules_ (PASS) is used. The PASS defines a schedule as the sequence in which the actors must fire. An admissible schedule is the firing order that avoids a deadlock and ensures a bounded storage allocation while a periodic schedule denotes the sequence of firing repeats after every iteration [16]. The following steps outline how the PASS is created using the SDF-AP model in Figure 1 as an example:  
* **Step 1. ** First, we create a topology matrix (\(TM\)) of the SDF-AP graph as using Equation (1). The number of \(TM\) rows equals the graph edges (FIFO channels) while the number \(TM\) columns equal the graph nodes (actors). The entry \((i,j)\) at \(i\)-\(th\) row and \(j\)-\(th\) column of the \(TM\) is positive if the node \(j\) produces tokens into channel \(i\). Furthermore, the entry is negative if node \(j\) consumes tokens from channel \(i\) and the rest of the entries are filled with a value 0 to denote the absence of the edge. \[ \begin{array}{c}\text{x}\quad\text{y}\\ TM=[2\quad-3]\leftarrow\text{edge(x,y)}\end{array} \] (1)
* **Step 2. ** The existence of PASS is checked by determining the rank of \(TM\) which must be one less than the graph order (also known as the number model actors or graph vertices) and the proof of this theorem is provided in [12]. The rank is the number of linearly independent vectors in \(TM\) which in this case is \(1\). Figure 1: An SDF-AP model example (ex1). * **Step 3. ** Since the rank (i.e., =1) of _TM_ is valid in that it is one less than the order of the graph (i.e., 2), the system has an infinite number of solutions for a firing vector _RV_. We determine the simplest solution with the algorithm by [PERSON] et al. [17] and the results are shown in Equation (2). \[RV= \begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}3\\ 2\end{bmatrix} \] (2) To ensure finite buffer allocation and infinite execution, the product of _TM_ and RV must be zero as shown in Equation (3). \[TM\times RV= \begin{bmatrix}2&-3\end{bmatrix} \times \begin{bmatrix}3\\ 2\end{bmatrix} = \begin{bmatrix}0\\ 0\end{bmatrix} \] (3)
* **Step 4. ** Each actor in model is then fired the number of times as specified in _RV_. If all the firings for each is successful, the the system is deemed deadlock-free. The PASS schedule is followed by another schedule of a bounded SDF-AP model execution which is referred to as a _1-periodic schedule_[11].