Showing 1–24 of 24 results for author: Drechsler, R

AutoBench: Automatic Testbench Generation and Evaluation Using LLMs for HDL Design

Authors: Ruidi Qiu, Grace Li Zhang, Rolf Drechsler, Ulf Schlichtmann, Bing Li

Abstract: In digital circuit design, testbenches constitute the cornerstone of simulation-based hardware verification. Traditional methodologies for testbench generation during simulation-based hardware verification still remain partially manual, resulting in inefficiencies in testing various scenarios and requiring expensive time from designers. Large Language Models (LLMs) have demonstrated their potentia… ▽ More In digital circuit design, testbenches constitute the cornerstone of simulation-based hardware verification. Traditional methodologies for testbench generation during simulation-based hardware verification still remain partially manual, resulting in inefficiencies in testing various scenarios and requiring expensive time from designers. Large Language Models (LLMs) have demonstrated their potential in automating the circuit design flow. However, directly applying LLMs to generate testbenches suffers from a low pass rate. To address this challenge, we introduce AutoBench, the first LLM-based testbench generator for digital circuit design, which requires only the description of the design under test (DUT) to automatically generate comprehensive testbenches. In AutoBench, a hybrid testbench structure and a self-checking system are realized using LLMs. To validate the generated testbenches, we also introduce an automated testbench evaluation framework to evaluate the quality of generated testbenches from multiple perspectives. Experimental results demonstrate that AutoBench achieves a 57% improvement in the testbench pass@1 ratio compared with the baseline that directly generates testbenches using LLMs. For 75 sequential circuits, AutoBench successfully has a 3.36 times testbench pass@1 ratio compared with the baseline. The source codes and experimental results are open-sourced at this link: https://github.com/AutoBench/AutoBench △ Less

Submitted 4 July, 2024; originally announced July 2024.

In-Memory Mirroring: Cloning Without Reading

Authors: Simranjeet Singh, Ankit Bende, Chandan Kumar Jha, Vikas Rana, Rolf Drechsler, Sachin Patkar, Farhad Merchant

Abstract: In-memory computing (IMC) has gained significant attention recently as it attempts to reduce the impact of memory bottlenecks. Numerous schemes for digital IMC are presented in the literature, focusing on logic operations. Often, an application's description has data dependencies that must be resolved. Contemporary IMC architectures perform read followed by write operations for this purpose, which… ▽ More In-memory computing (IMC) has gained significant attention recently as it attempts to reduce the impact of memory bottlenecks. Numerous schemes for digital IMC are presented in the literature, focusing on logic operations. Often, an application's description has data dependencies that must be resolved. Contemporary IMC architectures perform read followed by write operations for this purpose, which results in performance and energy penalties. To solve this fundamental problem, this paper presents in-memory mirroring (IMM). IMM eliminates the need for read and write-back steps, thus avoiding energy and performance penalties. Instead, we perform data movement within memory, involving row-wise and column-wise data transfers. Additionally, the IMM scheme enables parallel cloning of entire row (word) with a complexity of $\mathcal{O}(1)$. Moreover, our analysis of the energy consumption of the proposed technique using resistive random-access memory crossbar and experimentally validated JART VCM v1b model. The IMM increases energy efficiency and shows 2$\times$ performance improvement compared to conventional data movement methods. △ Less

Submitted 4 July, 2024; v1 submitted 3 July, 2024; originally announced July 2024.

Comments: Accepted in IFIP/IEEE VLSI-SoC 2024

BinSym: Binary-Level Symbolic Execution using Formal Descriptions of Instruction Semantics

Authors: Sören Tempel, Tobias Brandt, Christoph Lüth, Rolf Drechsler

Abstract: BinSym is a framework for symbolic program analysis of software in binary form. Contrary to prior work, it operates directly on binary code instructions and does not require lifting them to an intermediate representation (IR). This is achieved by formulating the symbolic semantics on top of a formal description of binary code instruction semantics. By building on existing formal descriptions, BinS… ▽ More BinSym is a framework for symbolic program analysis of software in binary form. Contrary to prior work, it operates directly on binary code instructions and does not require lifting them to an intermediate representation (IR). This is achieved by formulating the symbolic semantics on top of a formal description of binary code instruction semantics. By building on existing formal descriptions, BinSym eliminates the manual effort required by prior work to implement transformations to an IR, thereby reducing the margin for errors. Furthermore, BinSym's symbolic semantics can be directly related to the binary code, which improves symbolic execution speed by reducing solver query complexity. △ Less

