Yang, Xiaoqing. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 113-120). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

The new Field Programmable Gate Array (FPGA) technologies and their structures have opened up new approaches to logic design and synthesis. The main feature of an FPGA is an array of logic blocks surrounded by a programmable interconnection structure. Cellular FPGAs are a special class of FPGAs which are distinguished by their fine granularity and their emphasis on local cell interconnects. While these characteristics call for specialized synthesis tools, the availability of logic gates other than Boolean AND, OR and NOT in these architectures opens up new possibilities for synthesis. Among the possible realizations of Boolean functions, XOR logic is shown to be more compact than AND/OR and also highly testable. In this dissertation, the concept of structural regularity and the advantages of XOR logic are used to investigate various synthesis approaches to cellular FPGAs, which up to now have been mostly nonexistent. Universal XOR Canonical Forms, Two-level AND/XOR, restricted factorization, as well as various Directed Acyclic Graph structures are among the proposed approaches. In addition, a new comprehensive methodology for the investigation of all possible XOR canonical forms is introduced. Additionally, a new compact class of XOR-based Decision Diagrams for the representation of Boolean functions, called Kronecker Functional Decision Diagrams (KFDD), is presented. It is shown that for the standard, hard, benchmark examples, KFDDs are on average 35% more compact than Binary Decision Diagrams, with some reductions of up to 75% being observed.

Esta dissertação introduz o conceito de cortes KL, o que permite controlar tanto o número K de entradas como o número L de saídas em uma região de um circuito. O projeto de um circuito digital pode ser dividido em duas fases: síntese lógica e síntese física. Dentro de síntese lógica, um dos principais passos é o mapeamento tecnológico. Tradicionalmente, o processo de mapeamento tecnológico somente lida com funções de saída única, para a construção de circuitos. O objetivo deste método é explorar o uso de blocos de múltiplas saídas no mapeamento tecnológico. Para prover escalabilidade, o conceito de fatoração de cortes é estendido para os cortes KL. Algoritmos para enumerar esses cortes e também para enumerar alguns subconjuntos de cortes com características específicas são apresentados e os resultados são mostrados. Como exemplos de aplicações práticas, diferentes algoritmos de cobertura são propostos. O algoritmo guloso é uma alternativa simples e produz bons resultados em área, mas é muito restritivo, pois não é factível em mapeamento orientado à atraso. Outro algoritmo de cobertura apresentado é uma extensão do algoritmo de fluxo de área e permite a utilização de cortes com várias saídas, mantendo possível a consideração de outros custos. Um algoritmo de correspondência Booleana que é capaz de lidar com blocos com múltiplas saídas também é descrito. Isso permite a utilização de uma biblioteca padrão com células com mais de uma saída no mapeamento tecnológico. Os resultados mostram a viabilidade e utilidade do método. / This thesis introduces the concept of KL-feasible cuts, which allows controlling both the number K of inputs and the number L of outputs in a circuit region. The design of a digital circuit can roughly be divided in two phases: logic synthesis and physical synthesis. Within logic synthesis, one of the main steps is the technology mapping. Traditionally, the technology mapping process only handles single output functions, in order to construct circuits. The objective of this method is to explore the use of multiple output blocks on technology mapping. To provide scalability, the concept of factor cuts is extended to KL-cuts. Algorithms for enumerating these cuts and also for enumerating some subsets of cuts with some special characteristics are presented and results are shown. As examples of practical applications, different covering algorithms are proposed. The greedy algorithm is a simple alternative and produces good results in area, but it is too restrictive, as it is not practical in timing oriented mapping. The other covering algorithm presented is an extension to the area flow algorithm and allows cuts with multiple outputs to be used while making possible the control of some other costs. A Boolean matching algorithm that is able to handle multiple output blocks is also described, which permits the use of a standard cell library with more than one output on technology mapping. The results show the viability and usefulness of the method.

Esta dissertação introduz o conceito de cortes KL, o que permite controlar tanto o número K de entradas como o número L de saídas em uma região de um circuito. O projeto de um circuito digital pode ser dividido em duas fases: síntese lógica e síntese física. Dentro de síntese lógica, um dos principais passos é o mapeamento tecnológico. Tradicionalmente, o processo de mapeamento tecnológico somente lida com funções de saída única, para a construção de circuitos. O objetivo deste método é explorar o uso de blocos de múltiplas saídas no mapeamento tecnológico. Para prover escalabilidade, o conceito de fatoração de cortes é estendido para os cortes KL. Algoritmos para enumerar esses cortes e também para enumerar alguns subconjuntos de cortes com características específicas são apresentados e os resultados são mostrados. Como exemplos de aplicações práticas, diferentes algoritmos de cobertura são propostos. O algoritmo guloso é uma alternativa simples e produz bons resultados em área, mas é muito restritivo, pois não é factível em mapeamento orientado à atraso. Outro algoritmo de cobertura apresentado é uma extensão do algoritmo de fluxo de área e permite a utilização de cortes com várias saídas, mantendo possível a consideração de outros custos. Um algoritmo de correspondência Booleana que é capaz de lidar com blocos com múltiplas saídas também é descrito. Isso permite a utilização de uma biblioteca padrão com células com mais de uma saída no mapeamento tecnológico. Os resultados mostram a viabilidade e utilidade do método. / This thesis introduces the concept of KL-feasible cuts, which allows controlling both the number K of inputs and the number L of outputs in a circuit region. The design of a digital circuit can roughly be divided in two phases: logic synthesis and physical synthesis. Within logic synthesis, one of the main steps is the technology mapping. Traditionally, the technology mapping process only handles single output functions, in order to construct circuits. The objective of this method is to explore the use of multiple output blocks on technology mapping. To provide scalability, the concept of factor cuts is extended to KL-cuts. Algorithms for enumerating these cuts and also for enumerating some subsets of cuts with some special characteristics are presented and results are shown. As examples of practical applications, different covering algorithms are proposed. The greedy algorithm is a simple alternative and produces good results in area, but it is too restrictive, as it is not practical in timing oriented mapping. The other covering algorithm presented is an extension to the area flow algorithm and allows cuts with multiple outputs to be used while making possible the control of some other costs. A Boolean matching algorithm that is able to handle multiple output blocks is also described, which permits the use of a standard cell library with more than one output on technology mapping. The results show the viability and usefulness of the method.

