Only a few mathematically proven bounds on the runtime behavior of Ant Colony Optimization (ACO) have been reported. To alleviate this situation, we investigate the ACO variant we call Bivalent ACO ( BACO ) that uses exactly two pheromone values. We provide and successfully apply a Markov chain-based approach to calculate the expected optimization time, i.e., the expected number of iterations until an adjustable quality \(\kappa\) of the solution is reached and the algorithm terminates. This approach allows to derive exact formulas for the expected optimization time and its variance for the problems Sorting and LeadingOnes . It turns out that the ratio of the two pheromone values significantly governs the runtime behavior of BACO . We present tight bounds \(\Theta(\kappa\cdot n^{2})\) for Sorting with a specifically chosen objective function and \(\Theta(\kappa\cdot n)\) for LeadingOnes . We show that, despite having a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, the known bound on the expected optimization time for the problem LeadingOnes ( \(\mathcal{O}(n^{2})\) ) can be re-produced. Experiments validate our theoretical findings.

Approximate Computing is a design paradigm that trades off computational accuracy for gains in non-functional aspects such as reduced area, increased computation speed, or power reduction. The latter is of special interest in the field of Internet of Things. In this paper we present SAS, a framework for symmetry-based approximate logic synthesis. Given a Boolean multi-output function, SAS approximates it by (partially) replacing its output functions by symmetric functions with minimal Hamming distance. The framework is capable of restricting the introduced error with respect to a parameterized error metric that covers many real-word use-cases.

Spiking Neural Networks (SNNs) are a promising class of algorithms for hardware acceleration, even outper-forming traditional neural networks in some cases. However, existing SNN accelerator approaches do not perform exhaustive explorations of possible network parameters, including neuron models and spike codings; instead, they often focus on a single network setting and a given fixed hardware architecture for its implementation. Chisel is a hardware construction language that allows the modeling of high-level abstractions from the Register-Transfer Level (RTL) and above. It promises a more transparent and more performance-predictable approach than compiler-based methodologies, like High-Level Synthesis (HLS). In this paper, we propose a novel multi-layer Domain-Specific Language (DSL) for SNN accelerator design based on Chisel, allowing for design space explorations that vary neuron models, spike codings, reset behaviors, and even accelerator topologies. Moreover, we propose an SNN accelerator generation framework using this DSL, which covers training to deployment. We explore and evaluate implementations and provide results regarding execution time, Field-Programmable Gate Array (FPGA) resource usage, power consumption, and accuracy.

Most digital hardware is described in hardware description languages, such as VHDL and (System)Verilog. These languages provide limited programming models for hardware construction despite receiving regular updates and extensions. Chisel defines itself as a hardware construction language, which means it shall permit more than the mere description of digital circuits. However, programmatic hardware generation is not new. Scripting languages like Perl generate VHDL or Verilog code from sources like Excel spreadsheets. Chisel, embedded in the general-purpose language Scala, lends itself to writing hardware generators in that language. We consider this Chisel-Scala ecosystem an ideal starting point for programming hardware generators and illustrate this point with examples using various programming models. We are confident that proven technologies from the software development world can be leveraged in the hardware design domain to improve hardware designers' productivity to build the next billion transistor chips.

So far, only few bounds on the runtime behavior of Ant Colony Optimization (ACO) have been reported. To alleviate this situation, we investigate the ACO variant we call Bivalent ACO (BACO) that uses exactly two pheromone values. We provide and successfully apply a new Markov chain-based approach to calculate the expected optimization time, i. e., the expected number of iterations until the algorithm terminates. This approach allows to derive exact formulæ for the expected optimization time for the problems Sorting and LeadingOnes. It turns out that the ratio of the two pheromone values significantly governs the runtime behavior of BACO. To the best of our knowledge, for the first time, we can present tight bounds for Sorting (Θ(n3)) with a specifically chosen objective function and prove the missing lower bound Ω(n2) for LeadingOnes which, thus, is tightly bounded by Θ(n2). We show that despite we have a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, known bounds on the expected optimization time for the problems OneMax (O(n log n)) and LeadingOnes (O(n2)) can be re-produced as a by-product of our approach. Experiments validate our theoretical findings.

