Este trabalho introduz o conceito de cortes k e cortes kl sobre um circuito mapeado, em uma representação netlist. Esta nova abordagem é derivada do conceito de cortes k e cortes kl sobre AIGs (and inverter graphs), respeitando as diferenças entre essas duas formas de representar um circuito. As principais diferenças são: (1) o número de entradas em um nodo do grafo, e (2) a presença de inversores e buffers de forma explícita no circuito mapeado. Um algoritmo para enumerar cortes k e cortes kl é proposto e implementado. A principal motivação de usar cortes kl sobre circuitos mapeados é para realizar otimizações locais na síntese lógica de circuitos digitais. A principal contribuição deste trabalho é uma abordagem nova de remapeamento iterativo, utilizando cortes kl, reduzindo a área do circuito e respeitando as restrições de temporização do circuito. O uso de portas lógicas complexas pode potencialmente reduzir a área total de um circuito, mas elas precisam ser escolhidas corretamente de forma a manter as restrições de temporização do circuito. Ferramentas comerciais de síntese lógica trabalham melhor com portas lógicas simples e não são capazes de explorar eventuais vantagens em utilizar portas lógicas complexas. A abordagem proposta de remapeamento iterativo utilizando cortes kl é capaz de explorar uma quantidade maior de portas lógicas com funções lógicas diferentes, reduzindo a área do circuito, e mantendo as restrições de temporização intactas ao fazer uma checagem STA (análise temporal estática). Resultados experimentais mostram uma redução de até 38% de área na parte combinacional de circuitos para um subconjunto de benchmarks IWLS 2005, quando comparados aos resultados de ferramentas comerciais de síntese lógica. Outra contribuição deste trabalho é um novo modelo de rendimento (yield) para fabricação de circuitos integrados (IC) digitais, considerando problemas de resolução da etapa de litografia como uma fonte de diminuição do yield. O uso de leiautes regulares pode melhorar bastante a resolução da etapa de litografia, mas existe um aumento de área significativo ao se introduzir a regularidade. Esta é a primeira abordagem que considera o compromisso (trade off) de portas lógicas com diferentes níveis de regularidade e diferentes áreas durante a síntese lógica, de forma a melhorar o yield do projeto. A ferramenta desenvolvida de remapeamento tecnológico utilizando cortes kl foi modificada de forma a utilizar esse modelo de yield como função custo, de forma a aumentar o número de boas amostras (dies) por lâmina de silício (wafer), com resultados promissores. / This work introduces the concept of k-cuts and kl-cuts on top of a mapped circuit in a netlist representation. Such new approach is derived from the concept of k-cuts and klcuts on top of AIGs (and inverter graphs), respecting the differences between these two circuit representations. The main differences are: (1) the number of allowed inputs for a logic node, and (2) the presence of explicit inverters and buffers in the netlist. Algorithms for enumerating k-cuts and kl-cuts on top of a mapped circuit are proposed and implemented. The main motivation to use kl-cuts on top mapped circuits is to perform local optimization in digital circuit logic synthesis. The main contribution of this work is a novel iterative remapping approach using klcuts, reducing area while keeping the timing constraints attained. The use of complex gates can potentially reduce the circuit area, but they have to be chosen wisely to preserve timing constraints. Logic synthesis commercial design tools work better with simple cells and are not capable of taking full advantage of complex cells. The proposed iterative remapping approach can exploit a larger amount of logic gates, reducing circuit area, and respecting global timing constraints by performing an STA (static timing analysis) check. Experimental results show that this approach is able to reduce up to 38% in area of the combinational portion of circuits for a subset of IWLS 2005 benchmarks, when compared to results obtained from logic synthesis commercial tools. Another contribution of this work is a novel yield model for digital integrated circuits (IC) manufacturing, considering lithography printability problems as a source of yield loss. The use of regular layouts can improve the lithography, but it results in a significant area overhead by introducing regularity. This is the first approach that considers the tradeoff of cells with different level of regularity and different area overhead during the logic synthesis, in order to improve overall design yield. The technology remapping tool based on kl-cuts developed was modified in order to use such yield model as cost function, improving the number of good dies per wafer, with promising interesting results.