Esta dissertação introduz o conceito de cortes KL, o que permite controlar tanto o número K de entradas como o número L de saídas em uma região de um circuito. O projeto de um circuito digital pode ser dividido em duas fases: síntese lógica e síntese física. Dentro de síntese lógica, um dos principais passos é o mapeamento tecnológico. Tradicionalmente, o processo de mapeamento tecnológico somente lida com funções de saída única, para a construção de circuitos. O objetivo deste método é explorar o uso de blocos de múltiplas saídas no mapeamento tecnológico. Para prover escalabilidade, o conceito de fatoração de cortes é estendido para os cortes KL. Algoritmos para enumerar esses cortes e também para enumerar alguns subconjuntos de cortes com características específicas são apresentados e os resultados são mostrados. Como exemplos de aplicações práticas, diferentes algoritmos de cobertura são propostos. O algoritmo guloso é uma alternativa simples e produz bons resultados em área, mas é muito restritivo, pois não é factível em mapeamento orientado à atraso. Outro algoritmo de cobertura apresentado é uma extensão do algoritmo de fluxo de área e permite a utilização de cortes com várias saídas, mantendo possível a consideração de outros custos. Um algoritmo de correspondência Booleana que é capaz de lidar com blocos com múltiplas saídas também é descrito. Isso permite a utilização de uma biblioteca padrão com células com mais de uma saída no mapeamento tecnológico. Os resultados mostram a viabilidade e utilidade do método. / This thesis introduces the concept of KL-feasible cuts, which allows controlling both the number K of inputs and the number L of outputs in a circuit region. The design of a digital circuit can roughly be divided in two phases: logic synthesis and physical synthesis. Within logic synthesis, one of the main steps is the technology mapping. Traditionally, the technology mapping process only handles single output functions, in order to construct circuits. The objective of this method is to explore the use of multiple output blocks on technology mapping. To provide scalability, the concept of factor cuts is extended to KL-cuts. Algorithms for enumerating these cuts and also for enumerating some subsets of cuts with some special characteristics are presented and results are shown. As examples of practical applications, different covering algorithms are proposed. The greedy algorithm is a simple alternative and produces good results in area, but it is too restrictive, as it is not practical in timing oriented mapping. The other covering algorithm presented is an extension to the area flow algorithm and allows cuts with multiple outputs to be used while making possible the control of some other costs. A Boolean matching algorithm that is able to handle multiple output blocks is also described, which permits the use of a standard cell library with more than one output on technology mapping. The results show the viability and usefulness of the method.

A stability checker is a clocked storage element, much like a flip-flop, which detects unstable and late signals in the pipeline of a digital system. The On-line stability checker operates concurrently with its associated circuit-under-test (CUT). This thesis describes the full custom very-large-scale integration (VLSI) design and testing process of On-Line Stability Checkers. The goals of this thesis are to construct and test Stability Checker designs, and to create a design template for future class projects in the EE 431 Computer-Aided Design (CAD) of VLSI Devices course at Cal Poly. A method for concurrent fault testing called On-line Stability Checking was introduced by Franco and McCluskey [10] to detect reliability failures. Reliability failures initially manifest themselves as delay faults and transient glitching, which become progressively larger over time due to the wearout of conducting metal lines, eventually leading to functional faults. Stability checkers periodically detect reliability failures by monitoring CUT output signals for unstable and late input signals over a time period after the sampling clock edge. The checkers are tested by applying variable delayed input test patterns to emulate reliability failures. Consequently, configurable delay chains were incorporated into the system to provide variable delays on the input signal lines. The system also includes external test signal ports. Circuit and layout designs were implemented in the Electric VLSI Design tool [12] and simulated with LTSPICE [13]. Electric provides Design Rule Checking (DRC) and Layout-versus-Schematic (LVS) utilities for verification. Each module was designed in a bottom-up, hierarchical cell-based approach. Functional simulation, DRC and LVS checks were performed at every subsequent higher cell layer in the design hierarchy. The final chip layout was taped out for fabrication on November 29, 2010 and finished parts were received on July 7, 2011 after two manufacturing delays. Finished packaged parts were successfully verified for functionality based on SPICE simulations. The stability checkers were tested for flip-flop operation, glitch detection and late signal arrival detection. Configurable delay chains were tested to determine delay resolution and uniformity. Actual delay resolution and range measurements show a 3 to 4 times difference compared to simulated values. The Electric design template created from this project includes basic CMOS logic gates with uniform standard cell heights. The template contains a 40-pin pad ring cell along with the individual pad ring components. EE 431 students would be able to create custom chips that are compatible for fabrication via the MOSIS MEP service. In future work, the template design library can be expanded to include more logic gate variants of various inputs and drive strengths as well as more complex functional modules.