技术征文第7期：基于分布式计算框架的自动测试向量生成算法（海思篇）--东南大学--New Time队

一、活动背景

集成电路EDA设计精英挑战赛 是国内首个EDA领域专业赛事，赛题覆盖EDA应用及算法，从本科到博士都可参赛，需具备计算机、电子、物理、数学等知识储备，对参赛队伍的要求极具综合性。通过两届大赛的举办，受到了来自产业及高校的高度关注，产业界和学术界专家反馈，参赛作品具有很好的参考和学习价值，继第一届后现选出第二届优秀作品并参与技术征文投稿的队伍作品和大家分享。

二、团队介绍

队伍名称：New Time

队伍成员：金蕾蕾 叶雨阳 王宗辉

所在学校：东南大学

获奖情况：2020第二届集成电路EDA设计精英挑战赛全国总决赛麒麟杯

指导老师

闫浩，东南大学电子科学与工程学院国家专用集成电路系统工程技术研究中心讲师，硕士研究生导师。研究方向聚焦于面向宽电压高能效设计的静态时序分析和良率分析等设计方法学。近年来主持国家自然科学基金青年项目、国家重点研发计划等项目。

三、赛题介绍

本次分享的作品题目是由海思命制的赛题：基于分布式计算框架的自动测试向量生成算法

华为海思是全球领先的fabless IC半导体与器件公司，扎根基础、持续创新，引领产业发展，在半导体领域具有关键地位。业务范围覆盖通信设备、智能终端、光电、处理器、AI等领域。多年来，先后推出麒麟、巴龙、鲲鹏、昇腾等系列芯片，支撑华为ICT产品竞争力在业界持续领先。

四、作品分享

1、参赛作品背景

在 VLSI 电路 的设计过程中，DFT 是保证回片测试质量的重要手段，TPG（Test Pattern Generation）是其中一个重要的环节。随着电路规模的增大、设计复杂度的提升和先进工艺演进，高效率、高质量的产生测试向量变得更加困难。

ATPG（Automatic Test Pattern Generation ）是整个TPG Flow中的核心组件，一个好的工业级ATPG算法应能够在更短的时间内，产生更少的测试向量数并获得更高的测试覆盖率，使得测试成本更低。多年以来，业界针对 ATPG 有着持续研究，从布尔差分法、GF二值算法将电路模型转换成数学模型来生成测试向量，到D算法及其改进算法 PODEM、FAN等基于故障激活的测试向量生成算法，以及BDD、SAT Based ATPG 算法，持续努力在寻求新的算法方案 以达到高效率、高质量的测试向量。随着电路规模的日益增大，TPG Flow的性能逐渐成为瓶颈主要表现在算法的效率和内存两方面。在算法上的优化探索不能十分有效地解决问题。传统的数据计算和数据存储方式已经无法满足要求。为解决内存和效率问题业界提出了分布式的解决方案。MapReduce6是当前较为成熟的开源分布式计算框架Hadoop和Spark是MapReduce框架的两个比较有影响力的实现。Hadoop的核心组件包括Hadoop Distributed File System HDFS、Hadoop MapReduce 等模块，其中HDFS完成数据的分布式存储，Hadoop MapReduce完成数据的分布式计算。而Spark不同于Hadoop的是其job的中间输出和迭代结果可以保存在内存中，从而可以获得更高的数据访问速度。同时，结合 Redis 高性能数据库，在提升TPG中的静态数据的读取速度方面有较大可能性。

综上所述，分布式计算框架与Redis的结合来实现TPG Flow是当前解决TPG Flow性能瓶颈问题的值得探索方向之一。

2、作品成果

结合题目的要求我们将主要工作分为了两个部分：

1）针对ATPG算法的改进

2）分布式ATPG算法的实现

3、作品创新点

分布式系统方面：我们实现了基于Spark的分布式ATPG算法流程，并且使用了共享内存帮助我们减少通信成本，实现更高效的访存。

算法方面：我们针对ATALANTA的FAN Engine进行改进，结合主流的SAT Based ATPG以及Random ATPG，完成了一个Random TPG + FAN TPG + SAT TPG的完整ATPG Engine，并且针对传统的Random TPG和SAT TPG以及FAN TPG算法都进行了改进。

4、问题及解决方法

一、ATPG算法：

1.Random TPG：