The number of Digital Signal Processor (DSP) resources available in Field Programmable Gate Arrays (FPGAs) is often quite limited. Therefore, full utilization of available DSP resources for the computationally intensive parts of an algorithm is paramount for optimizing the non-functional properties of an implementation (i.e., performance, power, and area). The DSPs available in Xilinx devices implement large bit width operators (i.e. a 48-bit accumulator or a 18 × 27 multiplier). However, using such a DSP for low-precision quantized data (as is common in image processing or machine learning applications) leaves the DSP resources underutilized. As a remedy, a method has been proposed to pack and compute four 4-bit multiplications on a single DSP in a single clock cycle. This paper presents a generalization of this scheme to arbitrary bit widths and number of multiplications. We also demonstrate that the previously proposed approach leads to errors (Mean Absolute Error (MAE) = 0.37). Furthermore, we explain where these errors come from and how they can be corrected. On top, we introduce a novel approximate method called “Overpacking” which allows to squeeze even more multiplications into a single DSP at the cost of small errors (MAE = 0.47). Overpacking allows to squeeze six 4-bit multiplications into a single DSP compared to just four in the literature. Finally, we introduce an alternative method for packing multiple small-bit width additions into a single 48-bit accumulator for use in applications such as Spiking Neural Networks.

Spiking neural networks (SNNs) compute in an event-based manner to achieve a more efficient computation than standard neural networks. In SNNs, neuronal outputs are not encoded as real-valued activations but as sequences of binary spikes. The motivation of using SNNs over conventional neural networks is rooted in the special computational aspects of spike-based processing, especially the high degree of sparsity of spikes. Well-established implementations of convolutional neural networks (CNNs) feature large spatial arrays of processing elements (PEs) that remain highly underutilized in the face of activation sparsity. We propose a novel architecture optimized for the processing of convolutional SNNs (CSNNs) featuring a high degree of sparsity. The proposed architecture consists of an array of PEs of the size of the kernel of a convolution and an intelligent spike queue that provides a high PE utilization. A constant flow of spikes is ensured by compressing the feature maps into queues that can then be processed spike-by-spike. This compression is performed at run-time, leading to a self-timed schedule. This allows the processing time to scale with the number of spikes. Also, a novel memory organization scheme is introduced to efficiently store and retrieve the membrane potentials of the individual neurons using multiple small parallel on-chip RAMs. Each RAM is hardwired to its PE, reducing switching circuitry. We implemented the proposed architecture on an FPGA and achieved a significant speedup compared to previously proposed SNN implementations (~10 times) while needing less hardware resources and maintaining a higher energy efficiency (~15 times).

Quantum computers exploit quantum effects in a controlled manner in order to efficiently solve problems that are very hard to address on classical computers. The ion-trap-based technology is a particularly advanced concept of realizing quantum computers with advantages with respect to physical realization and fault-tolerance. Accordingly, several physical design methods aiming at realizing quantum circuits to corresponding architectures have been proposed. However, all these methods are heuristic and cannot guarantee minimality. In this work, we propose a solution which can generate exact physical designs, i.e., solutions which require a minimal number of time steps. To this end, satisfiability solvers are utilized. Experimental evaluations confirm that, despite the underlying computational complexity of the problem, this allows to generate minimal physical designs for several quantum circuits for the first time.

Digital microfluidics biochips are a promising emerging technology that provides fluidic experimental capabilities on a chip (i.e., following the lab-on-a-chip paradigm). However, the design of such biochips still constitutes a challenging task that is usually tackled by multiple individual design steps, such as binding, scheduling, placement, and routing. Performing these steps consecutively may lead to design gaps and infeasible results. To address these shortcomings, the concept of one-pass design for digital microfluidics biochips has recently been proposed—a holistic approach avoiding the design gaps by considering the whole synthesis process as large. But implementations of this concept available thus far suffer from either high computational effort or costly results. In this article, we present an efficient one-pass solution that is runtime efficient (i.e., rarely needing more than a second to successfully synthesize a design) while, at the same time, producing better results than previously published heuristic approaches. Experimental results confirm the benefits of the proposed solution and allow for realizing really large assays composed of thousands of operations in reasonable runtime.

For many embedded applications, non-functional requirements such as safety, reliability, and execution time must be guaranteed in tight bounds on a given multi-core platform. Here, jitter in non-functional program execution qualities is caused either by outer influences such as faults injected by the environment, but can be induced also from the system management software itself, including thread-to-core mapping, scheduling and power management. A second huge source of variability typically stems from data-dependent workloads. In this paper, we classify and present techniques to enforce nonfunctional execution properties on multi-core platforms. Based on a static design space exploration and analysis of influences of variability of non-functional properties, enforcement strategies are generated to guide the execution of periodically executed applications in given requirement corridors. Using the case study of a complex image streaming application, we show that by controlling DVFS settings of cores proactively, not only tight execution times, but also reliability requirements may be enforced dynamically while trying to minimize energy consumption.

Most approximate logic synthesis techniques successively apply local approximate transformations to Boolean circuits. Naturally, an efficient, robust, and scalable error estimation technique is due. This paper addresses this problem by propagating error probabilities within a network of circuits, each circuit being described by an approximated Boolean function. We specifically tackle error rate, that is, the likelihood of a logic network evaluating to an erroneous output. Our simulation-free error rate estimation technique is fully accurate when there are no mutual dependencies among signals in the Boolean network-also known as fanout-reconvergence-and shows a neglectable inaccuracy lying within 1% with respect to exhaustively simulated values for benchmark designs including signal correlations. Moreover, our methodology is capable of computing the error rate in the order of milliseconds for every tested benchmark, allowing the proposed error analysis to be applied during design space exploration. For comparison, we finally applied our methodology to a state-of-the-art approximate logic synthesis framework showing its superiority in terms of quality and runtime.

