多核结构

多核结构（共8篇）

多核结构 篇1

1 引言

互联网数据通道上大量的处理工作主要通过像路由器这样的分组处理系统来完成,如防火墙、NAT、Web交换机、IP追踪、用于高性能区域存储的TCP/IP卸载、媒体流化和加/解密等。这些功能在接入和边缘网络实现,随着互联网的不断发展,网络内部更加复杂的分组处理将会变得越来越必要。

多核分组处理不同于一般的多核应用系统(如多核OS)。首先,分组处理过程中,只有当分组属于同一条流时相互之间才有依赖关系而不同流的分组之间没有依赖关系其次多核处理单元之间的通信和同步开销,影响系统性能的一个重要因素。最后,分组的处理通常可以分为不同的阶段顺序进行,而这些阶段在各个处理单元上的分配(即,任务映射)将对系统的性能起着决定性的作用。

软件结构是构建高效系统的基础。传统软件结构的研究关注的重点在于系统功能的可扩展性和代码的重用等方面,如SOA。多核分组处理系统的软件结构不仅要关注功能的可扩展性,更关注性能的可扩展性,即如何保证分组处理系统的吞吐率随着处理单元的增加而线性或接近线性的增加。充分利用分组处理和多核处理器的特点设计高效的分组处理软件结构是开发多核分组处理系统所面临的主要挑战。

关于分组处理系统功能可扩展性方面的研究,已经有一些成熟的成果可以使用,Click[1]模块化路由器架构就是构建在通用处理器上的分组处理系统的典型结构。性能可扩展性方面的研究必须建立在恰当的系统结构上,不同的结构,决定了不同的解决思路和方法。本文将针对几种基本的分组处理系统结构,结合最新的多核网络处理器的特点进行详细的分析和讨论,并针对发现的问题提出了一些设计时需要注意的基本原则,以期对后续的相关研究提供一定参考。

本文接下来的安排如下:第2节介绍了多核网络处理器的模型;第3节对基本的多核分组处理系统结构进行了介绍和分析;第4节介绍了我们在Cavium CN 5860多核网络处理器上对第3节的分析的实验验证;第5节针对分析中发现的问题,介绍了一些相关的研究;第6节是对全文的总结和对未来工作的展望。

2 多核网络处理器模型

随着网络处理器技术的不断发展,目前的网络处理器大多采用共享内存对称多处理的多核架构,因此,指令存储空间不再受限制,如RMI的XLR系列处理器和Cavium的OCTEON系列处理器。这些网络处理器通常在一片芯片上集成多个处理核,所有的核共享内存和二级缓存,每个核有自己独立的一级缓存,包括指令缓存和数据缓存。此外,还有一些针对网络处理应用而优化的特殊指令集、协处理器和硬件加速单元。典型的多核网络处理器结构如图1所示。

尽管这些网络处理器不再有指令存储空间的限制,但是,其Cache的存储空间依然有限,一般为8K到将数据从内存加载到的时间开销对于高速分组处理而言依然不可忽略分组处理过程中,Cache丢失包括指令Cache的丢失和数据Cache的丢失。不防假定分组处理的指令存储空间连续,且大小为I字节,指令Cache的大小为LI字节。则对同一种应用的处理而言,在处理完第一个分组以后,因指令Cache丢失而导致的停顿周期χ仅与I有关。根据文献[2]的分析,在采用最优指令Cache替换策略的情况下:

式(1)中,η表示从内存加载一字节数据到Cache的平均周期开销。

由于对于分组处理而言,每一个分组都不相同,因此,分组数据Cache的丢失不可避免。但是对分组处理的各个阶段,所需要的配置数据相对固定,因此,配置数据存储空间的大小和范围会影响数据Cache的命中率,不妨假定分组处理过程中的配置数据储空空间为D,处理的分组长度为P字节,数据Cache的大小为LD,数据Cache丢失导致的停顿周期为

3 基本软件结构分析

一般而言,多核分组处理系统主要包括三种基本的结构:全并行结构、全串行结构和混合结构,如图2所示。由于处理阶段间没有核间通信和同步的开销,全并行结构比其他结构的系统吞吐率高,但是很少有相关文献在这方面给出完整的说明和详细的讨论,特别是结合多核处理器的特点进行分析。文献[4]对多核服务器内的分组处理结构进行了简单的分析和测试,测试的结果表明,系统采用全并行结构的吞吐率比采用混合结构高2倍以上。事实上,我们认为,造成性能差异大的根本原因,不是两种结构的差异,而是在混合结构下,没有做到阶段间负载的均衡。

图2中灰色圆圈代表分组处理的各个阶段,方框和圆圈分别代表网络处理器的处理单元、分组输入单元和分组输出单元。

由于全串行结构容易造成资源的浪费,实际的设计中很少使用,而且全串行结构也可以看做是混合结构的一种特例,因此本文仅讨论全并行结构和混合结构的相关问题。

3.1 全并行结构

全并行结构如图2(a)所示。设每条指令的平均执行周期数为-k。分组处理过程中,处理阶段i所需的指令数为φi,则每个分组的处理的周期开销为

进一步,假定系统中处理单元的数量为N,每个处理单元的处理能力为ΥHz,则系统的最大吞吐率为

从(4)式可以看出,当I LI,D LD,时,系统的吞吐率最大;反之,则I和D越大,系统的吞吐率随之下降。

3.2 混合结构

混合结构如图2(c)所示。混合结构下,各个阶段的处理开销与并行结构类似。同时考虑通信和同步的开销,设为τi,则阶段i的处理开销为

其中,Ii为阶段i的指令存储空间大小,Di为阶段i的配置数据存储空间大小,Pi为阶段i处理的分组长度,且通常满足以下关系:n i=∑1Pi P≈n i=∑1Di D≈n i=∑1Ii I≈Ni·Υ设Ni为分配给阶段i的处理单元的数量,则各个阶段的吞吐率为θi=,分组处理的总开销为φi nφs=∑φi。i=1串行系统下,系统的吞吐率取决于各个处理阶段中吞吐率最低的阶段,即:θs=min(θ1,θ2,…,θn)(6)N1·ΥN2·Υ,Nn·Υ,…,=min(N2·Υ)φ1=…=φ2Nn·Υφn N1·Υφ1不难证明,当且仅当时,θs取最大值:=φ2θs,max=φn N·ΥN1·Υφ1==n i=∑1φi(7)N·Υn ni=∑1φi·k+∑(χI(Ii)+χD(Di,Pi)+τi)i=1如果,i,1 i n,IiLI,DiLD,则,N·Υθs,max=(8)n n ni=∑1φi·k+∑τi+∑η·Pi i=1i=1根据公式(3)和(4),不难得到以下不等式:n n i=∑1χI(Ii)χI(i=∑1Ii),等式成立当且仅当I LI n n i=∑1χD(Di)χD(i=∑1Di),等式成立当且仅当D LD考察式和式我们可以得到不等式

式(9)说明,当分组处理应用比较复杂时,只要能够平衡各个阶段的资源分配,使用混合结构不但不会导致系统吞吐率急剧下降,反而有可能获得比并行结构更好的性能。因此,我们可以得出多核分组处理系统采用混合结构时的设计原则:

(1)各个阶段在处理单元上的分布应该考虑Cache命中率的影响。

(2)阶段分配到处理单元的过程中,应当遵循尽量减少核间通信开销的原则。即,只要相邻的多个处理阶段放到同一个处理单元上不比放到多个处理单元上的Cache命中率差,就应将其放到同一个处理单元上,以减少核间通信和同步的开销。

(3)用串行结构,各个分组处理阶段的资源的分配要尽量与其处理负载相当,避免出现瓶颈。

4 实验验证

4.1 实验设置

尽管在以上分析中,对Cache替换的机制进行了最优化的假定,但是这并不妨碍分析结果的普遍适用性。我们将在Cavium的CN 5860网络处理器上进行实验验证。CN 5860网络处理器拥有16个MIPS核,每个核的工作频率为750MHz,16个核共享2MB的二级缓存,每个核拥有32KB的指令缓存和16KB的数据缓存。CN 5860的Cache替换机制采用4路关联,LRU替换机制,因此,即便在指令空间小于32KB时,其指令Cache命中率也未必是100%。

实验中,我们对分组进行全加密处理,将整个处理操作分为:输入、处理和输出三个阶段。其中输入阶段主要完成加密配置数据查找操作,处理阶段完成分组头部替换和载荷加密操作,输出阶段完成IP头部校验和计算和输出。我们分别对以下四种情况的分组处理延迟和Cache丢失造成的停顿进行了测量:

(1)三个阶段处于一个核上,即,并行结构;

(2)输入阶段处于一个核上,后两个阶段处于另一个核上;

(3)前两个阶段处于一个核上,输出阶段处于另一个核上;

(4)三个阶段分别处于不同的核上。

在实验中测量Cache丢失导致的停顿的方法是:通过读取处理器寄存器记录的丢失次数,根据内存带宽换算成停顿周期。

4.2 实验结果

图3是测得的分组处理延迟情况,图4是测得的Cache丢失导致的处理停顿周期。

