《中国科学: 信息科学》2022：图计算在ATPG中的应用探究

自动测试向量生成(Automatic Test Pattern Generation, ATPG) 是VLSI电路测试中非常重要的技术, 它的好坏直接影响测试成本与开销。然而现有的并行ATPG方法普遍存在负载不均衡、并行策略单一、存储开销大和数据局部性差等问题。由于图计算的高并行度和高扩展性等优点, 快速、高效、低存储开销的图计算系统可能是有效支持ATPG的重要工具, 这将对减少测试成本显得尤为重要。

本文介绍了ATPG的背景和挑战，分析了现有图计算系统应用于ATPG面临的挑战，并从基于传统架构的优化、新兴硬件的加速和基于新兴存储器件的优化几个方面，对图计算系统支持ATPG所面临的挑战和未来研究方向进行了讨论。

该成果“图计算在ATPG中的应用探究” 发表在CCF 推荐的A类期刊《中国科学: 信息科学》2022上。该期刊是计算机信息学科领域的学术期刊，主要关注计算机科学与技术、控制科学与控制工程、通信与信息系统、微电子与固体电子学等领域基础与应用研究方面的原创性成果。

• 论文链接：

  https://www.sciengine.com/SSI/doi/10.1360/SSI-2021-0267

ATPG的一般流程如下。在预处理过程ATPG会分析电路中所有可能出现的故障模型, 这些故障模型的集合称为故障列表。故障模型的目的是为了将电路的物理缺陷等效于逻辑故障, 它可以划分为不同类型。本文只考虑ATPG中单固定型故障模型, 即电路中某一条线路的信号值固定为0或1。在生成故障列表后, ATPG从故障列表中选出一个故障模型进行测试生成和故障模拟, 这是最核心的两个过程。测试生成为给定的故障模型求解能检测到该故障的测试向量, 它是ATPG性能的关键。对于生成的测试向量, 还需要通过故障模拟来判断它是否能检测到故障列表中的其它故障模型, 故障模拟同样很大程度上影响着ATPG的性能。测试生成选定的故障模型和故障模拟检测到的故障模型被一并从当前故障列表中排除, 然后ATPG继续重复两个核心过程, 直到故障列表为空。如何在保证较高覆盖率的情况下获取尽可能小的测试向量集是电路测试的关键问题。先前工作已证明, 即使对于单调电路, ATPG也是NP完全问题。此外, 在最坏的情况下, ATPG算法的时间复杂度与电路的规模呈指数相关。因此, ATPG问题一直是EDA领域的重要研究课题。

目前, 大致有三类方法被用于加速ATPG：可测试性设计(Design for Testability, DFT)、串行算法优化和算法的并行化。但是, 现有并行ATPG的相关工作还面临着诸多挑战:。(1)负载均衡问题: 现有的并行ATPG方法对子任务的划分主要在较为粗粒度的层次。(2)并行策略单一: 无论是故障模拟还是测试生成过程都存在多种并行性, 但是现有的并行ATPG系统中往往只采用某一种并行策略。(3) 存储开销大, 数据局部性差。传统的ATPG系统以链表的形式表达电路的拓扑, 而将相关的所有状态数据全部放在同一个结构体中。这种存储方式使得并行任务必须维护单独的电路副本, 在电路规模越来越大的情况下产生大量的空间开销。

表1给出了测试生成的几种典型并行化策略。

单机图计算系统：单机图计算系统能充分利用单机处理图计算任务的能力, 避免了分布式系统下代价高的网络通信开销。但是这类系统由于硬件资源有限, 使其无法实现好的扩展性, 需要的处理时间通常和图数据规模成比例。单机图计算系统可分为两类, 面向高端多核、大内存服务器的内存（In-memory）图计算系统和面向商用PC的核外（Out-of-core）图计算系统。第一类在图处理过程中会将图数据完全放入内存中, 第二类通常利用磁盘来存放图数据, 它采取一定的划分策略来进行分块处理。典型的单机图计算系统通常会将图顶点和边划分为小的分片, 以便分片能够在高速的存储设备中进行高效处理, 并提供了充分的并行性和优化的访存模式。对于内存图计算系统, 图数据进行划分的目的是使每个核心能有效处理各自分配的分片, 有些内存图计算系统不需要显式的运用划分策略, 只需要在计算过程中对任务进行适应性的调度, 就可以取得很好的并行效果。对于核外系统, 由于图数据无法被全部加载进内存, 图划分策略使得分片能够被加载进内存进行处理。对于编程模型是以点为中心的图计算系统, 一般将图顶点和边的分片同时加载进内存中。对于编程模型是以边为中心的系统只将图顶点分片整个加载进内存, 边数据从磁盘上以流的形式进行加载处理。

