A Generic Three-Sided Rearrangeable Switching Network for Polygonal FPGA Design

2.1. Three-Sided Polygonal Switching Network

The proposed generic three-stage 3-sided polygonal switching network (PSN) can be used to interconnect terminals in pairs of the three disjoint sets (P_P, P_O, and P_I). This PSN consists of S crossbars (CBs) interconnected by a S-side polygonal switch block (PSB). Figure 3(a) shows an example of PSN, where the first and third stages are composed of 8 CBs; and the second (internal) stage is a PSB with 8 sides.

As shown in Figure 3(b), each crossbar in a PSN, denoted as CB_i(n, m) for i = 1,2, …, S, is an n × m block architecture, where n is the number of external terminals connected to one of the three sets and m is the number of internal terminals connected to one side of PSB, m ∈ even [12]. We classify connection blocks CBs under three groups: CB_I, CB_O, and CB_P, which are used to connect the inputs and outputs of logic-blocks and I/O pins, respectively. Denote that CB_P = {CB₁, CB₂, …, $$, $$, $$, …, $$, $$, $$, …, $$, where s_p, s_o, and s_i are the number of CBs in the CB_P, CB_O, and CB_I, respectively. As shown in Figure 2, the I/O pins are connected to CB_P = {CB₁, CB₂}, and inputs and outputs of logic-blocks are connected to CB_I = {CB₅, CB₆, CB₇, CB₈} and CB_O = {CB₃, CB₄}, respectively. Therefore, a three-sided polygonal switching network should provide N_I = s_i × n, N_O = s_o × n, and N_P = s_p × n external terminals to connect the inputs and outputs of logic-block and I/O pins, respectively.

We label these external and internal terminals on a CB_i(n, m) as P_i = {p_i,1, p_i,2, …, p_i,n} and T_i = {t_i,1, t_i,2, …, t_i,m}, respectively. We represent the external terminals of a CB_i(n, m)P_P = $$ (I/O terminals), P_O = $$ (output terminals), and P_I = $$ (input terminals). Similarly, the internal terminals are denoted as T_P = $$, $$, and T_I = $$. In total, we have two sets of terminals: the external terminal set 𝒫 = P_P ∪ P_O ∪ P_I and the internal terminal set 𝒯 = T_P ∪ T_O ∪ T_I in a PSN. Furthermore, the set of P_P, P_O, and P_I have N_P = s_p × n, N_O = s_o × n, and N_I = s_i × n external terminals, respectively. Similarly, the set of T_P, T_O, and T_I have M_P = s_p × m, M_O = s_o × m, and M_I = s_i × m internal terminals on S CB(n, m) crossbars. For example, Figure 3(a) shows a 3-sided switching network PSN with P_P = P₁ ∪ P₂, P_O = P₃ ∪ P₄, and P_I = P₅ ∪ P₆ ∪ P₇ ∪ P₈, where P_i = {p_i,1,  p_i,2}, i = 1, 2, …, 8; and with T_P = T₁ ∪ T₂, T_O = T₃ ∪ T₄, and T_I = T₅ ∪ T₆ ∪ T₇ ∪ T₈, where T_i = {t_i,1,  t_i,2}, i = 1, 2, …, 8. Any pair of external terminals from two sets of P_P, P_O, and P_I can be connected to each other by using a 3-sided switching network PSN, but no pair external terminals from the same set can be interconnected.

Through the n × m programmable and electrically noninteracting switches in a crossbar CB_i(n, m), every external terminal in P_i can be connected to a free internal terminal in T_i without any blocking. For example, if switch SW(p_i,j, t_i,h) is programmed to be “ON”, then connection (p_i,j, t_i,h) between an external terminal p_i,j and an internal terminal t_i,h is established, where 1 ≤ i ≤ S, 1 ≤ j ≤ n, and 1 ≤ h ≤ m. Figure 3(b) shows a routing example, where p_i,1 is connected to t_i,2 by programming SW(p_i,1, t_i,2), and this routing solution is illustrated by thick lines. In such a way, an external terminal can be connected to an internal terminal by programming one switch in a CB_i(n, m).

The polygonal switch block in a PSN, denoted as a PSB(m, s_p, s_o, s_i), is an S-side switch block with m internal terminals on each side of the block, as shown in Figures 4(a) and 5(a). Label the terminals on the ith side of a PSB(m, s_p, s_o, s_i) as T_i = {t_i,1, t_i,2, …, t_i,m} for 1 ≤ i ≤ S. Remember that internal terminals 𝒯 = T_P ∪ T_O ∪ T_I, where $$, $$, and T_I = $$. If a switch SW(t_i,j, t_k,l) exists in PSB(m, s_p, s_o, s_i) and is programmed to be “ON”, then a connection between terminals t_i,j and t_k,l is established, where t_i,j and t_k,l belong to two different sets of T_P, T_O, and T_I. To form a 3-sided switching network PSN we need S CB(n, m) crossbars connected to a polygonal switch block PSB(m, s_p, s_o, s_i). Thus, a 3-sided switching network can be completely characterized by five parameters: n, m, s_p, s_o, and s_i, and denoted as PSN(n, m, s_p, s_o, s_i), for n ≥ 2, m ∈ even, s_p ≥ 1, s_o ≥ 1, s_i ≥ 1, and S = s_p + s_o + s_i. For example, Figure 3(a) shows a PSN with n = 2, m = 2, s_p = 2, s_o = 2, and s_i = 4.

As shown in Figures 4(a) and 5(a), we will study the 3-sided switching network with two different topologies of polygonal switch blocks in this paper, denoted as PSB_C(m, s_p, s_o, s_i) and PSB_SU(m, s_p, s_o, s_i), respectively. Algorithm 1 constructs a clique-based polygonal switch block PSB_C(m, s_p, s_o, s_i). As shown in Figure 4, a PSB_C(m, s_p, s_o, s_i) is equivalent to m isolated PSB_C(1, s_p, s_o, s_i). In Figure 6 we show a 3-sided switching network, PSN_C(n, m, s_p, s_o, s_i) constructed with a PSB_C(m, s_p, s_o, s_i). Algorithm 2 constructs the polygonal switch block PSB_SU(m, s_p, s_o, s_i). As shown in Figure 5, a PSB_SU(m, s_p, s_o, s_i) is equivalent to m/2 isolated PSB_SU(2, s_p, s_o, s_i), m ∈ even. A 3-sided switching network PSN_SU(n, m, s_p, s_o, s_i) consisting of S CB(n, m) crossbars connected to a PSB_SU(m, s_p, s_o, s_i) is shown in Figure 7. Table 1 lists some symbols of 3-sided switching network specified in this paper.

Note that we do not allow any two external terminals from the same set of P_P, P_O, and P_I to be interconnected in a PSN(n, m, s_p, s_o, s_i). Similarly, we do not allow any two internal terminals from the same set of T_P, T_O, and T_I to be interconnected in a PSB(m, s_p, s_o, s_i). For example, Figures 4(a) and 5(a) show that PSB_C(2,2, 2,4) and PSB_SU(4,2, 2,4) do not have any switches between the two sets of T₁ and T₂ from the same T_P for the interconnection. That is, in either a PSN_C(2,2, 2,2, 4) (Figure 6) or a PSN_SU(2,2, 2,2, 4) (Figure 7) no interconnections of external terminals from the same sets of P₁ and P₂ through PSB_C(2,2, 2,4) or PSB_SU(2,2, 2,4) are allowed. In a PSB_SU(m, s_p, s_o, s_i) or PSB_C(m, s_p, s_o, s_i), since a terminal from a side in one set of T_P, T_O, and T_I should be connected to any other terminal from the sides in the remaining two sets through switches, a polygonal switch block needs at least m(s_ps_o + s_ps_i + s_os_i) switches. Assume that both 3-sided switching networks PSN_SU(n, m, s_p, s_o, s_i) and PSN_C(n, m, s_p, s_o, s_i) have the same size and the same number of switches. We will show that the three-stage 3-sided switching network PSN_SU(n, m, s_p, s_o, s_i) with m ≥ n is rearrangeable and m is even [12], but the PSN_C(n, m, s_p, s_o, s_i) with m = n is not rearrangeable.

In a PSN(n, m, s_p, s_o, s_i), the connection pair (p_i,j, p_k,l) is a point-to-point connection, where p_i,j and p_k,l belong to different sets of P_P, P_O, and P_I. An assignment AS = {(p_i,j, p_k,l)} represents a set of connection pairs to be connected; thus each external terminal appears in at most one pair. A PSN(n, m, s_p, s_o, s_i) switching network is rearrangeable if any assignment AS is realizable (routable).

Note that a connection pair (p_i,j, p_k,l) belonging to AS is to be connected by passing through blocks CB − PSB − CB. Given an AS on a PSB(m, s_p, s_o, s_i), each pair of connection is accomplished using terminals from two different sides of T_P, T_O, and T_I; we can thus classify these connections passing through a PSB(m, s_p, s_o, s_i) into (s_ps_o + s_ps_o + s_os_i) types of connections. Figure 8 shows the twenty possible types of connections in an eight-side switch block PSB(m, 2,2, 4). A routing requirement vector (RRV)$$ [9–11] for a PSB(m, s_p, s_o, s_i) is a (s_ps_o + s_ps_o + s_os_i)-tuple $$, $$, …, $$, …, $$, …, $$, …, $$, …, $$, where r_i,k represents the number of type-(i, k) connections between T_i and T_k required to be connected through a PSB(m, s_p, s_o, s_i); 0 ≤ r_i,k ≤ m for 1 ≤ i < k ≤ S. In other words, r_i,k is the number of connections {(p_i,j, p_k,l)} in AS to be connected through the two sides T_i and T_k on a PSB(m, s_p, s_o, s_i), 1 ≤ j,   l ≤ m, where T_i and T_k belong to any two different sets of T_P, T_O, and T_I. An RRV $$ is said to be realizable (routable) on a PSB(m, s_p, s_o, s_i) if there exist disjoint paths for $$ on a PSB(m, s_p, s_o, s_i). Figure 8 shows an RRV $$ = (r_1,3, r_1,4, r_1,5, r_1,6, r_1,7, r_1,8, r_2,3, r_2,4, r_2,5, r_2,6, r_2,7, r_2,8, r_3,5, r_3,6, r_3,7, r_3,8, r_4,5, r_4,6, r_4,7, r_4,8) for PSB with eight sides.

For example, Figure 9(a) shows a routing instance with three nets corresponding to the RRV $$ = (1_1,3, 0, 0, 0, 1_1,7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1_3,7, 0, 0, 0, 0, 0), and we try to route this RRV using the two different polygonal switch blocks PSB_C(2,2, 2,4) and PSB_SU(2,2, 2,4) from Figures 4(a) and 5(b), respectively. As shown in Figures 9(b) and 9(c), however, there is always one net that cannot be routed on a PSB_C(2,2, 2,4). Thus, this RRV (1_1,3, 0, 0, 0, 1_1,7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1_3,7, 0, 0, 0, 0, 0) is not routable on a PSB_C(2,2, 2,4). Instances of the same RRV $$ routable on a PSB_SU(2,2, 2,4) are shown in Figures 10(a) and 10(b), where the routing solutions are illustrated by thick lines.

Each connection pair (p_i,j, p_k,l) ∈ AS is required to be connected by passing through CB_i − PSB − CB_k in a PSN(n, m, s_p, s_o, s_i). Given an AS = {(p_i,j, p_k,l)}, we want to obtain an RRV $$,  $$ to be realized on a PSB(m, s_p, s_o, s_i), where r_i,k is the number of the connection pairs (p_i,j, p_k,l) required to be connected through PSB(m, s_p, s_o, s_i). For example, let AS = {(p_1,1, p_7,2), (p_1,2, p_3,1), (p_3,2, p_7,1)} to be routed on a PSN_C(2,2, 2,2, 4) and a PSN_SU(2,2, 2,2, 4), which have been respectively shown in Figures 6 and 7. The RRV for the given AS on PSB(2,2, 2,4) is $$ = (1_1,3, 0, 0, 0, 1_1,7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1_3,7, 0, 0, 0, 0, 0). We have already shown in Figures 10(a) or 10(b) that the RRV $$ = (1_1,3, 0, 0, 0, 1_1,7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1_3,7, 0, 0, 0, 0, 0) can be routed on a PSB_SU(2,2, 2,4). Since any external terminal in P_i can be connected to a free internal terminal in T_i without blocking through a crossbar CB_i(n, m), we show in Figures 11(a) and 11(b) two possible routing solutions for the given AS on a PSN_SU(2,2, 2,2, 4) switching network. Instances in Figures 12(a) and 12(b) show that the same AS is not routable on a PSN_C(2,2, 2,2, 4) switching network, because the RRV $$ = (1_1,3, 0, 0, 0, 1_1,7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1_3,7, 0, 0, 0, 0, 0) contains at least one connection that cannot be routed on a PSB_C(2,2, 2,4) as already shown in Figures 9(b) and 9(c). Therefore, we conclude a PSN_C(n, m, s_p, s_o, s_i) switch network constructed with a PSB_C(m, s), where m = n is not rearrangeable. In the following, we prove that a PSN_C(n, m, s_p, s_o, s_i) with m ≤ n is not rearrangeable.

Arbitrarily select three sides i, k, and u of a PSN_C(n, n, s_p, s_o, s_i), 1 ≤ i ≤ s_p < k ≤ s_p + s_o < u ≤ S, we form an assignment AS = {(p_i,1, p_u,1), (p_i,2, p_u,2), …, (p_i,n−1, p_u,n−1), (p_i,n, p_k,n), (p_k,1, p_u,n)} to be connected between the P_i ∈ P_P, P_k ∈ P_O, and P_u ∈ P_I on a PSN_C(n, n, s_p, s_o, s_i). The RRV for routing AS_D on a PSB_C(n, s_p, s_o, s_i) is $$, as shown in Figure 4(a). Since a PSB_C(n, s_p, s_o, s_i) is equivalent to n isolated PSB_C(1, s_p, s_o, s_i)’s, the first r_i,u = (n − 1) can be realizable on (n − 1) isolated PSB_C(1, s_p, s_o, s_i)’s, as shown in Figure 4(b). But, we cannot find enough disjoint paths to simultaneously realize an r_i,k = 1 and an r_k,u = 1 on the last PSB_C(1, s_p, s_o, s_i), as shown in Figure 4(b). Thus, this AS cannot be realizable on a PSN_C(n, n, s_p, s_o, s_i), because this RRV $$ contains at least one connection that cannot be routed on a PSB_C(n, s_p, s_o, s_i). Therefore, the PSN_C(n, n, s_p, s_o, s_i) is not rearrangeable.

In the following, we will explore the properties of the semiuniversal and polygonal switch block PSB_SU(m, s_p, s_o, s_i) and show a PSN_SU(n, m, s_p, s_o, s_i) switching network constructed with semiuniversal PSB_SU(m, s_p, s_o, s_i), where m ≥ n is rearrangeable.

2.2. Semiuniversal and Polygonal Switch Blocks

Note that the number of connections interconnecting through each side of PSB(m, S) cannot exceed m; this dimensional constraint [9–11] is characterized by the preceding S inequalities, one for each side.

Label the terminals on the ith side of a PSB(m, S) as T_i = {t_i,1, t_i,2, …, t_i,m} for 1 ≤ i ≤ S. A generic universal switch block has been proposed by Shyu et al. [11]. As shown in Algorithm 3, the algorithm can be used to construct an S-side universal switch block PSB_U(m, S) with m terminals on each side. That is to say, any RRV $$ satisfying the dimension constraint (i.e., the number of connections on each side of a PSB(m, S) is at most m) is realizable on a PSB_U(m, S), for S ≥ 2 and m ∈ even [12]. For example, Figure 13(b) shows a universal PSB_U(2,6).

Since a semiuniversal PSB_SU(m, s_p, s_o, s_i) in a PSN_SU(n, m, s_p, s_o, s_i) does not allow any two internal terminals in the same set of T_P, T_O, and T_I to be interconnected, where $$, $$, and $$, we have to modify Algorithm 3 to construct our PSB_SU(m, s_p, s_o, s_i). Algorithm 2 removes the switches SW(t_i,j, t_k,l), where t_i,j and t_k,l belong to the same set of T_P, T_O, and T_I from PSB_U(m, S), S = s_p + s_o + s_i. For example, Figure 13(a) shows a semiuniversal switch block PSB_SU(2,2, 2,4), which is equal to a universal PSB_U(2,8) in Figure 13(b) minus some prohibited switches in Figure 13(c). That is to say, a semiuniversal switch block PSB_SU(m, s_p, s_o, s_i) contains a partial topology of the universal switch block PSB_U(m, S).

Note that the number of connections interconnecting through each side of PSB(m, s_p, s_o, s_i) cannot exceed m; this dimensional constraint is characterized by the preceding S inequalities, one for each side. Thus, the PSB_SU(m, s_p, s_o, s_i) constructed by Algorithm 2 is semiuniversal. Also, any RRV $$ satisfying the dimension constraint is simultaneously realizable on a PSB_SU(m, s_p, s_o, s_i).

5.1. Number of Switches in a PSN_SU

Let L be the total number of BLB’s in a PFPGA with B  I/O pins, and a BLB has r inputs and 1 output. The complete cluster-based logic block (CLB) is composed of k BLB’s, denoted as CLB(k). The number of switches in polygonal switching network PSN_SU(n, m, s_p, s_o, s_i) is obtained as follows.

From (10), SW_SU(n, m, s_p, s_o, s_i) is determined by the k and m values. In the following section, we will find proper k values and m to minimize the number of switches needed in a polygonal switching network through experiments.

5.2. Experimental Results

To explore the effects of k and m values of a polygonal switching network on the switch-efficiency in a PFPGA with L BLB’s and B  I/O pins, we have implemented a maze router [19–21] in C language and executed the codes on an IBM System M3. We examine the effect of two parameters, k and m, on the switch performance using the CGE [1] and SEGA [22] benchmark circuits.

By routing different cluster size of logic blocks, the switch performance of a three-sided polygonal switching network was evaluated. From the results of a CLB(5), as listed in Table 4, we first determine the minimum number of tracks m required to complete the 100% routing of each circuit, using three-sided polygonal switching networks PSN_SU(n, m, s_p, s_o, s_i). Then we can find the SW_SU(n, m, s_p, s_o, s_i) value by substituting the values of n, m, s_i, s_o, and s_p into (10).

Figure 16 shows that the numbers of programmable switches SW_SU(n, m, s_p, s_o, s_i) used in the 14 benchmarks vary with CLB(k), where k = 1,2, …, 12. Experimental results demonstrate that the switches number used in PSN_SU is minimum for a PFPGA with CLB(5) (for CGE) and CLB(3) (for SEGA), respectively. We assume that the available pin count of a PFPGA is B = 84 and the number of BLB is about 208. Therefore, our PFPGA consists of 52 CLB(5) and B = 84  I/O pins interconnected by a three-sided polygonal switching network SW_SU(n = 20, m = 25, s_i = 52, s_o = 11, s_p = 5).

5.3. VLSI Chip Implementation of the PFPGA

The chip layout of our PFPGA using a 0.18 μm CMOS technology is shown in Figure 17. The polygonal switching network area of a PFPGA is 1255 μm × 1350 μm. And the total area of this PFPGA is 1550 μm × 1600 μm. So we can calculate the ratio of routing area to total area to be 68.81%. Since routing area typically takes 70–90 percent of the total chip area in general FPGA [3]. So we conclude that the polygonal FPGA gets more area utilization.

In our proposed PFPGA architecture, we provide a three-stage routing resources concept. The first and third stages of routing are the connection blocks in two CLBs, which can meet local signal routing requirements. And the second layer of routing is the polygonal switch block, which is used to connect any output signal of a CLB to any input signal of a CLB. Thus, the longest distance in our PFPGA is only three stages. The maximum point-to-point of PSN_SU delay is 13 ns. So we conclude that the architecture of PFPGA has better speed improvement. As mentioned above, this chip architecture uses less number of programmable switches and the speed performance of a PFPGA can be achieved. Thus, it is very suitable for VLSI implementation.