图计算在ATPG中的应用探究_毛伏兵.pdf

SCIENTIA SINICA Informationis中国科学:信息科学2023年第53卷第2期:211233c 2023中国科学 杂志社评述图计算在ATPG中的应用探究毛伏兵1,2,3,4,彭达1,2,3,4,张宇1,2,3,4*,廖小飞1,2,3,4,姜新宇1,2,3,4,杨赟1,2,3,4,金海1,2,3,4,赵进1,2,3,4,刘海坤1,2,3,4,王柳峥51.华中科技大学大数据技术与系统国家地方联合工程研究中心,武汉 4300742.华中科技大学服务计算与系统教育部重点实验室,武汉 4300743.华中科技大学集群与网格计算湖北省重点实验室,武汉 4300744.华中科技大学计算机科学与技术学院,武汉 4300745.华为海思半导体有限公司,深圳 518129*通信作者.E-mail:收稿日期:20210806;修回日期:20211226;接受日期:20220321;网络出版日期:20230202国家自然科学基金(批准号:61832006,61825202,62072193)、中央高校基本科研业务费资助(HUST)(批准号:2020kfyXJJS018,2020kfyXJJS109)项目摘要ATPG(automatic test pattern generation)是VLSI(very large scale integration circuits)电路测试中非常重要的技术,它的好坏直接影响测试成本与开销.然而现有的并行ATPG方法普遍存在负载不均衡、并行策略单一、存储开销大和数据局部性差等问题.由于图计算的高并行度和高扩展性等优点,快速、高效、低存储开销和高可扩展性的图计算系统可能是有效支持ATPG的重要工具,这将对减少测试成本显得尤为重要.本文将对图计算在组合ATPG中的应用进行探究;介绍图计算模型将ATPG算法转化为图算法的方法;分析现有图计算系统应用于ATPG面临的挑战;提出面向ATPG的单机图计算系统,并从基于传统架构的优化、新兴硬件的加速和基于新兴存储器件的优化几个方面,对图计算系统支持ATPG所面临的挑战和未来研究方向进行了讨论.关键词图计算,超大规模集成电路,自动测试向量生成,电子设计自动化,电路测试1引言电路测试是超大规模集成电路(very large scale integration circuits,VLSI)设计中必不可少的步骤14.对于生产出来的芯片,必须通过测试的方法确定其功能是否能达到设计的预期.随着电路集成度的增加,电路中出现缺陷的可能性增加,测试的难度提升,总成本中测试所占的比重变大.因此,电路测试的重要性越来越凸显出来.电路测试的原理是在输入产生激励信号,然后将其产生的输出信号与预期的信号值进行比较,输入的激励信号称为测试向量.在过去,测试向量由人工计算产生.随着电路规模的扩大,这种人工引用格式:毛伏兵,彭达,张宇,等.图计算在ATPG中的应用探究.中国科学:信息科学,2023,53:211233,doi:10.1360/SSI-2021-0267Mao F B,Peng D,Zhang Y,et al.Research on the application of graph processing in ATPG(in Chinese).Sci SinInform,2023,53:211233,doi:10.1360/SSI-2021-0267毛伏兵等:图计算在 ATPG 中的应用探究计算的方式失去了可行性.为了满足VLSI的测试需求,自动测试向量生成(automatic test patterngeneration,ATPG)技术得到长足发展.ATPG技术大大减少了测试的时间和人力成本,它在保证高故障覆盖率的前提下尽量压缩测试向量集的大小,并且能轻松、无风险地部署到电路设计和测试的流程中.但是,ATPG在整个电路设计过程中仍占用很大一部分时间.甚至ATPG的时间/空间开销已经随电路复杂度的提升成为VLSI电路设计的瓶颈,如何使ATPG算法高效执行的问题亟待解决.为了加速ATPG过程,研究人员提出了各种ATPG系统,其中比较典型的有PP-TGSt5、Proper-TEST36、HIPERTEST4907,8、CAS模式并行测试生成系统9,10、GATTOB11等.上述系统都是通过如下3个方面来优化ATPG:可测试性设计(design for testability,DFT)、串行算法优化和算法的并行化.其中,随着硬件条件的不断提升,ATPG算法的并行化越来越成为主要的研究方向.尽管学术界和工业界都在ATPG的并行化上做出了许多努力,现有的并行ATPG方法仍然存在负载不均衡、并行策略单一、存储开销大和数据局部性差等问题14.本文针对图计算在组合ATPG中的应用进行了探究.图计算(graph processing)是研究事物之间的关联关系并对其进行建模、分析和计算的图处理技术12.由于图计算的高效并行度和高扩展性等优点,快速、高效、低存储开销和高可扩展性的图计算系统可能是有效支持ATPG的重要工具,这对减少测试成本来说尤为重要.事实上,在电子设计自动化(electronic design automation,EDA)的其他领域已经有很多尝试应用图计算的工作14.美国的国防高级研究计划局(Defense Advanced ResearchProjects Agency,DARPA)提出了名为IDEA(innovation development&entrepreneurship accelerator)的项目计划,该项目由耶鲁大学(Yale University)负责.其目的是基于图计算系统实现一个电路布局生成器,使用者在掌握的EDA知识有限的情况下能通过该生成器完成单板计算机等电子硬件的设计14.我们分析了现有图计算系统在实现组合ATPG时可能遇到的各种挑战,并据此提出了一种专门面向组合ATPG的单机图计算系统.最后从传统架构、新兴硬件加速器和新兴存储硬件几个方面对图计算系统支持ATPG的未来挑战和研究方向进行了初步探讨.2ATPG 背景与挑战2.1ATPG简介电路测试是判断生产的电路器件是否合格的过程.具体来说,测试是给电路输入产生若干组激励信号,然后观察电路的输出信号是否符合预期.如果所有的输出符合预期,则说明生产的硬件与设计过程预期的功能一致;反之,则说明硬件产生了故障,这时需要定位故障的位置.用于测试的输入激励信号称为测试向量,测试向量集的不同决定了测试过程的质量,它主要由两个指标来判定:(1)测试向量集的大小.一般来说集合中测试向量的数量越少越好,因为测试时间和测试向量的数量成正比;(2)测试向量集的故障覆盖率.故障覆盖率(fault coverage,FC)是电路测试中一个重要概念,它是测试向量集能够检测的故障数与电路可能产生的所有故障数的比值.合格的测试向量集要达到95%以上的故障覆盖率14.如何在保证较高覆盖率的情况下获取尽可能小的测试向量集是电路测试的关键问题.在最初的工业界,测试向量集是工程师根据设计经验以人工计算的方式来获取的.随着大规模电路的出现,测试向量集的获取难度急剧上升,相关计算的复杂度已经无法人为处理.在此情况下,自动测试向量生成(ATPG)技术得到飞速发展14.但是Fujiwara和Toida13的工作已证明,即使对于单调电路,ATPG也是NP完全问题.也就是说,在最坏的情况下,ATPG算法的时间复杂度与电路的规模呈指212中国科学:信息科学第 53 卷第 2 期StartGenerate fault listSelect a fault from fault listTest generationFault simulationUpdate fault listFault list is emptyEndYN图1ATPG 一般流程Figure 1General ATPG flow数相关.因此,ATPG问题一直是EDA领域的重要研究课题和瓶颈之一.图1给出了ATPG的一般流程.在预处理过程ATPG会分析电路中所有可能出现的故障模型,这些故障模型的集合称为故障列表.故障模型的目的是将电路的物理缺陷等效于逻辑故障,它可以划分为不同类型.在ATPG中只考虑单固定型故障模型,即电路中某一条线路的信号值固定为0或114.在生成故障列表后,ATPG从故障列表中选出一个故障模型进行测试生成和故障模拟,这是最核心的两个过程.测试生成为给定的故障模型求解能检测到该故障的测试向量,它是ATPG性能的关键.对于生成的测试向量,还需要通过故障模拟来判断它是否能检测到故障列表中的其他故障模型,故障模拟同样很大程度上影响着ATPG的性能.测试生成选定的故障模型和故障模拟检测到的故障模型被一并从当前故障列表中排除,然后ATPG继续重复两个核心过程,直到故障列表为空.2.2现有ATPG加速技术目前,大致有下面3类方法被用于加速ATPG:可测试性设计(DFT)、串行算法优化和算法的并行化14.可测试性设计.与另外两种加速电路测试过程本身的方法不同,DFT的理念是在电路的设计阶段就考虑如何组织电路结构使得之后的测试阶段更加简单15,16.DFT可被视为一系列技术的集合,其中有两类比较典型的技术:扫描方法和内建自测试(built-in self test,BIST)方法.扫描方法采用诸如LSSD(level-sensitive scan design)17、扫描路径18等移位寄存器技术,将时序电路的ATPG问题简化为组合电路的ATPG问题.对于全扫描设计电路,只需要针对组合电路开发一种快速有效的ATPG算法就足够了.BIST方法则是在芯片设计时在电路中加入专门的测试模块19.这类加入了213毛伏兵等:图计算在 ATPG 中的应用探究测试模块的芯片能够通过BIST电路进行自测试,而不需要使用复杂的自动测试设备(automatic testequipment,ATE).串行算法优化.串行算法的优化主要针对测试生成过程,其类型大致可以分为两大类:一类是基于拓扑的结构式测试生成算法14,20.这类方法分析电路的拓扑结构信息,跟踪故障电路中错误信号的传递过程.在跟踪的过程中,算法通过调整输入激励使得错误信号能够敏化到输出,最终得到需要的测试向量.其中,D算法21,22、PODEM算法23和FAN算法24是最有代表性的结构式ATPG算法.D算法21,22是已知最早的ATPG算法,它于1966年就已发布.该算法试图通过对电路的所有节点进行结构搜索来确保错误信号的传播,因此决策树很大.PODEM23和FAN24对此进行了改进,PODEM算法将搜索空间限制为电路的主要输入;而FAN算法进一步引入约束线、自由线和线头的概念,在跟踪过程中仅在线头进行判定,进一步减小了决策树的大小.结构式的测试生成算法提出较早,也得到了广泛的关注和研究,早已应用于工业界的芯片生产中.另一类是基于符号的代数式测试生成算法25.这类方法不依赖于电路的拓扑信息,而是通过布尔函数的形式对电路进行描述,然后利用布尔可满足性(Boolean satisfiability problem,SAT)或其他方法对函数进行求解以获得所需要的测试向量.Shi等26评估了ATPG中不同SAT求解器的性能,并挖掘出针对特定问题用启发式算法加速SAT的潜力.此外,它们通过有效的内存分配减少了生成合取范式(conjunctive normal form,CNF)所需的时间.Tafertshofer等20,27提出了另一种基于SAT的技术,他们通过在蕴涵图结构上执行故障传播,加速了对布尔网络的分析.Safarpour等28的工作通过将变量标记为非活跃的来加速SAT.以与门为例,如果其输入之一是0,那么逻辑锥中的所有变量都可以被SAT求解器忽略.代数式的测试生成方法潜力很大,但发展不够成熟,目前只在学术界受到关注,在工业界中鲜有应用.并行ATPG.随着硬件条件和计算资源的不断丰富,越来越多研究开始关注于ATPG的并行化.测试生成和故障模拟作为ATPG的两个重要过程,在并行化方面都得到了一定程度的发展.对于组合电路,现在大体有两类故障模拟的并行化方案:并发式故障模拟2932和并行模式单故障传播3338.并发式故障模拟同时对多个电路进行模拟,其中包括一个无故障电路和多个故障电路.并发式故障模拟的最大好处在于它灵活和适应性强,从而使得它在工业界被广泛采用.早期工作中3032提出了启发式方法用来提高并发式故障模拟的速度.然而,并发式故障模拟需要维护多个电路的数据,因此存在存储开销大的问题.单故障传播方法则预先计算好无故障电路的模拟结果,之后每次只处理一个故障,然后将模拟结果与预存的无故障电路比对.单故障传播方法与并发式故障模拟相对比,存储开销要小很多,而且运行时只需要模拟和故障相关的子电路,所以时间开销也相对较小.对于组合电路,采用测试向量并行可以提高单故障传播方法的性能,此方法为并行模式单故障传播(parallel pattern singlefault propagation,PPSFP)3436.PPSFP能够实现与并行处理的测试向量数相同的加速比,而且还能和隐式的故障模拟算法结合来进一步提升性能33,35,39.临界路径追踪算法是Antreich和Schulz34设计的一种隐式故障模拟算法,该算法能快速排除无扇出区域的可检测故障.Harel等39在单故障传播中使用支配点的概念,利用支配点能更方便找出电路中的无扇出区域.Maamari和Rajski35则提出了茎区域概念.上述3种算法都能很方便地和PPSFP结合在一起,以减少电路中的显式故障模拟区域.测试生成的并行化策略也有一些研究工作,表1给出了测试生成的几种典型并行化策略2939.同时,有大量研究用GPU加速ATPG方法4043.现有的基于GPU的测试生成的研究主要通过比特位级别并行来提高并行性43.现有的故障模拟主要通过算法并行(并行化故障模拟算法)、模型并行(把电路划分为不相交的子部分)、数据并行(向量并行和故障并行)来提高故障模拟的并行度40,43.目前电路规模逐渐增大,由于GPU内存有限,在支持ATPG算法时,现有方法存在主机和GPU之间214中国科学:信息科学第 53 卷第 2 期表1并行测试生成方法Table 1Parallel approaches of test generationParallel strategiesIntroductionFault-level parallelismFault-level parallelism divides the fault list into multiple sub-fault lists,and theneach distributed node processes the corresponding sub-fault lists in parallel.Theupside is that coding is easy,and the communication overhead is very low.If thefault list is properly partitioned,this kind of approach can achieve a nearly linearspeedup.The downside is the imbalance-load problem.In addition,the size ofits test vector set may increase compared to the serial method.Heuristic parallelismThe purpose of heuristic parallelism is mainly to improve the final fault coverage.Structured serial test generation algorithms often adopt different heuristic rules.However,the various heuristic rules used to guide test generation are not universal,and their effects will have their own advantages and disadvantages according tothe different faults handled.Heuristic parallelism means that each distributednode utilizes different test generation algorithms to deal with the same fault.When a node generates a corresponding test vector,it will immediately notifyother nodes to terminate the current work and start processing the next fault atthe same time.This kind of method can guarantee a higher coverage than theserial algorithm,but the reduced time overhead is very limited.Search space parallelismSearch space parallelism divides the decision tree into multiple independentsub-search spaces,each of which is statically or dynamically assigned to nodeprocessing.Its upsides are low communication overhead and high parallelism,but its coding is relatively difficult.Function-level parallelismFunction-level parallelism is to divide the serial algorithm into unrelated subtasks,and then assign the subtasks to different nodes for parallel processing.Thisapproach must ensure that there are no common variables between subtasks.Otherwise,it will greatly increase the difficulty of parallel control,and in theworst case,it can only execute the subtasks in a serial order.At the same time,because each subtask performs completely different processing,it is difficultfor developers to estimate the workload of different tasks for load balancingrelated processing.Circuit parallelismCircuit parallelism is adopted when the circuit size is so large that the memoryof a single node cannot hold the relevant data of the entire circuit.It dividesthe topology of the circuit into sub-topologies and stores them in different nodes,and its performance greatly varies depending on the division method.Existingpartitioning methods often lead to a huge communication overhead,and it isdifficult to guarantee the parallelism of the algorithm.的数据传输开销大、GPU内存消耗大、GPU有效利用率低等问题,导致可扩展性差4043.然而,本文图计算方法可以通过挖掘电路图的拓扑信息,动态识别每一轮迭代中需要处理的电路图数据以及精确评估任务负载,通过只加载需要处理的电路图数据到GPU中,并基于识别的负载进行任务分配,从而提高GPU的利用率以及保证GPU的负载均衡.同时,也可以通过分析电路图的拓扑信息挖掘各并行任务数据访问之间的空间/时间关联性,规则化各任务的数据访问行为,使得大量任务能够共享电路图数据的存储和访问,极大减少电路图的冗余存储和访问开销,从而减少GPU的内存消耗以及主机和GPU之间的数据传输量.这使得我们方法具有很好的可扩展性,未来能够高效支持大规模电路图分析.2.3并行ATPG的挑战无论是DFT技术还是对于ATPG串行算法的优化,都已经发展到相当成熟的地步.近年来,有关这方面的新成果已经非常少,而且基本都是有关代数式的测试生成算法的工作,在工业界还没有得到215毛伏兵等:图计算在 ATPG 中的应用探究应用.随着硬件水平的提升,ATPG的并行化已经成为加速电路测试的最有潜力的研究方向之一.但是,现有并行ATPG的相关工作还面临着诸多挑战.(1)负载均衡问题.现有的并行ATPG方法对子任务的划分还停留在较为粗粒度的层次.以测试生成的故障级并行为例,该类方法将故障列表划分为子列表.多个处理器对这些子列表进行并行处理,也就是说处理器之间对不同的故障进行测试生成.而不同故障的测试生成过程的时间开销差距是十分大的,而且这个开销很难预估.这可能导致工作负载的严重不平衡,使并行给ATPG带来的收益大打折扣.(2)并行策略单一.无论是故障模拟还是测试生成过程都存在多种并行性,但是现有的并行ATPG系统中往往只采用某一种并行策略.不同的并行策略各有优劣,甚至在并行性上不互斥,对这些并行策略进行有机组合相较于执行单一的并行策略在性能上有更大的提升空间.另外,在现有的并行ATPG系统中,测试生成和故障模拟过程是紧耦合的.也就是说,每个并行任务既进行测试生成,也进行故障模拟.然而,测试生成和故障模拟之间的并行性并非完全一致.因此耦合方式也限制了并行ATPG系统能够采用的并行策略.(3)存储开销大,数据局部性差.传统的ATPG系统以链表的形式表达电路的拓扑,而将相关的所有状态数据全部放在同一个结构体中.这种存储方式使得并行任务必须维护单独的电路副本,在电路规模越来越大的情况下产生大量的空间开销.除此之外,大部分ATPG算法往往只处理少数几类状态数据.结构体链表的数据结构使得同种状态数据的存储在物理上是十分离散的,最终导致计算时访存效率低下.3图计算用于 ATPG将图计算应用于ATPG中是一种可行的并行化方案.电路的拓扑结构可以抽象为一般图,而故障模拟和测试生成都有很多结构式的算法是在电路拓扑的基础上执行的,这些算法可以转换为图算法.图计算中对并行任务的划分是细粒度的,它会把不同的顶点分配给不同线程进行处理.这在ATPG中相当于将单个逻辑门的处理视为一个可并发的子任务,而传统ATPG方法对逻辑门的处理都是串行的.通过这种逻辑门级别细粒度的划分,能够进一步提高ATPG的并行度,并且也更便于进行负载均衡.除此之外,电路在图计算系统中的存储方式也将发生很大变化.传统的ATPG系统以链表的形式表达电路的拓扑,而相关的所有状态数据全部放在同一个结构体中.这种存储方式不仅会产生较大空间开销,并且数据局部性也很差.图计算则完全将图结构数据和状态数据分离开来:图结构数据可以用压缩稀疏行(compressed sparse row,CSR)等压缩格式44存储,这样能减少空间开销;不同类型的状态数据用单独的数组存储,这样能提高数据的局部性.我们将在本节中简单介绍基于拓扑结构的组合电路算法在图计算模型下的实现.3.1组合电路的图抽象给定一个组合逻辑电路C,如图2(a)所示,电路由输入端集合PI(primary input)、输出端集合PO(primary output)、逻辑门集合CG和它们之间的连线构成.输入端、输出端和逻辑门都有信号值(或称为逻辑值).本文涉及的逻辑门类型包括:与门(AND)、或门(OR)、非门(NOT)、异或门(XOR)、与非门(NAND)、或非门(NOR)、异或非门(XNOR),以及自定义的扇出结点(STEM)等.图2(b)给出了该电路拓扑结构的图抽象,其中PI、PO和逻辑门被抽象为电路中的顶点,顶点自带类型值.图中的边用于表示电路中的连线,因为连线实际上用于信号值的传输,自带有方向这一属性,所以图中的边216中国科学:信息科学第 53 卷第 2 期(a)(b)图2(a)电路图;(b)相对应的带有一个 STEM 类型结点的抽象图Figure 2(a)Circuit graph;(b)corresponding abstract graph with a stem node均为有向边,方向同信号值传输方向一致.如果在电路中有元件向多个其他元件输出信号,即存在一个扇出节点,那么该节点会抽象为STEM类型的顶点4.3.2ATPG算法转化为图算法介绍我们用图计算中常用的Gather-Apply-Scatter(GAS)模型来说明如何将测试算法以图算法的形式描述3,44.GAS模型采用以顶点为中心的编程模型,将图处理中的一轮迭代分为3个阶段:Gather,Apply和Scatter.在Gather阶段,活跃顶点u收集邻接顶点和边的状态值,然后对这些状态值求广义和,即vNbrug(Du,D(u,v),Dv),(1)其中,Du,Dv和D(u,v)分别代表顶点u、顶点v和边(u,v)的状态值,顶点v是顶点u的邻接顶点.广义和运算是由用户自定义的操作,它必须满足交换律和结合律.式子中求出的值被Apply阶段用于更新活跃顶点u的状态值:Dnewu a(Du,).(2)最后,Scatter阶段用更新后的活跃顶点状态值Dnewu来将活跃顶点邻接边的状态值进行更新:v Nbru:(Dnew(u,v)s(Dnewu,D(u,v),Dv).(3)在Scatter阶段还会生成新的活跃顶点集合,用于下一轮迭代.当活跃顶点集为空时,图算法达成收敛.对于有向图,在Gather和Scatter阶段的扇入和扇出根据具体的算法确定.比如,在PageRank中,Gather阶段只对入边操作,Scatter只对出边操作.在GAS模型下,必须由用户定义4个接口函数:Gather(),Sum(),Apply()和Scatter().在Gather阶段,Gather()和Sum()分别用于收集邻接顶点的状态和对所有状态求广义和.Gather()并行处理邻接表中的边,将边和顶点的数据传给Sum()做广义和计算.Gather()可调用的边集可以是空集、入边、出边和所有邻接边,具体由用户来决定.Gather阶段完成后,Apply()获取最后的累加值,并根据累加值计算新的顶点状态.计算出来的顶点状态通过原子操作写回到对应的活跃顶点.在Scatter阶段,Scatter()也并行处理邻接表中的边,根据边和更新后的顶点的状态产生新的边值Dnew(u,v).对于很多图算法,在GAS模型下并不需要维护邻接边的状态值,这时Scatter()只用于活跃顶点集的更新.逻辑仿真是电路测试过程较为简单的算法,它的目的是根据给定的PI的逻辑值计算出电路PO的逻辑值.算法1给出了逻辑仿真在GAS模型下的图算法实现,它实现了GAS模型的4个接口函数,最后由LogicSim()调用这些函数以实现逻辑仿真的功能.具体来说,Gather()收集的是邻接顶点217毛伏兵等:图计算在 ATPG 中的应用探究(a)(b)图3(a)电路图;(b)相应的带有多个 STEM 类型结点的抽象图Figure 3(a)Circuit graph;(b)corresponding abstract graph with multiple stem nodes的逻辑值,并在Sum()根据顶点类型对收集的逻辑值进行逻辑运算.Apply()则会根据顶点类型判断是否对Sum()计算出的逻辑值进行取反,因为在Sum()中NAND,NOR和XNOR这几个逻辑门是和AND,OR和XOR做相同的处理.因为逻辑值是作为顶点的状态值进行存储的,逻辑仿真只需要维护这唯一的顶点状态值.因此,Scatter()只需要更新活跃顶点集,它将所有前驱顶点都完成逻辑值运算的顶点加入到下一轮迭代的活跃顶点集中.Algorithm 1 Logic simulationInput:G,Logic.Output:Logic.1:function Gather(u,e,v);2:return v;3:end function4:5:function Sum(a,b,type)6:if type AND,NAND then7:return a b;8:else if type OR,NOR then9:return a b;10:else if type XOR,XNOR then11:return a b;12:else if type=NOT then13:return b;14:else15:return b;16:end if17:end function18:19:function Apply(u,Accum,isActive)20:isActive isActive u;21:if u.type NAND,NOR,XNOR then22:Accum Accum;23:end if24:return Accum;25:end function26:27:function Scatter(u,e,v)28:v.count v.count+1;29:if Dv.count=Dv.indegree then30:isActive isActive v;31:end if32:end function33:34:function LogicSim(G,Logic,Type)35:isActive ;36:do37:for each vertex isActive do38:for each edge vertex.inNbr do39:Logicvertex Sum(Logicvertex,LogicGather(vertex,edge,edge.src),vertex.type);40:end for41:Logicvertex Apply(vertex,Logicvertex,isActive);42:for each edge vertex.outNbr do43:Scatter(vertex,edge,edge.dst);44:end for45:end for46:while isActive/=;47:return Logic;48:end function以图3来举例说明图计算用于逻辑仿真.初始化PI1,PI2的逻辑值为0,1,并把两个PI设置为活跃顶点.第1轮迭代开始.因为PI没有入边,因此这一轮迭代跳过Gather和Apply操作,通过Scatter操作将两个PI顶点的逻辑值传递给后续顶点STEM,该过程各顶点并行.两个STEM顶点在该轮迭代都收到一次Scatter信号,收到信号次数和STEM顶点入度相同,因此将它们设为第2轮迭代的活跃顶点.第2轮迭代开始,活跃顶点为两个STEM.第1个STEM进行Gather操作,收到一个逻辑值0,然后进入Apply阶段,STEM根据自身类型将逻辑值置为0,然后通过Sactter操作将逻辑值传递给后续顶点G1和G2.第2个STEM进行Gather操作,收到一个逻辑值1,然后进入Apply阶段,218中国科学:信息科学第 53 卷第 2 期STEM根据自身类型将逻辑值置为1,然后通过Sactter操作将逻辑值传递给后续顶点G1和G2.顶点在第2轮迭代都受到两次Scatter信号,收到信号次数和它们的入度相同,因此它们是第3轮迭代的活跃顶点.注意,对两个STEM的处理是并行的.第3轮迭代开始,活跃顶点为G1和G2.G1进行Gather操作,收到两个逻辑值0,1,然后进入Apply阶段,G1根据其自身类型AND,对逻辑值进行逻辑与操作得到G1逻辑值0,然后通过Sactter操作将逻辑值传递给后续顶点PO1.G2进行Gather操作,收到两个逻辑值0,1,进入Apply阶段,G2根据自身类型NOR将两个逻辑值进行或非得到逻辑值0,然后在Scatter阶段将逻辑值传递给PO2,对G1和G2的处理也是并行的.第4轮迭代开始,活跃顶点为PO1和PO2.PO1进行Gather操作,收到一个逻辑值0,进入Apply阶段,PO1根据自身类型将逻辑值置为0,因为PO1没有出边,跳过Scatter阶段.PO2进行Gather操作,收到一个逻辑值0,进入Apply阶段,PO2根据自身类型将逻辑值置为0,因为PO2没有出边,跳过Scatter阶段.最后没有活跃顶点,logic simulation算法结束.我们基于学术上流行的开源ATPG工具Atalanta45进行研究,对FAN算法(通过对电路中的关键节点进行决策)进行了支持.ATPG主要包括测试生成和故障模拟,对于显式故障模拟,类似于逻辑仿真,可用上面定义的4个接口函数进行实现.对于测试生成,在FAN算法中的蕴含(implication)、线确认(line justification)和回溯(backtrace)3个阶段用我们定义的4个接口函数进行逻辑值的计算.4图计算系统相关研究图计算是以图作为数据模型来表达问题,并对问题进行解决的过程12,44,4654.目前已经出现了单机图计算系统、分布式图计算系统,以及图计算硬件加速技术.单机图计算系统能处理小规模电路.然而,当电路规模大时(例如对于AI芯片,图顶点规模达到万亿规模),单机系统处理慢或是处理不了.需要用硬件加速技术进行加速或是用分布式系统进行处理.本节将对目前图计算系统相关研究进行基本介绍.4.1单机图计算系统单机图计算系统能充分利用单机处理图计算任务的能力,避免了分布式系统下代价高的网络通信开销.但是这类系统由于硬件资源有限,使其无法实现好的扩展性,需要的处理时间通常和图数据规模成比例55,56.单机图计算系统可分为两类,面向高端多核、大内存服务器的内存(in-memory)图计算系统5660和面向商用PC的核外(out-of-core)图计算系统6167.第1类在图处理过程中会将图数据完全放入内存中,第2类通常利用磁盘来存放图数据,它采取一定的划分策略来进行分块处理.典型的单机图计算系统通常会将图顶点和边划分为小的分片,以便分片能够在高速的存储设备中进行高效处理,并提供了充分的并行性和优化的访存模式.对于内存图计算系统,图数据进行划分的目的是使每个核心能有效处理各自分配的分片,有些内存图计算系统不需要显式地运用划分策略,只需要在计算过程中对任务进行适应性的调度,就可以取得很好的并行效果.对于核外系统,由于图数据无法被全部加载进内存,图划分策略使得分片能够被加载进内存进行处理.对于编程模型是以点为中心的图计算系统,一般将图顶点和边的分片同时加载进内存中.对于编程模型是以边为中心的系统只将图顶点分片整个加载进内存,边数据从磁盘上以流的形