从实验结果我们可以看出,一方面串行结构的分组处理延迟并没有比并行结构的分组处理延迟增加很多;另一方面,由于并行结构的Cache命中率不稳定,导致分组处理延迟出现较大的波动;最后,我们发现,采用(b)方案,Cache命中率比较稳定且维持在较低水平,分组处理延迟也接近最低水平且比较稳定。总的看来采用方案比采用方案更优越这就证明了我们前面的分析是合符实际情况的

5 相关研究

不少研究人员对多核分组处理系统的任务映射机制进行了研究,采用的方法包括动态自适应的方法[5,6,8]和随机映射[7,10]的方法乃至遗传算法[11]。文献[5]针对IntelIXP系列网络处理器代码存储空间有限的特点,提出了基于分组到达、离开速率动态为各个处理阶段分配处理单元的算法。但是一方面该算法仅针对代码存储空间有限的问题另一方面该算法也没有充分考虑各个处理阶段负载的均衡性文献基于Click分组处理模型,针对任务受限的情况下,提出了基于贪婪分配策略的动态任务复制算法和UDFS任务映射算法。文献[8]通过对每个处理阶段的队列长度的测量,动态的为每个处理阶段分配或者回收处理资源,以达到在满足分组处理延迟边界的情况下,系统的功耗最低。总之,类似的针对多核分组处理系统的任务映射机制的研究很多。他们分别提出了不同的映射机制和算法来改善混合结构所面临的处理核负载不均衡的问题。尽管他们的研究主要针对指令存储空间有限的多核网络处理器,如IntelIXP系列网络处理器,但是他们的研究成果对于其他网络处理器上的任务映射也有一定的借鉴意义。

此外,有大量的研究文献[12,13]对多核处理器上的一般任务分配问题提出了不同的启发式算法,特别是遗传算法。这些问题同分组处理系统上的任务分配和调度问题有些相似,但是也不等同。主要的区别在于,分组处理系统上,需要考虑的任务的负载是时变的,并且还需要考虑Cache命中率,通信和同步开销,以及任务间负载的均衡问题。因此,这些方法可以借鉴,但是不能直接使用。

6 结论和展望

虽然并行结构具有简单和通信开销小的优点。一方面在一些指令存储空间有限的多核处理器上,如IntelIXP系列处理器,当代码空间超出限制时,必须将分组处理的任务分布到不同的核上。另一方面,为了对分组处理进行有效的QoS控制和调度,采用混合结构也是一种比较直观和简单的方法。而事实上,我们前面的分析和实验也证明了,采用混合结构未必就比并行结构性能差。因此,客观条件和实际需求决定了现实中的大多数分组处理系统都采用了混合结构。

混合结构必需要解决两个问题:一是在已经划分好分组处理阶段的前提下,如何给各个处理阶段分配合理的处理资源,以保证各个阶段的处理能力与处理负载的适配;二是如何将这些处理阶段分布到不同的处理单元上,即任务映射问题。当处理变得复杂,而流量又不断变化的时候,这些问题的解决将变得更加困难。结合分组处理和多核处理器的特点,包括核间通信和同步开销、Cache命中率等,借助合适的启发式算法设计出有效的任务映射算法能将是我们未来工作的主要方向

参考文献

[1]E.Kohler,R.Morris,B.Chen,J.Jannotti and M.F.Kaashoek.The Click modular router.ACM Transactions on Computer Sys-tems18,3(Aug.2000),263-297

[2]A.Raghunath,V.Balakrishnan,A.Kunze,and E.Johnson.Framework for Supporting Multi-Service Edge Packet Processing on Network Processors.In ANCS’05.

[3]Q.Wu,and T.Wolf.On runtime management in multi-core packet processing systems.In Proc.of ACM/IEEE Symposium on Ar-chitectures for Networking and Communication Systems(ANCS)(San Jose,CA,Nov.2008).

[4]T.Wolf,N.Weng,and C.-H.Tai.Run-time support for multi-core packet processing systems.IEEE Network,21.(4),July2007,29-37

[5]R.Kokku,U.Shevade,N.Shah,H.Vin,and M.Dahlin.Adaptive Processor Allocation in Packet Processing Systems.Technical report,University of Texas at Austin TR-04-04,2004.

[6]J.E.Smith,J.R.Goodman.Astudy of instruction cache organizations and replacement policies.Tenth Annual Symposium on Com-puter Architecture,June1983.

[7]N.Weng,T.Wolf.Analytic Modeling of Network Processors for Parallel Workload Mapping.ACM Trans.Embedded Comp.Sys.(TECS),418(3),Apr.2009,Vol Article18.

[8]L.Noonan,C.Flanagan.An effective network processor design framework:using multi-objective evolutionary algorithms and ob-ject oriented techniques to optimise the intel IXP1200network processor.In Proc.of the2006ACM/IEEE symposium on Architec-ture for networking and communications systems(ANCS),San Jose,California,USA,2006,P.103-112

[9]R.Hwang,M.Gen,H.Katayama.A comparison of multiprocessor task scheduling algorithms with communication costs.Comput.Oper.Res.35,976-993(2008).doi:10.1016/j.cor.2006.05.013

[10]M.R.Bonyadi,M.E.Moghaddam.A Bipartite Genetic Algorithm for Multi-processor Task Scheduling.International Journal of Parallel Programming,Oct.2009,37(5)462-487

多核结构 篇2

从应用需求上去看，越来越多的用户在使用过程中都会涉及到多任务应用环境，日常应用中用到的非常典型的有两种应用模式。

一种应用模式是一个程序采用了 线程级并行编程，那么这个程序在运行时可以把并行的线程同时交付给两个核心分别处理，因而程序运行速度得到极大提高。这类程序有的是为多路 工作站或服务器设计的专业程序，例如专业图像处理程序、非线视频编缉程序、动画制作程序或科学计算程序等。对于这类程序，两个物理核心和两颗处理器基本上是等价的，所以，这些程序往往可以不作任何改动就直接运行在 双核电脑上。

还有一些更常见的日常 应用程序，例如Office、IE等，同样也是采用线程级并行编程，可以在运行时同时调用多个线程 协同工作，所以在 双核处理器上的运行速度也会得到较大提升。例如，打开IE 浏览器上网。看似简单的一个操作，实际上浏览器进程会调用代码解析、Flash播放、多媒体播放、Java、脚本解析等一系列线程，这些线程可以并行地被双核处理器处理，因而运行速度大大加快（实际上IE浏览器的运行还涉及到许多进程级的交互通信，这里不再详述）。由此可见，对于已经采用并行编程的软件，不管是专业软件，还是日常 应用软件，在多核处理器上的运行速度都会大大提高。

日常应用中的另一种模式是同时运行多个程序。许多程序没有采用并行编程，例如一些 文件压缩软件、部分游戏软件等等。对于这些 单线程的程序，单独运行在多核处理器上与单独运行在同样参数的 单核处理器上没有明显的差别。但是，由于日常使用的最最基本的程序—— 操作系统——是支持 并行处理的，所以，当在多核处理器上同时运行多个单线程程序的时候，操作系统会把多个程序的指令分别发送给多个核心，从而使得同时完成多个程序的速度大大加快。

另外，虽然单一的单线程程序无法体现出多核处理器的优势，但是多核处理器依然为 程序设计者提供了一个很好的平台，使得他们可以通过对原有的单线程序进行并行设计优化，以实现更好的程序运行效果。

上面介绍了 多核心处理器在软件上面的应用，但游戏其实也是软件的一种，作为一种特殊的软件，对PC发展作出了较大的贡献。一些多线程游戏已经能够发挥出多核处理器的优势，对于单线程游戏，相信游戏厂商也将会改变 编程策略，例如，一些游戏厂商正在对原来的一些单线程游戏进行优化，采用并行编程使得游戏运行得更快。有的游戏可以使用一个线程实现人物动画，而使用另一个线程来载入地图信息。或者使用一个线程来实现图像渲染中的 矩阵运算，而使用另一个来实现更高的人工智能运算。如今，大量的支持多核心的游戏涌现出来，从而使得多核处理器的优势能得到进一步的发挥。但布赖恩特直言不讳地指出，要想让多核完全发挥效力，需要硬件业和软件业更多革命性的更新。其中，可编程性是多核处理器面临的最大问题。一旦核心多过八个，就需要执行程序能够 并行处理。尽管在 并行计算上，人类已经探索了超过40年，但编写、调试、优化并行处理程序的能力还非常弱。

易观国际分析师李也认为，“出于技术的挑战，双核甚至多核处理器被强加给了产业，而产业却并没有事先做好准备”。或许正是出于对这种失衡的担心，中国国家智能计算机中心主任孙凝辉告诉《财经》记者，“十年以后，多核这条道路可能就到头了”。在他看来，一味增加并行的处理单元是行不通的。并行计算机的发展历史表明，并行粒度超过100以后，程序就很难写，能做到128个以上的 应用程序很少。CPU到了100个核以上后，现在并行计算机系统遇到的问题，在CPU一样会存在。“如果解决不了主流应用并行化的问题，主流CPU发展到100个核就到头了。现在还不知道什么样的革命性的进展能解决这些问题。”孙补充说。

