We present a latency-constrained iterative list scheduling type algorithm, FALLS, to minimize the total number of functional units (FUs) allocated, and thus the total area, in high-level synthesis designs. The algorithm incorporates a novel lookahead technique to selectively schedule available operations by allocating the needed FUs earlier or reserving available FUs for scheduling more timing-urgent operations later, such that no additional FU is needed and higher FU utilization is obtained. Further, a fractional search framework is developed to iteratively estimate the number of FUs of each function type required in the final design based on the current scheduling solution and FU utilization, and reiterate the lookahead-based list scheduling with the new FU allocation estimate to further increase FU utilization. Extensive experiments conducted over several DFGs and a wide range of latency constraints demonstrate that FALLS is much more effective than other approximate state-of-the-art algorithms in both number of FUs and total FU area, and has a much smaller runtime. Results also show that FALLS has only an average 5.5% optimality gap compared to an optimal integer linear programming (ILP) formulation, but is 278k times faster. FALLS also performs much better in architectural (FU + mux/demux + register) area, interconnect congestion and number of interconnects than approximate algorithms, and is at most 4.0% worse in them than the ILP method.

Current nanoscale designs are highly interconnect dominated, taking about 70% of the chip area. Interconnects also consume significant dynamic power, and about 60% of signal delays. It is thus important to be able to synthesize much lower interconnect-complexity designs than are possible with current high-level synthesis (HLS) tools and algorithms. Towards that end, we have developed the new paradigms of: a) flexibly-structured buslets that connect a few “neighborhood” functional units (FUs) instead of dedicated interconnect between pairs of FUs, thereby sharing interconnects among a number of FU pairs that need to communicate; b) communication scheduling (followed by standard operation scheduling) in which communication between FUs are scheduled at appropriate times to minimize the number of buslets needed, subject to buslet cardinality constraints (for the purpose of upper bounding signal delay). Using a force-directed technique for communication and operation scheduling, and a chronological algorithm that simultaneously performs communication-to-buslet, FU-connections-to-buslets and operation-to-FU binding, we obtain significant wirelength (WL) reduction in the range of 35–71% in our designs compared to conventional FDS-based designs with dedicated-interconnects between communicating FU pairs.

We present a physical-synthesis based power optimization technique that simultaneously explores the four transforms, multipleVdd, multipleVth, cell sizing, and placement, to find a minimum power solution under timing and other constraints. The optimal selection of the design options of all transforms for all cells in the circuit is solved using a new optimization technique called discretized network flow that we have recently developed. Among the constraints we consider, timing and the voltage-island constraints are the two most important and complex ones. The voltage-island constraint specifies the maximum allowed number of voltage islands in the layout, and the requirement that each island be rectangular. We develop an approach that along with the option selection process can simultaneously determine the voltage islands needed, as well as satisfy all given constraints. Experimental results on ISCAS'89 and Faraday benchmarks show that compared to an initial wire length (WL)-optimized placement with high supply and low threshold voltage levels, we obtain a power reduction by up to 42% and an average of 30% for the same delay as that of the initial design. These improvements are also 44-50% relatively better than the improvements yielded by sequentially applying the four power reduction transforms, which is the currently standard method for applying multiple transforms. Finally, compared to an industry tool Synopsys IC Compiler (ICC) that also applies all four transforms, our method reduces power by an additional amount of up to 19%, and an average of 16%.

We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits without appreciable increase in wire length (WL). FlowPlace includes: 1) a timing-driven (TD) analytical global placer TAN that uses accurate pre-route delay functions and minimizes a combination of linear and quadratic objective functions; 2) a discretized network-flow-based detailed placer DFP that has new and effective techniques for performing TD/WL-driven incremental placement while satisfying row-width (white space) constraints; 3) new and accurate unrouted net delay models that are suitable for an analytical placer; and 4) an effective probability-based WL-cost function in detailed placement for reducing WL deterioration while performing TD-incremental placement. We ran FlowPlace on three sets of benchmarks with up to 210 K cells. Starting from WL-optimized placements done by Dragon 2.23, and using purely timing-driven incremental placement, we are able to obtain up to 33.4% and an average of 17.3% improvement in circuit delays at an average of 9.0% WL increase. When incorporating both timing and WL costs in the objective functions of global and detailed placement, the average WL increase reduces to 5.8%, a 35% relative reduction, while the average delay improvement is 15.7%, which is only relatively 9% worse. The run time of our incremental placement method is only about 10% of the run time of Dragon 2.23. Furthermore, starting from an already timing-optimized placement done by TD-Dragon, we still obtain up to 10% and an average of 6.5% delay improvement with a 6.1% WL deterioration; the run time is about 6% of TD-Dragon's.

In this paper, we propose an effective white-space (i.e., row length) constraint satisfaction technique embedded in a network flow based detailed placer for standard cell designs that is suitable for both incremental as well as full detailed placement. The highlight of our method is a provable high-probability of obtaining a legal placement even under tight white space (WS) constraints. This high success probability of our method stems from our flexibility of allowing a well-controlled temporary WS constraint violation in the detailed placement process. The flexibility also helps improve the solution quality of the detailed placer, measured by the deterioration of the optimization metric from the global placement solution. We tested our WS constraint-satisfaction method controlled temporary violations (CTV) on two sets of benchmarks for both incremental and full placement applications, and for timing as well as wire length (WL) optimization problems. We obtained legal solutions for all circuits in reasonable times under a 3% WS constraint. For example, for a 210 k-cell circuit td-ibm18: 1) for the timing-driven incremental placement application, we obtain the final placement in 900 secs with a 35.2% delay reduction compared to an initial WL-optimized placement done by Dragon 2.23 and 2) for the full timing-driven placement problem, we obtain the final placement in less than 2.5 h with a timing improvement of 29.8% compared to the state-of-the-art WL-driven detailed placer of NTUplace3-LE. We also tested two internal methods, one that disallows any temporary WS violation, and another which moves cells from WS violated rows to non-full rows in a heuristic manner. The first method cannot legalize all benchmarks, and CTV is 41%-86% relatively better in delay and WL metrics than the two internal methods.

We develop two novel globally-informed gate-sizing algorithms for tackling the problems of statistical circuit timing optimization under a timing yield constraint, and timing yield optimization under a timing (i.e., delay) constraint. Unlike previous works, our techniques are global in the sense that they use objective functions that take into account either the entire circuit's variabilities and available gate sizes or those of the statistically timing-critical part of the circuit. The actual optimization, using the aforementioned objective functions, was performed using a recently introduced efficient discrete optimization technique called discretized network flow (DNF). We compared our algorithms to a state-of-the-art sensitivity based method. Experimental results show an absolute yield improvement of up to 43% and an average of 37% for the best of our two techniques over that of a non-statistical timing optimized circuit (optimized using a recent state-of-the-art method) based on the worst-case delay estimate for each gate. Our technique also gives a 19% better relative yield improvement over the sensitivity based method.

