摘要 ATPG (automatic test pattern generation)是VLSI (very large scale integration circuits)电路测试中非常重要的技术,它的好坏直接影响测试成本与开销.然而现有的并行ATPG方法普遍存在负载不均衡、并行策略单一、存储开销大和数据局部性差等问题.由于图计算的高并行度和高扩展性等优点,快速、高效、低存储开销和高可扩展性的图计算系统可能是有效支持ATPG的重要工具,这将对减少测试成本显得尤为重要.本文将对图计算在组合ATPG中的应用进行探究;介绍图计算模型将ATPG算法转化为图算法的方法;分析现有图计算系统应用于ATPG面临的挑战;提出面向ATPG的单机图计算系统,并从基于传统架构的优化、新兴硬件的加速和基于新兴存储器件的优化几个方面,对图计算系统支持ATPG所面临的挑战和未来研究方向进行了讨论.

摘要 移动蜂窝系统正经历着从2G/3G/4G到5G的交错式代际进化过程,多样化的信号与协议长期共存.如何在庞大、异构、高动态的蜂窝环境中保证服务的高速(传输快)、高能效(耗电少)和高可靠性(不断网)成为至关重要但又非常困难的问题,该问题同时涉及手机制造商、网络服务提供商、操作系统和应用软件开发商.我们研究和综述了近年来针对该问题的代表性工作,发现蜂窝系统表观层面的多个反常性能问题,实际上归因于核心机制层面隐蔽而深刻的“近因现象”:受社会舆论和商业宣传影响,在选择使用移动网络时,存在非理性的代际偏颇和不自觉的速度至上倾向,进而引发了偏向5G的“亏损迁移”、网络容量的“饱和饥饿”以及基站连接的“乒乓跳跃”等连锁效应.为修复上述缺陷,我们提出基于4G/5G双连接以及非齐次时变马尔可夫过程的自调控技术设计,将5G设备的故障发生率降低40%并将所有设备的平均故障持续时间缩短36%,同时探讨我们基于大规模工业合作实践的洞察和创新.

摘要 随着各类机器学习算法的广泛应用,高能效地定制机器学习系统受到越来越多的关注.定制机器学习系统高效部署的关键在于其编程与编译环境.中间表示是编程与编译环境的核心,用于连接上层编程语言和底层硬件指令.当前的中间表示或是面向上层算法或是面向以标量处理为核心的传统处理器,难以高效应对以张量处理为核心的机器学习系统.本文提出了面向机器学习系统的张量中间表示,以提升机器学习系统的编程和运行效率.具体而言,我们定义了一系列张量类型,张量操作及张量存储空间,并在此基础上进行张量处理优化.我们将所提出的张量中间表示对TVM的底层标量中间表示进行了扩展并在典型机器学习系统上进行了实验.我们探索了原有中间表示没有发掘的优化并取得了1.62～2.85倍的性能提升,同时在典型算子的开发效率上平均提升了5.46倍.

摘要 下一代互联网是全球各国推动科技产业革命和重塑国家长期竞争力的基础设施和先导领域,同样也是高科技密布、专利密集的战略性新兴产业领域,技术研发与创新竞争异常激烈.本文运用专利导航方法对全球下一代互联网互联设备相关技术进行了分析,通过对本导航领域多位技术专家的访谈,澄清和界定了下一代互联网互联设备关键技术的基本定义与范畴,从总体趋势、地域、核心申请人、核心发明人、专利强度、我国向国外申请专利,以及技术分支等方面分析了全球及我国下一代互联网互联设备关键技术的专利布局现状、竞争前沿和未来趋势,结合本导航领域国内外典型案例的总结,对研发创新和专利运用提出了相应的导航建议.

摘要 随着摩尔定律(Moore’s law)与迪纳德(Dennard)缩放定律逐步走向终结,依靠集成电路制程工艺的进步提升计算系统性能与效能越来越困难,计算体系架构的演进成为了未来计算系统发展的重要技术途径.本文首先从应用适应性、计算驱动方式、系统重心变化、计算核心构成,以及计算逻辑使用等不同的角度回顾了体系架构的发展历程,总结了不同体系架构的优缺点;然后着重分析了在人工智能、大数据等应用飞速发展的条件下未来计算系统的能力需求特征;最后提出了软件定义计算体系架构,并梳理了其重点研究内容与关键技术,为未来计算体系架构的发展提供了一条可行的技术途径.

摘要 微处理器是现代信息系统的核心基础设施.大数据、人工智能、5G等技术的快速发展催生了数据量的爆发性增长,随之对数据处理能力的需求也急剧增长.专用计算技术被广泛认为是后摩尔时代的计算机体系结构演化的重要方向.专用处理器技术的发展一直伴生着通用处理器的发展,数字信号处理技术甚至早于传统意义上的通用处理器.通用处理器技术的发展,不仅在商业上取得了巨大的成功,很多关键技术也被专用处理器吸收借鉴用于提升专用计算的性能、优化可编程性等.本文主要分析了数字信号处理器(DSP)、图像处理器(GPU)、深度学习处理器(AI芯片)和网络处理器(NPU)的关键技术特征,并进一步对专用计算架构未来发展可能涉及的关键点作出了简要的评述.

