Indirect connection aware attraction clustering algorithm is proposed for clustered field programmable gate array architecture model to achieve simultaneously optimization of several performance metrics. A new cost function considers the attraction of the subsequent basic logic elements (BLEs) to the selected cluster, the number of the used pins already in the cluster, as well as critical path delay. The attractions of which BLEs are directly and indirectly connected to the selected cluster are taken into account. As a result, more external nets are absorbed into clusters, less number of pins per cluster and fewer clusters are required. Hence, smaller channel width is required for routing and speed of the design is improved. Performance comparisons are carried out in details with respect to state-of-the-art clustering techniques interconnect resource aware clustering (iRAC) and many-objective clustering (MO-Pack). Results show that the proposed algorithm outperforms these two clustering approaches with achievements of 38.8% and 42.2% respectively in terms of channel widths and 40.1% and 44.8% respectively in terms of number of external nets but with no critical path and area overhead.

In this paper, Yet Another Many-Objective Clustering (YAMO-Pack) is proposed for academic field programmable gate array architecture model. The YAMO-Pack introduces the impact of attraction between Basic Logic Elements (BLE) and the selected Configurable Logic Blocks (CLB) when BLEs are indirectly connected to the CLBs. Consequently more external nets are absorbed into clusters and speed of the design is improved. Experimental results show that the proposed algorithm outperforms previous approaches in terms of number of CLBs, number of external nets and critical path.

Partially reconfigurable systems are promising computing platforms for streaming applications, which demand both hardware efficiency and reconfigurable flexibility. To realize the full potential of these systems, a streaming-based partially reconfigurable architecture and unified software/hardware multithreaded programming model (SPREAD) is presented in this paper. SPREAD is a reconfigurable architecture with a unified software/hardware thread interface and high throughput point-to-point streaming structure. It supports dynamic computing resource allocation, runtime software/hardware switching, and streaming-based multithreaded management at the operating system level. SPREAD is designed to provide programmers of streaming applications with a unified view of threads, allowing them to exploit thread, data, and pipeline parallelism; it enhances hardware efficiency while simplifying the development of streaming applications for partially reconfigurable systems. Experimental results targeting cryptography applications demonstrate the feasibility and superior performance of SPREAD. Moreover, the parallelized Advanced Encryption Standard (AES), Data Encryption Standard (DES), and Triple DES (3DES) hardware threads on field-programmable gate arrays show 1.61-4.59 times higher power efficiency than their implementations on state-of-the-art graphics processing units.

As a promising computing platform for stream processing, partially reconfigurable systems have shown their hardware efficiency and reconfiguration flexibility. This paper presents a partially reconfigurable architecture supporting hardware threads. It gives a unified software/hardware thread interface and high throughput point-to-point streaming structure. Dynamic computing resource allocation and streaming-based multi-threaded management are also provided at operating system level. It is easy for programmers to exploit the inherent thread, data and pipeline parallelism in a unified view of threads, enhancing hardware efficiency while improving productivity. The experimental results on a cryptography application demonstrate the feasibility and superior performance. Moreover, the parallelized AES, DES and 3DES hardware threads on field-programmable gate arrays show 1.61-4.59 times higher power efficiency than their implementations on state-of-the-art graphics processing units.

The reliability of SRAM-based Field Programmable Gate Array (FPGA) is susceptible to Single Event Upset (SEU) fault. To investigate the fault impact, particular the fault in interconnects on FPGA functionality, this paper proposes a SEU fault analysis framework by evaluating the fault with a unified metric. This metric, termed as criticality, quantifies the sensitivity of FPGA functional failure to the SEU fault on logical and interconnect configuration bits. Considering the post layout information, our framework can characterize the SEU fault with respect to different FPGA architectures and CAD algorithms, such that the sensitivity of FPGA functional failure can be investigated in detail during design phase. The experiment result quantitatively shows that the configuration bits in interconnects dominate those in LUTs, several times both in bit number and criticality contribution. The ratio of their criticalities is even higher when LUT input size increases from 4 to 6. The higher criticality of interconnects than their LUT counterpart is due to their natural sensitivity to functional failure instead of their majority of bits. In addition, it is also shown that, among the three common types of switch boxes, the Subset switch box is less fault tolerant than Wilton and Universal.

Boolean matching is one of the most important fundamental algorithms in FPGA synthesis and architecture evaluations. However, existing Boolean matchers for FPGAs, even with numerous improvements, are still not scalable to complex PLBs and large circuits. This paper aims to improve the efficiency of Boolean matching using lookup tables implemented by Bloom filters, which can store terabyte-lookup tables with a desktop PC. The key improvement is to efficiently prune a large set of non-implementable functions use the Bloom filter. Using the area-oriented re-synthesis as an application, the experiments on a broad selection of benchmark sets show that the re-synthesis with our improved Boolean matcher is 18X faster than the one with an optimized SAT-based Boolean matcher, while preserving the quality of the re-synthesizer.

This paper explores the FPGA routing architecture based on a new concept of “general switch box (GSB)” to improve the performance of FPGA. Compared with the existing CB/SB routing architecture and CS-box architecture, the proposed GSB architecture has much larger exploration space. Experimental results with MCNC benchmark circuits show that the performance of FPGAs with GSB is about 24.3% better than the CB/SB architecture with the same segment distribution in terms of product of channel width and delay using 0.17% less routing switches for the single wire length. For the two types of wire segments, we propose an architecture with 13.3% performance improvement at the cost of about 0.8% increase in switch number compared to the single wire length GSB architecture.