Submitted 5 April, 2024; originally announced April 2024.

Virtual-Peripheral-in-the-Loop : A Hardware-in-the-Loop Strategy to Bridge the VP/RTL Design-Gap

Authors: Sallar Ahmadi-Pour, Pascal Pieper, Rolf Drechsler

Abstract: Virtual Prototypes act as an executable specification model, offering a unified behavior reference model for SW and HW engineers. However, between the VP and the HW still exists a gap, as the step from an architectural level VP implementation on the Transaction Level Modeling to the Register Transfer Layer implementation is considerably big. Especially when a company wants to focus on their Unique… ▽ More Virtual Prototypes act as an executable specification model, offering a unified behavior reference model for SW and HW engineers. However, between the VP and the HW still exists a gap, as the step from an architectural level VP implementation on the Transaction Level Modeling to the Register Transfer Layer implementation is considerably big. Especially when a company wants to focus on their Unique Selling-Point, the HW Design Space Exploration and acceptance tests should start as early as possible. Traditionally, this can only start once the rest of the System-on-Chip is also implemented in the RTL. As SoCs consist of many common subsystems like processors, memories, and peripherals, this may impact the time-to-market considerably. This is avoidable, however: In this paper we propose a Hardware-in-the-Loop strategy that allows to bridge the gap between the VP and RTL design that empowers engineers to focus on their USP while leveraging an existing suite of TLM Intellectual Properties for the common base-system components. We show how VPs and partial RTL implementations of a SoC can be combined in a Hardware-in-the-Loop simulation environment utilizing Field-Programmable Gate Arrays. The proposed approach allows early DSE, validation, and verification of SoC subsystems, which bridges the TLM/RTL gap. We evaluate our approach with a lightweight implementation of the proposed protocol, and three case-studies with real-world peripherals and accelerators on HW. Furthermore, we assess the capabilities of our approach and offer practical considerations for engineers utilizing this HIL approach for SoC design; and finally propose further extensions that can boost the approach for specialized applications like high-performance accelerators and computation. △ Less

Submitted 1 November, 2023; originally announced November 2023.

Comments: 19 Pages, 6 figures, 2 tables, 5 listings

Experimental Validation of Memristor-Aided Logic Using 1T1R TaOx RRAM Crossbar Array

Authors: Ankit Bende, Simranjeet Singh, Chandan Kumar Jha, Tim Kempen, Felix Cüppers, Christopher Bengel, Andre Zambanini, Dennis Nielinger, Sachin Patkar, Rolf Drechsler, Rainer Waser, Farhad Merchant, Vikas Rana

Abstract: Memristor-aided logic (MAGIC) design style holds a high promise for realizing digital logic-in-memory functionality. The ability to implement a specific gate in a MAGIC design style hinges on the SET-to-RESET threshold ratio. The TaOx memristive devices exhibit distinct SET-to-RESET ratios, enabling the implementation of OR and NOT operations. As the adoption of the MAGIC design style gains moment… ▽ More Memristor-aided logic (MAGIC) design style holds a high promise for realizing digital logic-in-memory functionality. The ability to implement a specific gate in a MAGIC design style hinges on the SET-to-RESET threshold ratio. The TaOx memristive devices exhibit distinct SET-to-RESET ratios, enabling the implementation of OR and NOT operations. As the adoption of the MAGIC design style gains momentum, it becomes crucial to understand the breakdown of energy consumption in the various phases of its operation. This paper presents experimental demonstrations of the OR and NOT gates on a 1T1R crossbar array. Additionally, it provides insights into the energy distribution for performing these operations at different stages. Through our experiments across different gates, we found that the energy consumption is dominated by initialization in the MAGIC design style. The energy split-up is 14.8%, 85%, and 0.2% for execution, initialization, and read operations respectively. △ Less

Submitted 16 October, 2023; originally announced October 2023.

Comments: Accepted in VLSID 2024

MemSPICE: Automated Simulation and Energy Estimation Framework for MAGIC-Based Logic-in-Memory

Authors: Simranjeet Singh, Chandan Kumar Jha, Ankit Bende, Vikas Rana, Sachin Patkar, Rolf Drechsler, Farhad Merchant

