A survey of DA techniques for PLD and FPGA based systems <s> Wiring resources <s> Tabula Rasa is a user reconfigurable hardware system under development in AT&T Bell Labs. Its purpose is to assist in the development of new hardware systems, and possibly to serve as a computing engine in its own right. The core of the system is a full-custom CMOS chip. This chip has electrically programmed logic and routing, and allows an external monitor to observe, control, and reconfigure the circuit during operation. Unlike currently available programmable logic devices this chip is targeted specifically at the development rather than the production environment. One or more of these chips could be wired into the development version of an application system, to add flexibility and simplify the design process by making the design more controllable and observable. In another type of application, an array of these chips could be assembled into a dedicated processor attached to a workstation. The architecture of the chip, some of the tradeoffs involved, and the CAD challenges needed to support it are outlined. > <s> BIB001 </s> A survey of DA techniques for PLD and FPGA based systems <s> Wiring resources <s> A detailed routing algorithm, called the coarse graph expander (CGE), that has been designed specifically for field-programmable gate arrays (FPGAs) is described. The algorithm approaches this problem in a general way, allowing it to be used over a wide range of different FPGA routing architectures. It addresses the issue of scarce routing resources by considering the side effects that the routing of one connection has on another, and also has the ability to optimize the routing delays of time-critical connections. CGE has been used to obtain excellent routing results for several industrial circuits implemented in FPGAs with various routing architectures. The results show that CGE can route relatively large FPGAs in very close to the minimum number of tracks as determined by global routing, and it can successfully optimize the routing delays of time-critical connections. CGE has a linear run time over circuit size. > <s> BIB002
Wiring resources comprise of horizontal and vertical channels with switchboxes at each intersection. Within the switchbox, pass transistors are provided to switch an incoming wire to one of the three alternate directions. Longer busses are also provided to minimize the number of switches in each net path. Switches are provided for these longer nets at every other row and column intersection. Special wiring for clock and some dedicated wiring for carry calculations are also provided. In addition, all function inputs are connected directly to all single length wire segments; while the outputs are connected to a subset of both vertical and horizontal segments. A more general view of the overall routing architecture  is shown in Fig. 25 . The L boxes refer to the logic cells (i.e. the CLBs); the C (connection) blocks are rectangular switch boxes that connect the CLB pins to the routing channels via programmable switches; while the S(switch) blocks connect the wiring segments in one channel to those in another. The configuration of the C and S blocks largely determine the ease of routability of an FPGA and thus help differentiate between different members of this class. Clearly, the more the wiring segments that can be switched, the easier it is to route. The goal of routing is to configure all the CIPs (configurable interconnection points) within the capabilities of the switchboxes so as to obtain conflict free routes for all the nets. A sample C block structure is shown in Fig. 25(b) . Each dark dot indicates a CIP which can be programmed to either make or break the connection. The features of the FPGA which are especially important from a routing standpoint are as follows: • The number of wiring segments is predetermined. It is entirely possible that the successful routing of some net may rely on the assignment of a specific wiring segment to that net. If a sequential style of routing such as a maze router is used, then care has to be taken BIB002 to ensure that such essential segments are assigned appropriately. Figure 26 shows an instance wherein the wrong assignment of a segment to net A will lead to a failed connection for either net B or net C. • If the CLB is implemented in the form of a table-lookup using SRAM BIB001 , then the inputs to the function table are interchangeable. The router takes a request to route to a input as a request to route to any unassigned input. Thus for a maze router, the necessary modification is to start the expansion from all the unassigned input terminals simultaneously. • CIPs can be of two types: cross where the CIP comprises of a bidirectional pass gate and an SRAM cell; and muxcip which represents a member of a mutually exclusive group and is controlled by decoding one or more SRAM cells in parallel. The implication for the router is that a single path cannot use more than one member of a decoded CIP group. • Unlike gate-arrays there can be no doglegs in channels in an FPGA since the metallization pattern is fixed. Thus routing within a channel can use a simple left-edge kind of algorithm. • Proper allocation of nets to busses of appropriate length is needed for maintaining tighter delay bounds on nets. • Allocation of nets must also take into account the switchbox resources.