A survey of DA techniques for PLD and FPGA based systems <s> Algorithms <s> The algorithms and the implementation of a new macro/custom cell chip-planning, placement, and global routing package are presented. The simulated-annealing-based placement algorithm proceeds in two stages. In the first stage, the interconnect area around the individual cells is determined using a new dynamic interconnect area estimator. The second stage consists of: (1) a channel definition step, using a new channel definition algorithm, (2) a global routing step, using a new global router algorithm, and (3) a placement refinement step. This strategy has produced placements which require very little placement modification during detailed routing. Total interconnect length savings of 8 to 49 percent were achieved in experiments on 9 industrial circuits. Furthermore, circuit-area reductions ranged from 4 to 56 percent versus a variety of other placement methods. <s> BIB001 </s> A survey of DA techniques for PLD and FPGA based systems <s> Algorithms <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
In this section, we review a new type of detailed routing algorithm geared towards segmented channels. For larger FPGAs, a global router may first be invoked. The process entails splitting each multi-pin net into a set of connections and then assigning each connection to a specific channel. The global router can use the vertical feed-through segments for nets that span multiple channels. However, the issues involved are similar to regular custom and semi-custom designs BIB001 . Let us define a K-segment routing problem as one of connecting all nets such that no net occupies more than K segments. If the total lengths of the segments are also targeted for minimization, it is called a K-segment solution with delay optimization. Though, in principle, we can use any MPGA routing algorithm, the restricted nature of the routing segments and of the switching fabric mandates better algorithms. Otherwise, we may find several instances of routing conflicts that lead to failed connections. In this section, we review an FPGA router for matrix-based architectures BIB002 . This router consists of two phase: • Global routing wherein each net is assigned a path in the grid graph by assigning it a sequence of channel segments. Its main purpose is to distribute the channel densities among the channels so as to facilitate the detailed routing phase. This step does not require any specific knowledge of FPGA architectures and so a regular MPGA algorithm is used. • Detailed Coarse Graph Expansion (CGE) router: The goal of this router is to assign specific wiring segments to each net so as to generate the global route determined in the previous step. The basic idea is as follows: Global graph expansion: Given a global route for each net, find all possible wire segments that can be used to extend the path from one channel of its global route to the next until either the target is met or no more paths remain to be expanded. The expansion depends on the switching capability of the C and S blocks and the connections used up by the previously routed nets. An example of this process is illustrated in Fig. 27 for a net connecting pin 5 of logic block at coordinates < 1, 1 > to pin 2 of logic block at coordinates < 3, 3 >. The global route is shown on the left and the detailed expansion yields three paths. Paths marked with a # lead to blockages. Path sorting: All the paths found in the graph expansion process are placed in a single path list and are ordered in the increasing order of costs. Costs for each path can be based on two factors: (a) demand on the wiring segments by other nets, (b) timing issues that can be modeled by counting the number of switches used in the path. For example, if a certain segment is required by many nets, then its cost is higher so as to discourage its use as far as possible. On the other hand, if there is only one choice, then it is given a low cost so as to include it in the current expansion. Update: The net corresponding to the lowest cost path is selected and its route is used to update the costs for the channel segments to be used in the routing of the other nets. This can change the order of the paths in the path-list. Pruning the search tree: The overheads to maintain all possible paths is v~ry high. Consequently, it is better to maintain a certain limited number of paths. In BIB002 , the authors use two pruning factors limiting the fanout from the root and from intermediate nodes in the coarse grid graph. This method does not mean that the other paths are removed from consideration for all times. If a route cannot be found for a certain net, then the pruning factors are gradually increased till we are successful. A rip-up and reroute strategy is done only when complete expansion of the coarse graph fails to yield a connection. However, if the switch boxes are fairly simple and provide limited options, then the exponential increase in paths does not happen and consequently the elaborate pruning features may not be really needed. 3 Cost function: In the path ordering phase, each of the paths P is assigned a cost c (P) = ~-~eEP [ Cf (e)+ wt • he]. ci(e) represents a cost for the edge e based on the demand for the edge in paths for other nets. For an edge e that has j other occurrences el, e2 ..... ej, the cost cf(e) is given by c/(e) = ~j 1/alt(ej) where alt(ej) is the number of edges in parallel with ej. For instance, in Fig. 27 , the edge connecting C(1,2) and S(3,2) has three alternative track assignments possible and hence the alt value for it is 3. Because of the summing process in c/(e), the more graphs e occurs in, the higher will be the cost. This reflects that edge e is in high demand and should be avoided if possible. Also if alt(e) happens to be zero, then the edge is essential as there are no alternatives. When the cost computation reveals an essential path, the router attempts to schedule it for routing first. The second cost component determines the timing cost of the net in terms of the number of S and L blocks it has traversed so far. If a certain net is deemed timing-critical, then the latter cost can be given a larger weight in determining the next path to be expanded. Note, that many FPGAs also provide long-range connections which skip some S boxes along the way. This might need adjusting the expression for the timing cost appropriately. The next segment determination and the update steps in the expansion is achieved using a black-box technique. This makes the CGE somewhat independent of the exact architectural features of the S and L blocks in different FPGA implementations.