Field Programmable Reconfigurable Mesh (FPRM)

Abstract

Many application areas demand increasing amounts of processing capabilities. FPGAs have been widely used for improving this performance. FPRM (Field Programmable Reconfigurable Mesh) is a technique we propose to improve FPGA performance. A Reconfigurable Mesh (RM) consists of a grid of Processing Elements that use dynamic reconfigurations to create varying bus segments between them. The RM can thus perform computations such as Sorting or Counting in a constant number of steps. It has long been speculated that the RM’s dynamic reconfigurations should replace the FPGA’s static reconfigurations. We show that the RM is capable of not only speeding up specific computations such as sorting or summing, but also of speeding up the evaluation of Boolean circuits (BCs), which is the main purpose of the FPGA. Our proposed RM algorithm can evaluate BCs without causing size blowup. Furthermore, tri-state switching elements can be used instead of PEs in a grid.

1. Introduction

FPGAs are integrated circuits that form a matrix of conigurable logic units (CLUs)² connected via programmable routing interconnects. By downloading different routing configurations to the FPGA, any circuit $C\left(x_0,\dots ,x_{n-1}\right)$ can be embedded and then executed/evaluated. After embedding the circuit’s topology in the FPGA, the circuit is executed every time a new input is received. Due to the FPGA’s routing interconnects and CLUs, this evaluation mode makes the FPGA relatively slow compared to ASICs.

