片上多核处理器存储一致性验证

存储一致性验证是片上多核处理器功能验证的重要部分.由于验证并行程序的执行结果是否符合存储一致性模型理论上是NP难问题,现有的验证方法中只能采用一些时间复杂度大于O(n3)的不完全方法.发现在支持写原子性的多处理器系统中,两条执行时间不重叠的操作之间存在确定的时间序.通过引入时间序的概念,设计并实现了一种线性时间复杂度的存储一致性验证工具LCHECK.LCHECK利用时间序将验证局部化,使得在表示程序执行结果的有向图中,序关系边的推导和正确性检测都被限定在有限范围内.与现有其他方法相比,LCHECK时间复杂度低,对程序长度和访存地址数没有限制,因此验证效率更高.作为国产片上多核处理器龙芯3号的重要验证工具,LCHECK发现了一些存储系统的设计错误.

片上多核处理器共享资源分配与调度策略研究综述

对于片上多核处理器,如何在多线程间公平有效地分配调度有限的共享资源是一个很重要的问题.随着处理器核规模的增长,多线程对于系统中有限的共享资源的争夺将愈发激烈,由此导致的对于系统性能的影响也将更加显著.为了缓解乃至解决这一问题,除了增加可用共享资源外,一个能够公平有效地在多线程间分配共享资源的调度算法也至关重要.在各类共享资源中,对于系统性能有着最大影响的是共享缓存和动态随机存储器(dynamic random-access memory,DRAM)系统.对于共享缓存,可以通过缓存分区来降低由于线程间的争夺所带来的影响;对于DRAM系统,可以采取适当的调度算法来调节各个线程发出的访存请求的服务优先级,从而改善系统性能.首先分别以系统吞吐量和公平性为优化目标介绍了一系列对共享缓存的分区调度算法,并针对缓存分区粒度过大的问题给出了相关解决方案.然后从利用线程的访存行为特征和借鉴网络路由算法等多个角度介绍了DRAM的调度算法.研究了从全局出发的联合调度算法,以解决针对不同共享资源的调度算法间相互矛盾的问题.最后从不同角度对于今后的研究进行了展望.

片上多核Cache资源管理机制研究

随着片上多核成为处理器发展的主流和片上Cache资源的持续增长,Cache资源的管理已成为片上多核的关键问题。介绍了片上多核Cache资源管理的研究进展,依据研究内容将Cache资源的管理分为Cache划分和Cache共享两类。对Cache划分,探讨了其主要组成部分和一般形式,分析和比较了典型的片上多核Cache划分机制。对Cache共享,给出了其主要研究内容,并介绍和比较了几种主流的片上多核Cache共享机制。通过分析,认为软硬件协同管理的页划分应是未来片上多核Cache划分机制的研究重点;而片上多核Cache共享机制的研究则应从目标应用的Cache行为特征着手。

Amdahl定律在层次化片上多核处理器中的扩展

层次化片上多核处理器以紧耦合的多个核构成超节点,对访存和片上通信的局部性有良好支撑,能有效地缓解片上多核中数据通信带来的通信开销.在关于多核处理器的Amdahl开销/性能模型已有的研究基础上,引入片上数据通信延迟作为Amdahl任务计算开销的新元素,构建了层次化片上多核处理器的Amdahl加速比扩展模型.基于该扩展模型,就层次化片上多核处理器的加速比与超节点配置的关系问题展开研究.模拟分析发现,要获得良好的加速比性能,层次化片上多核处理器需要在超节点数目与超节点的大小(超节点内核的个数)之间作仔细的权衡;对于给定核数目的层次化片上多核处理器,使系统性能最优的超节点大小往往出现在中间某个值而不是最大或者最小,并且该值随着系统规模的变化会发生相应的变化.

片上多核处理器验证:挑战、现状与展望

随着集成电路工艺水平的不断提升以及应用对处理器性能要求的日益增长,验证已成为未来片上多核处理器发展的主要技术瓶颈.文中深入分析了片上多核处理器验证中状态空间大、完备性不足、存储结构与互连网络验证复杂、硅后验证困难等突出问题,系统地总结了片上多核处理器模拟验证、硬件仿真、形式验证、硅后验证等方面的研究进展,并对该领域未来的发展方向进行了分析与展望.

