A fundamental feature of Dynamically Reconfigurable FPGAs (DRFPGAs) is that the logic and interconnect are time-multiplexed. Thus, for a circuit to be implemented on a DRFPGA, it needs to be partitioned such that each subcircuit can be executed at a different time. In this paper, the partitioning of sequential circuits for execution on a DRFPGA is studied. To determine how to correctly partition a sequential circuit and what are the costs in doing so, we propose a new gate-level model that handles time-multiplexed computation. We also introduce an enchanced force directed scheduling (FDS) algorithm to partition sequential circuits that finds a correct partition with low logic and communication costs, under the assumption that maximum performance is desired. We use our algorithm to partition seven large ISCAS'89 sequential benchmark circuits. The experimental results show that the enhanced FDS reduces communication costs by 27.5 percent with only a 1.1 percent increase in the gate cost compared to traditional FDS.

Functional scan chains are scan chains that have scan paths through a circuit's functional logic and flip-flops. Establishing functional scan paths by test point insertion (TPI) has been shown to be an effective technique to reduce the scan overhead. However, once the scan chain is allowed to go through functional logic, the traditional alternating test sequence is no longer enough to ensure the correctness of the scan chain. We identify the faults that affect the functional scan chain, and show a methodology to find tests for these faults. Our results have the number of undetected faults at only 0.006% of the total number of faults, or 0.022% of the faults affecting the scan chain.

A fundamental feature of Dynamically Reconfigurable FP-GAs (DRFPGAs) is that the logic and interconnect is time-multiplexed. Thus for a circuit to be implemented on a DRFPGA, it needs to be partitioned such that each subcircuit can be executed at a different time. In this paper, the partitioning of sequential circuits for execution on a DRF-PGA is studied. To determine how to correctly partition a sequential circuit, and what are the costs in doing so, we propose a new gate-level model that handles time-multiplexed computation. We also introduce an enchanced force directed scheduling (FDS) algorithm to partition sequential circuits that finds a correct partition with low logic and communication costs, under the assumption that maximum performance is desired. We use our algorithm to partition seven large ISC AS'89 sequential benchmark circuits. The experimental results show that the enhanced FDS reduces communication costs by 27.5% with only a 1.1% increase in the gate cost compared to traditional FDS.

It has been observed experimentally that the mapping of global to detailed routing in a conventional FPGA routing architecture (2D array) yields unpredictable results. A different class of FPGA structures called greedy routing architectures (GRAs), where a locally optimal switch box routing can be extended to an optimal entire-chip routing, were investigated by Wu et al. (1994), Takashima et al. (1996) and Wu et al. (1996). It was shown that GRAs have good mapping properties. An H-tree GRA with W/sup 2/+2W switches per switch box (SpSB) and a 2D array GRA with 4W/sup 2/+2W SpSB were proposed by those authors (W is the number of tracks in each switch box). We continue this work by introducing an H-tree GRA with W/sup 2//2+2W SpSB and a 2D array GRA with 3.5 W/sup 2/+2 W SpSB. These new GRAs have the same good mapping properties but use fewer switches. We also show a class of FPGA architectures in which the mapping problem remains NP-complete, even with 6(W-1)/sup 2/+6W/sup 2/ SpSB (this is close to the maximum number of SpSB, which is 6W/sup 2/). Thus, more switches do not necessarily result in more routability.

In this paper, we present a test synthesis approach which integratesBALLAST (BALAnced structure Scan Test) withan enhanced test point insertion (TPI) algorithm to functionallyscan the flip-flops chosen by BALLAST.BALLASTis an attractive partial scan technique in that it offers combinationalATPG efficiency while promising to reduce full scanoverhead.However, the practical problem with BALLASTis it typically requires more scan flip-flops than other partialscan techniques.The TPI enhancements enable TPI toaim at the reduction of BALLAST overhead.The enhancementsinclude a more flexible test point insertion heuristic,a modified gain function which enables TPI to target a selectedset of flip-flops, and a more efficient procedure toremove redundant test points.The experimental results onnine benchmark circuits show the proposed test synthesisapproach can achieve on average 38% area saving comparedto full scan, while BALLAST alone achieves 17%.

We investigate the hardware implications when combinational logic is implemented on Dynamically Reconfigurable FPGAs (DRFPGAs). We first investigate the number of communication buffers needed by a DRFPGA. These buffers are needed because the time-multiplexednature of DRFPGAs means that only a portion of the circuit implemented on the chip is present at any given time instance. Thus there is a need to store OT buffer signals until they are no longer needed. The hardware cost in a DRFPGA is the maximum number of buffers (plus associated routing) needed at any given time. We show experimentally that this number is almost as large as the number of computation nodes needed at any given time, and in some circuits twice as large. We also give a heuristic algorithm based on rescheduling nodes that reduces the number of buffers needed by 23%. Next we investigate time-multiplexed I/0 on a DRFPGA. We show that by using time-multiplexed 1/0pins, the number of physical I/0pins needed can be reduced by up to 83%.

Investigates the pin redistribution problem (PRP) for multi-chip modules. A novel transformation to the max-flow problem is introduced. This approach provides an efficient algorithm for finding a 2-layer solution, whenever one exists. A greedy heuristic to find a k-layer solution is described. The approach can find a minimum layer solution for two variants of the PRP; when each net can be routed on more than one layer, and when source and target terminals are drilled through all layers. Except for the heuristic procedure which takes O(km/sup 4/ log/sup 2/ m) time, the algorithms take O(/spl verbar/S/spl verbar/km/sup 2/) time, where S is the set of source terminals, m is the number of rows and columns in the grid, and k is the number of layers required. One can show that generalizations of the k-layer PRP are NP-complete problems.>