The hardware complexity related to the number of transistors in electronic devices used by today’s society has grown considerably in the last decades because of technological progress. In order to guarantee the correct behavior of such devices and meet time-to-market constraints, there is a need to continuously develop more efficient data structures and algorithms in formal verification. The performance of verification algorithms depends in particular on the compactness of data structures. A reduced ordered binary decision diagram (BDD) is basically a suitable data structure to verify digital circuits, as it represents Boolean functions canonically respecting a variable ordering and allows direct manipulation of them. However, one of the main challenges with BDDs is to find a variable ordering so that the BDD size of a function is compact and does not become impractical due to a dramatically increasing number of BDD nodes. To address the aforementioned issue, this article presents a novel evolution strategy having an efficient evaluation of variable ordering in a divide-and-conquer manner for BDD optimization. Experiments on benchmarks of multilevel circuits show that using this strategy results in considerably smaller BDDs being found significantly faster compared to state-of-the-art optimization techniques.

The hardware complexity in electronic devices used by today's society has increased significantly in recent decades due to technological progress. In order to cope with this complexity, data structures and algorithms in electronic design automation must be continuously improved. Decision Diagrams (DDs) are an important data structure in the design and analysis of circuits because they allow efficient algorithms for their manipulation. The practical relevance of DDs leads to an ongoing quest for appropriate software solutions that enable working with different DD types. Unfortunately, existing DD software libraries focus either on efficiency or usability. Consequences are a disproportionately high effort for extensions or considerable loss of performance. To tackle these issues, a modular and efficient Framework to Engineer Decision Diagrams Yourself (FrEDDY) is proposed in this paper. Various experiments demonstrate that no compromise with regard to performance has to be made when using FrEDDY. It is on par with or clearly more efficient than established DD libraries.

The hardware complexity in electronic devices has increased significantly in recent decades due to technological advancements. To ensure correct behavior of such devices and meet time-to-market constraints, modern circuit verification and testing tools rely on formal proof techniques. The two most popular methods in this context are Binary Decision Diagrams (BDDs) and Boolean Satisfiability (SAT) solvers. Even though these methods share some similarities, they are fundamentally different. Whereas BDDs usually require a large amount of memory to represent all solutions, SAT solvers are memory-efficient but they typically compute only a single solution. To tackle these issues, a hybrid approach called Binary Hybrid Diagram (BHD) is proposed for efficient generation of multiple solutions. BHDs combine the major advantages of BDDs and SAT solvers, and generate distinct solutions heuristically via algorithms. Experiments demonstrate that feasible solutions are generated rapidly by using BHDs while the memory requirement remains small compared to state-of-the-art methods.

Tailoring hardware to an application significantly enhances its performance compared to using a general-purpose processor. While hardware optimization is essential to meet the user requirements for resource-constrained embedded systems, it generally entails considerable costs and a high level of effort. In recent work virtual prototypes have been shown to be an effective analysis tool for guiding this process. In best-case scenarios, it is possible to identify a single recurring instruction sequence that covers approximately 55 % of all executed instructions and is thus suitable for optimization by a Hardware Accelerator (HA). However, challenges arise for applications where each identified sequence only covers a small fraction of the total execution. In order to achieve comparable coverage, several HAs can be designed, but this also multiplies the hardware costs. To address these issues, this work proposes an approach to extend and merge identified sequences allowing the design of a single HA for the merged sequence. Experiments show that this approach significantly increases the coverage achievable with a single HA while the resulting performance loss is negligible compared to building multiple HAs.

In recent years, hardware systems have significantly grown in complexity. Due to the increasing complexity, there is a need to continuously improve the quality of the hardware design process. This leads designers to strive for more efficient data structures and algorithms operating on them to guarantee the correct behavior of such systems through verification techniques like model checking and meet time-to-market constraints. A Binary Decision Diagram (BDD) is a suitable data structure as it provides a canonical compact representation of Boolean functions, given variable ordering, and efficient algorithms for manipulating them. However, reduced ordered BDDs also have challenges: There is a large memory consumption for the BDD construction of some complex practical functions and the use of realizations in the form of BDD packages strongly depends on the application.

The complexity of hardware systems has increased significantly in recent decades. Due to increasing user requirements, there is a need to develop more efficient data structures and algorithms to guarantee the correct behavior of such systems. A Reduced Ordered Binary Decision Diagram (BDD) is a suitable data structure as it represents all Boolean functions canonically given a variable order as well as provides algorithms for efficient manipulation. However, BDDs also have challenges: practicability depends on their minimization and there is a large memory consumption for some complex functions.To address these issues, this work investigates the number of emerged intermediate nodes that are not used in the final BDD result and presents a novel approach for efficient BDD manipulation by reducing the number of such nodes. Experiments on BDD benchmarks show that peak BDD node sizes can be significantly reduced, leading to accelerated BDD manipulation.