Search

We present a machine learning (ML) framework to improve the use of computing resources in the FPGA compilation step of a commercial FPGA-based logic emulation flow. Our ML models enable highly accurate predictability of the final place and route design qualities, runtime, and optimal mapping parameters. We identify key compilation features that may require aggressive compilation efforts using our ML models. Experiments based on our large-scale database from an industry’s emulation system show that our ML models help reduce the total number of jobs required for a given netlist by 33%. Moreover, our job scheduling algorithm based on our ML model reduces the overall time to completion of concurrent compilation runs by 24%. In addition, we propose a new method to compute “recommendations” from our ML model to perform re-partitioning of difficult partitions. Tested on a large-scale industry system on chip design, our recommendation flow provides additional 15% compile time savings for the entire system on chip. To exploit our ML model inside the time-critical multi-FPGA partitioning step, we implement it in an optimized multi-threaded representation.

Contemporary integrated circuits (ICs) are increasingly being constructed using intellectual property blocks (IPs) obtained from third parties in a globalized supply chain. The increased vulnerability to adversarial changes during this untrusted supply chain raises concerns about the integrity of the end product. The difference in the levels of abstraction between the initial specification and the final available circuit design poses a challenge for analyzing the final circuit for malicious insertions. Reverse engineering presents one way to help reduce the difficulty of circuit analysis and inspection. In this work, we provide a framework that given (i) a gate-level netlist of a design and (ii) a block diagram for the design with relative sizes of the blocks, outputs a matching between the partitions of the circuit and blocks in the block diagram. We first compute a geometric embedding for each node in the circuit and then apply a clustering algorithm on the embedding features to obtain circuit partitions. Each partition is then mapped to the high-level blocks in the block diagram. These partitions can then be further analyzed for malicious insertions with much reduced complexity in comparison with the full chip. We tested our algorithm on different designs with varying sizes to evaluate the efficacy of algorithm, including the open-source processor OpenSparc T1, and showed that we can successfully match over 90% of gates to their corresponding blocks.

Outsourcing of design and manufacturing processes makes integrated circuits (ICs) vulnerable to adversarial changes and raises concerns about their integrity. Reverse engineering the manufactured netlist helps identify malicious insertions. In this article, we present an automated approach that, given a reference design description with high-level blocks, infers these blocks in an untrusted gate-level (test) implementation. Using the graph connectivity of the netlists, we compute a geometric embedding for each wire in the circuits, which, then, is used to compute a bipartite matching between the nodes of the two designs and identify high-level blocks in the test circuit. Experiments to evaluate the efficacy of the proposed technique on various-sized designs, including the multi-core processor OpenSparc T1, show that it can correctly match over 90% of gates in the test circuit to their corresponding block in the reference model.

With the advent of globalization in the semiconductor industry, it is necessary to prevent unauthorized usage of third-party IPs (3PIPs), cloning and unwanted modification of 3PIPs, and unauthorized production of ICs. Due to the increasing complexity of ICs, system-on-chip (SoC) designers use various 3PIPs in their design to reduce time-to-market and development costs, which creates a trust issue between the SoC designer and the IP owners. In addition, as the ICs are fabricated around the globe, the SoC designers give fabrication contracts to offshore foundries to manufacture ICs and have little control over the fabrication process, including the total number of chips fabricated. Similarly, the 3PIP owners lack control over the number of fabricated chips and/or the usage of their IPs in an SoC. Existing research only partially addresses the problems of IP piracy and IC overproduction, and to the best of our knowledge, there is no work that considers IP overuse. In this article, we present a comprehensive solution for preventing IP piracy and IC overproduction by assuring forward trust between all entities involved in the SoC design and fabrication process. We propose a novel design flow to prevent IC overproduction and IP overuse. We use an existing logic encryption technique to obfuscate the netlist of an SoC or a 3PIP and propose a modification to enable manufacturing tests before the activation of chips which is absolutely necessary to prevent overproduction. We have used asymmetric and symmetric key encryption, in a fashion similar to Pretty Good Privacy (PGP), to transfer keys from the SoC designer or 3PIP owners to the chips. In addition, we also propose to attach an IP digest (a cryptographic hash of the entire IP) to the header of an IP to prevent modification of the IP by the SoC designers. We have shown that our approach is resistant to various attacks with the cost of minimal area overhead.

In this article we propose an effective algorithm flow to handle modern large-scale mixed-size placement, both with and without geometry constraints. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow consists of four steps: (1) The objects in the original netlist are clustered into blocks; (2) floorplanning is performed on the blocks; (3) the blocks are shifted within the chip region to further optimize the wirelength; (4) with large macro-locations fixed, incremental placement is applied to place the remaining objects. There are several advantages to handling placement at the global level with a floorplanning technique. First, the problem size can be significantly reduced. Second, exact Half-Perimeter WireLength (HPWL) can be minimized. Third, better object distribution can be achieved so that legalization only needs to handle minor overlaps among small objects in a block. Fourth, macro-rotation and various geometry constraints can be handled. To demonstrate the effectiveness of this new flow, we implement a high-quality and efficient floorplan-guided placer called FLOP . We also construct the Modern Mixed-Size (MMS) placement benchmarks that can effectively represent the complexities of modern mixed-size designs and the challenges faced by modern mixed-size placers. Compared with most state-of-the-art mixed-size placers and leading macroplacers, experimental results show that FLOP achieves the best HPWL and easily obtains legal solutions on all circuits with all geometry constraints satisfied.

