A survey of DA techniques for PLD and FPGA based systems <s> Matching algorithm <s> Routing channels in a field-programmable gate array contain predefined wiring segments of various lengths. These may be connected to the pins of the gates or joined end-to-end to form longer segments by programmable switches. A segmented channel routing problem is formulated, and polynomial time algorithms are given for certain special cases. The general problem is NP-complete, but it can be adequately solved in practice with reasonable CPU time by heuristics. The experiments show that a segmented channel can generally accommodate connections using only a few more tracks than a conventional channel would.<<ETX>> <s> BIB001 </s> A survey of DA techniques for PLD and FPGA based systems <s> Matching algorithm <s> A two-slot addition called Splash, which enables a Sun workstation to outperform a Cray-2 on certain applications, is discussed. Following an overview of the Splash design and programming, hardware development is described. The development of the logic description generator is examined in detail. Splash's runtime environment is described, and an example application, that of sequence comparison, is given. > <s> BIB002
One part of the algorithm is fairly obvious by now. The goal is to detect a subgraph within the logic-block BDD that is isomorphic to the function BDD. A few observations are in order. First, it is sufficient to search for subgraphs of the same height as the function BDD. Secondly, it is necessary to consider all possible input orderings in the process. However, the number of such searches can be reduced by only considering non-isomorphic cases. The GBDD structure is quite useful for this purpose. The second part of the algorithm is executed if a match is found and pertains to "personalizing" the logic block by connecting input variables or constants 0 or 1 to each of the inputs of the logic block. This is done as follows: • The variables on the path leading from the root node of the module BDD to the root of the matched subgraph will be assigned constant 0 or 1 values depending on the corresponding edge labels. These variables can be thought of as stuck-at faults. • The mapping between the nodes in the matched subgraph and the circuit BDD specifies the input assignment to be made. Even when the matching algorithm fails to find a set of stuck-at faults that personalizes the logic block to the cluster function, it may still be possible to do so by bridging together certain inputs. The idea is as follows: Suppose in an input ordering variables a and b are adjacent to one another. Now if they were to be bridged, i.e. have the same logic value, then it is clear that of the four possible of the logic BDD is that the subgraphs corresponding to the other two cofactors, viz., Fa, b and Fab, can be deleted. Also the node corresponding to the variable b can be dropped. Figure 15(a) shows the general case of bridging; while Fig. 15(b) shows the effect of bridging variables a and e for the Act-1 logic block under the first input ordering of Fig. 14. Often times, the resulting BDD is structurally different from the ones constructed purely on the basis of input orderings. Hence, the matching process can be continued on the new BDDs. Note that bridging can in principle be carried out for any number of variables. However, even for the simplest case of a 1-bridge fault, wherein only two variables are considered, the possibilities are astronomical. Clearly for each of the input orderings, a different pair of input variables can be considered. In practice, though, the one-bridge algorithm considers each of the function variables in order and constructs a function BDD with that variable as the first one in the BDD 6rdering. For each of the function BDDs, all possible input orderings are considered for the logic-block BDD. It then searches for subgraphs within this BDD where bridging the first two variables of the subgraph (say a and b) to the first variable of the function BDD (say x) results in a match being found. In actual practice, this determination can be done in place rather than create a new BDD as suggested by Fig. 15(b) . The key point is to note that the effect is the same as checking for match between the subgraph of the function BDD specified by the stuck-at-fault x = 0 and that in the logic-block BDD specified by the pair of faults a = 0 and b = 0. Similarly, a match is checked between the subgraph of the function BDD specified by the stuck-at-fault x --1 and that in the logic-block BDD specified by the pair of faults a = 1 and b = 1. Figure 16 shows the logic-block BDD based on the input ordering (a f c b d e g). We consider the 1-bridge of the first two variables a and f and check for isomorphic subgraphs based on the stuck-at notion developed above. The two subgraphs for the logic-block BDD corresponding to the appropriate stuck-at BDDs of the function module are also marked in the figure. From this it can be determined that the required personalization is a = v, b = y, c = 0, d = z, e = w, f = v, g = x. Note how the input variable v is simultaneously applied to both inputs a and f which represent the bridge set in this case. Example 6.1. Figure 17 shows the implementation of the vending machine design using Eq. (2) and the Actel mux-based architecture shown in Fig. 14 with b, c, d, e, f, g replaced by SA, A1, AO, SB, B1 , B0 and signal a formed by the OR of S1 and SO. As can be seen, this is a three-level implementation and needs only 7 basic blocks and so is quite compact. The lines beginning with an asterisk have been added by us to clarify the function being implemented by that logic block. On the other hand, a two-level implementation would require upto 16 basic blocks. INSTANCE "BASIC_BLOCK":physical NAME = INST0 "A0" "AI" "SA" "B0" "BI" "SB" "SO" "SI" "out" ******=> out = ql'q0 INSTANCE "BASIC_BLOCK" "A0" "AI" "SA" "B0" "BI" "SB" "SO" "SI" "out " ******=> out = [24]'q0 INSTANCE "BASIC_BLOCK" "A0" "AI" "SA" "B0" "BI" "SB" "S0" "SI" "out" ******=> out = ql N' + : "GND"; : "q0"; : "vdd"; : "GND"; : "GND"; : "Vdd"; : "ql"; : "GND"; : "  "; :physical NAME = INST1 : "GND"; : "q0"; : "Vdd"; : "GND"; : "GND"; : "Vdd"; : "  "; : "GND"; : " BIB002 "; :physical NAME = INST2; : "GND" ; : " BIB002 " ; : "Vdd" ; : "Vdd" ; : " BIB002 " ; : "n" ; : "ql " ; : "GND" ; [:613 "  "; INSTANCE "BASIC_BLOCK":physical NAME = INST3 "A0" : "GND"; "AI" : "  "; "SA" : "Vdd"; "B0" : "GND"; "BI" : "GND"; "SB" : "Vdd"; "SO" : "d"; "SI" : "GND"; "out" : " BIB001 "; ******=> out = D'  INSTANCE "BASIC_BLOCK":physical NAME = INST4 "A0" : "  "; "AI" : "Vdd"; "SA" : "d"; "B0" : " BIB001 "; "BI" : "Vdd"; "SB" : "  "; "SO" : "q0"; "SI" : "GND"; "out . 