Synthetic genetic regulatory networks (or genetic circuits) can operate in complex biochemical environments to process and manipulate biological information to produce a desired behavior. The ability to engineer such genetic circuits has wide-ranging applications in various fields such as therapeutics, energy, agriculture, and environmental remediation. However, engineering multilevel genetic circuits quickly and reliably is a big challenge in the field of synthetic biology. This difficulty can partly be attributed to the growing complexity of biology. But some of the predominant challenges include the absence of formal specifications -- that describe precise desired behavior of these biological systems, as well as a lack of computational and mathematical frameworks -- that enable rapid in-silico design and synthesis of genetic circuits. This thesis introduces two major frameworks to reliably design genetic circuits. The first implementation focuses on a framework that enables synthetic biologists to encode Boolean logic functions into living cells. Using high-level hardware description language to specify the desired behavior of a genetic logic circuit, this framework describes how, given a library of genetic gates, logic synthesis can be applied to synthesize a multilevel genetic circuit, while accounting for biological constraints such as 'signal matching', 'crosstalk', and 'genetic context effects'. This framework has been implemented in a tool called Cello, which was applied to design 60 circuits for Escherichia coli, where the circuit function was specified using Verilog code and transformed to a DNA sequence. Across all these circuits, 92% of the output states functioned as predicted. The second implementation focuses on a framework to design complex genetic systems where the focus is on how the system behaves over time instead of its behavior at steady-state. Using Signal Temporal Logic (STL) -- a formalism used to specify properties of dense-time real-valued signals, biologists can specify very precise temporal behaviors of a genetic system. The framework describes how genetic circuits that are built from a well characterized library of DNA parts, can be scored by quantifying the 'degree of robustness' of in-silico simulations against an STL formula. Using formal verification, experimental data can be used to validate these in-silico designs. In this framework, the design space is also explored to predict external controls (such as approximate small molecule concentrations) that might be required to achieve a desired temporal behavior. This framework has been implemented in a tool called Phoenix. / 2021-02-28T00:00:00Z

Most part of my thesis is devoted to efficient automated logic synthesis of oracle processors. These Oracle Processors are of interest to several modern technologies, including Scheduling and Allocation, Image Processing and Robot Vision, Computer Aided Design, Games and Puzzles, and Cellular Automata, but so far the most important practical application is to build logic circuits to solve various practical Constraint Satisfaction Problems in Intelligent Robotics. For instance, robot path planning can be reduced to Satisfiability. In short, an oracle is a circuit that has some proposition of solution on the inputs and answers yes/no to this proposition. In other language, it is a predicate or a concept-checking machine. Oracles have many applications in AI and theoretical computer science but so far they were not used much in hardware architectures. Systematic logic synthesis methodologies for oracle circuits were so far not a subject of a special research. It is not known how big advantages these processors will bring when compared to parallel processing with CUDA/GPU processors, or standard PC processing. My interest in this thesis is only in architectural and logic synthesis aspects and not in physical (technological) design aspects of these circuits. In future, these circuits will be realized using reversible, nano and some new technologies, but the interest in this thesis is not in the future realization technologies. We want just to answer the following question: Is there any speed advantage of the new oracle-based architectures, when compared with standard serial or parallel processors?