分布式图计算系统：分布式图计算系统在大数据时代, 图已经增长到无法放入一台机器的内存中。即使可以, 性能也会受到内核数量的限制。单机处理并不是真正可扩展的解决方案。为了有效地处理大规模图, 分布式图计算系统被提出。分布式计算机系统也存在一些问题。分布式图计算需要对图进行分割, 而现实世界中的图复杂的结构加剧了图分割的难度, 很难找到一个高时效并且能保证得到高质量的图分割方法。当图算法在每次迭代中仅需要更新少数点的值时, 无法充分发挥分布式平台计算资源多的优势, 反而会因网络消息延迟而影响图算法的性能。分布式图计算系统有负载不均衡、成本高的通信开销以及弱健壮性等缺点。典型系统主要以同步和异步方式来对大规模图进行分布式处理并且一些系统主要支持静态图。

图计算硬件加速技术：加速器因其具备丰富的带宽资源、高的并行能力以及低的数据传输延迟等技术优势, 从而使它成为实现高效图计算的重要技术手段之一。按照加速器物理器件性质来分, 面向图计算的硬件加速方案大体可分为基于GPU的图计算加速器、基于MIC的图计算加速器、基于FPGA的图计算加速器和基于ASIC（Application Specific Integrated Circuit）的图计算加速器等。

图计算应用于组合电路ATPG的挑战主要包括ATPG算法转化为图算法的挑战、ATPG对应的图算法高效执行面临的挑战。ATPG算法转化为图算法的挑战主要有两点：1、大多数ATPG算法，例如D算法、PODEM算法和FAN算法，都是用邻接链表存储电路图数据的，存在存储和处理开销大的问题。2、现有的图计算系统不支持ATPG算法。例如传统的ATPG算法得不到现有图计算系统的支持。现有图计算系统主要研究如何高效支持单个图分析任务的有效执行。然而，ATPG算法处理每个故障都是一个图分析任务。这意味着，将ATPG算法转化为图算法后，其需要执行大量的并发图分析任务。因此，将ATPG算法转化为图算法后，其高效执行面临下述挑战：1、在现在图计算系统上，大量并发图分析任务会独立地存储和访问它们各自的电路图数据，从而存在大量冗余数据存储和访问，导致内存消耗大和数据访问开销高的问题。2、大量并发图分析任务的非规则数据访问，导致与数据访问相关的资源竞争激烈，进一步致使数据访问开销高，大量核处于空闲状态。3、大量并发图分析任务调度开销大并且难以有效调度。

为提高测试的速度、减少内存开销以及提高可扩展性, 我们可以通过优化图计算系统解决上述问题。我们可考虑以下几个方面。

传统架构上的软件系统优化：在现有图计算软件系统中, 并发ATPG任务互不感知数据访问的空间/时间关联性, 并且不同图计算任务的图顶点状态沿着复杂多变的依赖进行传递。因此, 并发ATPG任务在执行中会存在大量冗余且不规则的数据访问, 这使得他们面临着严重的数据访问瓶颈和底层硬件资源难以有效利用等挑战, 最终导致现有软件系统在支持并发ATPG任务执行时吞吐率低。为此, 如何设计面向ATPG的图计算软件系统来充分挖掘和利用并发ATPG任务之间在运行时的数据访问关联性和图顶点状态之间的依赖关联性, 并透明有效地支持并发ATPG任务在底层硬件平台上的执行是亟需解决的问题。

基于硬件加速器的技术：随着新兴硬件(例如, GPU, FPGA, 以及ASIC)的不断发展, 这给如何高效支持并发ATPG任务执行带来了机遇和挑战。虽然GPU通过提供大规模并行计算资源来获得高性能, 但是并发ATPG任务之间不规则的数据访问导致大量冗余访问开销, 从而限制了并发ATPG任务计算的并行度。为此, 如何设计有效的执行机制来高效利用GPU的高并行性是提高并发ATPG任务计算吞吐率的重要途径。此外, 虽然FPGA和ASIC能够为并发ATPG任务执行提供专用的存储子系统和处理单元来有效提高计算的效率, 但是他们面临着片上存储资源有限等挑战。

基于新兴存储硬件的优化：大量新兴存储硬件的涌现也为如何有效降低并发ATPG任务的数据访问开销提供了机遇。HMC与ReRAM等新兴存储硬件能够有效减少数据移动与通信消耗。由于图计算是一种数据访问密集型的应用, 因此可以通过有效利用并发ATPG任务计算的数据访问关联性等特征来充分挖掘HMC与ReRAM的硬件特性, 从而极大地降低执行并发ATPG任务的数据访问开销。并且, 现实世界的图往往规模巨大并采用分布式集群的方式来处理, 为此, 通过有效地利用RDMA等新兴硬件来加速并发ATPG任务在机器间的通信能够显著降低通信延迟。以上新兴硬件都为执行并发ATPG任务的优化提供了新的可能。

详细内容请参见：

Mao Fubing, Peng Da, Zhang Yu, Liao Xiaofei, Jiang Xinyu, Yang Yun, Jin Hai, Zhao Jin, Liu Haikun, Wang Liuzheng, 图计算在ATPG中的应用探究,  SCIENTIA SINICA Informationis, 2022, ISSN 1674-7267, https://doi.org/10.1360/SSI-2021-0267 .