Approximate Computing is a design paradigm that trades off computational accuracy for gains in non-functional aspects such as reduced area, increased computation speed, or power reduction. Computing the error of the approximated design is an essential step to determine its quality. The computation time for determining the error can become very large, effectively rendering the entire logic approximation procedure infeasible.As a remedy, we present methods to accelerate the computation of error metric computations by (a) exploiting structural information and (b) computing estimates of the metrics for multi-output Boolean functions represented as BDDs. We further present a novel greedy, bucket-based BDD minimization framework employing the newly proposed error metric computations to produce Pareto-optimal solutions with respect to BDD size and multiple error metrics. The applicability of the proposed minimization framework is demonstrated by an experimental evaluation. We can report considerable speedups while, at the same time, creating high-quality approximated BDDs.

With the advent of gated quantum computers and regular structures of the qubit layout, methods for placement, routing, noise estimation and logic to hardware mapping become imminently required. In this paper, we propose a method for quantum circuit layout that is intended to solve such problems when mapping a quantum circuit to a quantum computer. The proposed method starts by building a Circuit Interaction Graph (CIG) that represents the ideal hardware layout minimizing the distance and path length between the individual qubits. The CIG is also used to introduce a qubit noise model. Once constructed, the CIG is iteratively reduced to a given architecture (qubit coupling model) specifying the neighborhood, qubits, priority and qubits noise. The introduced constraints allow to additionally reduce the graph according to preferred weights of desired properties. The proposed method is verified and tested on a set of standard benchmarks.

We present an approach to simplify the task of extracting assertions from specifications given in natural language. Our goal is to accept and understand a broad range of linguistic variation, allowing the author of the natural language specifications to express herself freely. To enable this, we leverage the Dialogflow framework from Google. Dialogflow is usually used to build chatbots that understand and respond to conversational statements. We have trained a Dialogflow model to recognize a range of different natural language expressions of properties, and to identify key information inside the expression. The model responses to each statement with a generated SystemVerilog assertion whose semantic meaning is equivalent to that of the English statement.

Digital microfluidics is an emerging technology that provide fluidic-handling capabilities on a chip. One of the most important issues to be considered when conducting experiments on the corresponding biochips is the routing of droplets. A recent variant of biochips uses a micro-electrode-dot-array (MEDA) which yields a finer controllability of the droplets. Although this new technology allows for more advanced routing possibilities, it also poses new challenges to corresponding CAD methods. In contrast to conventional microfluidic biochips, droplets on MEDA biochips may move diagonally on the grid and are not bound to have the same shape during the entire experiment. In this work, we present an exact routing method that copes with these challenges while, at the same time, guarantees to find the minimal solution with respect to completion time. For the first time, this allows for evaluating the benefits of MEDA biochips compared to their conventional counterparts as well as a quality assessment of previously proposed routing methods in this domain.

Digital Microfluidic Biochips (DMFBs) are an emerging technology promising a high degree of automation in laboratory procedures by means of manipulating small discretized amounts of fluids. A crucial part in conducting experiments on biochips is the routing of discretized droplets. While doing so, droplets must not enter each others' interference region to avoid unintended mixing. This leads to cells in the proximity of the droplet being impassable for others. For different cell shapes, the effect of these temporary blockages varies as the adjacency of cells changes with their shapes. Yet, no evaluation with respect to routability in relation to cell shapes has been conducted so far. This paper analyses and compares various tessellations for the field of cells. Routing benchmarks are mapped to these and the results are compared in order to determine if and how cell shapes affect the performance of DMFBs, showing that certain cell shapes are superior to others.

Ensuring nearest neighbor compliance of quantum circuits by inserting SWAP gates has heavily been considered in the past. Here, quantum gates are considered which work on non-adjacent qubits. SWAP gates are applied in order to “move” these qubits onto adjacent positions. However, a decision how exactly the SWAPs are “moved” has mainly been made without considering the effect a “movement” of qubits may have on the remaining circuit. In this work, we propose a methodology for nearest neighbor optimization which addresses this problem by means of a look-ahead scheme. To this end, two representative implementations are presented and discussed in detail. Experimental evaluations show that, in the best case, reductions in the number of SWAP gates of 56% (compared to the state-of-the-art methods) can be achieved following the proposed methodology.