Assuming the circuit $C\left(x_0,\dots ,x_{n-1}\right)$ that has been discussed previously, we wish to examine the possibility of speeding up the evaluation of $C$ by using a dynamic mode of reconfiguration rather than the above-mentioned FPGA mode. Essentially, we devised an algorithm that evaluates $C\left(x_0,\dots ,x_{n-1}\right)$ faster than its depth [1] (the longest path from the root/output to any leaf/input)³. In a sequence of reconfiguration steps this algorithm: 1) Spans bus segments on different subsets of $\left\{x_0,\dots ,x_{n-1}\right\}$ in parallel; 2) Uses a single broadcast in each of these bus segments, and computes in parallel the AND/OR/COUNTING-1 s(counting the $\#$ of ‘1’s) of each segment; 3) Computes $C$ in a fixed small number of steps regardless of $C$‘s depth based on the above computations. The above algorithm uses a platform based on Reconfigurable Mesh (RM) [2], which is a 2D grid of Processing Elements (PEs) that uses dynamic bus reconfiguration to create varying bus segments for fast communication. Consequently, computations such as summation and sorting can be expedited.

Reconfigurable Mesh (RM) has been demonstrated to be able to perform parallel computations faster than the Parallel random access machine model (PRAM) [3], which is an abstract model for parallel computation. This includes $O\left(1\right)$ summing [4], $O\left(log\right)$ integer summing [5], $O\left(1\right)$ multiplication [6], sorting [7], convex hall [8], graph algorithms [9, 10] and image processing [11]. Despite this potential power of the RM model, it has not yet been fully realized since the model assumes a signal can be transmitted along a bus/connected component in a single step regardless of the number of switches/ports. From this perspective, a variety of restricted RMs have been proposed. These include the RMBM [12], where only the structure of the RM’s switch has been simplified but still busses with a linear number of switches are used. The SRGA [13, 14] proposed a mesh, where each row/column has a complete binary tree of reconfigurable switches, allowing to route messages between the leaves of this tree. [15] proposes a linear RM (LR-Mesh) bending cost, where the delay of a bus varies as a function of how many times it bends between rows and columns. It showed that for busses with a reasonable delay of at most $D=N^{\epsilon }$ bends they can simulate algorithms for LR-Meshes in constant time. A bus of length $d\left(n\right)=n^{1/k}$ was suggested in [16], also showing that restricted RM algorithms can be directly coded in Verilog. This way of programming RM-algorithms overcomes most of the drawbacks of the C-like programming style proposed so far for RM-algorithms (e.g.,ARMlang [17]). However, they only addressed the problem of COUNTING-1 s. Our method of evaluating the circuit is partially based on the solution for COUNTING-1 s. [18] shows that integrating branching program with Boolean circuits is better than using each of them separately. Other realizations of the RM [19] were mainly to a small-size grid of Soft-CPUs and cannot be synthesized for large values of $n$.

A number of dynamic reconfiguration (DR) FPGAs have also been proposed, mainly for the purpose of speed acceleration. However, the main challenge was the reconfiguration delay. The use of DR is therefore rare [20]. There is also a method of addressing this problem, and it is commonly referred to as partial reconfiguration (PR) at runtime. PR can be implemented through external FPGA interfaces as well as special internal interfaces such as the ICAP on Xilinx devices [21]. Even so, PR is still primarily an auxiliary feature in modern commercial FPGAs rather than something with which the architecture is designed [22, 23]. Thus, PR design involves many details related to low-level architecture that require a high level of expertise. [24] proposed time-multiplexed DRFPGA, where registers are added to store computational states and partial results. Yet, only a few contexts are allowed because of area overhead. Memristors (RRAM), have also been applied as a programmable switch, as they are naturally more delay-efficient and lead to higher-performance FPGA architectures. However, [25, 26] only focus on the architectural repercussions of this technology. Very limited works investigate realistic RRAM-based circuit design constraints, while these have a strong impact on the final architectural performances. Fine-grain DR (FDR), described in [27], consists of homogeneous reconfigurable logic elements (LEs). It is possible to configure each LE as either a lookup table (LUT) or as an interconnect, or even as a combination of both. While this improves flexibility for allocating hardware resources between LUTs and interconnects, it still consumes a large amount of space. At first glance, this model seems to be close to what we have proposed, but one of the main difference lies in the algorithm for evaluating the Boolean Circuit $C\left(x_0,\dots ,x_{n-1}\right)$ faster than its depth.

Our approach to the speed-up evaluation problem is to use the Reconfigurable Mesh (RM). We propose an infrastructure called FPRM (Field Programmable Reconfigurable Mesh) which is a sub-model of the RM model based on current CMOS technology and adapted to the proposed algorithm. The FPRM consists of two-dimensional grids of switches ${\mathit{pe}}_{i,j}$, with each switch connected to four neighbors ${\mathit{pe}}_{i-1,j},{\mathit{pe}}_{i+1,j},{\mathit{pe}}_{i,j-1},{\mathit{pe}}_{i,j+1}$ via four links. It allows reconfiguration of its internal links in different reconfiguration modes $S_0,S_1,S_2,\dots$ as depicted in Figure 1 (upper left). Each ${\mathit{pe}}_{i,j}$ has four registers used to read/write to each of the four links: $\mathit{Nr}$ to read/write to the link connecting ${\mathit{pe}}_{i,j}$ to ${\mathit{pe}}_{i-1,j}$ and $\mathit{Sr}/\mathit{Wr}/\mathit{Er}$ to read/write to ${\mathit{pe}}_{i+1,j}/{\mathit{pe}}_{i,j-1}/{\mathit{pe}}_{i,j+1}$ respectively. Each ${\mathit{pe}}_{i,j}$ executes a program based on its current state, its coordinates $i,j$ and the values of $\mathit{Nr},\mathit{Sr},\mathit{Wr},\mathit{Er}$. Upon execution, each ${\mathit{pe}}_{i,j}$ can change its reconfiguration mode, its state, and the content of its registers $\mathit{Nr},\mathit{Sr},\mathit{Wr},\mathit{Er}$. Figure 1 contains a four instructions program (bottom left side) for executing COUNTING-1 s of a four bits input. As depicted in Figure 1 right side, the execution of this program creates a bus whose bendings corresponds to the ${}^{\text{'}}{1}^{\prime }$s input values. By examining the exit point (row number) of a signal sent through $S>$ we obtain the number of $1-\mathit{\text{bits}}$ in the input.

Figure 1.

The FPRM switches and a program to compute COUNTING-1 s using a $4\times 4$ FPRM.

The second step of the FPRM computation is shown in Figure 2 computing the DNF (Disjunctive Normal Form): $\left(\left(x_0\wedge x_1\wedge x_2\right)\vee \left({\overline{x}}_0\wedge {\overline{x}}_3\right)\vee \left({\overline{x}}_1\wedge {\overline{x}}_3\right)\vee \left(x_2\wedge {\overline{x}}_3\right)\right)$ where each and-term (minterm) is computed in a different row. As with COUNTING-1 s, we broadcast the input values along the columns in the first step. If ${\mathit{pe}}_{i,j}$ is associated with $\wedge x_i\wedge \dots$ in an and-term (minterm) and the input $x_i==1$ then ${\mathit{pe}}_{i,j}$ switches to a connect mode selecting $S_2$, alternatively on ($x_i==0$) it switches to a disconnect mode selecting $S_4$. The opposite is performed if ${\mathit{pe}}_{i,j}$ is associated with $\wedge {\overline{x}}_i\wedge \dots$. A $\mathit{\text{true}}$ signal is sent from $S>$ for every row, while each disconnected ${\mathit{pe}}_{i,j}$ broadcasts a $\mathit{\text{false}}$ signal from its $\mathit{Er}$. The or-term of these and-terms is computed in another broadcast along the last column. Obviously, the FPRM can be used to execute the $O\left(1\right)$ RM algorithms such as summing of $n$ numbers, multiplication [6, 28], sorting, convex hull [2], graph algorithms [9] and image processing [11]). However, here we consider the problem of parallel evaluation of circuits with large depths for which no previous RM algorithm exists. Preliminary results demonstrate the FPRM feasibility and that it is likely to outperform FPGAs.

Figure 2.

Computing a DNF formula using a $4\times 4$ FPRM.

According to the proposed algorithm, boolean circuits $C\left(x_0,\dots ,x_{n-1}\right)$ can be evaluated in a constant number of FPRM steps regardless of $C$‘s depth. During compilation, we calculate the minimized DNF formula ${\mathit{dnf}}_y$ for every possible result of COUNTING-1 s, which is $y={\sum }_0^{n-1}{x}_i$. An FPRM program is generated for each of the DNFs (${\mathit{dnf}}_y$) using the algorithm described in Figure 2. Each of these DNFs (${\mathit{dnf}}_y$) is compiled into an FPRM program working in a similar manner to the algorithm described in Figure 2. At run-time, after performing COUNTING-1 s of the input, the FPRM selects the DNF-program ${\mathit{dnf}}_y$ for $y$ and executes it. Thus, in a constant number of steps this algorithm computes $C\left(x_0,\dots ,x_{n-1}\right)$, using dymamic reconfiguration (DR). By first applying COUNTING-1 s, we get that the size of the FPRM grid needed to execute each of the ${\mathit{dnf}}_{y=0,\dots ,n-1}$ is less or equal to the size of the original $C\left(x_0,\dots ,x_{n-1}\right)$. This is expected since each ${\mathit{dnf}}_y$ in $C\left(x_0,\dots ,x_{n-1}\right)$ is restricted to the case where $y={\sum }_0^{n-1}{x}_i$. Further, the and-terms of ${\mathit{dnf}}_y$ are packed in a 2D-FPRM layout with multiple and-terms computed in a single row (unlike Figure 2, where each and-term is computed separately).

The rest of the chapter is organized as follows. The following section describes the use of COUNTING-1 s operation in order to reduce the formula size. The next step describes the problem of fitting as many and-terms as possible into an FPRM grid, which is one of the most challenging aspects of the technique. The results of the experiments will be presented next, followed by a summary of the conclusions.

2. Using the counting-1 s operation to reduce formula size

For every possible outcome of $y={{\sum }_0}^{\ast }n-1x_i$, the proposed algorithm starts by obtaining the minimized DNF formula, ${\mathit{dnf}}_y$. The input is divided into $k$ segments containing $\mathit{\text{fracnk}}$ bits, and the number of 1-bits is counted for each segment. For each of the ${\left(\frac{n}{k}+1\right)}^k$ possible COUNTING-1 s results $y_1,\dots ,y_k\left(y_i=0\dots \frac{n}{k}\right)$, we compute a minimized DNF ${\mathit{dnf}}_{y_1,\dots ,y_k}$ by:

1. Building a truth table $T_{y_1,\dots ,y_k}$ of $C\left(x_0,\dots ,x_{n-1}\right)$ for all the binary numbers $x_0,\dots ,x_{n-1}$ with $y_i$${}^{\text{'}}{1}^{\prime }$s in the $i$ segment.

2. Our initial DNF is formed by the nonzero entries of $T_{y_1,\dots ,y_k}$, which we simplify using the Logic Friday Espresso package [29].

3. Using reduced DNF, ${\mathit{dnf}}_y$, monochromatic rectangles $M\times V$ are created by searching for all minterms in $M$, and variables in $V$ in such a way that any minterm in $M$ contains all variables in $V$. We obtain a smaller version of ${\mathit{dnf}}_y$ by replacing each variable in $M$ by a new variable (which is the AND of all variables in $M$). A separate step needs to be performed in order to compute the value of the new variables corresponding to monochromatic rectangles.

Consider the truth table $T$ of the address-function of $n=6$ boolean variables given in Figure 3.

$$F\left(a,b,c,d,e,f\right)=\left\{\begin{array}{ll}c& <a,b>=0,0\\ d& <a,b>=0,1\\ e& <a,b>=1,0\\ f& <a,b>=1,1\end{array}\right.$$

Figure 3.

Truth table of the address function arranged by COUNTING-1 s results.

$T$ is arranged by COUNTING-1 s in $<a,b,c>$ ($y_1\left(a,b,c\right)\in \left\{\mathrm{0,1,2,3}\right\}$), and COUNTING-1 s in $<d,e,f>$ ($y_2\left(d,e,f\right)\in \left\{\mathrm{0,1,2,3}\right\}$). Since the address function has a very small formula to begin with

$$F\left(a,b,c,d,e,f\right)=c{a}^{\prime }{b}^{\prime }+d{a}^{\prime }b+\mathit{ea}{b}^{\prime }+\mathit{fab}$$

(where $x^{\prime }\mathit{\text{is}}\neg x$), it is not expected that using COUNTING-1 s can significantly reduce the size of the remaining circuits $C^{y_1\left(a,b,c\right)=i,y_2\left(d,e,f\right)=j}\left(a,b,c,d,e,f\right)$. Indeed, the results in Figure 3 shows that the minimal boolean formula for $C^{y_1\left(a,b,c\right)=2,y_2\left(d,e,f\right)=1}\left(a,b,c,d,e,f\right)$ is $a^{\prime }\mathit{bcd}{e}^{\prime }{f}^{\prime }+a{b}^{\prime }c{d}^{\prime }e{f}^{\prime }+\mathit{ab}{c}^{\prime }{d}^{\prime }{e}^{\prime }f$ which is even larger than the original formula for the whole function $c{a}^{\prime }{b}^{\prime }+d{a}^{\prime }b+\mathit{ea}{b}^{\prime }+\mathit{fab}$. However, this happens only for four out of the sixteen possible cases of $y_1\left(a,b,c\right)=i,y_2\left(d,e,f\right)=j$. In all the remaining 12 cases the boolean formula has one or no variables.

Yet, COUNTING-1 s is very helpful for the multiplication function

$$F\left(a,b,c,d,e,f\right)=1\mathit{iff}\left(a\cdot 2+b\right)\cdot \left(c\cdot 2+d\right))\mathit{mod}4=\left(e\cdot 2+f\right)$$

The results depicted in Figure 4 shows that in all sixteen cases, the minimal boolean formula for $C^{y_1\left(a,b,c\right)=i,y_2\left(d,e,f\right)=j}\left(a,b,c,d,e,f\right)$ is very small.

Figure 4.

Truth table of the mult function arranged by COUNTING-1 s results.

Figure 5 depicts the largest ${\mathit{dnf}}_y$ for $C=\mathit{\text{STCON}}\left(x_0,\dots ,x_{48}\right)$ of a seven nodes directed graph where the input is $7\times 7$ adjacency matrix of the graph. In this case we selected $k=\sqrt{49}=7$, hence $y=<y_1,\dots ,y_7>y_i=0\dots 7$. Out of all the COUNTING-1 s cases for $\mathit{\text{STCON}}\left(x_0,\dots ,x_{48}\right)$, Figure 5 depicts the worst/largest ${\mathit{dnf}}_y$ obtained. The ${\mathit{dnf}}_y$ of Figure 5 should be read as follows:

• $\mathit{\text{stcon}}en$ means STCON for graph of size $n$, while $e$ is the number of entries in the adjacency matrix of the graph.

• $.ie$ is the number of variables denoted by $e$ (a variable for every entry in the adjacency matrix).

• $.pm$ where $m$ denotes the number of rows where the function is evaluated to TRUE.

• The rows are composed of $e$ variables $a_0,\dots a_{e-1}$, where $-/1/0$ denotes $\mathit{do}{n}^{\prime }t-\mathit{\text{care}}/a_i/a_{i^{\prime }}$.

Figure 5.

Resulting formula for worst COUNTING-1 s case of $7\times 7$ STCON.

As shown in Figure 5, the ${\mathit{dnf}}_y$ contains only 16 minterms (and-terms), each containing 10 variables (or negation of variables) omitting some $\mathit{all}\mathit{do}{n}^{\prime }t-\mathit{\text{care}}$ columns at the end of each row. To compare, we obtained the full circuit for $\mathit{\text{STCON}}\left(x_0,\dots ,x_{48}\right)$ using VIVADO-HLS on the following C-code:

$$\begin{array}{c}\#\mathit{\text{define}}\mathit{SQM}7\\ \mathit{\text{for}}\left(k=0;k<\mathit{SQM};k++\right)\{\\ \#\mathit{\text{pragma}}\mathit{HLS}\mathit{\text{unroll factor}}=7\\ \mathit{\text{for}}\left(i=0;i<\mathit{SQM};i++\right)\{\\ \#\mathit{\text{pragm}}\mathit{HLS}\mathit{\text{unroll factor}}=7\\ \mathit{\text{for}}\left(j=0;j<\mathit{SQM};j++\right)\{\\ \#\mathit{\text{pragma}}\mathit{HLS}\mathit{\text{unroll factor}}=7\\ \mathit{\text{if}}(\mathit{mat}\left[i\right]\left[j\right]\parallel \parallel (\mathit{mat}\left[i\right]\left[k\right]\&\&\\ \mathit{mat}\left[k\right]\left[j\right]\left)\right)\mathit{mat}\left[i\right]\left[j\right]=1;\}\\ \}\\ \}\\ \mathit{\text{return}}\left(\mathit{mat}\left[1\right]\left[\mathit{SQM}-1\right]\right);\\ \end{array}$$

The synthesys results of the Verilog code obtained for the above code are: $\mathit{\text{clock}}-\mathit{\text{latency}}=6\mathit{ns}$, $\#\mathit{\text{registers}}=591$, $\#\mathit{\text{LUTs}}=742$ and $\#\mathit{\text{MUXes}}=782$. This is significantly larger than ${\mathit{dnf}}_y$ of Figure 5 which is a DNF with $143$ gates and clock latency of less than $1\mathit{ns}$. The experiments show that using a fast pre-computation function of the inputs (COUNTING-1 s) can significantly reduce the size of ${max}_y\mid {\mathit{dnf}}_y\mid$ compare to the size of the complete circuit.

The above ${\mathit{dnf}}_y$ could have been further simplified by replacing monochromatic rectangles with new variables. As illustrated in the Figure 6, it is possible to simplify the largest ${\mathit{dnf}}_y$ of a five node graph by replacing eight monochromatic rectangles (left-side) with new variables. The result is a reduction from $\left(94/14\right)/\mathit{\text{simeq}}6$ to $\left(49/14\right)/\mathit{\text{simeq}}3$ in the average number of variables per minterm. As each rectangle is evaluated at runtime, its subset of variables is logically ANDed. This can be achieved with a sub-bus of the FPRM that allows a zero-$x_i$ to broadcast, on the value of $0$.

Figure 6.

Reducing the DNF size of a ${\mathit{dnf}}_y$ by pre-computing monochromatic rectangles.

3. Computing the FPRM layout of ${\mathrm{dnf}}_y$

Using the algorithm of Figure 2, we can evaluate the ${\mathit{dnf}}_y$s on the FPRM in three steps. Broadcasts representing the minterms of ${\mathit{dnf}}_y$ are used to evaluate the DNF. As a result, we can evaluate the DNF using the $n\times k$ grid of sub-FPRM, where $n$ is the number of rows (minterms), and $k$ is the number of variables ($14\times 17$ for the DNF shown in Figure 6 right). There are two steps involved: broadcasting the values of each $x_i$ over the columns in the sub-FPRM; and configuring each row as a single bus and computing the logical AND on each row. We can, however, pack several minterms/bus segments in one row, reducing the size of the FPRM sub-grid needed for the computation. Our 2D layout of a ${\mathit{dnf}}_y$ can be optimized by swapping minterms in each level and arranging the literals in each minterm (node).

Figure 7.

Optimized FPRM layout.

Figure 7 illustrates the optimized (by hand) layout of the DNF of Figure 5 (called $\mathit{LG}$), wherein the minterms are arranged in six levels, each containing 1–4 minterms. Straight busses are used to broadcast the values of the literals in this layout. According to Figure 7, this layout also includes the extra duplications of ${}^{\text{'}}{b}^{\prime }$ and ${}^{\text{'}}{n}^{\prime }$ required. There is a significant improvement in the total area and max-switching length when compared to the simple method of arranging all minterms in one column. The optimized (by-hand) layout of Figure 7 is also better compared to that of Figure 5 when used as an $\mathit{LG}$. In the following sections, we describe the details of the proposed algorithm to find a minimized $\mathit{LG}$.

3.1 First stage: find the level arrangement of minterms in the final FPRM layout

1. We build an intersection graph $G^0$ where each node corresponds to one minterm and each edge corresponds to an intersection between two such minterms. Figure 8 (left) illustrates this graph for the DNF of Figure 6. The edges are labeled by the intersection size.

2. Next, we compute a maximal independent set (MIS) in $G^0$ that also maximizes the highest label edge in each of its nodes (as depicted in Figure 8). This MIS will be used as the first level in the FPRM layout we seek to build. Note that all the minterms in this MIS have no intersection in their variables, thus can be safely mapped to the same level of the layout.

3. We remove the MIS from $G^0$ creating $G^1$ and as depicted in Figure 9. compute the next MIS in $G^1$ creating the next level in the FPRM layout. This process of extracting MIS, forming the next level of minterms in the layout is repeated until there are no more MISs. Figure 10 depicts the last step of this process.

Figure 8.

The intersection graph $G^0$ and extracting first MIS.

Figure 9.

$G^2$ and extracting the next level in the layout.

Figure 10.

$G^5$ and extracting the last level in the layout.

3.2 Second stage: rearranging the minterms in each level

The position/index of each node/minterm in the final layout is computed as follows:

• Create a leveled graph $\mathit{LG}$ whose nodes $V_{\mathit{\text{level}},\mathit{\text{index}}}$ correspond to the minterms in each column of the layout previously obtained.

Figure 11 depicts the resulting $\mathit{LG}$.

• Rearrange the minterms in each level of $\mathit{LG}$ by: Finding a set of nodes (called “mid-cut”), one from each level of $\mathit{LG}$, and a partition of the remaining nodes in each level into a “left-part” and a “right-part” such that:

  • The number of edges between the left-part and the right-part is minimal.

  • The number of nodes in the left-part in each level is about the same as the number of nodes in the right-part of that level.

Figure 11.

The leveled graph (LG) of the MIS arrangment.

Figure 12 depicts finding a mid-cut and the resulting partition to a left-part and right-part. As can be seen, only one edge (the ${}^{\text{'}}{b}^{\prime }$) crosses from the left-part to the right-part in Figure 12. In the final FPRM layout, the mid-cut minterms will be stacked one on top of the other. Recursively, the process is applied to the left-part and the right-part until all nodes of $\mathit{LG}$ are arranged in 2D.

Figure 12.

Rearanging the minterms in $\mathit{LG}$‘s levels via mid-cuts.

3.3 Third stage: rearranging the order of literals in each minterm

1. For the current order of literals in each minterm, we expand the edges of the current $\mathit{LG}$ to show the duplication of each literal from one level to another. We also add source-edges (arrows in Figure 13) depicting that the source of each literal comes from the lowest level below the present 2D layout of the $\mathit{LG}$. Figure 13 illustrates the resulting graph called the literals graph $\mathit{TG}$.

2. Crossing edges between minterms that are in the same index at their level are eliminated by rearranging the literals inside one minterm.

3. Next we eliminate crossing edges by:

   • Replacing one pair of crossing edges with a down-going source-edge.

   • Reordering literals in the two minterms of the crossing edge. Crossing edges between minterms with the same level-index are resolved by rearranging the literals in those minterms.

Figure 13.

Expanding current level graph $\mathit{LG}$ to a literal graph $\mathit{TG}$.

The next edge selected to be replaced by a source edge is the one with the maximal number of crossings. For example, in Figure 13 the first edge to be replaced by a source edge is the edge connecting the left ${}^{\text{'}}{b}^{\prime }$ in the first level to the right ${}^{\text{'}}{b}^{\prime }$ in the fourth level, as this edge cut acrosses seven edges. The process is repeated until there are no crossing edges, as shown in Figure 14. Since source edges will be aligned vertically later, crossing with source edges is not counted.

Figure 14.

Final arrangement of literals in each minterm.

3.4 Fourth stage: completing the alignment

At this stage, the minterms in each level and the literals in each minterm have been arranged so that no crossing edges exist. Aligning the literals such that all the edges form straight vertical columns leads to the final FPRM layout:

1. We start by placing the bottom leftmost literal/source-edge at the bottom leftmost corner of the FPRM layout. We align all the edges connected to the left corner at a vertical “duplication” column (for duplicating literals, if needed).

2. Let $v_i$ be the nearest node to the last aligned duplication column. We align $v_i$ and the literal/source edges connected to it, into an adjacent vertical duplication column.

3. This is repeated until all edges are aligned into adjacent duplication columns.

Figure 15 illustrates the resulting layout with a total area of about $143$, which includes the area for broadcasting the duplicated literals ($c,h,b,k,n,l$).

Figure 15.

Completing the alignment.

Since the FPRMs constructed with literals as control entries into the tristate switches.

4. Realization and results

Tri-state switch is the natural candidate for the infrastructure logic realization of the final FPRM layout, as other switching devices such as NMOS are not supported by ASIC synthesis tools. For control input of ‘1’, the output of the tri-state is exactly identical to its input, but for control input of ‘0’ the output is high impedance (disconnected or ‘z’). As a result, multiple tri-states can share the same output wires. The DNF is simply a ${\vee }_{i=1}^n{m}_i$, where $m_i$ represent a minterm $m_i={\wedge }_{j=1}^{\mid m_i\mid }{a}_j$, and $a_j$ is a literal. For each literal, a minterm can be represented conceptually by a list of connected tri-states. The leftmost tri-state outputs ‘1’ or ‘z’ based on input of ‘1’ and control from the literal. The next tri-state, produces the input according to the next literal value in $m_i$, thus performs the operation of ${\wedge }_{j=1}^{\mid m_i\mid }{a}_j$. Since the output of each minterm $m_i$ is ‘1’ or ‘z’, their output wires can be connected directly, performing ${\vee }_{i=1}^n{m}_i$. Figure 16 illustrates the FPRM for the DNF of two minterms $M=\left(a1\wedge a2\right)\vee \left(a2\wedge a3\right)$, where the literal values are represented by thick vertical lines (dark-gray for ‘1’ and light-gray for ‘0’). Each (potential) literal $a_j$ in a minterm $m_i$ residing in row $r$ consists of $6$ tri-states and one encoder (depicted in the dashed line rectangle). The ${\mathit{cn}}_{r,j}$ tri-state is connecting the literal value to minterm $m_i$, providing that $a_j$ appears in $m_i$. Otherwise, ${\mathit{cn}}_{r,j}$ will pass the incoming signal to the next literal. The output of ${\mathit{cn}}_{r,j}$ is the control of ${\mathit{tl}}_{r,j}$, transferring the input from $a_{j-1}$ or disconnecting (producing ‘z’) given the value of $a_j$. According to the encoder’s $e_{r,j}$ input, ${\mathit{tr}}_{r,j}$ will pass/hold the current signal to $a_{j+1}$, or ${\mathit{ci}}_{r,j}$ will start a new minterm calculation, sending ‘1’ to the next literal on the right. Finally, the role of ${\mathit{co}}_{r,j}$ is to send down the output of the current minterm, providing that it is the rightmost literal in the current minterm. Note that the outputs of the minterms are connected together since these are outputs of tri-states (‘1’ or ‘z’). The output of the DNF is indicated by $M$ on the right-bottom side.

Figure 16.

Tri-state configuration of the FPRM.

Based on the description in [30], the FPRM implementation is compared to an Island FPGA routing architecture. Figure 17 shows a variant that contains: A logic unit with and/or-gate that is connected to a grid of $4-\mathit{\text{bits}}N\mathit{\text{vertical buses}}\times 4-\mathit{\text{bits}}N\mathit{\text{horizontal buses}}$ via two connection units. Any vertical-bus can be connected to any horizontal-bus using a crossbar-like routing unit. Additionally, vertical/horizontal busses can be disconnected, so that bends will not consume the entire bus.

Figure 17.

The FPGA routing architecture used for the experiments.

All connections/disconnections and fuse operations are made by a back-to-back pair of tri-state devices, allowing bi-directional signals. ASIC synthesis results obtained with Synopsys Design compiler using a 160 nm cell library. As shown in Table 1, the FPRM architecture is 4X faster and more efficient in both power and area⁴ than the FPGA routing infrastructure. Based on the FPRM of Figure 16 and the assumption that the counting stage requires two cycles. When the expected latency of the FPGA is added, we get about twice as fast performance from the FPRM.

Size	Area		Power		Clock latency
	FPRM	FPGA	FPRM	FPGA	FPRM	FPGA
$16\times 16$	6156 uC	38,256 uC	66 uW	161 uW	6.98 ns	14.36 ns
$12\times 12$	3463 uC	21,528 uC	52 uW	149 uW	4.75 ns	11.27 ns
$8\times 8$	1221 uC	9579 uC	34 uW	148 uW	2.85 ns	8.18 ns
$4\times 4$	333 uC	2411 uC	12 uW	80 uW	1.36 ns	5.09 ns

Table 1.

Synthesis results comparing the FPRM vs. the FPGA routing infrastructure.

A chain of switches (tri-states) selects whether values should be passed on or not in the circuit we designed. This idea will obviously work faster than a chain of $\mathit{\text{and}}$ and $\mathit{\text{or}}$ gates as implemented in FPGA. The fact that there are no switches along the wire that ends with M further accelerates the speed of receiving the output. This is triggered when a value of 1 comes out from one of the minterms. Given that the tri-state consumes power as an ordinary buffer, and the $\mathit{\text{and}}/\mathit{\text{or}}$ operations (${\vee }_{i=1}^n\mathit{\text{mintermi}}$) are implemented simply by merging the tri-states outputs, the power consumption is likely to be a function of the number of tri-state buffers. On the other hand, the FPGA needs to be powered for the $\mathit{\text{and}}/\mathit{\text{or}}$ gates as well as the switching systems to connect the logical blocks. Compared to a real FPGA, we have simplified our implementation, but this can only reduce power. Conversely, the FPRM is general, assuming that any Boolean Circuit can be represented as a DNF.

5. Conclusions

As part of the contribution of this work, we developed the algorithm to evaluate boolean circuits on the RM; a method to compute an optimized FPRM layout; and a method for realizing the FPRM as a tri-state circuit with comparable performance to the conventional FPGA implementation. A tri-state (MOSFET transistor) acts as a switching element in both the FPGA and FPRM. Passing a signal through a chain of $k$ switches (that is, a chain of $k$ source-drain connected transistors) incurs a quadratic delay of $\frac{k^2}{2}r\cdot c$ (where $r$ is the resistance and $c$ is the capacitance of each transistor). As a result of the reconfiguration of the FPRM, a relatively long chain of transistors can be created. Due to the short chains involved in the circuit evaluation problem discussed here, the FPRM will be able to execute the circuit evaluation process fairly quickly. In order to compare the FPRM with the FPGA/ASIC realization of $f\left(x_1,\dots ,x_n\right)$, a SPICE simulation of the FPRM can be carried out. This includes selecting the most appropriate MOSFET transistor technology to minimize signal propagation delays through the FPRM bus.

This research can be furthered by comparing the synthesized results with those obtained from HLS (High Level Synthesis) of the $f\left(x_0,\dots ,x_{n-1}\right)$ C-code. Analyzing other functions that can be efficiently computed using the FPRM in $O\left(1\right)$. Finally, study how the partitioning into segments affects the size of the resulting formulas, and build a decision tree that computes $f\left(x_0,\dots ,x_{n-1}\right)$ on the FPRM in an even smaller size.

A. List of acronyms and abbreviations

• ASIC: Application Specific Integrated Circuit

• BC: Boolean Circuit

• CLU: Configurable Logic Unit

• CMOS: Complementary Metal-Oxide Semiconductor

• DNF: Disjunction Normal Form

• DR: Dynamic Reconfiguration

• DRFPGA: Dynamic Reconfiguration FPGA

• FDR: Fine-Grain Dynamically Reconfigurable Architecture

• FPRM: Field Progammable Reconfigurable Mesh

• HLS: High Level Synthesis

• LE: Logic Elements

• LR-Mesh: Linear Reconfigurable Mesh

• LUT: Lookup Table

• MIS: Maximal Independence Set

• MOSFET: Metal-Oxide Semiconductor Field-Effect Transistor

• NMOS: N-type Metal-Oxide Semiconductor

• PE: Processing Elements

• PR: Partial Reconfiguration

• PRAM: Parallel Random Access Machine

• RM: Reconfigurable Mesh

• RMBM: Reconfigurable Multiple Bus Machine

• RRAM: Resistive Random Access Memory

• SRGA: Self Reconfigurable Gate Array

• STCON: st-connectivity