Power analysis tools are an integral component of any current power sign-off methodology. The performance of a design's power grid affects the timing and functionality of a circuit, directly impacting the overall performance. Ensuring power grid robustness implies taking into account, among others, static and dynamic effects of voltage drop, ground bounce, and electromigration. This type of verification is usually done by simulation, targeting a worst-case scenario where devices, switching almost simultaneously, could impose stern current demands on the power grid. While determination of the exact worst-case switching conditions from the grid perspective is usually not practical, the choice of simulation stimuli has a critical effect on the results of the analysis. Targetting safe but unrealistic settings could lead to pessimistic results and costly overdesigns in terms of die area. In this article we describe a software tool that generates a reasonable, realistic, set of stimuli for simulation. The approach proposed accounts for timing and spatial restrictions that arise from the circuit's netlist and placement and generates an approximation to the worst-case condition. The resulting stimuli indicate that only a fraction of the gates change in any given timing window, leading to a more robust verification methodology, especially in the dynamic case. Generating such stimuli is akin to performing a standard static timing analysis, so the tool fits well within conventional design frameworks. Furthermore, the tool can be used for hotspot detection in early design stages.

Recent advanced power optimizations deployed in commercial FPGAs, laid out a roadmap towards FPGA devices that can be integrated into ultra low power systems. In this article, we present a high-level design tool to support the process of mapping an application onto a FPGA device with dual supply voltages. Our main contribution in this paper is an algorithm, which creates voltage scaling ready clusters by utilizing the timing slack available in the designs. We propose to first create clusters of CLBs within a given CLB-level netlist. This clustering algorithm intends to group chains of CLBs possessing similar amounts of timing slack along their critical path together. Once these clusters are identified, they are placed onto respective V dd partitions on the device. We have evaluated different dual V dd fabrics and the potential gain in power consumption is explored. When a subset of the logic blocks on the device can be driven by low V dd levels (either with a dedicated low V dd supply or with a programmable selection between low and high V dd levels for these blocks) this affects placement and routing. As a result the maximum frequency of the designs may be affected. In order to evaluate the overall impact of creating voltage islands, we measured the Energy-Delay Product for our benchmark designs. We observed that the Energy-Delay product can be decreased by 26.9% when the placement of the designs into different voltage levels is guided by our clustering algorithm.

We propose two new algorithms for rewiring: a postplacement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. In the first algorithm, we extract small subcircuits consisting of several gates from the design and reconnect pins according to the symmetries of the subcircuits. To enhance the power of symmetry detection, we also propose a graph-based symmetry detector that can identify permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating abundant opportunities for rewiring. Our second algorithm, called long-range rewiring, is based on reconnecting equivalent pins and can augment the first approach for further optimization. We apply our techniques for wirelength optimization and observe that they provide wirelength reduction comparable to that achieved by detailed placement.

In this article, we propose a symbolic simulation method where Boolean functions can be efficiently manipulated through a 2-domain partitioned OBDD data structure. The functional partition is applied by automatically exploring the key decision points implicitly built inside a circuit. The partition can help to significantly reduce the OBDD sizes, solving problems that could not be solved with monolithic OBDD data structure. We demonstrate the performance of the approach through the symbolic simulation of several benchmark circuits with complex control logics and datapath. The symbolic simulation based on 2-domain partitioned OBDD can be also applied in equivalence checking. It can generate the signature of functions to identify the critical partition points in the optimized gate-level netlist.

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.

The AGENTS system is a set of programs designed to generate automatically the mask-level layout of full custom CMOS, BICMOS, and bipolar leaf cells. The system is formed from four sever programs: the placer, router, database, and broker. The placer places components in a cell, the router wires the circuits sent to it, the database stores all the information that is dependent upon the fabrication process, such as the design rules, and the Broker makes the services of the other servers available. These servers communicate over a computer network using the TCP/IP Internet Protocol. The Placer server receives from its client the description and netlist of the circuit to be generated using EDIF (Electronic Design Interchange Format.) The output to its client is the mask layout of the circuit, again codified in EDIF. The comcept of agents as software components which have the ability to communicate and cooperate with each other is at the heart of the AGENTS system. This concept is not only used at the higher level, for the four servers, but at a lower level as well, inside the Router and Placer servers, where small relatively simple agents work together to accomplish complex tasks. These small agents are responsible for all the reasoning carried out by the two servers, as they hold the basic inference routines and the knowledge needed by the servers. The system's philosophy is that competence should emerge out of the collective behavior of a large number of relatively simple agents. In addition and integrated to these small agents, the system uses a genetic algorithm to improve components' placement before routing.