A novel trust-based design method for FPGA circuits that uses error-correcting code (ECC) structures for detecting design tampers (changes, deletion of existing logic, and addition of extradesign logic-like Trojans) is proposed in this article. We determine ECC-based CLB (configuration logic block) parity groups and embed the check CLBs for each parity group in the FPGA circuit. During a trust-checking phase, a Test-Pattern Generator (TPG) and an Output Response Analyzer (ORA), configured in the FPGA, are used to check that each parity group of CLB outputs produce the expected parities. We use two levels of randomization to thwart attempts by an adversary to discover the parity groups and inject tampers that mask each other, or to tamper with the TPG and ORA so that design tampers remain undetected: (a) randomization of the mapping of the ECC parity groups to the CLB array; (b) randomization within each parity group of odd and even parities for different input combinations (classically, all ECC parity groups have even parities across all inputs). These randomizations along with the error-detecting property of the underlying ECC lead to design tampers being uncovered with very high probabilities, as we show both analytically and empirically. We also classify different CLB function structures and impose a parity group selection in which only similarly structured functions are randomly selected to be in the same parity group in order to minimize check function complexity. Using the 2D code as our underlying ECC and its 2-level randomization, our experiments with inserting 1-10 circuit CLB tampers and 1-5 extraneous logic CLBs in two medium-size circuits and a RISC processor circuit implemented on a Xilinx Spartan-3 FPGA show promising results of 100% tamper detection and 0% false alarms, obtained at a hardware overhead of only 7-10%.

We propose a post-placement physical synthesis algorithm that can apply multiple circuit synthesis and placement transforms on a placed circuit to improve the critical path delay under area constraints by simultaneously considering the benefits and costs of all transforms (as opposed to considering them sequentially after applying each transform). The circuit transforms we employ include, but are not limited to, incremental placement, two types of buffer insertion, cell resizing and cell replication. The problem is modeled as a min-cost network flow problem, in which nodes represent circuit transform options. By carefully determining the structure of the network graph and the cost of each arc, a set of near-optimal transform options can be obtained as those whose corresponding nodes in the network graph have the min-cost flow passing through them. We also tie the transform selection network graph to a detailed placement network graph with TD arc costs for cell movements. This enables our algorithms to incorporate considerations of detailed placement cost for each synthesis transform along with the basic cost of applying the transform in the circuit. We have tested our algorithms on three sets of benchmarks under 3-10% area increase constraints, and obtained up to 48% and an average of 27.8% timing improvement. Our average improvement is relatively 40% better (8.2% better by an absolute measure) than applying the same set of transforms in a good sequential order that is used in many current techniques. Considering only synthesis transforms (no replacement), our technique is relatively 50% better than the sequential approach.

We present novel and efficient methods for built-in self-test (BIST) of field-programmable gate arrays (FPGAs) for detection and diagnosis of permanent faults in current, as well as emerging, technologies that are expected to have high fault densities. Our basic BIST methods can be used in both online and offline testing scenarios, although we focus on the former in this paper. We present 1- and 2-diagnosable BISTer designs that make up a ROving TEster (ROTE). Due to their provable diagnosabilities, these BISTers can avoid time-intensive adaptive diagnosis without significantly compromising diagnostic coverage-the percentage of faults correctly diagnosed. We also develop functional testing methods that test programmable logic blocks (PLBs) in only two circuit functions that will be mapped to them as the ROTE moves across a functioning FPGA. We extend our basic BISTer designs to those with test-pattern generators (TPGs) using multiple PLBs to more efficiently test the complex PLBs of current commercial FPGAs and to also prove the diagnosabilities of these designs. Simulation results show that our 1-diagnosable functional-test-based BISTer with a three-PLB TPG has very high diagnostic coverages-for example, for a random-fault distribution, our nonadaptive-diagnosis methods provide diagnostic coverages of 96% and 88% at fault densities of 10% and 25%, respectively, whereas the previous best nonadaptive-diagnosis method of the STAR-3 × 2 BISTer has diagnostic coverages of about 75% and 55% at these fault densities.

We present new techniques for explicit constraint satisfaction in the incremental placement process. Our algorithm employs a Lagrangian relaxation (LR) type approach in the analytical global placement stage to solve the constrained optimization problem. We establish theoretical results that prove the optimality of this stage. In the detailed placement stage, we develop a constraint-monitoring and satisfaction mechanism in a network (n/w) flow based detailed placement framework proposed recently, and empirically show its near-optimality. We establish the effectiveness of our general constraint-satisfaction methods by applying them to the problem of timing-driven optimization under power constraints. We overlay our algorithms on a recently developed unconstrained timing-driven incremental placement method flow-place. On a large number of benchmarks with up to 210K cells, our constraint satisfaction algorithms obtain an average timing improvement of 12.4% under a 3% power increase limit (the actual average power increase incurred is only 2.1%), while the original unconstrained method gives an average power increase of 8.4% for a timing improvement of 17.3%. Our techniques thus yield a tradeoff of 75% power improvement to 28% timing deterioration for the given constraint. Our constraint-satisfying incremental placer is also quite fast, e.g., its run time for the 210 K-cell circuit ibm18 is only 1541 secs.

In current very deep submicron (VDSM) circuits, incremental routing is crucial to incorporating engineering change orders (ECOs) late in the design cycle. In this paper, we address the important incremental routing objective of satisfying timing constraints in high-speed designs while minimizing wirelength, vias and routing layers. We develop an effective timing-driven (TD) incremental routing algorithm TIDE for ASIC circuits that addresses the dual goals of time-efficiency, and slack satisfaction coupled with effective optimizations. There are three main novelties in our approach: (i) a technique for locally determining slack satisfaction of the entire routing tree when either a new pin is added to the tree or an interconnect in it is re-routed - this technique is used in both the global and detailed routing phases; (ii) an interval-intersection and tree-truncation algorithm, used in global routing, for quickly determining a near-minimum-length slack-satisfying interconnection of a pin to a partial routing tree; (iii) a depth-first-search process, used in detailed routing, that allows new nets to bump and re-route existing nets in a controlled manner in order to obtain better optimized designs. Experimental results show that within the constraint of routing all nets in only two metal layers, TIDE succeeds in routing more than 94% of ECO-generated nets, and also that its failure rate is 7 and 6.7 times less than that of the TD versions of previous incremental routers Standard (Std) and Ripup & Reroute (R & R), respectively. It is also able to route nets with very little (3.4%) slack violations, while the other two methods have appreciable slack violations (16-19%). TIDE is about 2 times slower than the simple TD-Std method, but more than 3 times faster than TD-R&R

