Applications of Boolean Satisfiability to Verification and Testing of Switch-Level Circuits

This work extends to the switch level the verification and testing techniques based upon boolean satisfiability (SAT), so that SAT-based methodologies can be applied to circuits that cannot be well described at the gate level. The main achieved goal was to define a boolean model describing switch-level circuit operations as a SAT problem instance, to be applied to combinational equivalence checking and bridging-fault test generation. Results are provided for a set of combinational CMOS circuits, showing the feasibility of SAT-based verification and testing of switch-level circuits.     

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.     

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.     

一种用于FPGA的新型混合布线算法

布尔可满足性是计算机科学中最基础的问题之一,已经出现了包括著名的基于查找的SAT算法在内的各种算法.对于传统的一次布通一条线网的方法,基于布尔可满足性的算法有着独特的优点,例如:同步线网嵌入及可布通性确定.然而基于SAT的布线法在可扩展性方面有很大缺陷.而另一方面,几何查找布线算法即使具有广泛的拆线重布线的能力,但当北一个问题具有严格的布线约束条件时,它在布线方案收敛方面存在很大困难.文章提出了将一种布尔可满足性算法与VPR430相结合的新型、有效的混合布线算法.试验结果表明与相应的纯几何布线算法相比,这种算法在运行时间上有了极大的改善(减少了29%),并且对布线整体方案无不良影响.     

考虑拥挤度和性能的全芯片可控布线系统框架

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

Full-Chip Scalable Routing Framework Considering Congestion and Performance

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

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布线

介绍了用布尔可满足性(SAT)和子集可满足性(sub-SAT)算法解决FPGA的详细布线问题。在布线资源固定的FPGA布线环境中,布尔公式可以证明所给电路的不可布通性,这一点要优于典型的one-net-at-a-time方法。子集可满足性方法把一个有N个约束的"严格的"SAT问题转换成一个新的"松弛的"SAT问题,仅当在原始问题中变量的不可满足个数不超过阈值k(kN)时,这一问题是可满足的。它改进了布尔可满足性,但是却产生了很多额外的变量和子句。针对这一问题,提出了用伪布尔可满足性(PBS)来消除子集可满足性公式带来的缺点。初步的实验结果表明,把这个方法加入子集可满足性方法中可以减少变量和子句数量,并显著减少运行时间。     

Architecture driven circuit partitioning

In this paper, we propose an architecture driven partitioning algorithm for netlists with multiterminal nets. Our target architecture is a multifield-programmable gate array (FPGA) emulation system with folded-Clos network for board routing. Our goal is to minimize the number of FPGA chips used and maximize routability. To that end, we introduce a new cost function: the average number of pseudoterminals per net in a multiway cut. Experimental result shows that our algorithm is very effective in terms of the number of chips used and routability as compared to other methods     

FPGA routing and routability estimation via Boolean satisfiability

Guaranteeing or even estimating the routability of a portion of a placed field programmable gate array (FPGA) remains difficult or impossible in most practical applications. In this paper, we develop a novel formulation of both routing and routability estimation that relies on a rendering of the routing constraints as a single large Boolean equation. Any satisfying assignment to this equation specifies a complete detailed routing. By representing the equation as a binary decision diagram (BDD), we represent all possible routes for all nets simultaneously. Routability estimation is transformed to Boolean satisfiability, which is trivial for BDD's. We use the technique in the context of a perfect routability estimator for a global router. Experimental results from a standard FPGA benchmark suite suggest the technique is feasible for realistic circuits, but refinements are needed for very large designs     

基于伪布尔可满足性的纳米CMOS电路单元配置

针对传统布尔可满足性(SAT)法在处理纳米CMOS电路(CMOL)单元配置时,存在合取范式(CNF)表示的约束子句个数过多、中间处理文件过大的问题,该文提出了利用伪布尔可满足性(PBS)来解决CMOL电路的单元配置问题。实验结果显示,相对于传统的SAT法,PBS法在不增加额外的布尔变量集个数的条件下,通过降低编码过程中的约束个数,能有效减少中间处理文件大小,达到提高算法效率和提高处理大电路的能力。     