摘要 流连接广泛应用于提取多源流数据之间的关键信息,是大数据处理的重要支撑技术.但连接两条大数据流时大规模的连接谓词计算,使其易成为性能瓶颈.为提高处理性能,流连接系统常采用并行和分布式两种方式扩展.然而,采用多核并行的流连接系统的扩展性受到CPU核数限制,无法应对大规模数据流.采用分布式扩展的流连接系统由于引入分布式框架运行的开销,导致硬件处理效率严重下降.为实现高效大规模扩展,本文提出一种利用FPGA加速器外设向上扩展的流连接系统FJoin.加速器可进行高并行的流动连接,载入多个流元组后,连接窗口中的数据流经一次即可完成所有连接计算.对于逻辑容易在FPGA实现的连接谓词,通过大量基本连接单元串联构成深度连接流水线,实现大规模并行.通过主机CPU和FPGA设备协同进行连接控制,将连续的流连接计算划分为独立的小批量任务,高效地保证并行化流连接的完整性.在装备FPGA加速卡的平台实现了FJoin,基于大规模真实数据集的测试结果表明,对比部署在40个节点集群上的目前最好的分布式流连接系统,本文提出的流连接加速器FJoin可在单一FPGA加速卡上将连接计算速度提升16倍,达到5倍的系统吞吐,且时延满足实时流处理要求.

摘要 随着现实世界中图计算需求的快速增长,同一平台上往往并发运行着大量迭代图分析任务.然而,现有的图计算系统主要是为了高效执行单个图分析任务而设计的.因此,当多个并发图分析任务同时在同一个底层图上并行执行时,现有图计算系统会面临巨大的数据访问开销.为了提高并发图分析任务的吞吐量,现有的核外并发图处理方案通过共享图数据减少并发任务的数据存储与访问开销.但是,由于现实世界中图的图顶点度数幂律分布特性以及图分析任务之间的差异性,现有方案在访问数据时依旧存在着大量的不必要的冗余I/O开销.这是因为即使静态图分区中绝大部分顶点处于非活跃状态或者只被少数图分析任务共享,现有方法也依旧会将整个分区加载入内存供并发图分析任务处理.为解决上述问题,本文提出了一个面向并发图分析任务的高效存储系统GraphDP.它能够插入到现有核外图计算系统中来透明有效地减少现有图计算系统执行并发图分析任务时的存储消耗与数据访问开销,从而提高并发图分析任务的吞吐量.具体来说, GraphDP使用一种新颖的动态I/O调度策略,能够使系统以最优的I/O访问方式完成图数据的加载,并有效地减少加载到内存和cache的数据.同时, GraphDP通过高效的缓存机制在内存中优先缓存被频繁访问的图数据,从而进一步减少数据访问开销.为证明GraphDP的有效性,我们将GraphDP插入到目前流行的核外图计算系统中,包括GridGraph, GraphChi和X-Stream.实验结果表明, GraphDP分别将GridGraph, GraphChi和X-Stream的吞吐量提高了1.57～2.19倍, 1.86～2.37倍和1.62～2.21倍.

摘要 LEO巨型星座因其广覆盖、高通量及低延时的通信潜力而受到越来越多的关注.然而由于所处空间环境复杂及自身特点等原因, LEO巨型星座容错问题亟待研究.为此,本文关注如下问题:如何保证卫星失效后,网络流量依然无拥塞正常转发?本文提出了基于流量工程的主动容错方法 SN-FFC,主要思想是通过合理的链路冗余,使得对于至多k (k为可调参数)个卫星失效,网络流量依然能无拥塞正常转发. SN-FFC首先设计基于流量工程的容错建模方法,随后针对模型计算复杂度高的问题,提出基于对偶理论的算法,使得复杂度从O(C_n~k)降低到O(n).基于Starlink第一阶段星座模型的仿真实验表明SN-FFC相较现有方案,能实现故障下的无拥塞转发,并且计算时间和吞吐量开销较低.

摘要 随着信息技术创新日新月异,数字化、网络化、智能化深入发展,新应用层出不穷、新业态蓬勃发展,对业务系统的敏捷构造和持续运维提出了更高的要求.为此,本文提出了一种新的计算模式:方舱计算.所谓方舱计算,是通过网络访问的,面向IT任务全生命周期的跨域资源配置和协同的计算集成环境.其核心是"方舱专用机动、资源跨域伸缩、系统运维自治".本文给出了方舱计算系统结构及其工作原理,方舱计算系统主要由方舱生成与管理系统、跨域资源管理系统、虚拟数据中心系统和若干网关(方舱网关、虚拟数据中心网关、跨域资源网关等)组成.进而,给出了适于方舱计算的资源分配最优化问题定义,在兼顾数据资源、计算资源和存储资源等的基础上,实现最小化资源成本.通过规划求解器与近似优化算法仿真实验,表明本文的方法能够兼顾数据资源和物理资源的分布,实现方舱资源的优化配置.