We present a very effective on-line interconnect built-in-self-test (BIST) method I-BIST for FPGAs that uses a combination of the following novel techniques: a track-adjacent and a switch-adjacent (also called "mirror adjacent") pairwise net comparison mechanism that achieves high detectability, a carefully designed set of only five net-configurations that cover all types and locations of wire-segment and switch faults, a 2-phase global-detailed testing approach, and a divide-and-conquer technique used in detailed testing to quickly narrow down the set of potential suspect interconnects that are then detail-diagnosed. These techniques result in I-BIST having provable detectability in the presence of an unbounded number of multiple faults, very high diagnosability of 99-100% even for high fault densities of up to 10% that are expected in emerging nano-scale technologies, and much lower test times or fault latencies than the previous best interconnect BIST techniques. In particular, for application to on-line testing, our method requires 2n roving-tester (ROTE) configurations to test an entire n times n FPGA, while the previous best online interconnect BIST technique requires n2configurations. Thus, I-BIST is an order of magnitude more time- as well as power-efficient, and scale well with rapidly increasing FPGA device sizes that are expected in emerging technologies

We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits. FlowPlace includes: a) a timing-driven (TD) analytical global placer TAN that uses accurate delay functions and minimizes a combination of linear and quadratic objective functions; b) a network flow based detailed placer TIF that has new and effective techniques for performing TD incremental placement and satisfying rowlength (white space) constraints. We have obtained results on three sets of benchmarks: i) TD versions of the ibm benchmark suite that we have constructed; ii) benchmarks used in TD-Dragon; iii) the Faraday benchmarks. Results show that starting with Dragon-placed circuits, we are able to obtain up to 34 % and an average of 18 % improvement in critical path delays, at an average of 17.5 % of the run-time of the Dragon placer. Starting with a state-of-the-art TD placer TD-Dragon, for the TD-Dragon benchmarks we obtain up to about 10 % and an average of 4.3 % delay improvement with 12 % of TD-Dragon’s run times; this is significant as we are extracting performance improvements from a performanceoptimized layout. Wire length deterioration on the average over all benchmark suites is less than 8%. 1.

We tackle the problem of fault-free assumptions in current PLB and interconnect built-in-self-test (BIST) techniques for FPGAs. These assumptions were made in order to develop strong BIST methods for one class of components (PLBs or interconnects) while assuming that the other class is fault-free. This results in a cyclical conundrum that renders current PLB and interconnect BIST techniques impractical, since current deepsubmicron FPGAs as well as those of emerging single-digit nanometer technologies are expected to have a profusion of hard (permanent) PLB as well as interconnect faults. We address this issue here and develop a novel method M-BIST that uses a combination of (i) iterative bootstrapping that without any knowledge of the state of any PLB or interconnect determines a minimum contingent of fault-free test circuit components with high probability, and (ii) mixed testing of PLBs and interconnects in an interleaved manner that identifies fault-free components that are used in subsequent testing phases until the entire FPGA is tested. This approach is overlaid on current state-of-the-art PLB and interconnect BIST techniques. Simulation results obtained for faults present in both PLBs and interconnects show significant improvements in both fault coverage and false positives yielded by M-BIST compared to the PLB-only and interconnect-only BIST techniques used within the M-BIST wrapper that make fault-free assumptions about the other component type

We develop a novel on-line built-in self-test (BIST) technique for testing FPGAs that has a very high diagnosability, even in presence of clustered faults, a fault pattern for which previous BIST methods proved ineffective. Unlike previous BIST methods which unrealistically assume that the test circuitry used for testing PLBs is fault-free, our method, via an iterative bootstrapping process, first finds this fault-free test circuitry and then starts testing the PLBs. Also, unlike previous methods, our fault detection process does not require any unrealistic assumptions of fault-free status of some components or the existence of only some fault patterns (and the exclusion of others) in the FPGA. Our adaptive fault diagnosis process is more time efficient than its previous counterparts as it does not require testing of all the PLBs of a faulty BIST area, and its design is simpler in the sense that it does not require multiple modifications of the testing area for its implementation. We also analyze the probability of correct diagnosis in the presence of multiple faults. Our BIST technique gives excellent fault coverage and fault latency results, and supports the theoretical analysis.

We present novel and efficient methods for on-line testing in FPGAs. The testing approach uses a ROving TEster (ROTE), which has provable diagnosabilities and is also faster than prior FPGA testing methods. We present 1- and 2-diagnosable built-in self-tester (BISTer) designs that make up the ROTE, and that avoid expensive adaptive diagnosis. To the best of our knowledge, this is the first time that a BISTer design with diagnosability greater than one has been developed for FPGAs. We also develop functional testing methods that test PLBs in only two circuit functions that will be mapped to them (as opposed to testing PLBs in all their operational modes) as the ROTE moves across a functioning FPGA. Simulation results show that our 1-diagnosable BISTer and our functional testing technique leads to significantly more accurate (98% fault coverage at a fault/defect density of 10%) and faster test-and-diagnosis of FPGAs than achieved by previous work. The fault coverage of ROTE is also expected to be high at fault/defect densities of up to 25% using our 1-diagnosable BISTer and up to 33% using our 2-diagnosable BISTer. Our methods should thus prove useful for testing current very deep submicron FPGAs as well as future nano-CMOS and molecular nanotechnology FPGAs in which defect densities are expected to be in the 10% range.

We propose a roving tester (ROTE) that tests the PLBs of the FPGA by periodically moving across it. At any time, the ROTE occupies a certain area of the FPGA, say two columns, and tests all PLBs in that area using parallel built-in self-tester (BISTers). A significant contribution of this work are designs for 1- and 2-diagnosable BISTers. To the best of our knowledge, this is the first time that BISTer designs with provable diagnosabilities have been developed for FPGAs. We also develop functionality-specific testing methods that test PLBs in only two circuit functions that will be mapped to them (as opposed to testing PLBs in all their operational modes), for any reconfigurable fault pattern as the ROTE moves across the FPGA. The combination of our 1- or 2-diagnosable BISTer design and our functionality-specific testing technique leads to more accurate and faster test-and-diagnosis of FPGAs than achieved by previous work.