This work focuses on the usage of dominators in circuit graphs in order to reduce the complexity of synthesis and verification tasks. One of the contributions of this thesis is a new algorithm for computing multiple-vertex dominators in circuit graphs. Previous algorithms, based on single-vertex dominators suffer from their rare appearance in many circuits. The presented approach searches efficiently for multiple-vertex dominators in circuit graphs. It finds dominator relations, where algorithms for computing single-vertex dominators fail. Another contribution of this thesis is the application of dominators for combinational equivalence checking based on the arithmetic transform. Previous algorithms rely on representations providing an explicit or implicit disjoint function cover, which is usually excessive in memory requirements. The new algorithm allows a partitioned evaluation of the arithmetic transform directly on the circuit graph using dominator relations. The results show that the algorithm brings significant improvements in memory consumption for many benchmarks. Proper cuts are used in many areas of VLSI. They provide cut points, where a given problem can be split into two disjoint sub-problems. The algorithm proposed in this thesis efficiently detects proper cuts in a circuit graph and is based on a novel concept of a reduced dominator tree. The runtime of the algorithm is less than 0.4 seconds for the largest benchmark circuit. The final contribution of this thesis is the application of the proper cut algorithm as a structural method to decompose a Boolean function, represented by a circuit graph. In combination with a functional approach, it outperforms previous methods, which rely on functional decomposition only.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24748号 / 情博第836号 / 新制||情||140(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 湊 真一, 教授 橋本 昌宜, 教授 岡部 寿男 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

As complementary metal-oxide semiconductor (CMOS) technology faces more and more severe physical barriers down the path of continuously feature size scaling, innovative nano-scale devices and other post-CMOS technologies have been developed to enhance future circuit design and computation. These nanotechnologies have shown promising potentials to achieve magnitude improvement in performance and integration density. The substitution of CMOS transistors with nano-devices is expected to not only continue along the exponential projection of Moore's Law, but also raise significant challenges and opportunities, especially in the field of electronic design automation. The major obstacles that the designers are experiencing with emerging nanotechnology design include: i) the existing computer-aided design (CAD) approaches in the context of conventional CMOS Boolean design cannot be directly employed in the nanoelectronic design process, because the intrinsic electrical characteristics of many nano-devices are not best suited for Boolean implementations but demonstrate strong capability for implementing non-conventional logic such as threshold logic and reversible logic; ii) due to the density and size factors of nano-devices, the defect rate of nanoelectronic system is much higher than conventional CMOS systems, therefore existing design paradigms cannot guarantee design quality and lead to even worse result in high failure ratio. Motivated by the compelling potentials and design challenges of emerging post-CMOS technologies, this dissertation work focuses on fundamental design methodologies to effectively and efficiently achieve high quality nanoscale design. A novel programmable logic element (PLE) is first proposed to explore the versatile functionalities of threshold gates (TGs) and multi-threshold threshold gates (MTTGs). This PLE structure can realize all three- or four-variable logic functions through configuring binary control bits. This is the first single threshold logic structure that provides complete Boolean logic implementation. Based on the PLEs, a reconfigurable architecture is constructed to offer dynamic reconfigurability with little or no reconfiguration overhead, due to the intrinsic self-latching property of nanopipelining. Our reconfiguration data generation algorithm can further reduce the reconfiguration cost. To fully take advantage of such threshold logic design using emerging nanotechnologies, we also developed a combinational equivalence checking (CEC) framework for threshold logic design. Based on the features of threshold logic gates and circuits, different techniques of formulating a given threshold logic in conjunctive normal form (CNF) are introduced to facilitate efficient SAT-based verification. Evaluated with mainstream benchmarks, our hybrid algorithm, which takes into account both input symmetry and input weight order of threshold gates, can efficiently generate CNF formulas in terms of both SAT solving time and CNF generating time. Then the reversible logic synthesis problem is considered as we focus on efficient synthesis heuristics which can provide high quality synthesis results within a reasonable computation time. We have developed a weighted directed graph model for function representation and complexity measurement. An atomic transformation is constructed to associate the function complexity variation with reversible gates. The efficiency of our heuristic lies in maximally decreasing the function complexity during synthesis steps as well as the capability to climb out of local optimums. Thereafter, swarm intelligence, one of the machine learning techniques is employed in the space searching for reversible logic synthesis, which achieves further performance improvement. To tackle the high defect-rate during the emerging nanotechnology manufacturing process, we have developed a novel defect-aware logic mapping framework for nanowire-based PLA architecture via Boolean satisfiability (SAT). The PLA defects of various types are formulated as covering and closure constraints. The defect-aware logic mapping is then solved efficiently by using available SAT solvers. This approach can generate valid logic mapping with a defect rate as high as 20%. The proposed method is universally suitable for various nanoscale PLAs, including AND/OR, NOR/NOR structures, etc. In summary, this work provides some initial attempts to address two major problems confronting future nanoelectronic system designs: the development of electronic design automation tools and the reliability issues. However, there are still a lot of challenging open questions remain in this emerging and promising area. We hope our work can lay down stepstones on nano-scale circuit design optimization through exploiting the distinctive characteristics of emerging nanotechnologies. / Ph. D.

Verification is an important step for Integrated Circuit (IC) design. In fact, literature has reported that up to 70% of the design effort is spent on checking if the design is functionally correct. One of the core verification tasks is Equivalence Checking (EC), which attempts to check if two structurally different designs are functionally equivalent for all reachable states. Powerful equivalence checking can also provide opportunities for more aggressive logic optimizations, meeting different goals such as smaller area, better performance, etc. The success of Combinational Equivalence Checking (CEC) has laid a foundation to industry-level combinational logic synthesis and optimization. However, Sequential Equivalence Checking (SEC) still faces much challenge, especially for those complex circuits that have different state encodings and few internal signal equivalences. In this thesis, we propose a novel simulation-based multi-node inductive invariant generation and pruning technique to check the equivalence of sequential circuits that have different state encodings and very few equivalent signals between them. By first grouping flip-flops into smaller subsets to make it scalable for large designs, we then propose a constrained logic synthesis technique to prune potential multi-node invariants without inadvertently losing important constraints. Our pruning technique guarantees the same conclusion for different instances (proving SEC or not) compared to previous approaches in which merging of such potential invariants might lose important relations if the merged relation does not turn out to be a true invariant. Experimental results show that the smaller invariant set can be very effective for sequential equivalence checking of such hard SEC instances. Our approach is up to 20x-- faster compared to previous mining-based methods for larger circuits. / Master of Science

With significant research effort being directed towards designing lightweight cryptographic primitives, logical metrics such as gate count are extensively used in estimating their hardware quality. Specialized logic minimization tools have been built to make use of gate count as the primary optimization cost function. The first part of this thesis aims to investigate the effectiveness of such logical metrics in predicting hardware efficiency of corresponding circuits. Mapping a logical representation onto hardware depends on the standard cell technology used, and is driven by trade-offs between area, performance, and power. This work evaluates aforementioned parameters for circuits optimized for gate count, and compares them with a set of benchmark designs. Extensive analysis is performed over a wide range of frequencies at multiple levels of abstraction and system integration, to understand the different regions in the solution space where such logic minimization techniques are effective. A prototype System-on-Chip (SoC) is designed to benchmark the performance of these circuits on actual hardware. This SoC is built with an aim to include multiple other cryptographic blocks for analysis of their hardware efficiency. The second part of this thesis analyzes the overhead involved in integrating selected authenticated encryption ciphers onto an SoC, and explores different design alternatives for the same. Overall, this thesis is intended to serve as a comprehensive guideline on hardware factors that can be overlooked, but must be considered during logical-to-physical mapping and during the integration of standalone cryptographic blocks onto a complete system. / Master of Science / The proliferation of embedded smart devices for the Internet-of-Things necessitates a constant search for smaller and power-efficient hardware. The need to ensure security of such devices has been driving extensive research on lightweight cryptography, which focuses on minimizing the logic footprint of cryptographic hardware primitives. Different designs are optimized, evaluated, and compared based on the number of gates required to express them at a logical level of abstraction. The expectation is that circuits requiring fewer gates to represent their logic will be smaller and more efficient on hardware. However, converting a logical representation into a hardware circuit, known as “synthesis”, is not trivial. The logic is mapped to a “library” of hardware cells, and one of many possible solutions for a function is selected - a process driven by trade-offs between area, speed, and power consumption on hardware. Our work studies the impact of synthesis on logical circuits with minimized gate count. We evaluate the hardware quality of such circuits by comparing them with that of benchmark designs over a range of speeds. We wish to answer questions such as “At what speeds do logical metrics rightly predict area- and power-efficiency?”, and “What impact does this have after integrating cryptographic primitives onto a complete system?”. As part of this effort, we build a System-on-Chip in order to observe the efficiency of these circuits on actual hardware. This chip also includes recently developed ciphers for authenticated encryption. The second part of this thesis explores different ways of integrating these ciphers onto a system, to understand their effect on the ciphers’ compactness and performance. Our overarching aim is to provide a suitable reference on how synthesis and system integration affect the hardware quality of cryptographic blocks, for future research in this area.

Este trabalho apresenta a composição funcional (CF) como um novo paradigma para realização da síntese lógica de blocos combinacionais. CF usa uma abordagem ascendente para sintetizar funções Booleanas, sendo capaz de avaliar os custos das funções intermediárias e explorando dessa forma um grande número de combinações diferentes de funções candidatas. Há vantagens interessantes quando comparado à abordagem descendente da decomposição funcional. CF apresenta grande flexibilidade para criar algoritmos com resultados ótimos ou subótimos para diferentes aplicações. A estratégia proposta apresenta bons resultados para síntese de funções Booleanas visando diferentes tecnologias. CF é baseado nos seguintes princípios: (1) representação de funções lógicas como um par ligado com representações funcional e estrutural; (2) o algoritmo começa de um conjunto de funções iniciais; (3) funções mais simples são associadas para criar funções mais complexas; (4) existe uma ordem parcial que permite o uso da programação dinâmica; (5) um conjunto de funções permitidas pode ser mantido para reduzir o tempo de execução/consumo de memória. Este trabalho apresenta algoritmos de composição funcional para fatoração Booleana, incluindo fatoração ótima, fatoração considerando o operador OU-exclusivo, computação de cadeias mínimas de decisão e síntese de funções considerando somente portas lógicas majoritárias e inversores. / This work presents functional composition (FC) as a new paradigm for combinational logic synthesis. FC is a bottom-up approach to synthesize Boolean functions, being able to evaluate the cost of intermediate sub-functions, exploring a larger number of different candidate combinations. These are interesting advantages when compared to the top-down behavior of functional decomposition. FC presents great flexibility to implement algorithms with optimal or suboptimal results for different applications. The proposed strategy presents good results for the synthesis of Boolean functions targeting different technologies. FC is based on the following principles: (1) the representation of logic functions is done by a bonded pair of functional and structural representations; (2) the algorithm starts from a set of initial functions; (3) simpler functions are associated to create more complex ones; (4) there is a partial order, enabling dynamic programming; (5) a set of allowed functions can be used in order to reduce execution time/memory consumption. This work presents functional composition algorithms for Boolean factoring, including optimal factoring, Boolean factoring considering the exclusive-OR operator, minimum decision chain computation and synthesis of functions considering only majority and inverter logic gates.

Os avanços da indústria de semicondutores nas últimas décadas foram baseados fortemente na contínua redução de tamanho dos dispositivos CMOS fabricados. Os usos de dispositivos CMOS dependem profundamente da lógica de portas E/OU/INV. À medida que os dispositivos CMOS estão atingindo oslimites fisicos, pesquisadores aumento esforço para prolongar a vida útil da tecnologia CMOS. Também é necessário investigar dispositivos alternativos, que em muitos casos implicam no uso de operações lógicas básicas diferentes. Como as ferramentas comerciais de síntese não são capazes de manipular eficientemente estas tecnologias Esta tese de doutorado foca em produzir algoritmos eficientes para projeto de circuitos tanto em CMOS quanto em novas tecnologias, integrando estes algorithmos em fluxos de projeto. Para esta tarefa, aplicamos a técnica da composição functional, para sintetizar eficiente tanto em CMOS quanto em tecnologias emergentes. A composição funcional é uma abordagem de síntese de baixo para cima, provendo flexibilidade para implementar algoritmos com resultados ótimos ou sub-ótimos para diferentes tecnologias. A fim de investigar como a composição funcional se compara às abordagens de síntese estado-da-arte, propomos aplicar esse paradigma de síntese em seis cenários diferentes. Dois deles se concentram em circuitos baseados em CMOS e outros quatro em circuitos baseados em tecnologias emergentes. Em relação a circuitos baseados em CMOS, investigamos a composição funcional para fatoração de funções multi-saídas, aplicadas em um fluxo de resíntese. Também manipulamos funções aproximadas, a fim de sintetizar módulos de redundância tripla aproximada. No que diz respeito as tecnologias emergentes, exploramos a composição funcional através de diodos spintrônicos e outras abordagens promissoras com base em diferentes implementações de lógica: a lógica de limiar, lógica majoritária e lógica de implicação. Resultados apresentam uma melhoria considerável em relação aos métodos estadoda- arte tanto para aplicações CMOS quanto aplicações de tecnologias emergentes, demonstrando a capacidade de lidar com diferentes tecnologias e mostrando a possibilidade de melhorar tecnologias ainda não exploradas. / The advances in semiconductor industry over the last decades have been strongly based on continuous scaling down of dimensions in manufactured CMOS devices. The use of CMOS devices profoundly relies on AND/OR/Inverter logic. As the CMOS scaling is reaching its physical limits, researchers increase the effort to prolong the CMOS life. Also, it is necessary to investigate alternative devices, which in many cases implies the use of different basic logic operations. As the commercial synthesis tools are not able to handle these technologies efficiently, there is an opportunity to research alternative logic implementations better suited for these new devices. This thesis focuses on presenting efficient algorithms to design circuits in both CMOS and new technologies while integrating these algorithms into regular design flows. For this task, we apply the functional composition technique, to efficiently synthesize both CMOS and emerging technologies. The functional composition is a bottom-up synthesis approach, providing flexibility to implement algorithms with optimal or suboptimal results for different technologies. To investigate how the functional composition compares to the state-of-the-art synthesis methods, we propose to apply this synthesis paradigm into six different scenarios. Two of them focus on CMOS-based circuits, and other four are based on emerging technologies. Regarding CMOSbased circuits, we investigate functional composition to investigate multi-output factorization in a circuit resynthesis flow. Also, we manipulate approximate functions to synthesize approximate triple modular redundancy (ATMR) modules. Concerning emerging technologies, we explore functional composition over spin-diode circuits and other promising approaches based on different logic implementations: threshold logic, majority logic, and implication logic. Results present a considerable improvement over the state-of-the-art methods for both CMOS and emerging technologies applications, demonstrating the ability to handle different technologies and showing the possibility to improve technologies not explored yet.