实际上，市场研究公司In-Stat分析师 吉姆克雷格(Jim McGregor)就承认，虽然英特尔已向外界展示了 80核处理器原型，但尴尬的是，目前还没有能够利用这一处理器的操作系统。中科院软件所并行计算实验室副主任 张云泉也持类似的观点。他对《财经》记者表示，这个问题实际一直就存在，但原来在 超级计算机上才会遇到，所以，讨论也多局限在学术界。而现在，所有用户都要面对这样的问题。

目前，多核心技术在应用上的优势有两个方面：为用户带来更强大的计算性能；更重要的，则是可满足用户同时进行 多任务处理和多任务计算环境的要求。两大巨头都给 消费者描绘出了使用多核处理器在执行多项任务时的美妙前景：同时可以检查邮件、刻录CD、修改照片、剪辑视频，并且同时可以运行 杀毒软件。或者利用同一台电脑，父亲在查看财务报表，女儿在打游戏，母亲在给远方的朋友打 网络电话。但并不是所有家庭只有一台电脑，也不是所有用户都要用电脑一下子做那么多事，更何况目前的大部分应用程序还并不能自动分割成多任务，分别交给多个核心去执行。所以，对于大多数用户来说，多核所带来的实际益处，很可能并不明显。而多核所带来的挑战，或者说麻烦，却是实实在在的。美国卡内基梅隆大学计算机系教授朗道布赖恩特(Randal E Bryant)在接受《财经》记者采访时就坦称，“这给软件业制造了巨大的问题”。

四、多核处理器的应用情况

并行计算技术是 云计算的核心技术，也是最具挑战性的技术之一。多核处理器的出现增加了并行的层次性能使得并行程序的开发比以往更难。而当前业内并无有效的并行计算解决方案，无论是编程模型、开发语言还是开发工具，距离开发者的期望都有很大的差距。自动的并行化解决方案在过去的30年间已经被证明基本是死胡同，但传统的手工式的并行程序开发方式又难以为普通的程序员所掌握。Intel、微软、SUN、Cray等业内巨头正投入大量人力物力进行相关的研究，但真正成熟的产品在短期内很难出现。可扩展性是云计算时代并行计算的主要考量点之一，应用性能必须能随着用户的请求、系统规模的增大有效的扩展。当前目前大部分并行应用在超过一千个的处理器(核)上都难以获得有效的加速性能，未来的许多并行应用必须能有效扩展到成千上万个处理器上。这对开发者是巨大的挑战。

从Power、UltraSPARC T1、安腾到 双核Opteron、至强Xeon，各个领域都显示出，多核 处理器计算平台势必成为 服务器的主流或者说是强势计算平台，但这只是上游硬件厂商的乐观预计。并不是所有的 操作系统和应用 软件都做好了迎接多核平台的准备，尤其是在数十年来均为单一 线程开发应用的x86服务器领域。微软 软件架构师HerbSutter曾指出:软件开发者对多核处理器时代的来临准备不足。他说，软件开发社区认识到处理器厂商被迫采用多核设计以应对处理器速度提升带来的发热问题，但却没有清楚地了解这样的设计为软件开发带来多少额外的工作。

在过去一段长时间里，x86系统上软件的性能随着来自Intel和 AMD处理器速度越来越快而不断提高，开发者只需对现有软件程序作轻微改动就能坐观其性能在随着硬件性能的上升而不断提升。不过，多核设计概念的出现迫使软件世界不得不直面 并行性(将单个任务拆分成多个小块以便分别处理之后再重新组合的能力)问题。当然，为服务器设计软件的开发者已经解决了一些此类难题，因为多核处理器和多路系统在服务器市场已经存在多年(在传统的Unix领域)，一些运行在RISC 架构多核多路系统上的 应用程序已经被设计成多线程以利用系统的 并行处理能力。但是，在x86领域，应用程序开发者多年来一直停留在 单线程世界，生产所谓的“顺序软件”。

现在的情况是软件开发者必须找出新的开发软件的方法，面向对象编程的兴起增加了汇编语言的复杂性，并行编程也需要新的抽象层次。另一方面，处理器设计厂商在设计产品时也应该将软件开发者考虑在内，“处理器的首要着眼点应该是可编程性，而不是速度。”Sutter说。多核处理器要想发挥出威力，关键在于并行化软件支持，多核设计带动并行化计算的推进，而给软件带来的影响更是革命性的。

Intel很早就通过 超线程技术实现了逻辑上的双处理器系统，可以 并行计算，但这不过是对处理器闲置资源的一种充分利用而已，并且这种充分利用只有在特定的条件下，尤其是针对流水线比较长且两种运算并不相互交叉的时候，才会有较高的效率，如编码解码、长期重复某种 矩阵运算以及一些没有经过仔细编写的软件等。

即使 IBM的Power5架构，也需要跟最新的操作系统进行融合，加上运行在其上的软件，才有可能利用并发多线程。虚拟化技术在一定程度上能够处理一些因为多核带来的问题，可以让 应用软件和操作系统在透明的环境下对处理器资源进行分配和管理。

目前在对称多处理器方面，操作系统对资源的分配和管理并没有本质的改变，多以对称的方式进行平均分配。也就是说，在操作系统层面，当一个任务到来时，剥离成为两个并行的线程，因为线程之间需要交流以及操作系统监管，它导致的效率损失要比硬件层面大得多。并且，多数软件并没有充分考虑到双核乃至多核的运行情况，导致线程的平均分配时间以及线程之间的沟通时间都会大大增加，尤其是当线程需要反复访问内存的时候。目前，多数操作系统还没有完全实现 自由的资源分配，如IBM是通过AIX 5.3L来支持Power5上的虚拟化功能，才实现了资源的动态调配和划分的。

从长远来看，需要使用虚拟化技术才可能实现操作系统对任务的具体划分，这很可能改变一些通用的编程模式。

五、多核处理器新近的发展

近年来计算机技术取得了巨大的进步。但是在未来的十年，主流计算机技术中新的工作量、使用模式的出现及变化对未来的计算机平台提出的要求与过去取得的进展也差不多，这些巨大的要求包括：更高的性能、更低的功率密度、更好的功能可扩展性。作为计算机技术门下的一员，多核处理器技术同样面临相同的挑战。未来的处理器将是的社会和技术发展趋势的响应和直接产物，这些趋势包括：渗透性连接和主动性计算、数据的增长和高性能计算、因特网作为计算机和管道、全球化。这些趋势对未来的处理器有几个清晰的指向，处理器的架构需要进化，才能在下一个十年支持性能的增长和市场的需求。至少要满足以下几个关键需求：通用性能、功耗管理、特殊性能和适应性、可靠性安全性及易管理性、生态系统支持和稳定性、大众市场经济。为了满足这些需求，Intel多核处理器将不仅仅靠他们的基本性能，而且靠其丰富多样的计算机通信能力，电源管理等其他要素，使得Intel的处理器架构发展计划包括下列的关键特性：芯片层次的处理器、特殊用途的硬件、大型存储器子系统、微核心、虚拟、硅及工艺技术、兼容性和生态系统授权。为了实现上述的预期目标，Intel面临这许多的挑战：电源和热量管理、平行度、复杂化管理、安全性与易管理性、可变性和可靠性计算、高速互连。

多核结构 篇3

作为保障 信息安全 的重要手 段之一 , 密码算法 在整个信 息系统中 占有非常 重要的地 位[1]。 随着用户 对信息安 全越来越 重视 , 加密模式 正朝着多 协议配合 完成的复 杂加密模 式发展 , 同时密码 算法也正 朝着大位 宽 、 可重构的 方向发展[2]。 传统的单 核密码处 理器已经 无法满足 新型加密 模式和复 杂密码算 法日益增 长的性能 需求 。

相对于单 核处理器 而言 , 多核处理 器可以提 供更强的 处理能力 。 采用多核 处理器是 解决当前 复杂密码 算法实现 高性能计 算的有效 方案[3]。 但是当前 面向密码 操作的专 用多核处 理器仍没 有相对成 熟的设计 技术 。 结合多核 处理器设 计技术和 密码算法 硬件实现 技术 , 设计一款 面向多任 务密码算 法的多核 密码处理 器 , 不仅能够 有效满足 信息安全 领域日益 增长的需 求 , 同时也有 一定的理 论研究价 值 。

本文基于 多任务密 码算法并 行处理特 点与多核 互连结构 设计技术 , 分析了密 码算法处 理特征 , 提出了密 码多核处 理器性能 模型 , 设计了符 合密码算 法的密码 多核处理 器互联结 构 , 并与通用 多核处理 器中广泛 使用的2D-Mesh互联结构 在密码算 法执行性 能方面进 行了对比 。

1密码算法并行化分析及Amdahl定律的扩展

密码算法 数据处理 结构与数 据处理过 程具有不 同于通用 计算任务 的特殊性 , 设计与密 码处理特 征相吻合 的多核处 理器互联 结构势必 能够提高 密码的处 理性能[4]。 本文研究 和分析了 密码多核 处理模型 , 为实现密 码多核处 理器互联 结构的优 化设计奠 定基础 。

1.1密码算法统计分析

本文针对 典型的对 称密码算 法的执行 过程进行 统计分析 , 分析结果 如表1所示 。

由分析结 果可得如 下结论 :

( 1 ) 无论是分 组算法 、 杂凑算法 还是序列 算法 , 其结构要素内 部均存在 大量的数 据并行性 可开发 , 其主要表 现为大操 作位宽下 的小位宽 操作并行 执行 。