We have developed a hop-based complete detailed router ROAD-HOP that uses the Bump & Refit (B&R) approach to route a FPGA circuit in a near-optimal manner. This approach is based on generating a minimum-spanning tree (MST) from the complete pin-to-pin graph of each net with each edge cost based on a combination of its contribution to the net length, channel congestion and potential average bumping cost in the channels in which the edge lies. Using the MST, a hop-based routing of each net is performed that attempts to minimize the combination of net length, number of hops and total number of tracks needed in the FPGA. Given each net's global route, a FPGA detailed router can minimize net delays by minimizing the number of hops or equivalently the number of track switchings in complex switchboxes of current FPGAs---hop-based routing can model routing using complex switchboxes. By minimizing the number of hops and total net length, ROAD-HOP minimizes net delay. Note that ROAD-HOP can only be compared to another detailed router and we compare it to the best previous detailed router SEGA for the VPR architecture. We use the output of the VPR global router as input to both ROAD-HOP and SEGA. Our new algorithm achieves significantly better results than SEGA with respect to the number of tracks needed and the circuit speed. Across a number of benchmark circuits, our algorithm needs about 8% fewer tracks than SEGA. Furthermore, the average net delay of the routing generated by our algorithm is 34% less than that of SEGA, and is 52% less for the longest net.

In the engineering change order (ECO) process, engineers make changes to VLSI circuits after their layouts are completed in order to correct electrical problems or design errors. As far as routing is concerned, in order to capitalize on the enormous resources and time already spent on routing the circuit, and to meet time-to-market requirements, it is desirable to re-route only the ECO-affected portion of the circuit, while minimizing any routing changes in the larger unaffected part of the circuit in order to preserve its electrical properties. In this paper, we develop a novel algorithm to find incremental routing solutions using a gridless framework for VLSI circuits that require variable width and variable spacing on interconnects. The basic idea in our algorithm is to route the new or ECO-modified nets by minimally re-arranging, if necessary, some portions of some existing nets using a novel DFS controlled process that does not allow the perturbed existing nets' lengths and topologies to change beyond pre-set limits. With these constraints, it explores a number of low-cost ways of re-routing the portions of these nets within the available routing resources (2 metal layers only). Experimental results show that within the above constraints our incremental router succeeds in routing more than 98% of ECO-generated nets, and also that its failure rate is 5 to 12 and 2.4 to 9 times less than that of previous incremental routing techniques standard (Std) and Rip-up&Reroute (R&R), respectively. It is also able to route most of the wide nets using a reasonable number of vias and with near-minimal net lengths.

It is well known that the solution quality of the detailed routing phase is heavily influenced by the order in which nets are routed. To alleviate this situation a number of routing strategies have been developed that ripup and reroute (R&R) previously-routed nets that "block" the current net. In the R&R approach, there is not a significant amount of control over the solution quality (e.g., length, delay) for the ripped-up nets. We propose a detailed router ROAD (bump&Refit based Optimal Detailed router) that explores the solution space using an approach called bump-and-refit (B&R) in which the global routes of prior-routed nets are not changed but their track assignments are systematically altered in order to make space for the current net being routed. B&R thus does not have the above drawback of R&R. We start with an initial depth-first search method for this purpose that is optimal in finding a detailed routing solution with the minimum number of tracks irrespective of the net routing order. We then develop various optimality-preserving speedup methods including search space pruning based on clique detection and learning about and remembering unsuccessful search spaces, and second-level or lookahead transition costs. The combination of these methods results in an average speedup of 604 for small to medium VPR circuits and an extrapolated speedup of more than 5763 for larger circuits. Furthermore, comparison of ROAD run times to that of VPR's estimated detailed routing phase show that we are almost two times faster than VPR. This is noteworthy because an optimal detailed router is able to obtain solutions in reasonable times which are also faster than those of a nonoptimal (though effective) router.

This paper addresses the problem of tackling multiple constraints simultaneously during a partitioning driven placement (PDP) process, where a larger solution space is available for constraint-satisfying optimization compared to post placement methods. A general methodology of multi-constraint satisfaction that balances violation correction and primary optimization is presented. A number of techniques are introduced to ensure its convergence and enhance its solution search capability with intermediate relaxation. Application of our approach to congestion control modeled as pin density and external net distribution balance constraints shows it effectively reduces overall congestion by 14.3% and improves chip area by 8.9%, with reasonable running time and only 1.6% increase in wire length. As far as we know, this is the first time an approach to congestion reduction during placement optimization produced good congestion improvement with very small wire length increase.

Move-based iterative improvement partitioning (IIP) methods, such as the Fiduccia-Mattheyses (FM) algorithm [Fidducia and Mattheyses 1982] and Krishnamurthy's Look-Ahead (LA) algorithm [Krishnamurthy 1984], are widely used in VLSI CAD applications, largely due to their time efficiency and ease of implementation. This class of algorithms is of the "local/greedy improvement" type, and they generate relatively high-quality results for small and medium-size circuits. However, as VLSI circuits become larger, these algorithms suffer a rapid deterioration in solution quality. We propose new IIP methods CLIP and CDIP that select cells to move with a view to moving clusters that straddle the two subsets of a partition, into one of the subsets. The new algorithms significantly improve partition quality while preserving the advantage of time efficiency. Experimental results on 25 medium to large-size ACM/SIGDA benchmark circuits show up to 70% improvement over FM in mincut, and average mincut improvements of about 35% over all circuits and 47% over large circuits. They also outperform state-of-the-art non-IIP techniques, the quadratic-programming-based method Paraboli [Reiss et al. 1994] and the spectral partitioner MELO [Alpert and Yao 1995], by about 17% and 23%, respectively, with less CPU time. This demonstrates the potential of sophisticated IIP algorithms in dealing with the increasing complexity of emerging VLSI circuits. We also compare CLIP and CDIP to hMetis [Karypis et al. 1997], one of the best of the recent state-of-the-art partitioners that are based on the multilevel paradigm (others include ML c [Alpert et al. 1997] and LSR/MFFS [Cong et al. 1997]). The results show that one scheme of hMetis is 8% worse than CLIP/CDIP and the other two schemes are only 2--4% better. However, CLIP/CDIP have advantages over hMetis and other multilevel partitioners that outweigh these minimal mincut improvements. The first is much faster times-to-solution (for example, one of our best schemes CLIP-LA2 is 6.4 and 11.75 times faster than the two best hMetis schemes) and much better scalability with circuit size (e.g., for the largest circuit with about 162K nodes, CLIP-LA2 is 10.4 and and 21.5 times faster and obtains better solution qualities than the two best hMetis schemes). Second, CLIP/CDIP are "flat" partitioners, while multilevel techniques perform a sequence of node clustering/coarsening before partitioning the circuit. In complex placement applications such as timing-driven placement in the presence of multiple constraints, such circuit coarsening can hide crucial information needed for good-quality solutions, thus making the partitioning process oblivious to them. This, however, is not a problem with flat partitioners like CLIP/CDIP that can take all important parameters into account while partitioning. All these advantages make CLIP/CDIP suitable for use in complex physical design problems for large, deep-submicron VLSI circuits.

