An efficient logic emulation system

The Realizer, is a logic emulation system that automatically configures a network of field-programmable gate arrays (FPGAs) to implement large digital logic designs, is presented. Logic and interconnect are separated to achieve optimum FPGA utilization. Its interconnection architecture, called the partial crossbar, greatly reduces system-level placement and routing complexity, achieves bounded interconnect delay, scales linearly with pin count, and allows hierarchical expansion to systems with hundreds of thousands of FPGA devices in a fast and uniform way. An actual multiboard system has been built, using 42 Xilinx XC3090 FPGAs for logic. Several designs, including a 32-b CPU datapath, have been automatically realized and operated at speed. They demonstrate very good FPGA utilization. The Realizer has applications in logic verification and prototyping, simulation, architecture development, and special-purpose execution     

Hybrid Multi-FPGA Board Evaluation by Permitting Limited Multi-Hop Routing

Multi-FPGA Boards (MFBs) have been in use for more than a decade for implementing systems requiring high performance and for emulation/prototyping of multimillion gate chips. It is important to develop an MFB architecture which can be used for emulation or prototyping of a large number of circuits. A key feature of an MFB is its routing architecture defined by its inter-Field-Programmable Gate Array (FPGA) connections. There are two types of inter-FPGA connections, namely–fixed connections (FCs) connecting a pair of FPGAs through dedicated wires and programmable connections (PCs) which connect a pair of FPGAs through a programmable switch. An architecture which has a mix of both these type of connections is called a hybrid routing architecture. It has been shown in the literature [7] that a hybrid MFB architecture is more efficient for emulation than an architecture with only one type of connections. The cost of an MFB and delay of the emulated circuit on it depends on the number of PCs used for emulation. An objective of a designer of an MFB for circuit emulation is to minimize the required number of PCs. In this paper, we describe algorithms to evaluate the requirement of PCs for many hybrid routing architectures.The requirement of PCs can be reduced if some programmable connections are replaced by a connection using only FCs by routing through FPGAs. Such a routing is called multi-hop routing. We present an optimal and a heuristic algorithm for estimation of PCs when limited number of hops through FPGAs are permitted. The unique feature of our evaluation scheme is that it is generic and treat routing architecture as a parameter. We have used benchmark circuits as well as synthetic cloned circuits for testing our algorithms. Our heuristic algorithm is very fast and gives optimal results most of the time. Our algorithms can be used for actual routing during circuit emulation.     

An architecture for a DSP field-programmable gate array

This paper describes an application specific architecture for field-programmable gate arrays (FPGAs). Emphasis is placed on the logic module architecture and channel segmentation for the FPGAs targeted for application areas related to digital signal processing (DSP). The proposed logic module architecture is well-suited for efficient implementation of frequently used logic functions in the DSP application area. This is mainly because it is possible to implement most of these functions using one logic module, which results in a reduction in both the net lengths and the number of antifuses used. The performance improvements are achieved by customizing the logic module architecture and the programmable interconnect to suit the requirements of DSP applications     

A novel and efficient routing architecture for multi-FPGA systems

Multi-FPGA systems (MFSs) are used as custom computing machines, logic emulators and rapid prototyping vehicles. A key aspect of these systems is their programmable routing architecture which is the manner in which wires, FPGAs and field-programmable interconnect devices (FPIDs) are connected. Several routing architectures for MFSs have been proposed, and previous research has shown that the partial crossbar is one of the best existing architectures. In this paper, we propose a new routing architecture, called the hybrid complete-graph and partial-crossbar (HCGP) which has superior speed and cost compared to a partial crossbar. The new architecture uses both hard-wired and programmable connections between the FPGAs. We compare the performance and cost of the HCGP and partial crossbar architectures experimentally, by mapping a set of 15 large benchmark circuits into each architecture. A customized set of partitioning and interchip routing tools were developed, with particular attention paid to architecture-appropriate interchip routing algorithms. We show that the cost of the partial crossbar (as measured by the number of pins on all FPGAs and FPIDs required to fit a design), is on average 20% more than the new HCGP architecture and as much as 25% more. Furthermore, the critical path delay for designs implemented on the partial crossbar were on average 20% more than the HCGP architecture and up to 43% more. Using our experimental approach, we also explore a key architecture parameter associated with the HCGP architecture-the proportion of hard-wired connections versus programmable connections-to determine its best value     

Validation,off-line programming and optimisation of industrial control logic

This article proposes a classification of different methods for validation, off-line programming and optimisation of control logic. The classification is an overview of different methods available and includes advantages and disadvantages for each method. The method overview points out a superior method, control system emulation, which is the most cost-effective and flexible method. The control system emulation method is also general and may be applied to validate and optimise control logic in various applications. Further, the method is compared with several other methods for validation of industrial control systems. However the method requires a standardised system architecture. This article proposes such architecture for the control system emulation method. Here, a control system emulator has also been implemented with the specific system architecture described in this article. An application case is also provided to demonstrate an approach to the integration of a control system emulator into a virtual manufacturing system.     