(2 ) 对称密码算法的不 同结构要素间存在 一定的数 据并行性 。 例如分组 密码算法 中 , 结构要素 间的数据 并行性体 现为各子 块数据在 同一算法 执行阶段 可执行不 同类型的 基本操作 。 在序列密 码算法的 不同结构 要素中 , 反馈移位 寄存器的 更新函数 和密钥流 生成函数 表现为当 前时刻FSR状态序列 中部分状 态的不同 函数 , 可以同时 并行执行 。 钟控型和 结构可变 性的序列 密码算法 , 其钟控/结构控制 信号和密 钥流生成 函数 , 表现为某 时刻一个 或多个反 馈移位寄 存器状态 序列中相 关状态位 的不同函 数可以并 行计算 。 基于分组 原理设计 的序列算 法的FSR反馈函数 的计算过 程各操作 间可并行 计算 。

由分析可 知 , 密码算法 在数据处 理过程及 数据处理 特征上具 备并行处 理潜能 , 符合多核 处理器并 行处理特 征 。 因此 , 可以通过 设计密码 多核处理 器来提升 密码算法 的实现效 率 。

1.2Amdahl定律分析及推论

Amdahl定律是研 究如何提 升系统性 能的经典 定律[5]。 定律指出 加快某部 件执行速 度所获得 的系统性 能提升受 限于该部 件在系统 中被使用 的频率或 所占总执 行时间的 比例[6]。

由Amdahl定律可以 确定系统 中影响性 能最大的 部件 , 同时也可 以衡量由 于改进某 些部件而 获得的系 统性能的 提高[7]。 假设改进 系统某一 部件 , 那么系统 的性能提 升比就是 :

通过分析 系统性能 提升比的 公式可知 , 影响系统 性能提升 比的两个 主要因素 为 : (1) 系统完成 某任务的 总时间中 待改进部 分的执行 时间所占 总时间的 比重 , 记为f ; ( 2 ) 待改进部 分改进后 比改进前 性能提高 的倍数 , 记为n 。 基于上述 分析可以 得出如下 推论 :

推论1:设T0为系统改 进前完成 整个任务 的总时间 。 改进后完 成整个任 务的时间Tn为 :

推论2:系统改进 后整个系 统的性能 提升比Sp为 :

其中 , (1-f) 表示不可 改进部分 。 当f=0时 , Sp为1, 即没有可 改进部分 。 当n→∞ 时 , Sp=1/1 - f , 即可获得 的性能改善 的极限值 受到f的约束 。

推论3: 改进后被 改进部件 执行时间 占系统总 运行时间 比f′为 :

则有 :

当f′-f<0时 , 说明被改 进部件在 改进后的 执行时间 占系统运 行时间比 相较于改 进前要少 。

2密码多核处理器互联结构研究与设计

2.1密码多核处理器模型研究

密码算法 映射在多 核处理器 上时 , 在假设映 射的任务 量是固定 的情况下 , 处理器完 成该固定 任务量所 需的时间 越少则系 统性能越 高[8]。 设任务工 作量为W, W由W1, W2, W3… WM组成 , 其中Wi表示并行 度为i的任务工 作量, M表示任务工作量中最 大的并行度 , 则任务工作量W可表示为当系统有无限多个运算核心, 且核心间无 通信延迟 时 , 完成Wi所需时间 为ti= Wi/ ( △·i ) , 其中 △ 为单个运 算核心的 运算能力 。 由Amdahl定律扩展 推论1可知 , 完成W的时间为 :

事实上 , 密码多核 处理器系 统不可能 集成无限 多个密码运算核心。 当密码运算核心数目为N、任务工作量并行度为i, 单个密码 运算核心 的运算能 力为 △ 时 , 且N>i时 , 多核系统 完成Wi工作量的 时间ti= Wi/ ( △·i ) ; 当N < i时, 多核系统完成Wi工作量的时间ti= ( Wi/ ( △·i ) ) ·「 i / N骎 。

并行计算 中运算核 心间存在 通信延迟 , 设完成Wi工作量的 通信延迟 为tdi, 此时多核 系统完成W工作量所 需时间为 :

通信时间 消耗与通 信任务量 及通信网 络结构有 关 , 而通信任 务量是与 任务并行 度i及计算任 务Wi的函数[9]。 设密码处 理任务为Wi, 任务并行 度为i , N个密码运 算核心的 多核系统 内单位时 间可传输 的数据量 为Pd= Ψ (N) , 并行度为i时通信 / 计算比为 σ (i) , 则通信任 务总量Wdi= σ ( i ) Wi, 且 :

同样 , 考虑密码 多核系统 集成的计 算核心数N可能小于 密码算法 中的任务 并行度i, 式 (3) 修订为 :

将式 (3) 、式 (4) 代入式 (2) , 可以推得 :

式 (5) 给出了适 用于密码 多核处理 器的结构 模型 。 式 ( 5 ) 中 , 参数 △ 为常数 ; 当密码应 用确定时 , 参数Wi为固定值 ; 多核密码 处理器结 构确定时 Ψ (N) 为固定值 ;σ (i) 与处理器 结构及密 码应用有 关[10]。

2.2模型参数分析

由2.1节推导模 型可知 , 密码任务 并行度及 并行部分 所占比例 决定了密 码处理器 可达到的 最高性能 , 通信延迟 是影响密 码多核处 理器实现 性能的主 要因素之 一 。 在设计面 向该模型 的密码多 核处理器 时 , 应该首先 分析密码 应用的可 开发并行 度 , 初步确定 系统运算 核心数目 , 然后设计 互联结构 等 。 设计互联 结构时注 意使 Ψ (N) 及 σ (i) 尽量小 , 最后根据 设计对N值微调直 至最优 。

表2给出了常 见密码算 法并行度 的统计结 果 。 由表2的统计结 果分析可 知 : 密码应用 的特点是 数据运算 比较整齐 , 并行度变 化较少 。 密码算法 内并行度 一般为i= 1 、 2 、 4 、 8 、 16 , 例如AES轮运算并 行度i取值为1或4 ( S盒可开发i =16并行度 ) , DES轮运算并 行度i取值为1或8, IDEA轮运算并 行度i取值为1或4, MD5轮运算并 行度i取值为1或4。 对于密码 协议等应 用 , 通过对数 据包的拆 分 , 并行度理 论上可以 达到无限 大 , 考虑此类 问题 , 设大整数X作为可实 现的最大 并行度 。

为方便研 究 , 引入简化 条件对多 核密码处 理器模型 做定性分 析 。 假设当i≠1, i≠2, i≠4, i≠8, i≠16, i≠X时Wi= 0 。 式 ( 5 ) 可化简为 :

由公式分 析可知 , 影响密码 多核处理 器运算效 率的主要 因素为密 码算法并 行度i、 通信/计算比 σ (i) 、 系统单位 时间内可 传输数据 量 Ψ (N) 。 其中密码 算法并行 度由算法 本身决定 , 通信/计算比 σ (i) 由密码算 法及算法 任务映射 共同决定 。 本文仅讨 论多核处 理器中互 联方式对 多核系统 通信性能 的影响 , 即对系统 单位时间 内可传输 数据量 Ψ (N) 的影响 。

2.3簇状层次化多核互联结构设计

假设密码 算法中并 行度i与通信/计算比 σ (i) 为固定参 数 。 此时 , 通信性能 主要由传 递延迟决 定 , 设系统互 连结构里 消息传递 过程中跳 步数为H (N) , 消息经过 每个互联 节点的延 迟为tdc, 则一次通 信所需时 间tdi= H ( N ) · tdc。 一次通信 所完成的 工作量Wdc与通信位 宽为m bit、 一次可传 输n个数据有 关 , 即一次通 信完成的 工作量Wdc ( N ) = mn 。 推导可得 :

m与n的设计既 要考虑硬 件实现过 程布局布 线工艺又 要考虑密 码算法任 务间通信 量 。 据统计密 码算法中 任务间通 信一般为32 bit的整数倍 。 同时考虑 工艺技术 , 核间通信 一般采用32位宽进行 通信 。 因此系统 单位时间 内可传输 数据量 Ψ (N) 的大小主 要受通信 延迟tdi影响, tdi又主要由 核心间跳 数H (N) 与互联节 点中转延 迟tdc决定 。

本文结合 现有多核 互联结构 设计技术 , 通过减少 多核系统 内运算核 心间跳步 数的方法 , 优化设计2D-Mesh结构 。

对于传统2D-Mesh结构而言 , 因为运算 核心平铺 在一个平 面 , 随着多核 系统的不 断扩展 , 运算核心 间数据交 互跳数逐 渐增多 。 由文献 [11] 可知 , 传统2D-Mesh结构中消息 的平均跳 步数因此本文在保 留相同数 目密码运 算核心前 提下 , 针对如何 降低运算 核心间跳 数的问题 进行优化 设计 。