摘要 互联网和物联网规模的迅速扩张促使全球数据存储总量呈现爆炸式的增长,导致数据系统从计算密集型向数据密集型方向发展.如何构建可靠高效的数据存储系统,成为大数据时代迫切需要解决的问题.相比传统磁盘,非易失主存具有性能高以及字节寻址等优点,这些独特的优势为高效存储系统的构建提供了新的机遇.然而,传统存储系统的构建方式不适用于非易失主存,无法发挥出非易失主存的性能优势,并且容易造成一致性开销高、空间利用率低、编程安全性低等问题.为此,本文分析了基于非易失主存构建存储系统面临的挑战,在系统软件层次分别综述了空间管理机制、新型编程模型、数据结构、文件系统和分布式存储系统等方面的研究进展,并展望了基于非易失主存构建存储系统的未来研究方向.

摘要 除法运算是基本四则运算之一,如何进行快速除法一直是电子计算机、嵌入式系统和其他新型计算系统广受关注的问题.充分发挥三值光学处理器位数众多、运算功能可重构、按位可分配等优势,设计出高效并行MSD (modified signed digit)数除法器对提高大数据除法的运算效率、促进三值光学计算机(ternary optical computer, TOC)在数值计算领域的应用意义重大.本文首次提出MSD数的符号判定算法,并基于SRT算法首次提出利用一个并行无进位SJ-MSD加法器和一个MSD数比较器实现单组MSD整数除法或多组MSD整数并行除法方案——并行MSD整数除法,该算法对于被除数等长的多组与单组MSD整数除法需要的机器周期是相同的.实验表明,并行MSD整数除法方案是可行的,它将有效地提高大数据处理效率并加速TOC进入数值计算等实际应用领域.

摘要 多租户公有云是云计算的一种重要组成形式.近年来,多租户公有云数据中心在如火如荼发展的同时,其过低资源使用率所导致的巨大能耗浪费也引起了社会的高度关注.然而,由于多租户公有云的资源通常以"包年包月"的租赁形式预留给租户,云服务提供商无法通过关闭空闲服务器等常用能耗管理方法来降低数据中心能耗.针对这一难题,本文提出了面向多租户数据中心资源回收利用的激励机制来提升多租户数据中心能效.该机制以经济激励的形式来回收利用租户空闲预留型资源,即云服务提供商向租户支付合适的经济补偿,从而回收租户空闲预留型资源,并充分利用其运行其他云计算服务(如电商和搜索服务).基于Lyapunov方法,本文设计并分析了一种面向租户预留资源回收利用的动态定价算法,该算法无需预测系统未来信息便可作出在线定价决策,并且在保障系统稳定性的同时使得云服务提供商长期成本无限接近于理论最低值.通过严格的数学证明以及由真实数据驱动的仿真实验,本文验证了所提出的激励机制在回收利用租户空闲资源方面的有效性.

摘要 随着应用数据处理需求的激增,在传统冯·诺依曼(von Neumann)体系结构中,处理器到主存之间的总线数据传输逐渐成为瓶颈.不仅如此,近年来兴起的数据密集型应用,如神经网络和图计算等,呈现出较严重的数据局部性,缓存命中率低.在这些新兴数据密集型应用的处理过程中,中央处理器到主存间的数据传输量大,导致系统的性能不佳且能耗变高.针对传统冯·诺依曼体系结构的局限性,内存计算通过赋予主存端一定的计算能力,以缓解因数据量大以及数据局部性差带来的总线拥堵和传输能耗高的问题.内存计算有两大形式,一种是以高带宽的连接方式将计算资源集成到主存单元中(近数据计算),另一种是直接利用存储单元做计算(存内计算).这两种形式有各自的优缺点和适用场景.本文首先介绍并分析了内存计算的提出和兴起原因,然后从硬件和微体系结构方面介绍内存计算技术,接着分析和总结了内存计算所面临的挑战,最后介绍了内存计算给目前流行的应用带来的机遇.

摘要 机器学习方法对网络流量分类的前提是假设流量具有独立同分布性,而实际情况下流量特征不断发生变化,导致该方法在处理海量、不具备独立同分布的流量数据时开销较大,计算复杂度较高,精度较低.针对上述问题,本文提出一种新的分类模型.该模型将PCA算法与改进的深度卷积神经网络分类模型(improved deep LeNet-5 convolutional neural networks, LCNN)相结合进行流量分类.前者进行降维分析,发现影响检测精度的关键特征,后者采用自主特征学习方式提升分类精度.实验表明,本文方法的内存开销较之前方法降低了3.2%,检测精度提升了5%～8%.