Incremental physical CAD is encountered frequently in the so-called engineering change order (ECO) process in which design changes are made typically late in the design process in order to correct logical and/or technological problems in the circuit. Incremental routing is a significant part of an incremental physical design methodology. Typically after an ECO process, a small portion of the circuit netlist is changed, and in order to capitalize on the enormous resources and time already spent on routing the circuit it is desirable to reroute only the ECO-affected portion of the circuit, while minimizing any routing changes in the much larger unaffected part. Incremental rerouting also needs to be fast and to effectively use available routing resources. In this article, we develop a complete incremental routing methodology for FPGAs using a novel approach called bump and refit (B&R). The basic B&R idea (which was originally proposed in Dutt et al. [1999] in the much simpler context of extending some nets by a segment for the purpose of fault tolerance) in our algorithms is to rearrange some portions of some existing nets on other tracks within their current channels in order to find valid routings for the new/modified nets without requiring any extra routing resources and with little effect on the electrical properties of existing nets. Here we significantly extend the B&R concept to global and detailed incremental routing for FPGAs with complex switchboxes (SBox's) such as those in Lucent's ORCA and Xilinx's Virtex series. We introduce new concepts such as a B&R cost in global routing and the optimal subnet set to relocate for each bumped net (determined using an efficient dynamic programming formulation). We developed optimal and near-optimal algorithms (called Subsec_B&R and Subnet_B&R, respectively) to find incremental routing solutions using the B&R paradigm in complex FPGAs (e.g., Lucent's ORCA FPGA) with i-to-j SBox's, as well as an optimal version Fullnet_B&R for the VPR architecture from the University of Toronto using the simpler i-to-i SBox's. We compared our algorithms (simply called B&R when no distinction needs to be made between our versions) to two recent incremental routing techniques, Standard (Std) and Rip-up&Reroute (R&R), and to Lucent's A_PAR routing tool and the University of Toronto's VPR router used in complete rerouting modes. Experimental results for the ORCA show that B&R is 10 to 20 times faster than complete rerouting using A_PAR, and that B&R is also nearly 27% faster and yields new nets with nearly 10% smaller lengths compared to previous incremental routers. Furthermore, B&R routers do not change either the lengths or topologies of existing nets, a significant advantage in ECO applications, in contrast to R&R which increases the length of ripped-up nets by an average of 8.75 to 13.6%. Experimental results for the VPR architecture are dominated by the significantly larger (in many cases, orders of magnitude more) number of nets left unrouted by Std and R&R compared to B&R, which highlights the much greater efficacy of B&R-based incremental routing. However, B&R is significantly slower than the other two incremental routers, although on an absolute scale it is quite fast for two of four cases we simulated; in one case, it is about 25 times faster than VPR used in the full rerouting mode. The relative slowness of B&R for the VPR architecture arises from the fact that we used i-to-i SBox's which forces each net to be routed on the same track, thus causing significantly more bumpings and searches for rearranged solutions compared to i-to-j SBox's where a net can be routed on different interconnected tracks to minimize the amount of bumpings (as we did for the ORCA). Since modern FPGAs generally have the latter type of SBox's, B&R would be fast as well as very effective on them.

Incremental physical CAD is encountered frequently in the so-called engineering change order (ECO) process in which design changes are made typically late in the design process in order to correct logical and/or technological problems in the circuit. As far as routing is concerned, in order to capitalize on the enormous resources and time already spent on routing the circuit, and to meet time-to-market requirements, it is desirable to re-route only the ECO-affected portion of the circuit, while minimizing any routing changes in the much larger unaffected part of the circuit. Incremental re-routing also needs to be fast and to effectively use available routing resources. We develop a complete incremental routing methodology for FPGAs using a novel approach called bump and refit (B&R). We significantly extend this concept to global and detailed incremental routing for FPGAs with complex switchboxes such as those in Lucent's ORCA and Minx's Virtex series. We also introduce new concepts such as B&R cost estimation during global routing, and determination of the optimal subnet set to bump for each bumped net, which we obtain using an efficient dynamic programming formulation.

In this paper we take a fresh look at the partition-driven placement (PDP) paradigm for standard-cell placement for wire-length minimization. The goal is to develop several new algorithms for incorporation into a PDP framework that can rectify the well-known drawbacks of traditional PDP (increasingly localized view of nets with increasing levels of the partitioning tree, min cut objective, inaccuracy and cost of terminal propagation (TP), irreversibility of move decisions), while preserving its considerable advantages (time efficiency, flexibility in accurately incorporating many optimization metrics, and flexibility in satisfying most constraints). We have developed several novel techniques within a PDP-based framework that yield the best wire-length results so far on all but two of the MONO benchmark suite. Our major innovations are: (1) simultaneous level partitioning (SLP) in which we partition the entire circuit globally in every level of the partitioning tree, across the current cutline(s); (2) cell gain computation based on a global or distributed view of entire nets (thus obviating TP) and on the bounding-box (BB) minimization of nets (as opposed to mincut in prior PDP); (3) move irreversibility tackled in a pest-processing phase via vertical and horizontal swaps. Empirical results indicate that our PDP algorithm SPADE (for Simultaneous level Partitioning with Distributed lie., global] nEt views) provides almost 202 better wirelength results than an internal version of "regular" PDP with min-cut based gains, 10.8% better than the previous best PDP method QUAD, 10.6% better than TimberWolf (TW) 7.0, 15.846 better than the state-of-the-art force-directed technique from U. Munich (termed FD-98 here), and 15.3% better than the multilevel placement technique Snap-On. Besides TW7.0, we are also the only ones to report results on the approximately 100 K-cell circuit golem3 (12.2% better than TW7.0). Our run times are quite reasonable.

Iterative-improvement two-way min-cut partitioning is an important phase in most circuit placement tools, and finds use in many other computer-aided design (CAD) applications. Most iterative improvement techniques for circuit netlists like the Fiduccia-Mattheyses (FM) method compute the gains of nodes using local netlist information that is only concerned with the immediate improvement in the cutset. This can lead to misleading gain information. Krishnamurthy suggested a lookahead (LA) gain calculation method to ameliorate this situation; however, as we show, it leaves room for improvement. We present here a probabilistic gain computation approach called probabilistic partitioner (PROP) that is capable of capturing the future implications of moving a node at the current time. We also propose an extended algorithm SHRINK-PROP that increases the probability of removing recently "perturbed" nets (nets whose nodes have been moved for the first time) from the cutset. Experimental results on medium- to large-size ACM/SIGDA benchmark circuits show that PROP and SHRINK-PROP outperform previous iterative-improvement methods like FM (by about 30% and 37%, respectively) and LA (by about 27% and 34%, respectively). Both PROP and SHRINK-PROP also obtain much better cutsizes than many recent state-of-the-art partitioners like EIG1, WINDOW, MELO, PARABOLI, GFM and GMetis (by 4.5% to 67%), Our empirical timing results reveal that PROP is appreciably faster than most recent techniques. We also obtain results on the more recent ISPD-98 benchmark suite that show similar substantial mincut improvements by PROP and SHRINK-PROP over FM (24% and 31%, respectively). It is also noteworthy that SHRINK-PROP'S results are within 2.5% of those obtained by hMetis, one of the best multilevel partitioners. However, the multilevel paradigm is orthogonal to SHRINK-PROP. Further, since it is a "flat" partitioner, it has advantages over hMetis in partition-driven placement applications.

