【作者】 李瑛；

【导师】 程明琦；

【作者基本信息】 太原理工大学 ， 计算机应用， 2003， 硕士

【摘要】 逻辑模拟是数字电路自动设计的重要组成部分。为减少大规模电路的模拟时间，近年来大家的兴趣转向了并行模拟。其中，一个优化的划分算法是实现并行模拟的关键。 本文首先描述了几种现在比较通用的划分算法，并列出了这些算法的优点和局限性。然后，提出一种在对电路中节点进行线性排序的基础上的线性时间划分算法。该算法主要分为两个部分，第一部分是将电路中的节点按线性时间顺序排序，这样就保证了模拟过程的正确性；第二部分是将有序节点划分到以不同原始输入为根节点的子节点集中，并将这些子节点集按其连接量的大小合并为与处理器数目相等的子节点集合，最后将这些子节点集合按连接量分配到各个处理器上。第二部分又分为三个阶段，分别用来解决划分过程中互相冲突的三个方面：并发性、负载平衡和最小化通讯开销。为了减少计算的复杂性，每一阶段分别实现互相冲突的三个目的之一。以前出现的划分算法有一个共同的问题：它们通常只是尽量的平衡整个模拟过程的工作负载，而不是平衡实时的负载。本文提出的算法很好的解决了这个问题，保证了模拟过程中各个处理器上的实时负载平衡，实现了高度的并行性。更多还原

【Abstract】 Logic simulation is an important component of design automatic of digital circuits. To reduce the simulation time of large circuits, parallel logic simulation has attracted considerable interest in recent years. A better partition algorithm is a key to parallel simulation.In this thesis, several popular algorithms are described and their advantages and disadvantages are listed. Then, a linear-time partitioning algorithm based on a linear ordering of nodes in a circuit for parallel logic simulation is presented. The algorithm is composed of two sections. In the first section the nodes in a circuit are arranged in linear time order to preserve simulation validity. In the second section, the nodes in order are divided into several sets whose root is primary input node and nodes in which can be reached by path; then these sets are united by connectivity among sets into some larger sets, the number of which is equal to that of processors; at last the sets are assigned to each processor by connectivity among sets. The second section consists of three phases to solve three competing goals: to maximize concurrency, to balance processor workload, and to minimize inter-processor communication. Three conflicting goals can be separately considered in each phase so to reduce computational complexity.Most previous algorithms balance the accumulated amount of workload over the whole simulation period instead of the workload at real time. Unlike most other partitioning algorithms, the proposed algorithm preserves circuit concurrency by balancing the workload on processors at real time.更多还原