Development of hardware logic simulator using decision diagrams

1基于决策图的硬件仿真引擎提出了一种基于决策图的硬件逻辑仿真引擎。对于引擎的数据结构，我们提出了PMDDs （page约简有序多值决策图）。该引擎的一个单元由存储器（ram）和控制电路组成：ram存储PMDD数据，控制电路根据输入向量跟踪边缘。该发动机由几个单元组成，并通过流水线加速。给出了样机的实验结果。使用决策图评估多输出逻辑函数本部分展示了使用决策图评估多输出逻辑函数的四种不同方法：共享BDD (SBDD)，多终端BDD (MTBDD)，特征函数BDD （CF）和非零输出编码特征函数BDD （ECFNs）。给出了计算各类决策图平均评价时间的方法。通过实验分析，比较了多节点函数的节点数和平均评价时间。我们的研究结果表明，在节点数量和计算时间方面，ECFNs的bdd优于mtbdd、CFs的bdd和sdd。2 . ECFNs的bdd小于mtbdd、CFs的bdd和sdd。基于可重构硬件的多输出功能级联实现本文提出了一种利用RAM和顺序器实现多输出逻辑功能的方法。首先，用非零编码特征函数（ECFN）表示多输出函数。然后，它由一系列查找表（lut）表示。最后，用RAM和序列器对级联进行仿真。通过lut级联实现了基准函数的多输出函数，并给出了lut的数量和级联的级别。提出了一种用于并行计算的输出划分方法。利用RAM和fpga开发了一个原型。布尔函数的编码及其在LUT级联综合中的应用在逻辑综合的几个领域中都会出现编码问题。由于这个问题的性质，通常很难系统地探索所有可行编码的空间以找到最优编码。在这一部分中，我们证明了当要编码的对象是布尔函数时，可以最优地制定和解决问题。我们提出了一种用一个或多个具有理想性质的码位函数来解决编码问题的一般方法。该方法允许使用分支绑定过程与专门的BDD操作符相结合的有效实现。该方法用于合成实现布尔函数的查找表级联。实验结果表明，该算法能在不到1秒的CPU时间内找到复杂编码问题的最优解。有限轨道LUT级联的逻辑综合可编程LUT级联用于多输出布尔函数的求值。这一部分展示了多输出函数的几种表示，并介绍了一种适用于这些表示的新的分解算法。该算法产生具有有限轨数的LUT级联，从而导致显着更快的电路和适用于大型设计。实验表明，该算法在基准函数上具有良好的性能。平均路径长度作为二值决策图表示的函数快速求值的一种范式本部分重点研究了交换函数的BDD的平均路径长度。APL是计算机程序计算函数所需时间的度量。我们推导了与函数、或函数、奇偶函数、执行函数、比较函数、阈值对称函数和多数函数的api。我们还考虑了各种函数类的api的平均值，包括对称、阈值对称和单级联。对于对称函数，我们展示了平均APL接近于最大路径长度n，即变量的数量。我们证明了有两个函数，奇偶性函数，在api上对于所有依赖于n个变量的函数的BDD达到了上限n。所有其他函数的APL都严格小于n。我们证明了BDD的APL在所有依赖于n个变量的函数上的下界为2 - 2^<-(n-1)>。实现这个小值的函数集是唯一的可级联实现的函数集。我们还表明，基准函数的api通常比随机函数的api要小得多。用QRMDD表示逻辑函数本部分考虑k位的拟约简多值决策图（QRMDD(k)s）来表示二值逻辑函数。表示QRMDD中节点中的节点数(k)s与基准函数k值之间的关系；QRMDD中节点数的上界(k)；随机函数QRMDD的上界与节点数之差(k)s；以及QRMDD(k)的总内存、评估时间和区域时间复杂度。使用标准基准函数的实验结果表明，当k在3 ~ 6.8之间时，区域时间复杂度最小。共享二进制决策图的双分区共享二进制决策图（SBDD）表示一个多输出函数，其中节点在输出之间是共享的。一个分区的sdd通常由两个或多个sdd组成，这些sdd通常共享节点。单独的sdd是独立优化的，这通常会减少单个sdd上的节点数量。我们展示了一种将单个SBDD划分为两个部分的方法，这种方法可以减少节点数量。在测试的基准函数中，实现了高达16%的节点减少。伪kronecher决策图（PKDD）是二进制决策图（BDD）的推广。PKDD不需要比BDD更多的节点来表示相同的功能。在这一部分中，我们考虑了一种用pkdd表示不完全指定函数的方法。我们开发了一种启发式方法来获得pkdd。许多用于不关心的MCNC基准函数的pkdd被简化了。实验结果表明，考虑不关心后，PKDD的节点数可减少14%。多输出函数的紧凑BDD表示及其应用本部分展示了一种表示多输出函数的新方法：非零输出的编码特征函数（ECFN）。ECFN使用（n + u）二进制变量来表示n输入m输出函数，其中u = [log_2m]。ecfn的二进制决策图（bdd）永远不会大于相应的sdd。BDD的大小取决于输出的编码以及变量的顺序。我们推测存在一个n输入2^n-输出函数，其中最优编码产生2n + 2个节点的bdd，而最差编码产生2^<n+1>节点的bdd。我们提出了一个编码问题，并给出了一种启发式方法。使用标准基准函数的实验结果表明，考虑编码可以显著减小bdd的大小。在这一部分中，我们展示了一种定位随机存取存储器（RAM）单个卡在故障的方法。从RAM的故障位图中，我们得到了它们的沃尔什谱。对于单个卡滞故障，我们证明了仅使用谱的第0和第1个系数就可以识别和定位故障。我们还展示了计算这些系数的电路。与逻辑最小化法相比，该方法的计算时间大大缩短。少