The ability to reconfigure around manufacturing defects and operational faults increases FPGA chip yield, reduces system downtime and maintenance in field operation, and increases reliabilities of mission- and life-critical systems. The fault reconfiguration technique discussed in this work uses the principle of node covering in which reconfiguration is achieved by constructing replacement chains of cells from faulty cells to spare/unused ones. A key issue in such reconfiguration is efficient incremental rerouting in the FPGA. Previous methods for node-covering based reconfiguration are "static" in the sense that extra interconnects are added a-priori as part of the initial circuit routing so that a specific fault pattern (e.g. one fault per row) can be tolerated. This, however, results in worst-case track overheads and also in an inflexibility to tolerate other realistic fault patterns. We develop dynamic reconfiguration and incremental rerouting techniques that are fault specific. In this approach, the FPGA is initially routed without any extra interconnects for reconfiguration. When faults occur the routed nets have to be minimally perturbed to allow these interconnects to be inserted "on-the-fly" for reconfiguration. These requirements are addressed in our minimally incremental rerouting technique Conv-T-DAG, which uses a cost-directed depth-first search strategy. We prove several results that establishes the near-optimality of Conv-T-DAG in terms of track overhead. To the best of our knowledge this is the first time that an incremental rerouting technique has been developed for FPGAs. For several benchmark circuits, the static approach to tolerating one fault per row resulted in a 43% to 34% track overhead. Using the dynamic reconfiguration approach and Conv-T-DAG results in an average overhead of only 16%-an improvement of more than 50%. Over all circuits, the reconfiguration time per fault ranges from 16.8 to 72.9 secs. Simulation of smaller fault sets of one to four faults show very small track overheads ranging from 1.75% to 4.49%. Conv-T-DAG can also be used for interconnect fault tolerance.

A probability-based partitioning algorithm, PROP, was introduced in [8] that achieved large improvements over traditional "deterministic" iterative-improvement techniques like Fidducia-Mattheyses (FM) and Krishnamurthy's look-ahead (LA) algorithm. While PROP's gain function has a greater futuristic component than PM or LA, it incorporates spatially local information-only information on the removal probabilities of adjacent nets of a cell is used in its gain computation. This prevents a higher-level view of nonlocal structures. Also, giving uniform weights to all nets, results in an inability to differentiate between the futuristic benefit of removing one net from another. This paper investigates for the first time the issues of using nonlocal structural information in gain functions and variable net weights based on the futuristic (stochastic) benefit of moving them from the cutset. The result is a more sophisticated partitioner DEEP-PROP that performs better for circuits with large complexities by incorporating more nonlocal (second order) structural information than PROP. The second-order information is incorporated into cell gains as well as variable net weights-the latter helps to focus future cell moves in the "right" cluster around the currently moved cell and, thus, better utilizes the information that led to its selection as the best move. A lower complexity version, variable weight PROP (VAR-PROP), that also uses dynamically assigned variable net weights, but based on first-order information, has also been developed. Both versions yield significant improvements over PROP on the ACM/SIGDA benchmark suite. DEEP-PROP yields mincut improvements of as much as 39% and an average of 20% for large circuits (10-K to 25-K cells) and an average of 14% over all circuits. DEEP PROP is about a factor of 2.8 times slower than PROP, which is very fast. VAR-PROP, which has a much lower computational complexity than DEEP-PROP, yields for large circuits, maximum and average mincut improvements over PROP of 27% and 18%, respectively, and an average of 12.6% improvement over all circuits. It is only about 14% slower than PROP, For the only very large circuit golem3 in the suite (>100 K cells), the improvements produced by DEEP-PROP and VAR-PROP over PROP are 15.6% and 11.5%, respectively. We also compare DEEP-PROP to FM, PROP and hMetis for a subset of the newer 1SPD98 benchmark circuits, and demonstrate significant improvements over FM and PROP, and comparable mincuts (within 2%) to hMetis, one of the best multilevel partitioners.

A probability-based partitioning algorithm, PROP, was introduced in [5] that achieved large improvements over traditional "deterministic" iterative-improvement techniques like FM [7] and LA [10]. While PROP's gain function has a greater futuristic component than FM or LA, it incorporates spatially local information---only information on the removal probabilities of adjacent nets of a cell is used in its gain computation. This prevents a higher-level view of non-local structures. Also, giving uniform weights to all nets, results in an inability to differentiate between the futuristic benefit of removing one net from another. In this paper, we present a more sophisticated partitioner DEEP-PROP that incorporates more non-local (second-order) structural information than PROP. The second-order information is incorporated into cell gains as well as variable net weights---the latter helps to focus future cell moves in a cluster around the currently moved cell and thus better utilizes the info...

The very high levels of integration and submicron device sizes used in current and emerging VLSI technologies for FPGAs lead to higher occurrences of defects and operational faults. Thus, there is a critical need for fault tolerance and reconfiguration techniques for FPGAs to increase chip yields (with factory reconfiguration) and/or system reliability (with field reconfiguration). We first propose techniques utilizing the principle of node-covering to tolerate logic or cell faults in SRAM-based FPGAs. A routing discipline is developed that allows each cell to cover-to be able to replace-its neighbor in a row. Techniques are also proposed for tolerating wiring faults by means of replacement with spare portions. The replaceable portions can be individual segments, or else sets of segments, called "grids". Fault detection in the FPGAs is accomplished by separate testing, either at the factory or by the user. If reconfiguration around faulty cells and wiring is performed at the factory (with laser-burned fuses, for example), it is completely transparent to the user. In other words, user configuration data loaded into the SRAM remains the same, independent of whether the chip is detect-free or whether it has been reconfigured around defective cells or wiring-a major advantage for hardware vendors who design and sell FPGA-based logic (e.g., glue logic in microcontrollers, video cards, DSP cards) in production-scale quantities. Compared to other techniques for fault tolerance in FPGAs, our methods are shown to provide significantly greater yield improvement, and a 35 percent non-FT chip yield for a 16/spl times/16 FPGA is more than doubled.

