Interconnect synthesis in reconfigurable computing

Figure 11: Example of a Reconfigurable Computer
Figure 12: A Programmable Interconnection Network
Figure 13: A typical routing block

Many reconfigurable computers consist of multiple field-programmable processors (FPGAs) connected through a Programmable Interconnect Network (PIN) as shown in Figure 11. Interconnect synthesis is the process of configuring the PIN to match the communication requirements of the designs implemented on the processors. The general architecture of a PIN is depicted in Figure 12. A PIN routes signals between various input and output pins of the FPGAs: the specific routing is determined by the control signals on each of the routing blocks. One of many available routing blocks is shown in Figure 13, this one on the well-known Wildforce board.

Typically, but not necessarily, the control signals define a permutation of the inputs of the block and the permuted signals are routed to the corresponding output pins of the block. Each control signal can take a value from $\{T,F\}$ or be unassigned. An assignment of values to control signals is said to be a program of the interconnection network. Thus, a program defines a routing of the signals through the interconnection network. A required routing may be realizable through one or more programs or not realizable at all depending upon the routing capabilities of the interconnection blocks and how they are connected. A configuration of an interconnection network refers to a set of routes realized by a program. Whereas a program defines a configuration, it is not necessary that each configuration is realizable by a unique program.

The problem of interconnect synthesis can be formulated as a problem of determining the satisfiability of a class of QBFs. For a PIN, let $PI$ be the set of primary inputs (those connecting to FPGA outputs), $PO$ be the set of primary outputs (those connecting to FPGA inputs), and $IO$ be the set of intermediate outputs (those not directly accessible through pins). Let $M$ be a desired routing from $PI$ to $PO$ and $Constraints_{M,IO}(PI,PO)$ be a set of contraints which evaluates to T if and only if values on $PO$ match values on a given $PI$ according to $M$ without any inconsistencies among $IO$. The QBFs have the following form:

$$\forall ~PI~ \exists ~PO~\&~IO~ s.t.~Constraints_{M,IO}(PI,PO)$$

For this class, there is an efficient method for eliminating the Quantifiers resulting in a system of quantifier-free formulas that can be determined using ordinary satisfiability solvers. The key idea, called impulse response, is to establish constraints that force exactly one route from a single input to its destination at a time, and to repeat this process for all inputs.

Given an $n$ dimensional Boolean vector $V=\{x_1, x_2, \cdots x_n\}$, define impulse($i$) to be an assignment of F to variable $x_i$ and T to all the other variables in $V$. Clearly, there are $n$ impulses for an $n$ dimensional vector. For each impulse, it is straightforward to build constraints that force the target primary output to take value F and all other primary outputs to take value T while enforcing consistency among intermediate values (an example follows). Call such a constraint, for impulse($i$), $ImpConstraint_{M,IO}(i)$. Then the QBF above can be replaced with the following Boolean expression:

$$\wedge_{i=1}^n ImpConstraint_{M,IO}(i) \wedge x_i\equiv F \wedge_{j\not=i} x_j\equiv T$$

which, it can be shown, evaluates to T if and only if the QBF above does.

Consider, for example, just the routing block of Figure 13. The primary inputs are $\{x_1, x_2, x_3, x_4, s_1, s_2, s_3\}$, the primary outputs are $\{o_1, o_2, o_3, o_4\}$, and the two intermediate outputs are $\{o_5, o_6\}$. Suppose each subblock $S$ (there are three of them) either routes its two inputs directly to its two outputs (for example, $x_1$ is routed to $o_1$ and $x_2$ is routed to $o_5$ through the upper left subblock if $s_1=F$) or crosses its routes (for example, $x_1$ is routed to $o_5$ and $x_2$ is routed to $o_1$ if $s_1=T$). Then one can write the four equations shown in the Figure that relate primary outputs to primary inputs. Those equations are the basis for the consistency constraints needed.

The precise constraints depend on the routing desired. Suppose we wish to determine whether there is a program (assignment to $\{s_1, s_2, s_3\}$) that realizes the configuration $x_1$ to $o_1$, $x_2$ to $o_3$, $x_3$ to $o_2$, and $x_4$ to $o_4$. For impulse($1$) the consistency constraints are

$o_{11}\equiv ite(s_{1}, x_{12}, x_{11}) \wedge o_{12}\equiv ite(s_{3}, o_{16},... ...quiv ite(s_{3}, o_{15}, o_{16}) \wedge o_{14}\equiv ite(s_{2}, x_{13}, x_{14})$
$\wedge o_{15}\equiv ite(s_{1}, x_{11}, x_{12}) \wedge o_{16}\equiv ite(s_{2}, x_{14}, x_{13})$
$\wedge x_{11}\equiv o_{11}$

These are conjoined with the constraints forcing impulse($1$) which are

$x_{11}\equiv F\wedge x_{12}\equiv T\wedge x_{13}\equiv T\wedge x_{14}\equiv T$

Similar constraints may be constructed for impulse($2$) through impulse($4$). The conjunction of all four sets of constraints is the Boolean expression of interest: if some assignment to $\{s_1, s_2, s_3\}$ satisfies that expression, that assignment routes primary inputs to primary outputs as desired. The next step is to write the constraints in canonical form. This is straightforward and the result is shown in Figure 14.

Figure 14: Interconnect synthesis example in canonical form.