片上多核处理器Cache一致性协议优化研究综述

现代晶体管技术在单芯片上集成多个处理器已经成为现实.近年来,随着多核处理器集成核数的不断增加,高速缓存的一致性问题凸显出来,已成为多核处理器的性能瓶颈之一,亟待解决.介绍了片上多核处理器一致性问题的由来.总结了多核时代高速缓存一致性协议设计的关键问题,综述了近年来学术界对一致性的研究.从程序访存行为模式、目录组织结构、一致性粒度、一致性协议流量、目录协议的可扩展性等方面,阐述了近年来缓存一致性协议性能优化的方向.对目前片上多核处理器缓存一致性协议设计中存在的问题进行了讨论,并指出了未来进一步研究的方向.

求解N皇后问题的片上多核并行混合遗传算法

遗传算法求解大规模皇后问题的耗时长、速度慢。为此,在分析现有N皇后问题求解方案和并行遗传算法的基础上,将动态规划引入到局部搜索策略中,在多核平台实现粗粒度并行遗传算法(CPGA)用于求解N皇后问题,避免传统的粗粒度并行种群迁移、通信等开销。针对并行化后多个子种群解趋同、迭代慢等问题,提出改进的面向遗传算子并行化的遗传算法(OOPGA)。实验结果表明,改进后的OOPGA算法在运行时间、加速比等方面均比CPGA算法好。

片上多核处理器容软错误执行模型

随着工艺的进步,微处理器将面临越来越严重的软错误威胁.文中提出了两种片上多核处理器容软错误执行模型:双核冗余执行模型DCR和三核冗余执行模型TCR.DCR在两个冗余的内核上以一定的时间间距运行两份相同的线程,store指令只有在进行了结果比较以后才能提交.每个内核增加了硬件实现的现场保存与恢复机制,以实现对软错误的恢复.文中选择的现场保存点有利于隐藏现场保存带来的时间开销,并且采用了特殊的机制保证恢复执行和原始执行过程中load数据的一致性.TCR执行模型通过在3个不同的内核上运行相同的线程实现对软错误的屏蔽.在检测到软错误以后,TCR可以进行动态重构,屏蔽被软错误破坏的内核.实验结果表明,与传统的软错误恢复执行模型CRTR相比,DCR和TCR对核间通信带宽的需求分别降低了57.5%和54.2%.在检测到软错误的情况下,DCR的恢复执行带来5.2%的性能开销,而TCR的重构带来的性能开销为1.3%.错误注入实验表明,DCR能够恢复99.69%的软错误,而TCR实现了对SEU(Single Event Upset)型故障的全面屏蔽.

基于片上多核的频繁项集并行挖掘算法

关联规则挖掘中最主要的工作是如何高效地挖掘频繁项集。目前在单机平台上,由于计算量大等原因,大数据集上的关联规则挖掘很难得到理想结果。在分析现有频繁项集挖掘算法的基础上,结合Eclat和dEclat挖掘算法优点,针对大数据集和片上多核共享内存计算环境,提出一种高效的并行频繁项集挖掘算法PEclat,算法实现了任务级并行挖掘频繁项集,并在大数据集上进行了多项测试。实验结果表明,无论数据稠密程度如何,该算法均能取得较好的性能。

片上多核处理器的结构级功耗建模与优化技术研究

功耗是导致片上多核处理器出现故障的重要诱因,也是片上多核处理器设计的重要制约因素。如何降低多核处理器的功耗并提高处理器能量效率,具有很大的研究意义与探索空间。文中主要从体系结构设计者的角度,并结合电路实现,研究并总结纳米级工艺下片上多核处理器的功耗建模与评估方法,及其不同构件的低功耗优化技术。通过提出创新高效的多核处理器结构级功耗评估方法及其模拟平台,提高多核结构功耗模拟的准确性与灵活性,并以此为依托,开展处理器核、片上网络、片上存储及其一致性协议的各方面优化,寻求提高多核处理器功耗有效性的微体系结构,为国产多核处理器的低功耗设计提供一定借鉴与参考。

片上多核中一种共享感知的数据主动推送Cache技术