Constraint satisfaction during partitioning and placement of VLSI circuits is an important problem, and effective techniques to address it lead to high-quality physical design solutions. This problem has, however been cursorily treated in previous partitioning and placement research. Our work presented here addresses the balance-ratio constraint, and is a crucial first step to an effective solution to the general constraint-satisfaction problem. In current iterative-improvement mincut partitioners, the balance-ratio constraint is tackled by disallowing moves that violate it. These methods can lead to sub-optimal solutions since the process is biased against the movement of large cells and clusters of cells. We present techniques for an informed relaxation process that attempts to estimate whether relaxing the constraint temporarily will ultimately benefit the mincut objective. If so, then a violating move is allowed, otherwise it is disallowed. The violations are corrected in future moves so that the final solution satisfies the given constraint On a set of ACU/SIGDA PROUD benchmark circuits with actual cell sizes, we obtained up to 38% and an average of 14.5% better cutsizes with as little as 13% time overhead using our techniques compared to the standard method of not allowing any relaxation.

Structural fault tolerance (SFT) is the ability of a multiprocessor to reconfigure around faulty processors or links in order to preserve its original processor interconnection structure; In this paper, we focus on the design of SFT multiprocessors that have low switch and link overheads, but can tolerate a very large number of processor faults on the average. Most previous work has concentrated on deterministic k-fault-tolerant (k-FT) designs in which exactly k spare processors and some spare switches and links are added to construct multiprocessors that can tolerate any k processor faults. However, after k faults are reconfigured around, much of the extra links and switches can remain unutilized. It is possible within the basic node-covering framework, which was introduced by Dutt and Hayes as an efficient k-FT design method, to design FT multiprocessors that have the same amount of switches and links as, say, a two-FT deterministic design, but have s spare processors, where s/spl Gt/2, so that, on the average, k=/spl Theta/(s) (k/spl les/s) processor failures can be reconfigured around. Such designs utilize the spare link and switch capacity very efficiently, and are called probabilistic FT designs. An elegant and powerful method to construct covering graphs or CG's, which are key to obtaining the probabilistic FT designs, is to use linear error-correcting codes (ECCs). We show how to construct probabilistic designs with very high average fault tolerance but low wiring and switch overhead using ECCs like the 2D-parity, full-two, 3D-parity, and full-three codes.

For many applications of the A* algorithm, the state space is a graph rather than a tree. The implication of this for parallel A* algorithms is that different processors may perform significant duplicated work if interprocessor duplicates are not pruned. In this paper, we consider the problem of duplicate pruning in parallel A* graph-search algorithms implemented on distributed-memory machines. A commonly used method for duplicate pruning uses a hash function to associate with each distinct node of the search space a particular processor to which duplicate nodes arising in different processors are transmitted and thereby pruned. This approach has two major drawbacks. First, load balance is determined solely by the hash function. Second, node transmissions for duplicate pruning are global; this can lead to hot spots and slower message delivery. To overcome these problems, we propose two different duplicate pruning strategies: 1) To achieve good load balance, we decouple the task of duplicate pruning from load balancing, by using a hash function for the former and a load balancing scheme for the latter. 2) A novel search-space partitioning scheme that allocates disjoint parts of the search space to disjoint subcubes in a hypercube (or disjoint processor groups in the target architecture), so that duplicate pruning is achieved with only intrasubcube or adjacent intersubcube communication. Thus message latency and hot-spot probability are greatly reduced. The above duplicate pruning schemes were implemented on an nCUBE2 hypercube multicomputer to solve the Traveling Salesman Problem (TSP). For uniformly distributed intercity costs, our strategies yield a speedup improvement of 13 to 35 percent on 1,024-processors over previous methods that do not prune any duplicates, and 13 to 25 percent over the previous hashing-only scheme. For normally distributed data the corresponding figures are 135 percent and 10 to 155 percent. Finally, we analyze the scalability of our parallel A* algorithms on k-ary n-cube networks in terms of the isoefficiency metric, and show that they have isoefficiency lower and upper bounds of /spl Theta/(P log P) and /spl Theta/(Pkn/sup 2/), respectively.

REMOD (REprocessing with MicrO Delays) is a new method for fault-tolerant design of logic circuits composed of arrays of identical functional cells. The fault detection scheme is based on the principle of node covering, in which the computation of each cell is checked by a "covering" cell. After a faulty cell is detected, the node covering principle also allows the circuit to easily be reconfigured to perform correctly for subsequent inputs. Furthermore, the design method is extendable to multiple fault tolerance with only small increments of hardware and time. We have laid out and simulated REMOD-based circuits for adders and multipliers and show that the time overheads are a small factor of the original computation time-0 or /spl Theta/(1/n) to /spl Theta/(1/(log n)), for an n-cell circuit. For moderately complex cells, it is seen that area overhead is very reasonable as well.

Iterative-improvement 2-way min-cut partitioning is an important phase in most circuit partitioning tools. Most iterative improvement techniques for circuit netlists like the Fidducia-Mattheyses (FM) method compute the gains of nodes using local netlist information that is only concerned with the immediate improvement in the cutset. This can lead to misleading gain calculations. Krishnamurthy suggested a lookahead (LA) gain calculation method to ameliorate this situation; however, as we show, it leaves considerable room for improvement. We present here a probabilistic gain computation approach called PROP 1 that is capable of capturing the global and future implications of moving a node at the current time. Experimental results show that for the same number of runs, PROP performs much better than FM (by about 30%) and LA (by about 27%), and is also better than many recent state-of-the-art clusteringbased partitioners like EIG1, WINDOW, MELO and PARABOLI by 15% to 57%. We also show th...

Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm and Krishnamurthy's Look-Ahead (LA) algorithm are widely used in VLSI CAD applications largely due to their time efficiency and ease of implementation. This class of algorithms is of the "local improvement" type. They generate relatively high quality results for small and medium size circuits. However, as VLSI circuits become larger, these algorithms are not so effective on them as direct partitioning tools. We propose new iterative-improvement methods that select cells to move with a view to moving clusters that straddle the two subsets of a partition into one of the subsets. The new algorithms significantly improve partition quality while preserving the advantage of time efficiency. Experimental results on 25 medium to large size ACM/SIGDA benchmark circuits show up to 70% improvement over FM in cutsize, with an average of per-circuit percent improvements of about 25%, and a total cut improvement of about 35%. They also outperform the recent placement-based partitioning tool Paraboli and the spectral partitioner MELO by about 17% and 23%, respectively, with less CPU time. This demonstrates the potential of iterative improvement algorithms in dealing with the increasing complexity of modern VLSI circuitry.