1 A Hardware Simulation Engine Based on Decision DiagramA hardware logic simulation engine based on decision diagrams is presented. For the data structure of the engine, we propose PMDDs (Paged reduced ordered Multi-valued Decision Diagrams). A unit of this engine consists of memory (RAMs) and control circuits: RAMs store the PMDD data, and the control circuits trace the edges according to the input vectors. The engine consists of several units, and is accelerated by pipelining. Experimental results using a prototype are shown.2. Evaluation of Multiple-Output Logic Functions using Decision DiagramsThis part shows four different methods to evaluate multiple-output logic functions using decision diagrams: Shared BDD (SBDD), Multi-Terminal BDD (MTBDD), BDD for characteristic functions (CF), and BDDs for Encoded Characteristic Function for Non-zero outputs (ECFNs). Methods to compute average evaluation time for each type of decision diagrams are presented. By experimental analysis using be … More nchmark functions, the number of nodes and average evaluation time are compared. Our results show that BDDs for ECFNs outperforms MTBDDs, BDDs for CFs, and SBDDs with respect to both number of nodes and computation time. The sizes of BDDs for ECFNs are smaller than for MTBDDs, BDDs for CFs, and SBDDs.3. A Cascade Realization of Multiple-Output Function for Reconfigurable HardwareA realization of multiple-output logic functions using a RAM and a sequencer is presented. First, a multiple-output function is represented by an encoded characteristic function for non-zeros (ECFN). Then, it is represented by a cascade of lookup tables (LUTs). And finally, the cascade is simulated by a RAM and a sequencer. Multiple-output functions for benchmark functions are realized by cascades of LUTs, and the number of LUTs and levels of cascades are shown. A partition method of outputs for parallel evaluation is also presented. A prototype has been developed by using RAM and FPGA.4. Encoding of Boolean Functions and Its Application to LUT Cascade SynthesisThe problem or encoding arises in several areas of logic synthesis. Due to the nature of this problem, it is often difficult to systematically explore the space of all feasible encodings to find an optimal one. In this part, we show that when the objects to be encoded are Boolean functions, it is possible to formulate and solve problem optimally. We present a general approach to the encoding problem with one or more code-bit functions having some desirable properties. The method allows for an efficient implementation using branch-and-bound procedure coupled with specialized BDD operators. The proposed approach was used to synthesize lookup table (LUT) cascades implementing Boolean functions. Experimental results show that it finds optimal solutions for complex encoding problems in less than a second of CPU time.5. Logic Synthesis of LUT Cascades with Limited RailsProgrammable LUT cascades are used to evaluate multi-output Boolean functions. This part shows several representations of multi-output functions and introduces a new decomposition algorithm applicable to these representations. The algorithm produces LUT cascades with the limited number of rails, which leads to significantly faster circuits and applicability to large designs. The experiment shows that the proposed algorithm performs well on benchmark functions.6. Average Path Length as a Paradigm for the Fast Evaluation of Functions Represented by Binary Decision DiagramsThis part focuses on the average path length (APL) of BDD's for switching functions. APL is a metric for the time it takes to evaluate the function by a computer program. We derive the APL for the AND, OR, parity, carry-out, comparison, threshold symmetric, and majority functions. We also consider the average of the APL for various classes of functions, including symmetric, threshold symmetric, and unate cascade. For symmetric functions, we show the average APL is close to the maximum path length, n, the number of variables. We show there are exactly two functions, the parity functions, that achieve the upper bound, n, on the APL for BDD's over all functions dependent on n variables. All other functions have an APL strictly less than n. We show that the APL of BDD's over all functions dependent on n variables is bounded below by 2 - 2^<-(n-1)>. The set of functions that achieves this small value is uniquely the set of unate cascade realizable functions. We also show that the APL for benchmark functions is typically much less than for random functions.7. Representations of Logic Functions using QRMDDsThis part considers quasi-reduced Multi-valued decision diagrams with k bits (QRMDD(k)s) to represent two-valued logic function. It shows relations between the numbers of nodes in nodes in QRMDD(k)s and values of k for benchmark functions; an upper bound on the number of nodes in the QRMDD(k); difference between the upper bound and the number of nodes in the QRMDD(k)s for random function; and the amount of total memory, evaluation time, and area-time complexity for QRMDD(k)s. Experimental results using standard benchmark functions show that the area-time complexity takes its minimum when k is between 3 and 6.8. Bi-Partition of Shared Binary Decision DiagramsA shared binary decision diagram (SBDD) represents a multiple-output function, where nodes are shared among outputs. A partitioned SBDD usually consists of two or more SBDDs that often share nodes. The separate SBDDs are optimized independently, often resulting in a reduction in the number of nodes over a single SBDD. We show a method for partitioning a single SBDD into two parts that reduces the node the node count. Among the benchmark functions tested, a node reduction of up to 16% is realized.9. Representation of Incompletely Specified Switching Functions Using Pseudo-Kronecker Decision DiagramsPseudo-Kronecher decision diagram (PKDD) is a generalization of binary decision diagram (BDD). A PKDD requires not more nodes than a BDD to represent the same function. In this part, we consider a method to represent incompletely specified functions by using PKDDs. We developed a heuristic method to obtain PKDDs. Many PKDDs for MCNC benchmark functions with don't cares are simplified. Experimental results show that the number of nodes of PKDD can be reduced by 14% by considering don't cares.10. Compact BDD Representations for Multiple-Output Functions and Their ApplicationThis part shows a new method to represent a multiple output function: an encoded characteristic function for nonzero outputs (ECFN). The ECFN uses (n + u) binary variables to represent an n-input m-output function, where u = [log_2m]. The binary decision diagrams (BDDs) for ECFNs are never greater than corresponding SBDDs. The size of a BDD depends on the encoding of the outputs as well as the ordering of the variables. We conjecture that there exists an n-input 2^n- output function, where the optimal encoding produces BDDs with 2n + 2 nodes, while the worst encoding produces BDDs with 2^<n+1> nodes. We formulate an encoding problem and show a heuristic method. Experimental results using standard benchmark functions show that the sizes of BDDs can be reduced significantly by considering encodings.11. Fault Diagnosis for RAMs using Walsh SpectrumIn this part, we show a method to locate a single stuck-at fault of a random access memory (RAM). From the fail-bitmaps of the RAM, we obtain their Walsh spectrum. For single stuck-at fault, we show that the fault can be identified and located by using only the 0-th and 1-st coefficients of the spectrum. We also show a circuit to compute these coefficients. The computation time is much shorter than one that uses logic minimization method. Less