本文采用 如图1所示的簇 状层次化 多核结构 设计密码 多核处理 器 。 在整个多 核系统内 部建立了 三层结构 的立体多 核系统 。 最底层分 布着密码 运算核心 (标记为PCore的一层 ) , 负责基本 的密码运 算操作 。 中间层分 布着路由 节点 ( 标记为R的一层 ) , 负责将最 底层运算 核间所交 付的通信 数据进行 整个多核 结构的传 输 。 最高层为 多核系统 对外接口 层 ( 标记为输 入 / 输出控制 器的一层) , 负责将路 由节点层 与外界的 数据交互 。

在该多核系统中, 路由节点层的路由节点在连接过程中不再采用路由节点与运算核心一一对应的链接关系, 而是采用一个路由节点挂接四个运算处理核心的方式, 以此减少运算核心在整 个多核系统内部 数据交互 的跳数 。 同时, 输入/输出控制器也采用同样的方式链接路由节点, 以改善多核系统外部与多核系统内部数据交互的跳数。

本文设计 的层次化2D-Mesh结构保留 了簇状2D mesh结构的优 点 , 同时利用 输入 / 输出控制 器增强了 簇单元与 高层网络 通信的灵 活性 。 实现了处 理核单元 内部通信 与外部通 信的分离 , 为有序 、 高效的通 信提供了 结构上的 支持 。

3性能评估

根据1.2节中Amdahl定律分析 结论 , 对比改进 后与改进 前系统执 行效率即 可衡量系 统性能的 提升 。 基于此 , 本文将并 行部分所 占比重不 同的并行 度为4、8、16的密码算 法分别映 射在本文 设计的簇 状层次化 密码多核 结构与2D-Mesh多核密码 处理结构 上 , 对其执行 时间进行 对比 。 对比结果 如图2~图4所示 。

由图2可知 , 在多核系 统中运算 核心数目 (横轴 ) 确定的情 况下 , 改进后的 密码多核 系统相比 于改进前 在执行相 同任务映 射的密码 算法时所 需时间 (纵轴 ) 较少 , 即运算效 率越高 。 在图3、图4中 , 映射不同 串并比的 密码算法 也可得到 相同结论 。

通过上述 对比可知 , 随着运算 核心数目 的不断扩 展 , 本文提出 的簇状层 次化多核 互联结构 能够有效 提升多核 系统运算 效率 , 明显减少 了系统内 部运算核 心间通信 过程中传 递延迟 , 达到了预 期设计目 标 。

4结束语

针对密码 多核处理 器设计 , 本文深入 研究了对 称密码算 法的并行 实现特征 , 利用Amdahl定律推导 建立符合 密码并行 运算特征 的多核处 理器模型 。 通过参数 分析 , 仿真得到 硬件实现 的理论依 据 。 最后依据 理论结合 设计实际 , 本文提出 了基于2D-Mesh扩展结构 的簇状层 次化多核 处理器互 联结构 。

通过与其 他同类设 计相比 , 本文设计 的密码多 核处理器 互联结构 具有较高 的密码算 法适应性 和较高的 密码处理 性能 。 在统一的 可重构密 码多核处 理器下不 仅实现了 对公开对 称密码算 法密码处 理性能的 有效加速 , 而且还可 以支持几 乎所有其 他同类密 码算法 。

摘要：为了提高多任务密码算法硬件实现的高效性, 对密码算法的多核处理特征及多核互连结构设计基本定律——Amdahl定律进行了研究, 提出了密码多核处理器的结构模型, 并针对影响多核系统处理性能的参数进行了模拟及分析。基于分析结果, 对通用多核处理器中常用的2D-Mesh互联结构进行了优化设计, 并给出了优化方案的硬件实现。最后基于VCS仿真平台对设计方案进行了仿真验证。验证结果表明, 相比于传统2D-Mesh结构, 本方案具有较低的核间信息传递延迟, 证明了改进方案的合理性。

关键词：多核处理器,密码处理器,结构模型,互联结构

参考文献

[1]张晓丰, 樊启华, 程红斌.密码算法研究[J].计算机技术与发展, 2006, 16 (2) :179-180.

[2]HENNESSY J L, PATTERSON D A.Computer architecture:a quantitative approach[M].Elsevier, 2012.

[3]YU Z, YOU K, XIAO R, et al.An 800 MHz 320 m W 16-core processor with message-passing and shared-memory inter-core communication mechanisms[C].Solid-State Circuits Conference Digest of Technical Papers (ISSCC) , 2012IEEE International, 2012:64-66.

[4]KHANYILE N P, TAPAMO J R, DUBE E.An analytic model for predicting the performance of distributed applications on multicore clusters[J].IAENG International Journal of Computer Science, 2012.

[5]AMDAHL G M.Validity of the single processor approach to achieving large scale computing capabilities[C].Proceedings of spring joint computer conference.ACM, 1967:483-485.

[6]陈书明, 陈胜刚, 尹亚明.Amdahl定律在层次化片上多核处理器中的扩展[J].计算机研究与发展, 2012, 49 (1) :83-92.

[7]HILL M D, MARTY M R.Amdahl&apos;s law in the multicore era[J].Computer, 2008 (7) :33-38.

[8]BOSSUET L, GRAND M, GASPAR L, et al.Architectures of flexible symmetric key crypto engines—a survey:From hardware coprocessor to multi-crypto-processor system on chip[J].ACM Computing Surveys (CSUR) , 2013, 45 (4) :41.

[9]BLAKE G, DRESLINSKI R G, MUDGE T.A survey of multicore processors[J].Signal Processing Magazine, IEEE, 2009, 26 (6) :26-37.

[10]李文石, 姚宗宝.基于阿姆达尔定律和兰特法则计算多核架构的加速比[J].电子学报, 2012, 40 (2) :230-234.

多核操作系统发展综述 篇4

多核处理器的出现大大提升了系统并行处理能力,使越来越多不同类型的应用可以同时在多核平台上进行高效的并行计算。现有成熟的操作系统经过长期的发展,对目前普通多核处理器大多能够提供较好的支持。但同时,多核处理器的核数迅速增长、结构日益复杂,也为未来多核操作系统的设计与优化带来了巨大的挑战。如何适应未来多核处理器的迅速发展,设计高可用、高并行、高可扩展的多核操作系统,是目前业界共同的奋斗目标。

2 现状与挑战

传统多核操作系统采用宏内核[(Macro Kernel,或称为大内核(Monolithic Kernel)]架构,其中以Linux与Windows操作系统为主要代表。宏内核相当于一个巨大的并发协同的进程组,主要使用单一数据结构,内核本身提供大多数系统服务。在多核处理器核数有限、结构并不复杂的情况下,传统宏内核操作系统基本能够充分利用多核处理器的并行处理能力,对外体现为一个紧耦合、高效的单一操作系统。

随着技术的进步,多核处理器在硬件性能和结构上达到了长足的发展。多核处理器的核心数持续增加,目前已有集成超过100个核心的芯片。同时,多核处理器的结构也越来越多样化,出现了异构多核与类NUMA多核。

多核处理器的核心迅速增长、结构日益多样化,为传统多核操作系统的设计带来了巨大的挑战。尽管操作系统已经针对类SMP、类NUMA处理器结构对部分内核数据结构进行分布化,但它们本身与特定的同步模式以及数据布局紧密相关,其可扩展性受限于锁竞争、数据局部性以及对共享内存的依赖等。传统多核操作系统难以适应多核处理器的发展趋势,具体表现在两个方面。

首先,传统多核操作系统难以适应多核处理器核数的飞速增长。传统操作系统往往通过锁来保护共享数据,随着CPU核数的增加,进入内核的线程也会随之增加,对锁的竞争将更为激烈,影响系统的整体性能。

另外,核数增加时,传统多核操作系统一般通过创建更细粒度的锁来增加内核的并发性,而调整锁粒度是一项异常复杂的工作。未来处理器核心数量指数增长的情况下,重新设计子操作系统的速度难以与之同步。

其次,类NUMA多核处理器以及异构多核处理器的出现给传统多核操作系统设计带来了新的困难。类NUMA微结构多核处理器的特点是,多个核在访问片上数据比如L2Cache的时延是不同的,各个核部分共享L2Cache或者私有L2Cache。访问时延的不一致性使操作系统的设计更复杂,而且,当核数扩展时,为保证数据一致性所占用的操作系统开销将大大增加。异构多核处理器由一个或者多个主核以及其它从核组成,不同类型的核心给操作系统设计以及系统编程开发带来了很大的困难,其可扩展性也难以实现。

3 技术路线

为适应多核处理器的发展,可以利用分布式设计思想,从结构和功能上对传统多核操作系统进行分布式处理优化,将多核硬件划分为不同的子系统,尽可能降低各子系统之间的耦合度,从而提高多核操作系统的可扩展性。

目前,面向可扩展多核操作系统的研究主要可分为三种技术路线:1)改进传统宏内核架构,以适应多核体系结构,这是目前最广泛的研究方法;2)基于功能分布思想,将不同的核(或者核组)划分为不同的功能,不同功能之间通过共享内存或消息传递通信,开发功能分布式多核操作系统;3)借鉴分布式系统的数据分布思想以及消息通信机制,创新设计数据分布式多核操作系统。

3.1 改进传统宏内核架构