RTPG的本身加速原理是在Trade-off 生成Cube以及仿真Cube的性能，从左边的例子中我们可以看到ATPG是远远比Simulate过程要耗时的，在880-54479的bench集合中，单核ATPG的时间平均占比达到了85.59%，是Simulate时间耗时的6倍，针对ATPG系统这个特点，我们提出了Random-Based TPG方法，即在ATPG之前，随机生成几组固定数目的测试向量并进行Simulate，仅仅将Undetected Fault-list交付给ATPG，此时的Fault-list规模远远小于原始Fault-list，所以可以大幅度提升TPG的性能。

但是随机测试向量的覆盖能力是有限的，往往是一开始可以覆盖大部分“易检测Fault”，但是后期就很难有提升，所以何时停止RTPG过程是RTPG应用过程中必须解决的一个关键问题；另外，RTPG并不是对所有的Bench都可以取得很好的效果，降低“试错成本”同样是一个需要解决的难题。 

为了解决好上述两个问题，我们提出了右侧的RTPG应用流程，即Simulate过后如果Fault 覆盖率提升没有大于1%或者达到我们设置的RTPG次数上限，都会退出RTPG过程进入ATPG过程，并且一组随机测试向量的数目仅仅为32，很好的控制了“试错成本”。

2.改进FAN TPG：

针对FAN ATPG的改进，我们在测试时发现，ATPG针对某个Fault生成的Cube在Simulate过后生成的pattern，对应Fault的关系是“一对多”的映射关系，即一个Fault通过FAN算法生成的Cube可能可以用于检错多个Fault。

针对Cube的这个特点，我们在应用FAN ATPG过程之前提出了Select Fault的过程，即仅将Fault-list中具有代表性的Fault挑选出来，进行ATPG，再针对这些Cube进行Simulate，生成Pattern，输出undetected fault并将其再次输入Select Fault，重复过程，为了充分利用FAN ATPG过程，我们将ATPG的终止条件设置为了覆盖率提升小于0.25%。

这个过程的核心任务是如何Select Fault，我们在认真分析Fault-list后发现，存在很多Fault与其他Fault之间存在包含关系，如电路图所示，Fault b、c、d均为Fault a 的子集，而我们算法实现Select Fault的主要依据。

基于以上的特点我们提出了改进后的FAN TPG流程：

3.SAT TPG：

FAN方法中的回溯标准值，可以用来调节FAN方法的检错能力，即值越大，检错能力越强，FAN ATPG过程也越耗时；但是在针对一些大bench时，例如c103505中将回溯标准值设置为10时，覆盖率仅为89%，哪怕是不计耗时成本，将回溯标准值设置为1000，覆盖率也仅达到了90%都不能满足95%的覆盖率要求，所以此时需要更加高级的算法来提高覆盖率，所以经过广泛调研，我们选用了目前EDA业界比较认同的SAT ATPG算法来解决这个问题，即将电路TPG问题转换为布尔可满足性问题，进行求解。

SAT ATPG的实现过程涉及到两个核心问题：

一个是如何将电路信息转换为CNF即SAT（布尔可满足性）问题，另一个是实现DPLL算法求解SAT问题。

其中电路信息转化为CNF可以通过比较常见的逻辑推理和数学归纳方法完成。

DPLL算法部分的细节较多，由于时间的关系，这里就不完全展开讲解了，但是可以将算法本身理解成为一个一定约束下的搜索决策算法，并且在搜索与决策过程中会不断增加约束，当结果与约束存在矛盾时进行回溯重新进行决策搜索，直到输出结果SAT或发生顶层冲突输出UNSAT。

整个SAT问题的时间开销主要集中在电路信息转化为CNF的过程中，并且伴随着电路规模的不断增大，CNF的规模也越来越大，导致生成与求解的时间不断增加，于是针对这个问题我们提出了两种方法来加速这个过程。

Incremental CNF Generation，传统的SAT-Based方法，会将标准电路的全体Fanout cones以及Transitive fanin cones与故障电路用XOR逻辑连接，生成CNF并且进行求解，由于电路规模过大，无论是在cnf生成过程还是求解过程都需要大量的时间开销；但实际上输入测试向量只需要让标准电路与故障电路在一个Fanout的输出值存在差别，就可以利用这个测试向量对该Fault进行检测，根据这个特点，我们提出了片段“标准电路”，片段“故障电路”的概念，大幅度减小了需要求解的电路规模，提高了算法效率。

