Search

Field programmable gate array (FPGA) routing is one of the most time consuming steps in a typical computer-Aided design flow. The problem itself is similar to the NP-complete problem of computing a set of disjoint paths in a graph. The routing resource graph (RRG) that represents an FPGA routing network is necessarily large, and becomes even larger when modeling modern FPGAs that integrate sparse intracluster routing crossbars. This paper introduces two scalable heuristics that reduce the runtime and memory footprint of FPGA routing: 1) selective RRG expansion (SERRGE), which employs an application-specific memory manager that stores the RRG in a compressed form, and dynamically decompresses it as the router proceeds and 2) partial prerouting (PPR) locally routes all nets within each logic cluster, followed by a global routing stage to complete the routes. PPR and SERRGE converge faster than a traditional router using a fully expanded RRG. PPR runs faster and uses less memory than SERRGE, while SERRGE yields the highest clock frequencies among the three.

Modern FPGAs employ sparse crossbars in their intra-cluster routing. Modeling these crossbars enlarges the routing resource graph (RRG), a data structure used by most FPGA routers, while enlarging the search space for finding legal routes. We introduce two scalable routing heuristics for FPGAs with sparse intra-cluster routing crossbars: SElective RRG Expansion (SERRGE), which compresses the RRG, and dynamically decompresses it during routing, and Partial Pre-Routing (PPR), which locally routes all nets in each cluster, and routes global nets afterwards. Our experiments show that: (1) PPR and SERRGE converge faster than a traditional router using a fully-expanded RRG; (2) they both achieve better routability than the traditional router, given a limited runtime budget, with SERRGE achieving 1-2% better routability than PPR, on average; and (3) PPR uses far less memory and runs much faster than SERRGE, making it ideal for high capacity FPGAs. © 2012 IEEE.

In floating-point datapaths synthesized on FPGAs, the shifters that perform mantissa alignment and normalization consume a disproportionate number of LUTs. Shifters are implemented using several rows of small multiplexers; unfortunately, multiplexer-based logic structures map poorly onto LUTs. FPGAs, meanwhile, contain a large number of multiplexers in the programmable routing network; these multiplexer are placed under static control of the FPGA's configuration bitstream. In this work, we modify some of the routing multiplexers in the intra-cluster routing network of a CLB in an FPGA to implement shifters for floating-point mantissa alignment and normalization; the number of CLBs required for these operations is reduced by 67%. If shifting is not required, the routing multiplexers that have been modified can be configured to operate as normal routing multiplexers, so no functionality is sacrificed. The area overhead incurred by these modifications is small, and there is no need to modify every routing multiplexer in the FPGA. Experiments show that there is no negative impact in terms of clock frequency or routability for benchmarks that do not use the dynamic multiplexers. © 2012 ACM.

Embedded systems are becoming increasingly complex and heterogeneous, featuring multiple processor cores (which might themselves be heterogeneous) as well as specialized hardware accelerators, all accessing shared memory. Many accelerators are non-coherent (i.e., do not support hardware cache coherence) because it reduces hardware complexity, cost, and power consumption, while potentially offering superior performance. However, the disadvantage of non-coherence is that the software must explicitly synchronize between accelerators and processors, and this synchronization is notoriously error-prone. We propose an analysis technique to find data races in software for heterogeneous systems that include non-coherent accelerators. Our approach builds on classical results for data race detection, but the challenge turns out to be analyzing cache behavior rather than the behavior of the non-coherent accelerators. Accordingly, our central contribution is a novel, sound (data-race-preserving) abstraction of cache behavior. We prove our abstraction sound, and then to demonstrate the precision of our abstraction, we implement it in a simple dynamic race detector for a system with a processor and a massively parallel accelerator provided by a commercial FPGA-based accelerator vendor. On eleven software examples provided by the vendor, the tool had zero false positives and was able to detect previously unknown data races in two of the 11 examples. [ABSTRACT FROM AUTHOR]

A fully integrated 0.18 [micro]m DC-DC buck converter using a low-swing 'stacked driver' configuration is reported in this paper. A high switching frequency of 660 MHz reduces filter components to fit on chip, but this suffers from high switching losses. These losses are reduced using: 1) low-swing drivers; 2) supply stacking; and 3) introducing a charge transfer path to deliver excess charge from the positive metal-oxide semiconductor drive chain to the load, thereby recycling the charge. The working prototype circuit converts 2.2 to 0.75-1.0 V at 40-55 mA. Design and simulation of an improved circuit is also included that further improves the efficiency by enhancing the charge recycling path, providing automated zero voltage switching (ZVS) operation, and synchronizing the half-swing gating signals. Index Terms--Charge recycling, integrated output filter, low-power stacked driver, subgigahertz switching, switch mode DC-DC converter.