目前商业上应用最广泛的多核操作系统仍然是Linux、Windows等老牌操作系统。为改善系统的可扩展性,linux等传统操作系统一直没有停止过对多核处理器的优化支持。Linux针对NUMA结构处理器修改了内存分配策略,CPU会优先选择当前节点的物理内存,不够时才寻找附近节点请求物理内存分配。微软的Windows7移除了dispatcher锁,改动涉及50多个文件、6000多行代码。但限制可扩展性的根本因素———锁与共享内存等,依然是传统操作系统的主要运作元素,因此,对于多核的优化,他们还有较大的改进提升空间。

Corey操作系统是MIT等组织在Linux基础上修改操作系统接口实现的,其设计目标是针对当前主流的Cache一致性SMP多核处理器。其设计思想是“应用程序控制数据的共享”,即通过应用程序对内核间共享资源的控制,减少多核之间不必要的资源传递与更新,以达到更高效利用多内核的目的。

Corey在Linux中增加了三个新接口:1)地址范围,允许应用程序编程时决定私有地址与共享地址的范围;2)核心,允许应用程序制定特定的核心执行;3)共享对象,允许应用程序决定哪个对象对其它核心可见。Corey系统相对Linux系统性能提升明显,基于某AMD16核处理器的实验表明,Corey的Map Reduce性能较Linux提高了25%。但是,Corey改变了操作系统接口,普通应用程序需要经过修改才能在其上运行,其兼容性存在一定问题

3.2 功能分布式多核操作系统

传统多核操作系统的不同核心使用相同的宏内核,主要基于数据并行扩展多核性能,锁机制成为限制系统可扩展性的主要因素。功能分布式多核操作系统是一类将多核按照功能划分的操作系统,不同核心(Core)所使用的内核(Kernel)可以是宏内核或微内核。该类操作系统开辟了新的多核性能扩展路线,从原有的数据并行到新的功能分布,由于功能分布对数据的耦合度大大低于数据并行,因此可扩展性显著高于传统多核操作系统。

FOS是MIT开发的一种面向多核与云计算的操作系统,其设计宗旨是可扩展性以及自适应性。FOS的设计原则主要是:1)空间复用取代时间复用,FOS是在命名空间中进行调度,调度的资源是分布的多个核;2)操作系统分解成特定的服务,各操作系统服务分布在各服务器中,各服务器互相协作,彼此通过消息传递进行通信;3)错误自动检测与处理等。图1为FOS的微内核架构,其中每个处理器核运行一个不同的微内核,分别提供不同的操作系统服务或者运行应用程序。应用程序进程通过高效的消息传递获得操作系统服务,不同的服务或进程间的通信也通过消息机制进行。FOS对外提供单一系统映像(SSI,Single System Image),适用于传统操作系统的应用程序无需经过特定修改即可直接在FOS上运行。FOS系统具有良好的兼容性以及可扩展性。

3.3 数据分布式多核操作系统

异构以及类NUMA多核处理器的与传统多核处理器有明显的区别,即核间耦合度大大降低,主要表现在核间共享内存与cache的开销增加以及效率下降。传统紧耦合操作系统抑或Linux类NUMA操作系统,难以很好的发挥新型处理器的特点。考虑到新型处理器的硬件分布式特点,借鉴分布式系统的数据分布思想,创新设计松散耦合的类分布式多宏内核操作系统,对于提高多核操作系统的可扩展性,无疑是另辟蹊径。

Barrelfish系统基于Multikernel体系结构,是由剑桥微软研究院与瑞士苏黎世联邦理工学院联合开发的新型操作系统,其设计目标是高效管理使用异构的硬件资源,适应多核处理器的发展,如图2所示。该系统中每个内核都运行自己的操作系统,很好的支持了内核的异构性。同时它继承了分布式系统的思想,将各内核作为独立的单元,单元通过总线上的消息传递进行通信。这种模型可以带来更好的模块化性能,并使得分布式算法可以直接应用于多内核系统中。

4 结束语

多核处理器的核心迅速增长以及结构日益复杂,给未来操作系统的设计带来了很大的挑战。传统多核操作系统的可扩展性受限于锁竞争与Cache缺失,因而难以适应多核处理器的发展趋势。

目前,面向可扩展多核操作系统的研究主要可分为三种技术路线,分别是改进传统宏内核架构、开发功能分布式多核操作系统以及开发数据分布式多核操作系统。后两者通过利用分布式设计思想,从结构和功能上对传统多核操作系统进行分布式处理优化,将多核硬件划分为不同的子系统,尽可能降低各子系统之间的耦合度,从而提高多核操作系统的可扩展性。因此,功能分布和数据分布是未来多核操作系统的发展趋势。

参考文献

[1]D.Wentzlaff and A.Agarwal.Factored operating systems(fos):the case for a scalable operating system for multicores.SIGOPS Oper.Syst.Rev.,43(2):76-85,2009.

[2]T.C.Rajkumar Buyya,“Single system image(ssi),”the International Journal of High Performance Computing Applications,vol.15,pp.124-135,2001.

博通推出多核通信处理器 篇5

博通 (Broadcom) 公司宣布, 推出2 8 nm多核通信处理器。新型XLP 900 Series通过优化用于网络功能的部署, 例如硬件加速、虚拟化与深度包检测。XLP900 Series处理器得到了高度优化, 非常适合满足运营商、数据中心与企业网络对于性能、安全、效率和扩展能力的严格要求。通过多芯片一致性实现四指令执行 (quad-issue) 、四线程 (quad threading) 与高级乱序 (out-of order) 执行架构, X LP90 0 Series运算性能超过每秒1万亿次。这款旗舰处理器拥有端到端虚拟化功能、诸如深度包检测 (DPI) 等功能的高级安全性、以及线速网络和多层Qo S功能的创新网络及应用智能技术。

多核创造下的新IT时代 篇6

如果历史可以借鉴, 我想说将要发生的事情会是新软件的井喷, 其中的大部分创造性和有用的代码会利用到硬件性能提升带来的优势。

例如Intel新推出的芯片能将一个851 M B文件的加密速度从13.5秒减少到3秒, 这是个巨大的成就, 意味着加密交换将会变得非常普遍, 处理大容量和高安全性的数字交易将不再需要专用的加密卸载或CPU时间容载量, 这可能就是我们一直在寻找的帮助我们锁上大门的那把钥匙。另一方面, 现代的CPU中不断增加的内核数量让从前那些感觉有些困难的软件解决方案重新变得具有吸引力。

于是很自然的, 这一切都会进一步推动我们进入虚拟化, 这将不仅成为主流, 而且会成为唯一的流向。首先, 虚拟化是那些非线程应用可以继续存在于越来越多的线程世界中的唯一途径, 几乎没有例外。非虚拟的服务器成为珍稀品种只是时间问题, 嵌入式的hypervisor的统治即将到来。想象一下这样的世界吧, 这里绝大多数服务器都是专门为运行数十台虚拟服务器而设计的, 拥有几十个内核, 几百G B的内存, 而且几乎没有内部存储。这个现实正在敲我们的大门, 虽然现在还不是主流, 但我相信他们很快就会成为主流了。

OpenMP的多核并行程序设计 篇7

关键词：OpenMP,多核,并行编程

1 引言

目前, 主流CPU厂商都在致力于多核处理器的发展, 大幅增加了芯片支持的并行能力, 双核、四核处理器已十分普及, 迟早有一天还会用上8核, 甚至16核的CPU, 随着多核CPU的不断普及以及软件复杂度的继续提高, 如何有效地利用多核技术, 对于多核平台上的应用程序员来说是个首要问题。客户端应用程序开发人员多年来一直停留在单线程世界, 生产所谓的“顺序软件”, 但在多核计算机系统中, 多个进程和线程可以真正地并行运行, 而不是像在单处理器系统中那样轮流地在CPU上运行, 这样导致原有的单个程序运行速度并不能得到提高, 要提高单个程序的运行性能, 需要重新设计原有程序, 将单个计算任务分解成多个并行的子任务, 让这些子任务分别在不同的处理器核上运行。这样, 需要采用不同的程序设计手段。随着多核时代的到来, 并行程序设计将成为软件行业的必备知识和技能。

2 OpenMP

OpenMP是一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言, OpenMP标准形成于1997年, 它是一种API, 用于编写可移植的多线程应用程序。OpenMP程序设计模型提供了一组与平台无关的编译指令、指导命令、函数调用和环境变量, 可以显式地指导编译器如何以及何时利用应用程序中的并行性。对于很多循环来说, 都可以在其开始之前插入一条编译指导, 使其以多线程执行, 开发人员不需要关心实现细节, 这是编译器和OpenMP线程库的工作, 开发人员只需要认真考虑哪些循环应该以多线程方式执行, 以及如何重构算法以便在多核处理器上获得更好的性能等问题。

OpenMP执行模型采用分叉-合并的方式。程序开始是以一个单进程运行, 称为执行的主线程。主线程顺序运行到第一个并行块结构时就生成一个线程组, 原来的主线程成为线程组的主线程。程序中被并行块包围起来的所有语句在线程组中并行执行, 一直到并行块执行完后, 线程组中的线程中止, 而主线程继续执行。一个程序中可以定义任意数目的并行块, 因此, 在一个程序的执行中可以分叉、合并若干次。

3 OpenMP指令和语法