A routing algorithm for FPGAs with time-multiplexed interconnects

Previous studies show that interconnects occupy a large portion of the timing budget and area in FPGAs.In this work,we propose a time-multiplexing technique on FPGA interconnects.In order to fully exploit this interconnect architecture,we propose a time-multiplexed routing algorithm that can actively identify qualified nets and schedule them to multiplexable wires.We validate the algorithm by using the router to implement 20 benchmark circuits to time-multiplexed FPGAs.We achieve a 38%smaller minimum channel width and 3.8%smaller circuit critical path delay compared with the state-of-the-art architecture router when a wire can be time-multiplexed six times in a cycle.     

Architecture of field-programmable gate arrays

A survey of field-programmable gate array (FPGA) architectures and the programming technologies used to customize them is presented. Programming technologies are compared on the basis of their volatility, size parasitic capacitance, resistance, and process technology complexity. FPGA architectures are divided into two constituents: logic block architectures and routing architectures. A classification of logic blocks based on their granularity is proposed, and several logic blocks used in commercially available FPGAs are described. A brief review of recent results on the effect of logic block granularity on logic density and performance of an FPGA is then presented. Several commercial routing architectures are described in the context of a general routing architecture model. Finally, recent results on the tradeoff between the flexibility of an FPGA routing architecture, its routability, and its density are reviewed     

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     

Three-dimensional switchbox multiplexing in emerging 3D-FPGAs to reduce chip footprint and improve TSV usage

Three-dimensional integration technology is proposed to break down long wires and increase integration level of emerging complex designs. However, efficiency of this technology heavily depends on the usage of Through-Silicon Vias. TSVs are key solutions for cooling the 3D-chips but they occupy considerable silicon area. Therefore, reducing the number of required TSVs in routing step is very critical in 3D-chips. In this paper, a TSV multiplexing approach is proposed to reduce the number of required routing TSV. We proposed two multiplexed 3D-switchbox architectures. In the first architecture, the TSVs inside the switchboxes are multiplexed while in the second architecture, TSVs are multiplexed between the switchboxes. Moreover, a routing algorithm is suggested to route the FPGA using the multiplexed switchboxes to evaluate the proposed architectures. Experimental results show that the presented architectures and algorithms reduce the number of used TSVs by 64.58% and 71.27% on average for the first and second architectures respectively, in cost of a negligible overheads in total wire length and auxiliary switches.     

层次式布线资源FPGA连线开关的设计

提出了一种层次式布线资源FPGA连线开关的设计方法,采用迷宫算法,对连线开关的结构进行了分析.针对连线连接盒CB(connection box),提出了较为节省芯片面积的半连通结构;针对连线开关盒SB(switch box),在给出连通度fs概念后,提出了使SB连通能力达到最大值的设计方法,并通过数学推导予以证明.应用这种设计方法,设计了一种fs＝3的SB;成功地实现了采用这种结构的SB和半连通CB作为连线开关的FPGA芯片FDP-100K.该芯片在电路布通率和芯片面积方面取得了较好的平衡结果.     

Circuits and architectures for field programmable gate array with configurable supply voltage

Field programmable gate arrays (FPGAs) with supply voltage (Vdd) programmability have been proposed recently to reduce FPGA power, where the Vdd-level can be customized for FPGA circuit elements and unused circuit elements can be power-gated. In this paper, we first design novel Vdd-programmable and Vdd-gateable interconnect switches with minimal number of configuration SRAM cells. We then evaluate Vdd-programmable FPGA architectures using the new switches. The best architecture in our study uses Vdd-programmable logic blocks and Vdd-gateable interconnects. Compared to the baseline architecture similar to the leading commercial architecture, our best architecture reduces the minimal energy-delay product by 54.39% with 17% more area and 3% more configuration SRAM cells. Our evaluation results also show that LUT size 4 gives the lowest energy consumption, and LUT size 7 leads to the highest performance, both for all evaluated architectures.