Software as a Service (SaaS) 1.0 signifcantly lowers the infrastructure and maintenance cost and increases the accessibility of the software by hosting software via the web. Compared with SaaS 1.0, SaaS 2.0 is more flexible since it leverages software tools from both server and client sides with closer interaction between them. The SaaS 2.0 paradigm provides new opportunities and challenges for EDA. In this paper, we take Boolean matching, one of the core sub algorithms in logic synthesis for field programmable gate arrays (FPGAs), as a case study. We investigate the advantages and challenges of implementing a scalable EDA algorithm under SaaS 2.0 paradigm from a technical perspective. We propose SaaS-BM, a new Boolean matching algorithm customized to take full advantage of the cloud while addressing concerns such as security and the internet bandwidth limit. Extensive experiments are performed under a networked environment with concurrent accesses. Integrated into a post-mapping re-synthesis algorithm minimizing area, the proposed SaaS-BM is 863X times faster than state-of-the-art SAT-based Boolean matching with 0.5% area overhead. Compared with a recent Bloom Filter-based Boolean matching algorithm, our proposed SaaS-BM is 53X times faster on large circuits with no area overhead.

A universal FPGA routing architecture is presented, which ensures that every module in the FPGA including CLBs and IOBs have a uniform interconnect architecture, and the load of interconnect lines is equally distributed. So, this architecture is highly repeatable and the signal delay is predictable and regular. Furthermore, the realization of the programmable interconnect point (PIP) and the buffer driver is also optimized to benefit the signal delay up to 5%.The test results of the example chip show the reasonableness of these ideas.

In nanometer technologies, process variations possess growing nonlinear impacts on circuit performance, which causes critical path delays of combinatorial circuits variate randomly with non-Gaussian distribution. In this paper, we propose a novel clock skew scheduling methodology that optimizes timing yield by handling non-Gaussian distributions of critical path delays. Firstly a general formulation of the optimization problem is proposed, which covers most of the previous formulations and indicates their limitations with statistical interpretations. Then a generalized minimum balancing algorithm is proposed for effectively solving the skew scheduling problem. Experimental results show that the proposed method significantly outperforms some representative methods previously proposed for yield optimization, and could obtain timing yield improvements up to 33.6% and averagely 17.7%.

In this paper, we propose a novel statistical capacitance extraction method for interconnects considering process variations. The new method, called statCap, is based on the spectral stochastic method where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After that, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Experimental results show that our method is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical interconnect structures.

The increasing effort on full-chip validation constrains design cost and time-to-market. A waveform comparison tool named WCOMP is presented to automate mixed-signal validation regression in memory design. Unlike digital waveform comparison tools, WCOMP compares mixed-signal waveforms for functional match instead of graphical match, which tally with the requirements of full-chip validation regression. Simulations with different regression runs, process parameters, voltages and temperatures can be functionally compared. The methods are proved to be effective in Intelreg Flash memory design.

This paper presents a new universal test approach for FPGA logic resources. It includes a new greedy configuration-generating algorithm, and a new FPGA Configurable Logic Block (CLB) test model. The model is based on two directed graphs: a structure graph and a configuration graph, which convey the important information from the CLB gate level circuit to the greedy configuration-generating algorithm, so the algorithm can generate minimum the number of test configurations to achieve a given fault coverage. With this new approach, researchers can easily get test patterns optimized both in test time and fault coverage for different FPGA architectures. At the end, we compare experiment results with other test approaches, and the results show test pattern from the new approach is even more efficient than pattern from manual optimization. It also proves that the approach can deal with different types of FPGAs very well.

Non-uniform routing architecture contains routing channels of different widths. In this paper we propose a design methodology of domain specific non-uniform programmable routing architecture for embedded programmable IP cores. This non-uniform architecture is based on symmetrical FPGA model and consists of connection boxes of full connectivity and rectangular switch boxes. The rectangular switch box is derived from universal switch box module. Area and timing efficiency of the proposed architecture is compared with those of uniform architecture based on placement and routing result over a set of MCNC benchmark circuits. The comparison results show that non-uniform routing architecture gains up to 8% layout area reduction from uniform ones. Besides, by widening some of the routing channels where routing congestions accumulate, the average critical path delay of non-uniform architecture is 8% less than that of uniform one while maintain the same area.

This paper presents a high performance Configurable Analog Cell (CAC) which is made up of a Basic Configurable Analog Cell (BCAC) and a digital converter block. The CAC can be used either for Field Programmable Analog Array (FPAA) or for Field Programmable Digital-Analog Mixed Array (FPMA). The BCAC include three innovative Programmable Switch Blocks (PSBs), three Programmable Capacitor Arrays (PCAs), and an amplifier. PSB and PCA can be programmed to generate many equivalent components. In addition, digital converter block is used for enhancing the function of CAC. The results of the configuration demonstrate that the CAC architecture can not only implement linear functions including gain amplifier, integrator, and filter, etc., but also realize complex nonlinear functions such as Voltage Control Oscillator (VCO), Analog-Digital Convertor (ADC), and so on. Compared with other architectures, the CAC architecture can offer substantially more analog functions.

In an SRAM-based FPGA, MOS transistors connect wire segments to construct interconnections between CLBs, resulting in large and unpredictable path delays. So it is necessary to be able to estimate interconnection delays quickly and accurately in order that performance-driven layout and analysis algorithms can achieve high quality. Because the effective channel resistance of a MOS transistor changes with the voltage on a transistor's source pole, general methods for wire nets' path delay estimation, in which wire resistance is always a fixed value, will never be applicable, while SPICE would be too computationally expensive to be used in layout optimization. In this paper, an analytical delay model of FPGA interconnection under ramp input is put forward, and closed-form formulas for delay estimation are proposed. Compared with SPICE, our algorithm has been proved to be fast and accurate enough.