Abstract: Existing logic-in-memory (LiM) research is limited to generating mappings and micro-operations. In this paper, we present~\emph{MemSPICE}, a novel framework that addresses this gap by automatically generating both the netlist and testbench needed to evaluate the LiM on a memristive crossbar. MemSPICE goes beyond conventional approaches by providing energy estimation scripts to calculate the precis… ▽ More Existing logic-in-memory (LiM) research is limited to generating mappings and micro-operations. In this paper, we present~\emph{MemSPICE}, a novel framework that addresses this gap by automatically generating both the netlist and testbench needed to evaluate the LiM on a memristive crossbar. MemSPICE goes beyond conventional approaches by providing energy estimation scripts to calculate the precise energy consumption of the testbench at the SPICE level. We propose an automated framework that utilizes the mapping obtained from the SIMPLER tool to perform accurate energy estimation through SPICE simulations. To the best of our knowledge, no existing framework is capable of generating a SPICE netlist from a hardware description language. By offering a comprehensive solution for SPICE-based netlist generation, testbench creation, and accurate energy estimation, MemSPICE empowers researchers and engineers working on memristor-based LiM to enhance their understanding and optimization of energy usage in these systems. Finally, we tested the circuits from the ISCAS'85 benchmark on MemSPICE and conducted a detailed energy analysis. △ Less

Submitted 9 September, 2023; originally announced September 2023.

Comments: Accepted in ASP-DAC 2024

Should We Even Optimize for Execution Energy? Rethinking Mapping for MAGIC Design Style

Authors: Simranjeet Singh, Chandan Kumar Jha, Ankit Bende, Phrangboklang Lyngton Thangkhiew, Vikas Rana, Sachin Patkar, Rolf Drechsler, Farhad Merchant

Abstract: Memristor-based logic-in-memory (LiM) has become popular as a means to overcome the von Neumann bottleneck in traditional data-intensive computing. Recently, the memristor-aided logic (MAGIC) design style has gained immense traction for LiM due to its simplicity. However, understanding the energy distribution during the design of logic operations within the memristive memory is crucial in assessin… ▽ More Memristor-based logic-in-memory (LiM) has become popular as a means to overcome the von Neumann bottleneck in traditional data-intensive computing. Recently, the memristor-aided logic (MAGIC) design style has gained immense traction for LiM due to its simplicity. However, understanding the energy distribution during the design of logic operations within the memristive memory is crucial in assessing such an implementation's significance. The current energy estimation methods rely on coarse-grained techniques, which underestimate the energy consumption of MAGIC-styled operations performed on a memristor crossbar. To address this issue, we analyze the energy breakdown in MAGIC operations and propose a solution that utilizes mapping from the SIMPLER MAGIC tool to achieve accurate energy estimation through SPICE simulations. In contrast to existing research that primarily focuses on optimizing execution energy, our findings reveal that the memristor's initialization energy in the MAGIC design style is, on average, 68x higher. We demonstrate that this initialization energy significantly dominates the overall energy consumption. By highlighting this aspect, we aim to redirect the attention of designers towards developing algorithms and strategies that prioritize optimizations in initializations rather than execution for more effective energy savings. △ Less

Submitted 7 July, 2023; originally announced July 2023.

Comments: Accepted to published in IEEE EMBEDDED SYSTEMS LETTER

Finite State Automata Design using 1T1R ReRAM Crossbar

Authors: Simranjeet Singh, Omar Ghazal, Chandan Kumar Jha, Vikas Rana, Rolf Drechsler, Rishad Shafik, Alex Yakovlev, Sachin Patkar, Farhad Merchant