Routing on field-programmable switch matrices

In this paper, we address the problem of routing nets on field programmable gate arrays (FPGAs) interconnected by a switch matrix. We extend the switch matrix architecture proposed by Zhu et al. (1993) to route nets between FPGA chips in a multi-FPGA system. Given a limited number of routing resources in the form of programmable connection points within a two-dimensional switch matrix, this problem examines the issue of how to route a given net traffic through the switch matrix structure. First, we define the problem as a general undirected graph in which each vertex has one single color among six possible colors and formulate it as a constraint satisfaction problem. This is further modeled as a 0-1 multidimensional knapsack problem for which a fast approximate solution is applied. Experimental results show that the accuracy of our proposed heuristic is quite high for moderately large switch matrices.     

Graphene nanoribbon crossbar architecture for low power and dense circuit implementations

Crossbar array is a promising nanoscale architecture which can be used for logic circuit implementation. In this work, a graphene nanoribbon (GNR) based crossbar architecture is proposed. This design uses parallel GNRs as device channel and metal as gate, source and drain contacts. Schottky-barrier type graphene nanoribbon field-effect transistors (SB-GNRFETs) are formed at the cross points of the GNRs and the metallic gates. Benchmark circuits are implemented using the proposed crossbar, Si-CMOS and multi-gate Si-CMOS approaches to evaluate the performance of the crossbar architecture compared to the conventional CMOS logic design. The compact SPICE model of SB-GNRFET was used to simulate crossbar-based circuits. The CMOS circuits are also simulated using 16 nm technology parameters. Simulation results of benchmark circuits using SIS synthesis tool indicate that the GNR-based crossbar circuits outperform conventional CMOS circuits in low power applications. Area optimized cell libraries are implemented based on the asymmetric crossbar architecture. The area of the circuit can be more reduced using this architecture at the expense of higher delay. The crossbar cells can be combined with CMOS cells to exhibit better performance in terms of EDP.     

Antifuse field programmable gate arrays

An antifuse is an electrically programmable two-terminal device with small area and low parasitic resistance and capacitance. Field-programmable gate arrays (FPGAs) using antifuses in a segmented channel routing architecture now offer the digital logic capabilities of an 8000-gate conventional gate array and system speeds of 40-60 MHz. A brief survey of antifuse technologies is provided. the antifuse technology, routing architecture, logic module, design automation, programming, testing and use of ACT antifuse FPGAs are described. Some inherent tradeoffs involving the antifuse characteristics, routing architecture and logic module are illustrated     

Fine-grained and coarse-grained behavioral partitioning witheffective utilization of memory and design space exploration formulti-FPGA architectures

Reconfigurable computers (RCs) host multiple field programmable gate arrays (FPGAs) and one or more physical memories that communicate through an interconnection fabric. State-of-the-art RCs provide abundant hardware and storage resources, but have tight constraints on FPGA pin-out and inter-FPGA interconnection resources. These stringent constraints are the primary impediment for multi-FPGA partitioning tools to generate high-quality designs, in this paper, we present two integrated partitioning and synthesis approaches for RCs. The first approach involves fine-grained partitioning of a scheduled data-flow graph (DFG, or an operation graph), and the second involves a coarse-grained partitioning of an unscheduled control data flow graph (CDFG, or a block graph). A hardware design space exploration engine is integrated with the block graph partitioner that dynamically contemplates multiple schedules during partitioning. The novel feature in the partitioning approaches is that the physical memory in the RC is effectively used to alleviate the FPGA pin-out and inter-FPGA interconnection bottle-neck. Several experiments have been conducted, targeting commercial multi-FPGA boards, to compare the two partitioning approaches, and detailed summaries are presented     

Optimization of Pattern Matching Circuits for Regular Expression on FPGA

Regular expressions are widely used in the network intrusion detection system (NIDS) to represent attack patterns. Previously, many hardware architectures have been proposed to accelerate regular expression matching using field-programmable gate array (FPGA) because FPGAs allow updating of new attack patterns. Because of the increasing number of attacks, we need to accommodate a large number of regular expressions on FPGAs. Although the minimization of logic equations has been studied intensively in the area of computer-aided design (CAD), the minimization of multiple regular expressions has been largely neglected. This paper presents a novel sharing architecture allowing our algorithm to extract and share common subregular expressions. Experimental results show that our sharing scheme significantly reduces the area of pattern matching circuits for regular expression.     

Placement and routing tools for the Triptych FPGA

Field-programmable gate arrays (FPGAs) are becoming an increasingly important implementation medium for digital logic. One of the most important keys to using FPGAs effectively is a complete, automated software system for mapping onto the FPGA architecture. Unfortunately, many of the tools necessary require different techniques than traditional circuit implementation options, and these techniques are often developed specifically for only a single FPGA architecture. In this paper we describe automatic mapping tools for Triptych, an FPGA architecture with improved logic density and performance over commercial FPGAs. These tools include a simulated-annealing placement algorithm that handles the routability issues of fine-grained FPGAs, and an architecture-adaptive routing algorithm that can easily be retargeted to other FPGAs. We also describe extensions to these algorithms for mapping asynchronous circuits to Montage, the first FPGA architecture to completely support asynchronous and synchronous interface applications     

