测试是超大规模集成电路(VLSI，Very Large Scale Integration Circuits)设计中不可缺少的重要环节。随着VLSI电路复杂性的增长，自动测试生成(ATPG，Automatic Test PatternGeneration)的时间开销已经成为VLSI电路设计的瓶颈之一。并行计算是解决这个问题的一种有效的可行办法。本文的研究内容正是面向非扫描同步时序电路的并行ATPG算法。 目前，制约并行ATPG算法实用化的关键原因是算法的可移植性。因此，我们首先提出了基于消息传递系统——并行虚拟机(PVM，Parallel Virtual Machine)的并行ATPG原型系统框架，并根据它构建了一个实验系统HappyTest。由于PVM良好的可移植性，使得基于这个框架开发的分布式存储并行算法基本能够避免针对不同体系结构的并行机而进行重复开发。 测试生成(TG，Test Generation)和故障模拟(FS，Fault Simulation)是构成ATPG系统的两个紧密相关的部分。由于目标任务不同，它们内在的并行性也不尽相同。在FS方面，本文深入研究了提高单机FS效率的方法。首先提出并实现了一个新的同步时序电路单机字级测试码并行FS算法，该算法与现有同类方法的不同在于，利用确定性G-F二值TG算法的每个故障测试序列之间的相对独立性，对测试码进行分解并动态组装，避免了对添加的同步序列的冗余模拟，效果较好。接着又开发了一个新的单机字级故障并行FS算法。该算法的创新在于扩充了现有的组合电路无扇出区划分方法，使之对时序电路适用，并把它与扇出源故障并行模拟和临界路径追踪方法相结合。实验表明，其效率比经典的字级故障并行FS算法有明显提高，且时间复杂性随电路规模增长曲线趋于平缓。在此基础上，深入研究了针对FS的测试码分解和故障分解两类并行策略。并设计了针对同步时序电路的基于单机字级故障并行FS算法的多机故障并行FS算法和基于确定性算法的多机测试码并行FS算法。从实验结果看，后者加速比明显高于前者，而前者的性能与近年国外发表的同类方法相当。 在TG方面，本文深入研究了基于故障分解、搜索空间分解和电路划分三种并行TG方法。首先，设计了一个用静态、动态相结合灵活控制故障划分方式以获得较好效果的故障并行TG算法。然后，提出了一个新的基于故障敏化模式分解的搜索空间并行TG算法。与国外同类方法相比，其优点是易实现，控制灵活，同步开销小，并行效果好。最后重点对电路并行方法进行了研究，提出了一种新的以触发器为核且消除大功能块之间反馈的宽度优先反向搜索同步时序电路划分方法。在此基础上，提出并设计了一个新颖的电路并行TG算法。该算法在获得一定加速比的前提下，可较大地缓解VLSI的ATPG对内存需求的矛盾。 在ATPG方面，本文认为TG和FS采用松耦合模式更利于并行ATPG算法在研发中快速融合各种并行策略且及时集成各种最新的串行TG和FS算法。较之紧耦合串行ATPG系统的并行化具有独特的优势。本文基于松耦合模式，以G-F二值TG算法和HOPE FS算法为基础，快速开发了一系列有效的并行ATPG算法，获得了良好效果。 国防科学技术大学研究生院学位论文 最后，我们对松耦合模式的并行ATPG算法进行了性能分析。分析表明，和传统的紧耦合模式的并行ATPG算法相比，松耦合模式的并行ATPG算法能够减少时间和存储开销。