Abstract: Data movement costs constitute a significant bottleneck in modern machine learning (ML) systems. When combined with the computational complexity of algorithms, such as neural networks, designing hardware accelerators with low energy footprint remains challenging. Finite state automata (FSA) constitute a type of computation model used as a low-complexity learning unit in ML systems. The implementat… ▽ More Data movement costs constitute a significant bottleneck in modern machine learning (ML) systems. When combined with the computational complexity of algorithms, such as neural networks, designing hardware accelerators with low energy footprint remains challenging. Finite state automata (FSA) constitute a type of computation model used as a low-complexity learning unit in ML systems. The implementation of FSA consists of a number of memory states. However, FSA can be in one of the states at a given time. It switches to another state based on the present state and input to the FSA. Due to its natural synergy with memory, it is a promising candidate for in-memory computing for reduced data movement costs. This work focuses on a novel FSA implementation using resistive RAM (ReRAM) for state storage in series with a CMOS transistor for biasing controls. We propose using multi-level ReRAM technology capable of transitioning between states depending on bias pulse amplitude and duration. We use an asynchronous control circuit for writing each ReRAM-transistor cell for the on-demand switching of the FSA. We investigate the impact of the device-to-device and cycle-to-cycle variations on the cell and show that FSA transitions can be seamlessly achieved without degradation of performance. Through extensive experimental evaluation, we demonstrate the implementation of FSA on 1T1R ReRAM crossbar. △ Less

Submitted 30 June, 2023; v1 submitted 26 April, 2023; originally announced April 2023.

Comments: Accepted by 21st IEEE Interregional NEWCAS Conference 2023 (NEWCAS 2023)

Lower Bound Proof for the Size of BDDs representing a Shifted Addition

Authors: Jan Kleinekathöfer, Alireza Mahzoon, Rolf Drechsler

Abstract: Decision Diagrams(DDs) are one of the most popular representations for boolean functions. They are widely used in the design and verification of circuits. Different types of DDs have been proven to represent important functions in polynomial space and some types (like Binary Decision Diagrams(BDDs)) also allow operations on diagrams in polynomial time. However, there is no type which was proven ca… ▽ More Decision Diagrams(DDs) are one of the most popular representations for boolean functions. They are widely used in the design and verification of circuits. Different types of DDs have been proven to represent important functions in polynomial space and some types (like Binary Decision Diagrams(BDDs)) also allow operations on diagrams in polynomial time. However, there is no type which was proven capable of representing arbitrary boolean functions in polynomial space with regard to the input size. In particular for BDDs it is long known that integer multiplication is one of the functions, where the output BDDs have exponential size. In this paper, we show that this also holds for an integer addition where one of the operands is shifted to the right by an arbitrary value. We call this function the Shifted Addition. Our interest in this function is motivated through its occurrence during the floating point addition. △ Less

Submitted 26 September, 2022; originally announced September 2022.

Simulation-based Verification of SystemC-based VPs at the ESL

Authors: Mehran Goli, Rolf Drechsler

Abstract: SystemC-based Virtual Prototypes (VPs) at the Electronic System Level (ESL) are increasingly adopted by the semiconductor industry. The main reason is that VPs are much earlier available, and their simulation is orders of magnitude faster in comparison to the hardware models at lower levels of abstraction (e.g. RTL). This leads designers to use VPs as reference models for early design verification… ▽ More SystemC-based Virtual Prototypes (VPs) at the Electronic System Level (ESL) are increasingly adopted by the semiconductor industry. The main reason is that VPs are much earlier available, and their simulation is orders of magnitude faster in comparison to the hardware models at lower levels of abstraction (e.g. RTL). This leads designers to use VPs as reference models for early design verification. Hence, the correctness of VPs is of utmost importance as undetected errors may propagate to less abstract levels in the design process, increasing the fixing cost and effort. In this paper, we introduce a comprehensive simulation-based verification approach to automatically validate the simulation behavior of a given SystemC-based VP against both the TLM-2.0 rules and its specifications, i.e. functional and timing behavior of communications in the VP. △ Less

Submitted 16 February, 2022; originally announced February 2022.

ALF -- A Fitness-Based Artificial Life Form for Evolving Large-Scale Neural Networks

Authors: Rune Krauss, Marcel Merten, Mirco Bockholt, Rolf Drechsler