并且针对同一个的bench的不同Fault，片段标准电路的CNF存在可复用性，可以存储下来后需要时激活使用，避免每次重新生成，这就是我们动态激活cnf方法的核心观点。

二、分布式

分布式设计是并不局限与该竞赛项目的一种通用技术手段，我们结合一些成熟的框架与解决方案对分布式技术进行了移植落地。针对该项目，分布式工作解决了以下难点：

难点1：如何实现 Redis 存储数据、共享内存的功能；如何对 ATALANTA 中的复杂数据结构上传/共享。

为了解决这个难点，一方面我们将每一个Gate * 的信息都通过hiRedis中的函数r->set上传到Redis上并进行网表拼接。另外在share-netlist这一步把网表信息上传至共享内存，使用fork函数，把网表的真实路径给fork函数，得到一个用来标识共享内存块的键值key，然后通过调用shmget来分配一个共享内存块。

难点2：如何实现 Spark 对 ATALANTA 工程的调用；如何实现Spark 对输入输出流的控制。

我们具体解决方案和实现原理如图，SparkContext 是与 ClusterManager的接口，是由我们来创建的，SparkContext去向集群管理器ClusterManager申请资源同时给出需要多少CPU和内存等资源，ClusterManager去找WorkerNode并启动Excutor，通过Driver拆分成一批批的Task，将Task送给Executor去执行，这个过程不断迭代，直到所有Task执行结束。

我们最终给出的Spark需要下图的几个输入参数。包括Benchname Team名 HDFS输出目录并行核数。

五、团队采访

1、如何选择赛题

根据自身的相关知识能力以及兴趣进行选题。

我认为EDA的赛题大致可以分为两类：一类是电子相关课题；另一类是已经高度转化后的纯算法问题。

电子信息专业的同学可以选择电子相关的课题，发挥自身的专业优势，并且加深自身的专业理解；而计算机以及数学相关专业的同学则更加适合纯算法问题，为他们节省了大量理解赛题的时间，有利于他们在算法上进行创新突破。

2、如何组织

在完成选题和确定团队成员的基础上，我们首先不急于推进工作来解决问题，而是首先立足于问题本身，所有团队成员分工对问题的提出背景、产业界和学术界的研究现状做了充分调研，这一部分耗时1-2个周。

在经历了前期充分调研与充分熟悉题目的基础上，我们讨论确定了项目要实现的具体参数目标和基本的实现路径，绘制了完整的备赛路线图和每个节点的检查目标。

这之后，我们进入团队分工阶段。分工是基于团队每个成员不同的技术栈进行落定的，针对选题，我们团队分工分为ATPG算法优化、分布式和多线程设计、整体项目工程实现三大方向。

最后在截止时间为前2周的时候，我们已经完成了基本工作的开发，进入收尾梳理阶段和比赛要求的报告文档的撰写阶段。

3、团队如何分工

在前期1-2个周的调研基础上，我们结合产业界和学术界的研究现状，提出了我们竞赛的具体参数目标和实现路径，已经团队成员的分工和对应的时间线、节点检查目标。

针对赛题要求和团队的成员技术栈情况，我们划出了ATPG算法优化、分布式和多线程设计、整体项目工程实现三大方向，对进行了分工。

在备赛过程中，保持一个高效的团队交流和信息互通是非常重要的，我们创建了团队资料的文档沉淀空间和网盘空间，创建了项目的git仓库并定期维护与合并代码，我们每周内进行2-3次碰头讨论，最终保证了比较高效地完成了项目。

4、资源推荐

视频课程：https://www.youtube.com/watch?v=nX0XCD0ggHs&list=PLvd8d-SyI7hjk_Ci0zpTqImAtpEjdK5JF&index=1

L.T. Wang, C.W. Wu, and X. Wen, “VLSI Test Principles and Architectures”, Morgan Kaufmann, 2006.

（台湾李老师的VLSI Testing是很经典的课程，讲的非常用心，对于初学者来说，是很不错的入门课程。）

Rolf Drechsler ,Stephan Eggersglüß, “Test Pattern Generation using Boolean Proof Engines”, Springer, 2009.

（Rolf是今年ICCAD的主席也是SAT方面的专家，如果同学们希望对于SAT ATPG相关的知识有更加深刻的理解，这本书是很不错的学术材料。）