新闻动态

       2017年6月5日，中心在理科5号楼410会议室组织了沈明华同学的博士论文答辩。沈明华同学的指导教师为中心副主任、特聘研究员罗国杰博士。中心罗国杰老师、孙广宇老师、梁云老师，北京大学信息科学技术学院王亦洲副教授、佟冬副教授，清华大学蔡懿慈教授，中科院计算所胡瑜研究员等作为评委参加了答辩。

       沈明华同学以“面向FPGA可重构计算的并行布线研究”为题进行了答辩报告。此次答辩会上，沈明华同学认真讲解了博士论文的研究意义与学术贡献，并就各位评委提出的问题进行了清楚、细致的回答。评委们一致认为，沈明华同学在答辩过程中，准备充分、表述清楚，对评委的提问做出了准确的回答，评委们投票一致同意，通过沈明华博士学位论文答辩，并建议授予其理学博士学位。

       沈明华同学在读期间以第一作者发表4篇学术会议论文 (ICCAD’15, FPGA’17, FCCM’17, ISLPED’17)，同时还有两篇在审的论文。他在FPGA并行布线研究中获得的突出成绩得到了老师们的一致认可。

附：论文摘要

       随着摩尔定律的日渐消逝，大数据的计算处理技术正在变得越来越并行化与异构化。并行化是基于多核或众核的处理器技术来实现数据并行计算，异构化是利用可定制化的加速器技术来提高数据计算能力。在加速器技术中，具有可重构能力的FPGA技术由于可以提供高性能与低功耗的特性，因而在数据计算领域受到了广泛的关注与重视。例如，微软公司目前已经设计并开发出基于FPGA的大规模计算平台，此平台不仅用于加速网络搜索引擎，而且也用于加速深度神经网络的应用。与其他基于CPU或ASIC的计算平台相比，在大数据处理的过程中FPGA具有更高的能效性以及灵活的可重构性，同时能够提供高性能的计算技术。然而，由于制造工艺的进步以及设计复杂度的提高对现有的电子设计自动化算法带来一系列全新的挑战，这其中漫长的硬件综合时间严重阻碍FPGA的广泛使用。而在这FPGA流程中，布线设计是最耗时且复杂，同时也是最关键的环节。因此本文拟通过并行技术对布线方法进行一系列研究。

       本文的研究内容及创新点如下：
       粗粒度并行布线方法设计
       本方法是基于线网递归式分配的策略来探讨粗粒度的并行性进而实现并行布线方法的设计。基本策略是将线网划分成三类子集，其中第一类子集由潜在冲突的线网构成，而第二类与第三类子集分别由潜在不冲突的线网构成。对于第一类子集中存在冲突的线网，我们利用串行技术的实现线网的布线；对于其他两个存在潜在不冲突的线网，我们可以利用并行技术实现线网的布线。这其中第一类子集中线网串行布线结束以后，其他两类子集中的线网才能执行并行布线，而且这三类子集中线网可以通过相同的分配方式执行递归处理。值得注意的是，对线网采用二分递归式分配的方法所估计的运行时间是接近于使用最优分配方法所估计的运行时间。我们的粗粒度方法是利用消息传递接口技术(Message Passing Interface, MPI)在多核分布式内存的平台上实现多进程式的并行布线。

       细粒度并行布线方法设计
       本方法是基于具有大规模并行性的GPU技术来探索细粒度的并行布线方法的设计。
       基本设计思路包括两个部分，其一是利用布线搜索空间压缩的思路设计GPU友好的串行布线方法，其二是映射此布线方法到GPU平台上同时使用动态并行技术加快布线算法。设计GPU友好的布线方法包括三个基本策略，首先利用线网的节点确定线网的布线子图，接着利用先验信息来静态的估计线网所使用的布线资源，最后利用动态扩展的策略保证线网在布线的过程中有足够的布线资源。值得注意的是，在动态扩展技术中，我们设计了边界检测的机制来判断线网资源是否增加。映射布线算法到GPU平台时，我们考虑两种并行策略，一是单条线网的并行布线设计，二是多条线网的并行布线设计；在单条线网并行布线的设计中，我们利用动态并行性技术实现三种类别的并行性，分别是拓扑驱动的节点级别的并行布线，数据驱动的节点级别的并行布线，和数据驱动的边级别的并行布线。值得注意的是，由于每条线网具有不同的引脚数目，因而三种布线方法也表现出不同的并行能力。依据这个特性，我们设计出混合的并行布线方法。在多条线网并行布线的设计中，我们利用线网之间的依赖性设计有效的并行布线方法。主要的策略是在维持原有布线顺序的情况下，并行布通相邻的独立的线网，串行布通存在依赖的相邻线网。由于混合并行布线方法能够获得更多的并行性，我们引出虚拟节点的概念，将多个独立的线网连接成单一的线网，并利用混合方法实现并行处理。
       串行等价并行布线框架设计。
       在设计并行布线方法时，串行等价性是非常重要的影响因素。在软件工程维护中，这个因素可以使得递归测试更加容易以及用户售后支持更加方便。本方法是基于线网的调度策略来设计串行等价的并行布线方法。基本策略是在每次布线迭代的过程中，通过调度线网形成不同的子集，其中子集中的线网相互保持独立，不同子集间的线网存在依赖。我们并行执行子集内的线网，然后进行同步，接着并行执行下一个子集，直到所有子集中的线网布线结束。值得注意的是，我们并行布通子集内的线网，串行布通每一个子集。另外，我们设计的调度算法是最优的且可证明的。与此同时，我们在不同的平台上执行此调度算法都可以获得串行等价的布线结果。

       布线在FPGA的设计流程中是一个复杂且费时的关键步骤，而高效布线方法的设计是一个极具挑战性的问题。本文发现，对FPGA布线进行并行设计是一种行之有效的手段：粗粒度并行方法需要依据线网之间的冲突关系来确定分配进而获得可并行布线的线网。细粒度并行方法是对单条线网进行并行布线处理，两种粒度的并行布线方法相互配合，可以达到最好的效率。串行等价并行方法能够保证并行布线结果与串行布线结果一致，进而可以使得软件维护中的递归测试与用户支持更加容易。本文提出的一系列并行布线方法为电子设计自动化方法的并行布线设计提供了一条重要的研究思路，并且加以数学证明，同时通过实验进行了验证。本文相关内容多次在设计自动化以及与FPGA有关领域的国际顶级会议上发表，有望推动当前与FPGA设计有关的并行布线方法的发展。