Abstract: Machine Learning (ML) is becoming increasingly important in daily life. In this context, Artificial Neural Networks (ANNs) are a popular approach within ML methods to realize an artificial intelligence. Usually, the topology of ANNs is predetermined. However, there are problems where it is difficult to find a suitable topology. Therefore, Topology and Weight Evolving Artificial Neural Network (TWE… ▽ More Machine Learning (ML) is becoming increasingly important in daily life. In this context, Artificial Neural Networks (ANNs) are a popular approach within ML methods to realize an artificial intelligence. Usually, the topology of ANNs is predetermined. However, there are problems where it is difficult to find a suitable topology. Therefore, Topology and Weight Evolving Artificial Neural Network (TWEANN) algorithms have been developed that can find ANN topologies and weights using genetic algorithms. A well-known downside for large-scale problems is that TWEANN algorithms often evolve inefficient ANNs and require long runtimes. To address this issue, we propose a new TWEANN algorithm called Artificial Life Form (ALF) with the following technical advancements: (1) speciation via structural and semantic similarity to form better candidate solutions, (2) dynamic adaptation of the observed candidate solutions for better convergence properties, and (3) integration of solution quality into genetic reproduction to increase the probability of optimization success. Experiments on large-scale ML problems confirm that these approaches allow the fast solving of these problems and lead to efficient evolved ANNs. △ Less

Submitted 16 April, 2021; originally announced April 2021.

Polynomial Circuit Verification using BDDs

Authors: Rolf Drechsler

Abstract: Verification is one of the central tasks during circuit design. While most of the approaches have exponential worst-case behaviour, in the following techniques are discussed for proving polynomial circuit verification based on Binary Decision Diagrams (BDDs). It is shown that for circuits with specific structural properties, like e.g. tree-like circuits, and circuits based on multiplexers derived… ▽ More Verification is one of the central tasks during circuit design. While most of the approaches have exponential worst-case behaviour, in the following techniques are discussed for proving polynomial circuit verification based on Binary Decision Diagrams (BDDs). It is shown that for circuits with specific structural properties, like e.g. tree-like circuits, and circuits based on multiplexers derived from BDDs complete formal verification can be carried out in polynomial time and space. △ Less

Submitted 7 April, 2021; originally announced April 2021.

Comments: 8 pages, 5 figures

MSC Class: 68W30; 68M07; 68W35 ACM Class: B.6.3; B.2.1; F.2.2

Pick the Right Edge Device: Towards Power and Performance Estimation of CUDA-based CNNs on GPGPUs

Authors: Christopher A. Metz, Mehran Goli, Rolf Drechsler

Abstract: The emergence of Machine Learning (ML) as a powerful technique has been helping nearly all fields of business to increase operational efficiency or to develop new value propositions. Besides the challenges of deploying and maintaining ML models, picking the right edge device (e.g., GPGPUs) to run these models (e.g., CNN with the massive computational process) is one of the most pressing challenges… ▽ More The emergence of Machine Learning (ML) as a powerful technique has been helping nearly all fields of business to increase operational efficiency or to develop new value propositions. Besides the challenges of deploying and maintaining ML models, picking the right edge device (e.g., GPGPUs) to run these models (e.g., CNN with the massive computational process) is one of the most pressing challenges faced by organizations today. As the cost of renting (on Cloud) or purchasing an edge device is directly connected to the cost of final products or services, choosing the most efficient device is essential. However, this decision making requires deep knowledge about performance and power consumption of the ML models running on edge devices that must be identified at the early stage of ML workflow. In this paper, we present a novel ML-based approach that provides ML engineers with the early estimation of both power consumption and performance of CUDA-based CNNs on GPGPUs. The proposed approach empowers ML engineers to pick the most efficient GPGPU for a given CNN model at the early stage of development. △ Less

Submitted 2 February, 2021; originally announced February 2021.

Comments: Presented at DATE Friday Workshop on System-level Design Methods for Deep Learning on Heterogeneous Architectures (SLOHA 2021) (arXiv:2102.00818)

Report number: SLOHA/2021/06

PolyAdd: Polynomial Formal Verification of Adder Circuits

Authors: Rolf Drechsler

Abstract: Only by formal verification approaches functional correctness can be ensured. While for many circuits fast verification is possible, in other cases the approaches fail. In general no efficient algorithms can be given, since the underlying verification problem is NP-complete. In this paper we prove that for different types of adder circuits polynomial verification can be ensured based on BDDs. Whil… ▽ More Only by formal verification approaches functional correctness can be ensured. While for many circuits fast verification is possible, in other cases the approaches fail. In general no efficient algorithms can be given, since the underlying verification problem is NP-complete. In this paper we prove that for different types of adder circuits polynomial verification can be ensured based on BDDs. While it is known that the output functions for addition are polynomially bounded, we show in the following that the entire construction process can be carried out in polynomial time. This is shown for the simple Ripple Carry Adder, but also for fast adders like the Conditional Sum Adder and the Carry Look Ahead Adder. Properties about the adder function are proven and the core principle of polynomial verification is described that can also be extended to other classes of functions and circuit realizations. △ Less

Submitted 3 April, 2021; v1 submitted 7 September, 2020; originally announced September 2020.

Comments: 7 pages, 8 figures, published at 24th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS), 2021