OpenMP通过编译指导语句来显式的指导并行化, 编译指导语句的含义是在编译器编译程序时, 会识别特定的注释, 而这些特定的注释就包含着OpenMP程序的一些语义, 在一个无法识别OpenMP语义的普通编译器中, 会将这些特定的注释当作是普通的注释而被忽略, 这种性质带来的好处是程序员可以用同一份代码来编写串行或者并行程序, 或在把串行程序改编成并行程序的时候, 保持串行源代码部分不变, 从而极大地方便程序编写人员。

3.1 OpenMP指令格式

OpenMP的指令格式为:

#pragma omp directive-name[clause[[, ]clause]...]

OpenMP的所有编译指导语句以#pragma omp开始, 后面跟着具体的功能指令, 其中directive部分就包含了具体的编译指导语句, 包括parallel、for、parallel for、section、sections、single、master、critical、flush、ordered和atomic。这些编译指导语句或者用来分配任务, 或者用来同步。后面的可选字句clause给出了相应的编译指导语句的参数, 字句可以影响到编译指导语句的具体行为, 每一个编译指导语句都有一系列适合它的子句, 其中有5个编译指导语句 (master, critical, flush, ordered、atomic) 不能跟相应的子句。

3.2 循环并行化

对于大量的科学计算程序来说, 循环计算通常占有很大的比例, 对循环进行并行化处理可以大大提高应用程序的运行效率, 因此循环并行化在OpenMP应用程序中是一个相对独立且非常重要的组成部分。循环并行化语句的编译指导语句格式如下:

使用这个编译指导语句能将for循环中的工作分配到一个线程组中, 而线程组中的每一个线程将完成循环中的一部分内容。编译指导语句的功能区域一直延伸到for循环语句的结束部分。编译指导语句后面的子句 (clause) 用来控制编译指导语句的具体行为。例如:

在上面的代码中, 编译指导语句会将for循环中的工作分配到一个线程组中, 编译指导语句的作用范围直到for循环结束部分。

并不是所有的循环都可以并行化, 使用OpenMP对循环并行化有一定的限制:

(1) for循环语句必须明确循环次数, 循环变量必须为整数, 循环操作符必须是>, <, >=, <=。

(2) 循环语句块必须是单出口与单入口, 循环过程中不能使用break、goto、return语句, 但可以使用continue, exit。

3.3 迭代相关

为了保证对一个循环进行正确的并行化操作, 必须要保证数据两次循环之间不存在数据相关性, 数据相关性又称为“数据竞争”, 当两个线程对同一个变量进行操作, 并且一个操作为写操作时, 就说明这两个线程存在数据竞争。此时, 读出的数据不一定就是前一次写操作的数据, 而写入的数据也可能不是程序所需要的, 为了将一个循环并行化, 且不影响程序的正确性, 需要仔细检查程序, 使程序在并行化后, 两个线程之间不能够出现数据竞争。

上面的代码中, 循环k中S1对存储单元x[k]进行写操作, 而k+1中S2读取该单元, 这样就产生了数据相关, 多线程代码将不能得到正确结果, 要解决此问题可以将循环重写:

上面代码段使用循环分块技术创建了无循环迭代相关的循环m, 并且预先计算出x[49]和y[49]的初值, 这样就可以正确地将循环并行化了。因此, 在并行化的过程中, 必须仔细分析循环之间的数据相关性, 通过改写程序来消除数据相关。

3.4 数据共享

在多线程程序中, 确定哪些数据需要被共享, 哪些数据为私有数据是非常重要的, 这对程序的正确性有很大的影响。在使用OpenMP时, 开发人员应该告诉编译器哪一片存储区域应当在多个线程间共享, 哪一片区域应该保持私有。当某存储单元被标识为共享, 那么所有线程都能够访问该单元。但是, 如果某存储单元被标识为私有, 那么每个线程都拥有该变量的一个副本, 可以私有地访问。当循环退出执行后, 这些私有副本将变成未定义状态。

OpenMP使用数据作用域子句来指定变量的共享属性, 分别是shared、private、firstprivate和lastprivate。

(1) shared子句, 显式地定义一个变量的作用域是共享的。

(2) private子句, 显式地定义一个变量的作用域是私有的。

(3) firstprivate和lastprivate子句, 分别对私有变量进行初始化操作和终结操作, firstprivate将串行的变量值复制到同名的私有变量中, 且在每一个线程开始执行的时候初始化一次。而lastprivate则将并行执行中的最后一次循环的私有变量值复制到同名的串行变量中。

3.5 使用规约

规约操作是应用程序中经常出现的, 即将一个二元运算符应用在一个变量和另外一个值上, 并把结果保存在原变量中, OpenMP提供了reduction子句, 可以有效地合并循环中关于一个或多个变量的规约操作, 下面代码给出了对“+”的规约操作:

使用了reduction子句后, 编译器会为每个线程创建变量sum的私有副本。当循环完成后, 它将这些值加在一起并把结果放到原始变量sum中。并不是所有操作都能使用规约操作, 详细内容可以参考OpenMP规范。

4 编程实例

下面使用一个简单的计算程序来说明使用OpenMP并行化的效果, 编译环境使用VC2005, 新建一个控制台应用程序, 选择支持MFC, 为了使项目支持OpenMP程序的编译和链接, 需要通过配置项目属性打开OpenMP的支持, 如图1所示。

程序代码如下:

执行结果见图2。

将Sum函数中的#pragma omp parallel for reduction (+:result) 注释掉, 再次执行, 结果见图3。

可以看到, 使用OpenMP编译指导的执行时间比不使用的要提高了一倍, 图4显示了两种执行过程CPU的利用率, 使用了OpenMP编译指导后, CPU的利用率达到了100%, CPU的两个核都被使用, 而不使用OpenMP的执行过程只使用了51%的CPU资源, 没有充分发挥双核的优势。

5 总结

介绍了使用OpenMP进行多核程序设计的方法, 并通过一个实例程序证明了使用OpenMP编译指导后程序的执行效率有显著的提高。限于篇幅, 文中只介绍了for循环的并行化编程方法, 关于OpenMP更多的使用方法, 请参考OpenMp的使用规范。

参考文献

[1]OpenMP.C and C++Application Program Interface, Version2.0March2002.

混合关键性多核系统调度综述 篇8

1 混合关键性多核研究现状

“研究混合关键性系统的会议”[3]把混合关键性系统定义为包括一套完整的硬件操作系统、中断服务和应用软件的系统。在一个安全的应用平台上,应用软件支持安全关键性、任务关键性和非关键性任务的执行。大多数的应用紧接着就是物理上、模块上和安全性的限制,利用分布结构得以实施。不同类型的硬件单元(称为节点),通过网络进行连接。起初,每一个功能都有各自的节点,造成了节点的剧增。现在的趋势朝着“集成框架”发展,许多功能集成到相同的一个节点上。在现有的实时系统中,集结所有混合关键性的工作量在一个平台上是不可能的,这是由于两个方面的问题:由于WCET的悲观分析而导致的计算资源的未充分利用,尤其是HI任务,严重限制了硬件的计算工作。为了有效的利用多核平台提供的计算带宽,所有的研究都在考虑利用空闲带宽,相应的的调度策略应运而生。混合关键性被提出是为了实现潜在CPU资源的有效利用,同时保证任务安全性和对HI任务的暂时隔离。单核上的功耗和发热问题使多核平台在实时系统中越来越流行。多核的应用是受额外的计算带宽和嵌入式系统能耗等方面的影响,除此之外,所有的芯片制造商转为多核的设计和生产,降低了单核芯片的利用,由于计算工作量所支持的未来系统,是复杂的,混合关键性的,所以未来都将应用到多核系统。

2 混合关键性任务调度算法

2.1 HI任务的保证和LO任务的积极处理

文献[4]中提出了由不同WCET值组成的混合关键任务模型。先合理估算LO-WCET,它几乎满足所有可能出现的情况。在高度不可能的事件中只要运用的调度机制可以保证HI任务满足截止期,这个估算可以被违反,系统的设计一样被认为是安全的。现有的研究利用资源预留机制来提高资源的利用率,但是运行期间预留资源不充分时还是优先调度关键性的任务。其中的大多数还都做了不切实际的假设,即所有的关键应用同时需要额外的资源,通过降低LO任务的应用造成了资源的未充分利用。在文献[5]中指出当HI任务超过预期的WCET,其他HI任务同时需要更多资源的可能性在实际中非常低。因此在一些HI任务同时需要额外资源时抛弃LO任务是不合理的。

文献[6]中用一个新颖的算法克服了上述缺点,它用一个参数来模定同时请求更多资源的关键任务数量,基于这个参数来制定提高资源利用率的执行策略。在实际应用中混合关键系统是基于组件的,利用组件边界来支持执行隔离LO任务,同时保护HI任务。仿真结果显示在可调度性和支持LO任务应用方面有很大的提高。

混关实时系统中,WCET不仅很难计算,很多算法都提到了关键级逆转的问题,为了解决这个问题,文献[7]提出了零松弛调度算法。当然CAPA(criticality as priority assignment)能防止关键性的逆转,但是它的调度利用率不高。零松弛调度算法,假设任务刚开始时没有空闲时间,所有任务在HI mode下运行,然后把高关键模式下的计算时间转移到低关键模式作为发现的空闲时间,一直循环迭代直到低模式时没有空闲。零松弛调度算法在保障高关键任务的实施方面具有很大的作用,但忽略了对LO任务的调度保证。