Using bus-based connections to improve field-programmable gate-array density for implementing datapath circuits

As the logic capacity of field-programmable gate arrays (FPGAs) increases, they are increasingly being used to implement large arithmetic-intensive applications, which often contain a large proportion of datapath circuits. Since datapath circuits usually consist of regularly structured components (called bit-slices) which are connected together by regularly structured signals (called buses), it is possible to utilize datapath regularity in order to achieve significant area savings through FPGA architectural innovations. This paper describes such an FPGA routing architecture, called the multibit routing architecture, which employs bus-based connections in order to exploit datapath regularity. It is experimentally shown that, compared to conventional FPGA routing architectures, the multibit routing architecture can achieve 14% routing area reduction for implementing datapath circuits, which represents an overall FPGA area savings of 10%. This paper also empirically determines the best values of several important architectural parameters for the new routing architecture including the most area efficient granularity values and the most area efficient proportion of bus-based connections.     

多片FPGA系统互连结构研究

本文在分析现有多FPGA系统互连拓朴结构的基础上，指出其最佳形式，即硬布线和可编程布线相结合，优势互补，并提出了一种新的拓朴结构——最大权生成树与交叉开关相结合，详述了其设计流程和算法。     

高性能可编程互连资源设计研究

传统的可编程互联结构在短距离互连上往往采用单管、中距离上有双向线,这使得在CLB中查找表(LUT)数目变大后,互连上的延迟会随线长增加而呈指数增长.本文提出了一种改进的高性能互连结构,改进了短、中和长距离互连,使得其在CLB中LUT数目增加的情况下让芯片拥有更好的互连延迟特性,通过对这种互连结构和传统的互连结构进行建模...     

Probabilistic optimization for FPGA board level routing problems

Field programmable gate arrays (FPGAs) are an enabling technology in circuit designs. We consider the board-level multi-terminal net assignment in the FPGA-based logic emulation. A novel probabilistic optimization method is devised for solving the net assignment problem. The approach incorporates randomized rounding, genetic algorithm, and solution-improvement strategies. Experimental results demonstrate promising performance.     

基于RRAM双交叉阵列结构的三值存内逻辑电路设计

在RRAM交叉阵列结构中实现逻辑运算可以较好地解决传统冯诺依曼架构中的存储墙问题.三值逻辑相比于传统的二值逻辑,具有更少的逻辑操作数目和更快的运算速度.文中提出了一种基于RRAM双交叉阵列结构的三值存内逻辑电路设计,其中三值逻辑电路的输入与输出均通过多值RRAM的阻值表示.该结构支持两种三值逻辑门和一种二值逻辑门以提升...     

The Triptych FPGA architecture

Field-programmable gate arrays (FPGAs) are an important implementation medium for digital logic. Unfortunately, they currently suffer from poor silicon area utilization due to routing constraints. In this paper we present Triptych, an FPGA architecture designed to achieve improved logic density with competitive performance. This is done by allowing a per-mapping tradeoff between logic and routing resources, and with a routing scheme designed to match the structure of typical circuits. We show that, using manual placement, this architecture yields a logic density improvement of up to a factor of 3.5 over commercial FPGAs, with comparable performance. We also describe Montage, the first FPGA architecture to fully support asynchronous and synchronous interface circuits     

A Novel Switched-Capacitor Based Field-Programmable Analog Array Architecture

A novel field-programmable analog array (FPAA) architecture based on switched-capacitor techniques is proposed. Each configurable analog block (CAB) in the proposed architecture is an opamp with feedback switches which are controlled by configuration bits. Interconnection networks are used to connect programmable capacitor arrays (PCAs) and the CABs. The routing switches in the interconnection networks not only function as interconnection elements but also switches for the charge transfer required in switched-capacitor circuits. This scheme minimizes the number of connecting switches between CABs and PCAs, thereby, it reduces the settling time of the resultant SC circuits and thus achieving high speed operation. The architecture is highly flexible and provides for the implementation of various A/D and D/A converters when the FPAA is connected with external digital circuits or field-programmable gate arrays (FPGAs).     

Estimating Power for FPGAs Based on Signal Probability Theory

Power dissipation has become one of the key optimization conditions in logic design on field programmable gate arrays (FPGAs), thus the power estimation is necessary for logic design optimization. Nowadays, signal activity data created by logic simulation based on test vectors is essential to be used to determine the toggle rate of each signals and blocks in power estimation tools provided by field programmable gate array (FPGA) electronic design automation (EDA) tools. The accuracy of power estimation highly depends on the quality of test vectors, especially, pattern coverage. As probability distribution can describe the uncertainty signals, this work provides an algorithm which can estimate FPGAs power more effectively and accurately by using signal probability distribution rather than test vectors.