MSC Class: 68W30; 68M07; 68W35 ACM Class: B.6.3; B.2.1; F.2.2

One Additional Qubit is Enough: Encoded Embeddings for Boolean Components in Quantum Circuits

Authors: Alwin Zulehner, Philipp Niemann, Rolf Drechsler, Robert Wille

Abstract: Research on quantum computing has recently gained significant momentum since first physical devices became available. Many quantum algorithms make use of so-called oracles that implement Boolean functions and are queried with highly superposed input states in order to evaluate the implemented Boolean function for many different input patterns in parallel. To simplify or enable a realization of the… ▽ More Research on quantum computing has recently gained significant momentum since first physical devices became available. Many quantum algorithms make use of so-called oracles that implement Boolean functions and are queried with highly superposed input states in order to evaluate the implemented Boolean function for many different input patterns in parallel. To simplify or enable a realization of these oracles in quantum logic in the first place, the Boolean reversible functions to be realized usually need to be broken down into several non-reversible sub-functions. However, since quantum logic is inherently reversible, these sub-functions have to be realized in a reversible fashion by adding further qubits in order to make the output patterns distinguishable (a process that is also known as embedding). This usually results in a significant increase of the qubits required in total. In this work, we show how this overhead can be significantly reduced by utilizing coding. More precisely, we prove that one additional qubit is always enough to embed any non-reversible function into a reversible one by using a variable-length encoding of the output patterns. Moreover, we characterize those functions that do not require an additional qubit at all. The made observations show that coding often allows one to undercut the usually considered minimum of additional qubits in sub-functions of oracles by far. △ Less

Submitted 5 June, 2019; originally announced June 2019.

fiction: An Open Source Framework for the Design of Field-coupled Nanocomputing Circuits

Authors: Marcel Walter, Robert Wille, Frank Sill Torres, Daniel Große, Rolf Drechsler

Abstract: As a class of emerging post-CMOS technologies, Field-coupled Nanocomputing (FCN) devices promise computation with tremendously low energy dissipation. Even though ground breaking advances in several physical implementations like Quantum-dot Cellular Automata (QCA) or Nanomagnet Logic (NML) have been made in the last couple of years, design automation for FCN is still in its infancy and often still… ▽ More As a class of emerging post-CMOS technologies, Field-coupled Nanocomputing (FCN) devices promise computation with tremendously low energy dissipation. Even though ground breaking advances in several physical implementations like Quantum-dot Cellular Automata (QCA) or Nanomagnet Logic (NML) have been made in the last couple of years, design automation for FCN is still in its infancy and often still relies on manual labor. In this paper, we present an open source framework called fiction for physical design and technology mapping of FCN circuits. Its efficient data structures, state-of-the-art algorithms, and extensibility provide a basis for future research in the community. △ Less

Submitted 7 May, 2019; originally announced May 2019.

Near Zero-Energy Computation Using Quantum-dot Cellular Automata

Authors: Frank Sill Torres, Philipp Niemann, Robert Wille, Rolf Drechsler

Abstract: Near zero-energy computing describes the concept of executing logic operations below the (kBT ln 2) energy limit. Landauer discussed that it is impossible to break this limit as long as the computations are performed in the conventional, non-reversible way. But even if reversible computations were performed, the basic energy needed for operating circuits realized in conventional technologies is st… ▽ More Near zero-energy computing describes the concept of executing logic operations below the (kBT ln 2) energy limit. Landauer discussed that it is impossible to break this limit as long as the computations are performed in the conventional, non-reversible way. But even if reversible computations were performed, the basic energy needed for operating circuits realized in conventional technologies is still far above the (kBT ln 2) energy limit, i.e. the circuits do not operate physically reversible. In contrast, novel nanotechnologies like Quantum-dot Cellular Automata (QCA) allow for computations with very low energy dissipation and, hence, are promising candidates for breaking this limit. Accordingly, the design of reversible QCA circuits is an active field of research. But whether QCA in general (and the proposed circuits in particular) are indeed able to operate in a logically and physically reversible fashion is unknown thus far, because neither physical realizations nor appropriate simulation approaches were available yet. In this work, we address this gap by utilizing an established theoretical model that has been implemented in a physics simulator enabling a precise consideration of how energy is dissipated in QCA designs. Our results provide strong evidence that QCA is indeed a suitable technology for near zero-energy computing. Further, the first design of a logically and physically reversible adder circuit is presented which serves as proof-of-concept for future circuits with the ability of near zero-energy computing. △ Less