针对片上多核处理器的二级Cache访问延时持续增加以及并行程序在运行时线程间执行速率差异大的问题,提出了一种基于共享感知的数据主动推送Cache技术(SAAPC).SAAPC技术充分考虑并行程序的系统性能由速度最慢的线程所决定这一重要特性,根据并行线程间读数据共享程度高以及共享读数据访问局部性好的特征,采用基于指令的方法来预测共享读数据流,在后行线程需要共享数据之前将其主动推送至该线程的一级Cache中去,从而减少较慢线程的数据访问延时,提高执行速率,降低较慢线程与先行线程间执行速率的差异.SAAPC技术避免了预取技术所带来的额外片外带宽增加的缺点.使用SESC模拟器对来自于SPLASH2测试程序集的5个存储敏感型并行程序进行了测试仿真,结果表明,与传统的共享Cache相比,使用SAAPC技术减少了并行线程间执行速率的差异,系统的每周期指令数平均提高了7%,最高达到13.1%.

片上多核处理器共享Cache划分的公平性研究

公平性是一个关键的优化问题,当系统缺乏公平时,会出现线程饿死和优先级反转等问题。以公平性优化作为研究目标,分析当前共享Cache划分公平性的评价标准,找出了其评价参数和划分策略的不足,提出了一种新的共享Cache划分方案。通过提出一个新的多线程公平性评价指标并改进了已有的公平划分策略,从而提高多线程运行的公平性。实验结果表明,该共享Cache划分方案显著提高了系统公平性,并且系统吞吐量也有提高。

同构与异构片上多核系统的演进过程

系统级芯片是高端电子系统的核心,而片上多核系统是近年来系统级芯片的主要实现形式。近十年来,片上多核系统一直是数字集成电路领域的热点,经过众多研究者的不断努力诞生了大量很有意义的研究成果。但由于片上多核系统的研究者背景和应用领域不同导致发展演进过程较为复杂而难以理解。为减少这一问题的影响,总结了片上多核系统的演进历史与现状,并对片上多核系统未来的发展提出了一些看法。

基于π网的片上多核系统任务调度算法研究

为提高片上多核系统在任务调度方面的效率,基于先进的π网来研究其任务调度算法。在简单介绍π网之后,利用π网对片上多核系统的任务调度进行建模,并对模型进行动态演化、复杂度和子网划分等分析,然后对模型进行实验和仿真。通过实验和仿真,得到的模型在调度成功率、平均调度时长和处理器核利用率等方面优于其他算法。

层次化片上多核处理器性能研究

层次化片上多核处理器紧耦合多个处理核构成"簇节点",对访存和片上通信的局部性有良好支撑,能有效地缓解片上多核间数据通信带来的通信开销。文章通过构建精细的层次化片上多核处理器仿真器,利用随机任务模型研究"簇节点"大小对系统性能的影响。仿真发现,一定系统规模下,要获得良好的系统性能,层次化片上多核处理器需要在"簇节点"数目与"簇节点"的大小(节点内处理核的数目)之间仔细权衡。

片上多核处理器Cache访问均衡性研究

随着片上多核处理器(CMP)规模的不断扩大和处理核数的增多,系统对于片上缓存(Cache)在容量和速度方面有了更高的需求.为了能够有效利用Cache资源,非一致Cache体系结构(NUCA)被提出用于支持高容量低延迟的Cache组织结构.另一方面,片上网络(NoC)由于具备良好的可扩展性,在片上多核处理器的互连方式上具有显著优势.因此,基于片上网络的非一致Cache体系结构逐渐成为未来组织大容量Cache的主流系统架构.在这样的系统架构中,最后一级缓存(LLC)通常在物理上分布于每个处理节点,这些Cache存储体(Bank)在逻辑上共同构成一个统一的共享Cache.当处理核发出Cache访问请求时,其访问时间与请求处理核节点与访问数据所在的Bank节点的距离有关.当距离较近时,访问时间较短;当访问距离较远的Bank时,访问时间较长.因此,当系统规模逐渐增大时,这种访问延迟与网络距离相关的特性会使得不同节点之间的通信距离和通信延迟的差异性逐渐增大.另外,片上网络规模的增大也会使得Cache访问延迟逐渐由网络延迟主导.这种延迟差异性会引起网络报文延迟不均衡问题,导致Cache访问延迟的非一致性进一步增大,因而出现更多的大延迟Cache访问并成为制约系统性能的瓶颈.因此,研究片上多核处理器的Cache访问均衡性对于提升网络性能和系统性能具有积极意义.该文分析了造成Cache访问延迟不均衡的原因,并针对延迟的两个来源:无冲突延迟和竞争延迟,分别提出了非一致存储映射和非一致链路分布的设计方法.通过非一致存储映射,我们根据Cache存储体在网络中的物理位置调节其相应的Cache块映射比例,从而均衡Cache请求平均访问距离;通过合理设计非一致的链路分布,我们依据各条链路上的流量负载为其分配合适的通道数量,从而缓解流量压力较大的链路上的报文竞争.全系统模拟器上的实验表明,采用面向Cache访问均衡性的片上多核处理器能够有效均衡Cache访问延迟,并减少大延迟Cache访问请求的数量.相比于传统的NUCA结构,我们的设计在最大的实验规模(64核)下在延迟均方差、最大延迟和平均延迟上分别平均降低了19.6%、12.8%和6.4%,最大降低了40.8%、29.9%和11.9%.同时在系统性能方面,通过PARSEC应用程序的模拟实验表明,单位周期执行指令数(IPC)平均提升了6.7%,最大提升了14.0%.