Optical circuits are considered a promising emerging technology for applications in ultra-high-speed networks or interconnects. However, the development of (automatic) synthesis approaches for such circuits is still in its infancy. Although first generic and automatic synthesis approaches have been proposed, no clear understanding exists yet on how to keep the costs of the resulting circuits as small as possible. In the domain of optical circuits, this is particularly interesting for the number of gates and the effect of so-called splitters to the signal strength. In this work, we investigate this relation by considering a variety of (existing as well as proposed) synthesis approaches for optical circuits. Our investigations show that reducing the number of gates and reducing the number of splitters are contradictory optimization objectives. Furthermore, the performance of synthesis guided with respect to gate efficiency as well as synthesis guided with respect to splitter freeness is evaluated and an overhead factor between the contradictory metrics is experimentally determined.

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. We study this issue in this article. 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 and a corresponding embedding. For the approaches, we considered sum 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.

With the advancements in silicon photonics, optical devices have found applications e.g. for ultra-high speed and low-power interconnects as well as functional computations to be realized on-chip. Caused by the increasing complexity of the underlying functionality, also the need for computer-aided design methods for this technology rises. Motivated by that, initial work on the development of synthesis methods for optical circuits has been performed. But all approaches proposed thus far suffer e.g. from unsatisfactory synthesis results or restricted scalability. In particular, splittings in the resulting circuits which degrade the optical signals into hardly measurable fractions prevent an efficient and scalable synthesis for optical circuits. In this work, we present a synthesis approach based on Binary Decision Diagrams (BDDs) that overcomes these obstacles. The approach yields circuits that rely on a total of zero splitters - at the expense of a moderate increase in the number of optical gates. Experiments confirm that, by this, an efficient and scalable synthesis scheme for optical circuits eventually becomes available.

Advances in microfluidic technologies have led to the emergence of Digital Microfluidic Biochips (DMFBs), which are capable of automating laboratory procedures in biochemistry and molecular biology. During the design and use of these devices, droplet routing represents a particularly critical challenge. Here, various design tasks have to be addressed for which, depending on the corresponding scenario, different solutions are available. However, all these developments eventually result in an “inflation” of different design approaches for routing of DMFBs - many of them addressing a very dedicated routing task only. In this work, we propose a comprehensive routing methodology which (1) provides one (generic) solution capable of addressing a variety of different design tasks, (2) employs a “push-button”-scheme that requires no (manual) composition of partial results, and (3) guarantees minimality e.g., with respect to the number of timesteps or the number of required control pins. Experimental evaluations demonstrate the benefits of the solution, i.e., the applicability for a wide range of design tasks as well as improvements compared to specialized solutions presented in the past.

With the advances of the microfluidic technology, the design of digital microfluidic biochips recently received significant attention. But thus far, the corresponding design tasks such as binding, scheduling, placement, and routing have usually been considered separately. Furthermore, often just heuristic results have been obtained. In this work, we present a one-pass synthesis scheme which directly realizes the desired functionality onto the chip and, at the same time, guarantees minimality with respect to area and/or timing. For this purpose, the deductive power of solvers for Boolean satisfiability is exploited. Experiments show how the approach leverages the design of the respective devices.

Digital microfluidic biochips enable a higher degree of automation in laboratory procedures in biochemistry and molecular biology and have received significant attention in the recent past. Their design is usually conducted in several stages with routing being a particularly critical challenge. Previously proposed solutions for this design step suffer from two issues: They are mainly of heuristic nature and usually assume that the blockages to be bypassed are present the entire time. In contrast, we present a methodology which exploits the fact that blockages are often only present at certain intervals. At the same time, our approach guarantees exact solutions, i.e. always determines a routing with a minimal number of time steps. Experimental results show that, despite the huge complexity, optimal results can be achieved in reasonable run-time and that the consideration of temporary blockages indeed significantly improves the routing results.

There is a growing interest in software summarization and tools for automatically producing summaries. Discussions of relevant papers at recent conferences led to the observation that software summarization needs to consider migrating away from ``is this a good summary?" and towards ``is this a useful summary?" As a result, it has been suggested that to judge usefulness, one needs to view the summary through the lens of a particular task. A preliminary investigation of this suggestion was undertaken at the 2013 ICSE workshop NaturaLiSE. Initial results and lessons learned from this investigation support the notion that task plays a significant role and thus should be considered by researchers building and accessing automatic software summarization tools.

Synthesis of reversible circuits is an active research area motivated by its applications e.g. in quantum computation or low-power design. The number of used circuit lines is thereby a crucial criterion. In this paper, we introduce several methods (including a theoretical upper bound) for the efficient computation or at least approximation of the minimal number of lines needed to realize a given function in reversible logic. While the proposed exact approach requires a significant amount of run-time (exponential in the worst case), the heuristic methods lead to very precise approximations in very short run-time. Using this, it can be shown that current synthesis approaches for large functions are still far away from producing optimal circuits with respect to the number of lines.