Submitted 17 August, 2020; v1 submitted 9 November, 2018; originally announced November 2018.

On the Difficulty of Inserting Trojans in Reversible Computing Architectures

Authors: Xiaotong Cui, Samah Saeed, Alwin Zulehner, Robert Wille, Rolf Drechsler, Kaijie Wu, Ramesh Karri

Abstract: Fabrication-less design houses outsource their designs to 3rd party foundries to lower fabrication cost. However, this creates opportunities for a rogue in the foundry to introduce hardware Trojans, which stay inactive most of the time and cause unintended consequences to the system when triggered. Hardware Trojans in traditional CMOS-based circuits have been studied and Design-for-Trust (DFT) tec… ▽ More Fabrication-less design houses outsource their designs to 3rd party foundries to lower fabrication cost. However, this creates opportunities for a rogue in the foundry to introduce hardware Trojans, which stay inactive most of the time and cause unintended consequences to the system when triggered. Hardware Trojans in traditional CMOS-based circuits have been studied and Design-for-Trust (DFT) techniques have been proposed to detect them. Different from traditional circuits in many ways, reversible circuits implement one-to-one, bijective input/output mappings. We will investigate the security implications of reversible circuits with a particular focus on susceptibility to hardware Trojans. We will consider inherently reversible circuits and non-reversible functions embedded in reversible circuits. △ Less

Submitted 1 May, 2017; originally announced May 2017.

Comments: This is a 10 pages paper with 12 figures. The paper is submitted to the International Test Conference 2017 and still under review

Towards Reverse Engineering Reversible Logic

Authors: Samah Mohamed Saeed, Xiaotong Cui, Robert Wille, Alwin Zulehner, Kaijie Wu, Rolf Drechsler, Ramesh Karri

Abstract: Reversible logic has two main properties. First, the number of inputs is equal to the number of outputs. Second, it implements a one-to-one mapping; i.e., one can reconstruct the inputs from the outputs. These properties enable its applications in building quantum computing architectures. In this paper, we study reverse engineering of reversible logic circuits, including reverse engineering of n… ▽ More Reversible logic has two main properties. First, the number of inputs is equal to the number of outputs. Second, it implements a one-to-one mapping; i.e., one can reconstruct the inputs from the outputs. These properties enable its applications in building quantum computing architectures. In this paper, we study reverse engineering of reversible logic circuits, including reverse engineering of non-reversible functions embedded into reversible circuits. We propose the number of embeddings of non-reversible functions into a reversible circuit as the security metric for reverse engineering. We analyze the security benefits of automatic synthesis of reversible circuits. We use our proposed security metric to show that the functional synthesis approaches yield reversible circuits that are more resilient to reverse engineering than the structural synthesis approaches. Finally, we propose scrambling of the inputs and outputs of a reversible circuit to thwart reverse engineering. △ Less

Submitted 1 December, 2017; v1 submitted 26 April, 2017; originally announced April 2017.

Ancilla-free synthesis of large reversible functions using binary decision diagrams

Authors: Mathias Soeken, Laura Tague, Gerhard W. Dueck, Rolf Drechsler

Abstract: The synthesis of reversible functions has been an intensively studied research area in the last decade. Since almost all proposed approaches rely on representations of exponential size (such as truth tables and permutations), they cannot be applied efficiently to reversible functions with more than 15 variables. In this paper, we propose an ancilla-free synthesis approach based on Young subgroup… ▽ More The synthesis of reversible functions has been an intensively studied research area in the last decade. Since almost all proposed approaches rely on representations of exponential size (such as truth tables and permutations), they cannot be applied efficiently to reversible functions with more than 15 variables. In this paper, we propose an ancilla-free synthesis approach based on Young subgroups using symbolic function representations that can efficiently be implemented with binary decision diagrams (BDDs). As a result, the algorithm not only allows to synthesize large reversible functions without adding extra lines, called ancilla, but also leads to significantly smaller circuits compared to existing approaches. △ Less