片上多核处理器共享末级缓存动静结合地址映射机制

片上多核处理器(CMP)通常采用私有或者共享的末级高速缓存(cache)结构,而共享末级cache一般使用静态地址映射机制。该机制将各处理器临时私有访问的数据映射于分布在其他处理器的末级cache中,使得各处理器对临时私有数据的访问延时增加。针对该问题,提出了一种动静结合的共享末级cache地址映射方法。该方法可将原来静态映射于其他处理器末级cache中的临时私有数据动态映射于访问者处理器的本地末级cache中,减少了大量静态映射所造成的长延时非本地末级cache访问,从而有效降低了整个共享末级cache的访问延时,在提高性能的同时降低了功耗和带宽使用。实验结果表明,动静结合的地址映射方式应用于采用环连接互连结构和侦听顺序环协议的CMP结构时,可获得的平均性能提升为9%,最大性能提升为38%。

基于FPGA模拟片上多核处理器的新方法

为了解决使用现场可编程门阵列(FPGA)进行大规模片上多核处理器模拟的容量限制难题,提出了一种新颖的FPGA模拟方法。该方法通过混合真实的处理器核与伪造的处理器核,使用1个或2个FPGA即可模拟整个片上多核处理器,而且可以有效克服FPGA的容量限制问题,同时又不过多损害对多核处理器行为特征的有效模拟。用此方法实现了周期精确的全芯片模拟,并使用流片后的片上多核处理器芯片对此模拟方法进行了有效性验证。实验很容易地实现了50MHz以上的模拟速度,比基于相同设计的软件仿真快10万倍以上。模拟速度的大幅度提升,使得可以启动未经修改的Linux操作系统和运行完整的多用户SPEC CPU2006 train测试集。这种混合真实处理器核与伪造处理器核的模拟方法为片上多核处理器的功能验证和性能评估提供了一种简单高效的途径。

基于片上多核的H.264编码的并行加速性研究

针对便携设备上不断增强的视频处理要求和H.264编解码算法相对较高的计算复杂度之间的矛盾,提出了基于片上多核结构的H.264并行化方案,以达到实时编码的效果。该方案以FPGA为验证平台,通过硬件结构与软件算法协同优化的方式,在单总线双核结构的MPSoC上实现了基于片的H.264并行编码。实验结果表明,在嵌入式环境下利用多核技术实现H.264并行编码可以取得良好的加速效果。

面向多线程应用的片上多核处理器私有LLC优化

片上多核处理器已逐渐取代传统超标量处理器成为集成电路设计的主流结构,但芯片的存储墙问题依旧是设计的一个难题。CMP通过大容量的末级高速缓存来缓解访存压力。在软件编程模式向多线程并行方式转变的背景下,针对多线程应用在多核处理器上的Cache访问特征,提出一种面向私有末级Cache的优化算法,通过硬件缓冲器记录处理器访存地址,从而实现共享数据在Cache间的传递机制,有效降低Cache失效开销。实验结果表明,在硬件开销不超过Cache部件0.1%的情况下,测试用例平均加速比为1.13。