Analysis of FPGA/FPIC switch modules

Reviewer: Partha Sarathi Dasgupta

Field-programmable gate arrays (FPGAs) are useful solutions to cost and time-to-market challenges in the semiconductor industry. This is primarily due to the short design-time turnaround, with low risk and cost, facilitating easily modifiable designs. An FPGA is, in general, an array of logic modules that can be interconnected with the help of vertical and horizontal channels and switch modules. A net can change its routing direction via a switch module. A large circuit that cannot be accommodated in a single FPGA is divided into several parts, with each part being realized by an FPGA, and these FPGAs are in turn embedded and interconnected in a field-programmable interconnect chip (FPIC). Earlier studies revealed that the routability of switch modules in FPGAs has a significant effect in reducing the area requirement. Thus, the study of the routability of switch modules in FPGAs is of great importance in the study of the behavior of FPGAs. This paper addresses such a study. The routability analysis problem studied here is defined by the authors as follows: consider a switch module defined as a W x W block, with W terminals on each side of the block. The switch module has two kinds of switches, namely, crossing (row-column) switches and (row-specific or column-specific) separating switches. It is assumed that connection of any two terminals requires at most one switch being “ON.” The terminals around a switch module can be connected in any one of six different ways, two of which are straight, and four are bent connections. A routing requirement vector (RRV) is also present, which gives the required number of terminal connections in each of the six different ways. Formally, the switch module analysis problem (SMAP) is defined as follows: given the input, a switch module M (switch matrix or switch block) and a RRV, the objective is to find if the given RRV is routable on M . A network-flow-based algorithm is proposed to solve a particular class of SMAP. This is then used in approximating general SMAPs. The network-flow analyzer starts with an input switch module and a RRV, and constructs a network-flow diagram from this, assuming each of the cases of a sink terminal on any one of the four sides, with the other sides being the source. In each of the constructed flow networks, the proposed algorithm attempts to check if there is a feasible flow, where, for each i , s_i supplies a flow n_i (component of given RRV), and the sink t receives a flow of sum of all n_is . This problem is solvable in time O(W(N + W)log W) , where N is the number of switches, and W is the maximum number of terminals associated with any of the six directions. If there does not exist any feasible flow for any value of i , the switch module is not routable for the given RRV; otherwise, pick up another sink side. For the proposed flow analyzer, the performance bounds were analyzed, as measured by the ratio of the sizes of two feasible sets obtained by the flow analyzer and by an ILP-based exact flow analyzer. The theoretical performance bounds obtained for switch matrices and switch blocks are 5 and 5/4 respectively. The authors of the paper then extend the network-flow analyzer to a more general switch-module routing model. The relaxed condition for a connection to be feasible is that it does not contain any doglegs. Hence, in the relaxed model, a connection of two terminals can use up to one crossing switch, and two separating switches. The flow analyzer was implemented in C on a SUN SPARC 5 workstation. Empirical studies were performed for the performance of the flow analyzer on switch matrices, and the correlation between switch-matrix and chip level routability. Run times for computing all routable RRVs for a switch matrix by the flow analyzer and the exact analyzer are also reported. To summarize, the authors show the network-flow-based routability analyzer to be very efficient and accurate. They also claim that proving NP-completeness of SMAP is an unsolved problem. Future work may involve the study of routing capacity for multiple switch modules in series, and the interaction of switch modules and pin-to-track connections. Online Computing Reviews Service