Submitted 18 August, 2014; originally announced August 2014.

Comments: 25 pages, 15 figures

Embedding of Large Boolean Functions for Reversible Logic

Authors: Mathias Soeken, Robert Wille, Oliver Keszocze, D. Michael Miller, Rolf Drechsler

Abstract: Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions… ▽ More Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions are considered. In this paper, we study this issue. We prove that determining an optimal embedding is coNP-hard already for restricted cases. Then, we propose heuristic and exact methods for determining both the number of additional lines as well as a corresponding embedding. For the approaches we considered sums of products and binary decision diagrams as function representations. Experimental evaluations show the applicability of the approaches for large functions. Consequently, the reversible embedding of large functions is enabled as a precursor to subsequent synthesis. △ Less

Submitted 15 August, 2014; originally announced August 2014.

Comments: 13 pages, 10 figures

A framework for reversible circuit complexity

Authors: Mathias Soeken, Nabila Abdessaied, Rolf Drechsler

Abstract: Reversible single-target gates are a generalization of Toffoli gates which are a helpful formal representation for the description of synthesis algorithms but are too general for an actual implementation based on some technology. There is an exponential lower bound on the number of Toffoli gates required to implement any reversible function, however, there is also a linear upper bound on the numbe… ▽ More Reversible single-target gates are a generalization of Toffoli gates which are a helpful formal representation for the description of synthesis algorithms but are too general for an actual implementation based on some technology. There is an exponential lower bound on the number of Toffoli gates required to implement any reversible function, however, there is also a linear upper bound on the number of single-target gates which can be proven using a constructive proof based on a former presented synthesis algorithm. Since single-target gates can be mapped to a cascade of Toffoli gates, this synthesis algorithm provides an interesting framework for reversible circuit complexity. The paper motivates this framework and illustrates first possible applications based on it. △ Less

Submitted 22 July, 2014; originally announced July 2014.

Comments: 6 pages, 4 figures, accepted for Int'l Workshop on Boolean Problems 2014

On quantum circuits employing roots of the Pauli matrices

Authors: Mathias Soeken, D. Michael Miller, Rolf Drechsler

Abstract: The Pauli matrices are a set of three 2x2 complex Hermitian, unitary matrices. In this article, we investigate the relationships between certain roots of the Pauli matrices and how gates implementing those roots are used in quantum circuits. Techniques for simplifying such circuits are given. In particular, we show how those techniques can be used to find a circuit of Clifford+T gates starting fro… ▽ More The Pauli matrices are a set of three 2x2 complex Hermitian, unitary matrices. In this article, we investigate the relationships between certain roots of the Pauli matrices and how gates implementing those roots are used in quantum circuits. Techniques for simplifying such circuits are given. In particular, we show how those techniques can be used to find a circuit of Clifford+T gates starting from a circuit composed of gates from the well studied NCV library. △ Less

Submitted 12 August, 2013; originally announced August 2013.

Comments: 7 pages, 1 figure

Journal ref: Phys. Rev. A 88, 042322 (2013)

Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures

Authors: Mehdi Saeedi, Robert Wille, Rolf Drechsler

Abstract: While a couple of impressive quantum technologies have been proposed, they have several intrinsic limitations which must be considered by circuit designers to produce realizable circuits. Limited interaction distance between gate qubits is one of the most common limitations. In this paper, we suggest extensions of the existing synthesis flow aimed to realize circuits for quantum architectures with… ▽ More While a couple of impressive quantum technologies have been proposed, they have several intrinsic limitations which must be considered by circuit designers to produce realizable circuits. Limited interaction distance between gate qubits is one of the most common limitations. In this paper, we suggest extensions of the existing synthesis flow aimed to realize circuits for quantum architectures with linear nearest neighbor (LNN) interaction. To this end, a template matching optimization, an exact synthesis approach, and two reordering strategies are introduced. The proposed methods are combined as an integrated synthesis flow. Experiments show that by using the suggested flow, quantum cost can be improved by more than 50% on average. △ Less

Submitted 5 September, 2012; v1 submitted 28 October, 2011; originally announced October 2011.

Comments: 14 pages, 11 figures, 3 tables

Journal ref: Quantum Information Processing, Vol. 10, No. 3, pp. 355-377, 2011