Significant increases in chip yield can result if faulty logic cells and wiring in field programmable gate arrays (FPGAs) can be isolated from the remainder of the circuitry to retain a completely usable chip. Utilizing the principle of node-covering, a routing discipline has been developed that allows each logic cell in an FPGA to cover-to be able to replace-its neighbor in a row. An FPGA is factory-reconfigured such that a faulty cell is replaced by its cover, which in turn is replaced by its own cover, and so on until a spare cell in the row is reached. Since wiring channel area is a major portion of chip area in an FPGA, new techniques are also proposed for tolerating wiring faults. As with faulty logic cells, faulty wiring portions are replaced by adjacent ones, until eventually a spare wiring portion is reached. Compared to other techniques for fault tolerance in FPGAs, these methods are shown to provide significantly greater yield improvement.

Previous work analyzing k-my n-cubes with constant bisecrian-width und constant node-degree constraints have shown that generally lowerdtmenslon and middle-dimen.~ioncubes, respectively, have the best performance in terms of message [atencles under cantentimr, These analyses were done u.wummg a randam dtstrvbutian of 'me.wage traffic with same k)caliz,afion probabdiry, and da not necessarily capture the actual comrnunicatian patterns of many well-designed parallel application.v.In this work, we analyze.' theoretically and empirically, the perjimmance of k -ary n-cubes ,for the class of diwde-and-conquer (D&C) parallel algorithms that are u.fedfor solvarg many numerical and non-numerical computations.We cla.wi~D&C parallel algorithms accarding w their camrnunication patterns, and campare the perj%rrnance of three different classes qfthese alganthms on k-ary n-cubes In agreement with previous work, our results show that under the constant bmecrion-width constraint, the 2-D mesh perjarms best, the hypercube has the lowest perfarntance, and m general a lower dimension M better than a Iagher one, Howeve~unhke prewarrs results ,for the more reahstm constant node-degree constraint (pin limitations on proce.worlrouterchips quickly become the overriding constraint as system size increases) that show that middle-dimenswna[ cubes have the lowest latencies, we show that the hypercube has the best perjorrnance, the 2-D mesh the warst, and generally that a }ugher dlmen.non IS better than a lower one,

A system-level method for achieving fault tolerance called algorithm-based fault tolerance (ABFT) has been proposed by a number of researchers. Many ABFT schemes use a floating-point checksum test to detect computation errors resulting from hardware faults. This makes the tests susceptible to roundoff inaccuracies in floating-point operations, which either cause false alarms or lead to undetected errors. Thresholding of the equality test has been commonly used to avoid false alarms; however, a good threshold that minimizes false alarms without reducing the error coverage significantly is difficult to find, especially when not much is known about the input data. Furthermore, thresholded checksums will inevitably miss lower-bit errors, which can get magnified as a computation such as LU decomposition progresses. We develop a theory for applying integer mantissa checksum tests to "mantissa-preserving" floating-point computations. This test is not susceptible to roundoff problems and yields 100% error coverage without false alarms. For computations that are not fully mantissa-preserving, we show how to apply the mantissa checksum test to the mantissa-preserving components of the computation and the floating-point test to the rest of the computation. We apply this general methodology to matrix-matrix multiplication and LU decomposition (using the Gaussian elimination (GE) algorithm), and find that the accuracy of this new "hybrid" testing scheme is substantially higher than the floating-point test with thresholding.

In this paper we present a very efficient graph partitioning scheme QuickCut that uses the basic strategy of the Kernighan-Lin (K-L) algorithm to swap pairs of nodes to improve an existing partition of a graph G. The main feature of QuickCut is a "neighborhood search" strategy that is based on the result (obtained in this paper) that it is not necessary to search more than a certain subset of d/sup 2/ node pairs to find the node pair with the maximum swap gain. Here d is the maximum node degree of G. We also use an improved data structure, viz., balanced trees, to store the nodes in the two partitions. Due to the new search strategy and data structure, QuickCut has a worst-case time complexity of /spl Theta/(max(ed, e log n)), and an average-case complexity of /spl Theta/(e log n), where e is the number of edges of G. The K-L algorithm, on the other hand, has a time complexity of /spl Theta/(n/sup 2/ log n), where n is the number of nodes of G. Another contribution of this paper is the presentation of efficient node-pair scanning methods for obtaining the best node pair to swap in the K-L algorithm. We have implemented QuickCut, K-L, and its various enhancements suggested here. The results obtained from using these different algorithms to partition a number of random and other well-defined graphs show that QuickCut is the fastest, and that it is faster than the K-L algorithm by factors of 5 to 50. Thus QuickCut can serve as the basis for very fast VLSI partitioning and layout tools.

Methods for modeling and implementing various practical aspects of fault-tolerant multiprocessor systems largely neglected in prior research are examined. The node-covering design approach is generalized to accommodate systems whose structure and failure mechanisms are represented by arbitrary graphs. Several new types of covering graphs are defined, which lead to various useful design tradeoffs. A new technique for incremental design is presented, using a class of switch implementations that reduce a system's interconnection costs. The reduction of other cost factors is also addressed, and methods are presented for VLSI layout area minimization, fast and distributed reconfiguration, efficient transfer of state information for software recovery, and the efficient use of local spares.>

A precise characterization of the subcube allocation problem and a general methodology to solve it are presented. Subcube allocation and coalescing algorithms that have the goal of minimizing fragmentation are developed. The concept of a maximal set of subcubes (MSS), which is useful in making allocations that result in a tightly packed hypercube, is introduced. The problems of allocating subcubes and of forming an MSS are formulated as decision problems and shown to be NP-hard. It is proved analytically that the buddy strategy is optimal under restricted conditions, and it is shown using simulation that its performance is actually poor under more realistic conditions. A heuristic procedure for efficiently coalescing a released cube with the existing free cubes is suggested. This coalescing approach is coupled with a simple best-fit allocation scheme to form the basis of a class of MSS-based strategies that give a substantial performance (hit ratio) improvement over the buddy strategy. Simulation results comparing several different allocation and coalescing strategies, which show that the MSS-based schemes provide a marked performance improvement over previous techniques, are presented.>

A general approach to designing tree structured multiprocessors with optimal or near-optimal fault tolerance properties is developed. A multiprocessor architecture with a static interconnection network is represented by a graph whose nodes are processors and whose edges are interprocessor communication links. The design of k-fault-tolerant (FT) trees for arbitrary k is considered, with the primary goal of minimizing the number of spare nodes and edges. Also presented are strategies for reconfiguring a k-FT supergraph of a tree T around faults to obtain a fault-free tree isomorphic to T. A systematic methodology is presented for designing k-FT nonhomogeneous symmetry d-ary trees based on a concept termed node covering. The designs are shown to be optimal when k>