文献[8]中,基于同构多处理器平台构建了两个队列,包括就绪队列和被抛弃的LO任务队列,就绪队列采取混合关键级局部调度,被抛弃的LO任务则对空闲时隙进行分配,实验证明,它可以提高LO任务被调度的可能性和任务集的可接受数目。

为了提高LO任务调度的可能性,文献[9]中通过降低HI任务在低模式时截止期,也就是给HI任务提供一个虚拟截止期来提高LO任务的调度,但它只适合隐性截止期的混关系统。

文献[10],对大多数混合关键性系统提出了一个新的需求调度测试,同时限制LO任务和HI任务的需求。新提出的测试严格的决定了其它已知的需求调度测试,基于这个测试,又提出了新的截止期策略,通过仿真验证新的策略对于偶发任务系统,比其它策略要好的多。

文献[11]中,对EDF-VD做了扩展,从EDF-VD算法中了解到该算法用一个统一的参数因子构成虚拟截止期,这篇文章基于上述算法提出了EDF-NUVD算法,它通过不同关键性水平下的因子构成不同的虚拟截止期,通过实验仿真验证此算法与EDF-VD相比能够调度更多的任务,实现更广泛的任务调度,同时能够保证最基本算法中最坏资源利用率。

文献[12,13]中指出,当LO任务是控制任务时,立刻抛弃低任务这种方法会造成很严重的服务中断和严重的性能丢失,任务的性能受执行频率和服务间隔的影响很大。为了减轻这个问题,基于传统模型Santy et al在文献[14]中研究了在线调度,在进入HI模式之前计算它所允许的推迟时间,推迟取消LO任务从而提高它们的服务水平。然而,这个方法并没有给LO任务提供任何服务保障。弹性混合关键性任务模型(EMC)和最早释放EDF(ER-EDF)调度算法[15]已经被用来研究解决LO任务在单处理器系统上的服务中断问题。EMC任务模型主要是以不牺牲HI任务的最坏保障为前提,给LO任务不同的周期(即服务间隔),它的最小服务水平取决于最大周期,ER-EDF让LO任务在最大周期前释放。离线的保证LO任务的最小服务需要,来改善它们在运行期间的服务水平。

在文献[16]中受现存工作的激发但又不同于现有的工作,研究了E-MC任务在多核上的调度。文章介绍了EMC任务在P-EDF上的调度,集中于P-EDF调度,探索了不同任务划分到核上的E-MC任务调度,然后研究了不同的早期释放技术(以提高LO任务在运行期间的服务水平为目标),通过考虑有无任务转移,进一步研究全局和局部的最早释放调度,与目前的全局EDF调度相比P-EDF调度下的早期释放技术能够提高LO任务的执行频率。这篇文章还发现了不同混合度的LO、HI任务对任务集的调度有影响,LO、HI任务各占一半时有最坏的调度性能。

时间预测对于设计混合关键性来说非常重要。从文献[17,18]中可以看到,如果硬件是有预测性的,那么WCET的分析就变得容易很多。文献[19,20]中,许多研究者在探索设计可预测处理器的可能,文献[21,22]中研究了可预测的分级存储。如果程序小能够适应快速的计算,本地的SRAM是个很好的选择,但是对于较大的程序,DRAM存储比SRAM存储的要多,而且比较便宜。最近,设计出了一些可预测性的DRAM控制器。但对于混合关键性来说仅仅设计预测性能是不够的,还要考虑划分系统安全性时的冲突性需求和共享资源的有效利用。文献[23,24]中解释了为混合关键性设计的DRAM控制器,但是它们是以牺牲非关键任务的执行为代价来实现隔离和最坏情况下的预测。

文献[25]中作者利用区感知地址映射技术和DRAM基于优先级的抢占调度,以不牺牲非关键任务设计了新的DRAM控制器。在含有缓存的ARM ISA处理器执行基准上来重复估算存储路径,gem5 模拟框架上进行模拟。通过与现有的基于TMD的方法相比,文中提到的存储控制器能实现非关键任务的更高执行,也不会对关键性任务产生坏的影响。

2.2 严格的全局时间隔离

为了保持众核在共享存储上的隔离,可以选用一个静态调度总线或者在仲裁总线上放一个服务器,这个服务器上为每个核提供相应的预算。但是这些方法有很大的缺陷,静态调度总线不灵活,如果出现其他情况,在运行期间总线调度不能改变。仲裁总线上放一个服务器这种方法,虽然灵活但有很高的设计和实施开销,这两种方法在多核上也不能直接运用。于是基于预留的调度策略,时间触发或者是资源预留的方法被提出,以确保LO任务对HI任务不产生干扰,或是较低的干扰。

文献[26]在共享资源上,只允许相同关键性的任务运行在同一个时间帧里面,跟以往的静态资源划分策略有很大的不同,通过障碍机制来达到核内动态同步的全局时间触发调度,只有同等关键性的任务才会在资源共享、存储和总线上产生相互影响。利用FTTS策略,极大地减少了LO任务对HI任务的干扰,提高了HI任务的调度成功率和资源的利用效率。通过与传统的时间划分和现有的算法的对比,它的有效性更好,在实际的航空电子上也被验证有效。

文献[27]中解决了MC资源共享多核系统平台在WCET上的分析。作者提出了一个基于存储的节流机制来进一步控制共享存储路径上的核间干扰。它是假设所有的HI任务被划分在一个处理器上,在其他核上的LO任务有一个限制的存储预算。

在航空领域,划分结构被称为“集成模块化航空电子设备”(IMA),平台上的隔离区分机制由ARINC 653水平来定义。ARINC 653 包括硬件调停操作系统水平上的空间和时间分区机制。文献[28]中,设计者也在平台上应用了区分机制。这篇文章提出在成本限制的分区框架中用禁忌搜索算法来实现混合关键性的最优应用。这个体系结构由各种各样的进程元素通过广播总线相互连接。通过分区,不同关键性的任务仅可以利用预先决定好的时隙进程,因此在时间和空间上达到了隔离,并通过静态周期调度来调度任务和消息。在成本限制的框架上找到了可实施的调度,最小化了调度成本。在文献[29]所呈现的模拟退火技术中,为了最优化时隙的次序和大小,把固定的映射考虑了进去。结果显示,把映射和分区机制考虑进去给系统带来很大的提高,但是仍有即使考虑了这两种情况仍不满足的情形。

3 任务在多核处理器上的划分

多核调度大致可以分为三种,局部调度,全局调度和前两者的混合调度。全局调度(G-EDF)适合于软实时任务,实现了更高的利用率,但它对共享内存和总线会产生激烈竞争,使WCET的分析变得更难。局部调度提供了简单的和更有预测性的实施方法,任务被静态的划分到处理器不允许转移,对硬实时调度来说是很好的选择,但当划分任务到处理器由于装箱问题会引起处理器空间浪费。

在文献[30]中作者向我们呈现了混合关键性在多核上的结构框架。有五个关键水平,基于集装箱的分层调度机制,每个水平用不同形式的调度、分区。A水平(最高的)利用周期执行的方法,B水平用局部EDF调度,C和D水平用全局EDF调度,E水平用全局努力尝试调度,保证了关键水平间的暂时隔离,空闲转移策略缓解了当HI不是那么紧急而LO任务需要等待HI任务的情况,把P-EDF和G-EDF结合起来,弥补了各自调度的不足。

对于固定优先级调度,文献[30]中,比较了混关任务不同的分区装箱算法。任务按照利用率或者优先级的降序来调度,比较了首次适应,最坏适应和最好适应三种算法。实验证明由首次适应或者最好适应结合的关键性降序算法有最好的调度率。

在文献[31]中,提出了MPVD算法。在MPVD算法中,HI任务利用最坏适应装箱算法,LO任务利用首次适应算法来实施在多核上的调度。两种算法下,依靠每个关键水平上的利用率来划分任务,结果显示任务的调度成功率得到显著提高。

为了提供一个可预测的和有效的分区划分,文献[32]中,提出了双分区混合关键算法(DPM),HI任务在任何时候都静态的划分到处理器,同时LO任务允许有限制的转移来有效利用核空间。只要系统在稳定的模式就能够被完全划分,在关键性转换时,LO任务可以转移到其他核。DPM算法通过限制LO任务的转移来提高有效的分区同时维持分区系统的优点。结果显示DPM算法在利用率上达到了0.8 甚至更高,与已有的相比比其它算法调度多大百分之十七的任务。

4 结束语

当HI任务要进行模式转换时,要抛弃LO任务,转换的那一时刻我们还是需要LO任务数据所含带的信息,所以立刻终止LO任务是不适合的,但目前我们为了研究方便,我们都是做出这样的假设,显然这是我们未来研究中的一大方向。

安全性并没有详细精确的模型,对于大多数的安全水平来说,不同的关键性要有不同可能性的安全保证,这些保证在现有的研究结果上还不能实现。更深一步讲,抛弃或者降级服务会潜在的影响LO任务,我们知道这些在系统安全上的影响现有的方法中还没有定量的分析,为了限制这些影响的分析技术还需要发展起来。