存档

文章标签 ‘CMP’

CMP读书笔记五:通过并行加速程序

2011年4月10日 sigma 9 条评论 4,521 views

前一篇关于降低单任务延时的文章,主要讲的都是在现有的编程模式下,不改变现有串行程序代码下,通过编译器,操作系统,以及处理器自动给程序加速,降低延时。但是,这种加速方法加速很有限,不具有可升级性(scalable):辅助线程(helper thread)受限于只有一个主线程,一个辅助线程,加速比很难超过2;猜测多线程(TLS)受限于原来串行程序上下文的依赖性,可拆解的部分有限,加速比也不理想。

为了解决程序在多核系统加速受限的问题,出现了串行程序不同的编程模式,并行编程。和串行程序不同,并行程序设计要求程序员显示的声明程序的那些部分是可以并行的。因此,对于一个习惯于串行程序编写的程序员来说,写并行程序难度要大。

对于串行程序,只需要输入相同,每次执行的结果是一样的,是确定的。而对于并行程序,执行的结果每次都可能不一样。在这些所有的执行结果中,只需要能够把并行程序串成某个串行程序,并且该串行程序的执行结果和该次并行程序执行结果一致,则认为程序在顺序一致性模型(sequential consistency,SC)下是正确的。顺序一致性的严格定义如下:

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

意译成中文如下:

并行程序的任何一个执行结果都和某个顺序执行相同,该顺序执行符合:①该顺序执行是将所有处理器执行的并行操作(指令)串起来的。②对于原来任何一个处理器上的并行执行操作,其排序在改顺序执行上的排序一直。(通俗的将,在并行执行中,对于同一个核心的执行A,B,倘若A在B前,在最后的串起来的顺序执行,A还是要在B前)

因为这个一致性模型要求太强了,要保证并行执行符合该模型对硬件要求很高,并且会带来极大的性能损耗,因此,出现了很多弱的一致性模型。

另外,由于并行程序可能出现的符合一致性要求的结果不止一个,而事实上程序员希望的执行结果可能只有一个或几个,为了解决这个问题,对于要放到不同处理器核心执行的代码,就需要程序员显式的标记那段代码在那段代码之前执行,既需要通过一些barrier来同步不同处理器核心的执行。

另外,并行执行还涉及到对一些临界资源的访问,对于这些共享的资源,往往只能一个处理器访问,这是就会出现互斥,这时需要一些机制来保证互斥访问,于是出现了锁的机制。但锁很容易导致死锁活锁问题,导致性能极大下降。为了解决这个问题,受数据库启发,出现了事务内存(transaction memory,TM)的概念,但是TM对硬件的改动极大,现在还没有商业的处理器能够实现(之前sun公司的Rock处理器号称要实现,但是直到sun落下,rock也没出来,之后就直接停止了研发)。

写到这里,突然这个关于并行的题目有点大,有太多的东西需要讲,有太多的东西需要介绍,有种剪不断理还乱,不知从何处下手的感觉。好吧,这篇就先扯到这,让他虎头蛇尾好。

有空的话,我再写些东西把各种一致性,各种编程模型以及事务内存,以及其他的并行相关的东西介绍下~

最后,秉承每文一图的习惯,附一张顺序一致性的示意图(上面是符合的并行执行,下面是不符合的并行执行):

CMP读书笔记四:降低单任务的延时(Improve Latency)

2011年3月31日 sigma 4 条评论 6,485 views

上一篇关于提高处理器吞吐量的文章讲到,CMP以及SMT技术可以大大提高处理器的吞吐量,提高处理器的并发处理器能力,从而分别提高处理器的峰值和效率。

但是,现在的很多串行程序,还不能直接从CMP以及SMT技术中获利。并且,这些程序中有很多都又对延时很敏感,比如说各类实时应用。对于这些程序,提高单个任务的性能,降低延时就很有必要。在CMP出现之前,各类的复杂的处理器结构的基本目标都是这个,包括超标量,提高主频等,其基本思想都是提高单处理器核心的性能。但是,当多核时代来临后,出现了一些新的方法,最常见的有:辅助线程(Helper thread),猜测多线程(thread-level speculation,TLS),核融合(core fusion)等技术,下面对这些技术进行简要的介绍。

辅助线程技术是通过在任务主线程外的加一个辅助线程(helper thread),辅助线程要比主线程跑地快一点,但是可以跳过一些代码,功能主要是为主线程完成一些预取操作,比如将数据从主存搬到cache上,从而降低主线程的cache miss等,提高主线程(也即任务)的执行速度。

猜测多线程技术是通过在执行过程中将一些原来的串行比较容易并行化的代码(如循环,分支,不同函数等)的动态地分配给几个线程执行,从而提高程序的执行速度,但是猜测多线程会带来额外的消耗,一是线程分配的消耗,另外就是猜测失败重新执行的消耗。一个好的猜测多线程机制必须解决以下几个问题:

  • 线程间通信:如何拆解程序,使不同线程之间的通信尽可能少,同时如何通信,使得线程间通信效率尽可能高。
  • 检测处理各种相关:为了保证程序执行的正确性,必须检测线程间的各种相关并进行处理,包括读后写(RAW),写后读(WAR),写后写(WAW)相关。不合适的线程分配会导致大量相关,从而导致线程间大量依赖导致堵塞。不明智的相关处理器机制会导致堵塞的时间很长,从而程序效率低下。
  • 猜测失败的处理:既然是猜测,难免就会失败。失败后的恢复或者重新执行的机制需要保证系统的所有相关状态要回到猜测执行之前的状态,这样才能保证安全和正确。
  • 猜测线程机制:猜测线程需要考虑各种因素:由于每个线程的buffer size有限(在每个线程提交之前,为了保证正确性,所有执行都需要buffer下来),导致每个线程的长度不能太长。必须减少线程间的真依赖,减少堵塞。多长的时间进行check,何时进行重新执行等等。

核融合是指硬件将多个核的各个功能部件,如取值,执行等融合成一个核,就像superscale那样,从而提高串行程序的执行速度。这东西貌似比较新,wikipedia都还没有相关内容,想了解的话,可以自己google scholar “Core fusion”。

最后,附上一张TLS的示意图,图来自《Chip Multiprocessor Architecture:Techniques to Improve Throughput and Latency》一书:
猜测多线程TLS示意图

CMP读书笔记三:提高吞吐量(IMPROVING THROUGHPUT)

2011年3月31日 sigma 没有评论 8,170 views

随着互联网的发展,web服务器成为了一个很大的应用。和传统的科学计算以及桌面应用不同,web服务器对延时并不是很敏感,因为网络传输延时往往大于服务器端的计算延时。相反的,对于web服务器,提高并发处理能力倒显得极端重要,因为现在的web站点动辄就是几万人,甚至上千万人在线(当然,对于这种系统,往往不是一个服务器,而是服务器分布在各地,导出都是CDN),因此,提高web服务器的处理器吞吐量就显得极端重要(记得计算所所长李国杰院士去年提过高通量计算,不知道是不是这个意思)。

提高处理器的吞吐量的基本思路很简单,那就是提高处理器的并发线程数,而提高处理器的并发线程数,方法又有两类,同步多线程(Simultaneous MultiThreading,SMT)以及多核(Multicore)。

传统的处理器核心只能并发执行一个线程,而一个线程内部往往会由于相关(数据相关,控制相关)导致流水线堵塞,从而导致处理器的部件不能充分利用(包括取值部件,功能部件等)。为了减少由于线程内的依赖所造成的堵塞,提高单个处理器核心的吞吐量,出现了在一个处理器核心同时执行几个线程的技术(因为线程间的依赖比线程内要少很多),即同步多线程技术,Intel又叫超线程技术(Hyper-Threading Technology,HT)。

同步多线程(SMT)是一种在一个CPU 的时钟周期内能够执行来自多个线程的指令的硬件多线程技术。本质上,同步多线程是一种将线程级并行处理(多CPU)转化为指令级并行处理(同一CPU)的方法。 同步多线程是单个物理处理器从多个硬件线程上下文同时分派指令的能力。同步多线程用于在商用环境中及为周期/指令(CPI)计数较高的工作负载创造性能优势。 同步多线程使您可在同一处理器上同时调度多个线程,从而充分利用处理器的各个部件,提高性能功耗比。下面是一副不同粒度的多线程技术的比较,同时从图中也可以基本看出同步多线程的基本原理。
同步多线程示意图

很多厂商,包括IBM,Sun,Intel的处理器都应用了同步多线程技术,MIPS昨天也发布了代号为神童(Prodigy)的64位同步多线程处理器

另外一方面,多核也是提高并发线程数的好方法,但是多核会增加大量的面积及功耗,从而大大降低性能功耗比,而性能功耗比对于24小时在线的web服务器是至关重要的,因此,不能简单的在超标量核心上堆积现有的复杂的超标量(Superscale)处理器核心。

考虑到web应用对延时不敏感的特点,可以将每个处理器核心设计的尽量简单(但可以保持其同步多线程的能力),从而提高处理器核心数目同时,对面积和功耗并不会提高,同时可以大大的提高处理器处理并发线程数(等于处理器核心数X每个核心的多线程数)的能力,提高处理器的吞吐量,并且提高性能功耗比。下面这幅图比较了超标量的多核处理器和简单的多核处理器的吞吐量和功耗的比较,可以看到,简单的核心优势极其明显。
标量的多核处理器和简单的多核处理器的吞吐量和功耗的比较

在设计web服务器处理器方面,Sun做到了极致,其Niagara系列处理器绝对是这个领域的巅峰之作(可惜一心做技术的sun却被一心赚钱的oracle收购了!)。

CMP读书笔记二:CMP简要介绍

2011年3月31日 sigma 2 条评论 8,091 views

注:上个学期就下过决心要把《Chip Multiprocessor Architecture Techniques to Improve Throughput and Latency》看完,并且写了一篇关于CMP的读书笔记,《CMP的提出》,之后,虽然看了下,但一直不想写,今天突然感觉应该把看的东西简要写写,算是总结,故有此文。为了使得这几篇文章脉络稍微清晰点,在这里先对片上多核处理器进行简要的介绍。

片上多核处理器(Chip Multicore Processor,CMP)就是将多个处理器核心集成到一个处理器芯片中,从而提高单个处理器的处理能力。

按照集成的处理器核心的数目,片上多核处理器可以分为多核处理器和众核(Manycore)处理器。

按照计算内核对等与否,片上多核处理器处理器又可以分为同构多核处理器和异构多核处理器。同构多核处理器的各个核心的结构相同,地位对等,现在主流的处理器厂商,如Intel,AMD所推出的处理器一般都是属于这类。异构多核处理器的各个核心的结构不同,功能也不同,地位也不同,分为主处理器和协处理器,IBM,索尼,东芝联手推出的Cell处理器就是一个典型的代表,Cell由一个Power主处理器单元(Power Processor Element ,PPE)和8个协同处理单元(Synergistic Processing Elements,SPE)组成,8个SPE结构不同的,不同的SPE可以快速的完成不同的类型的运算。

片上多核处理器的出现使得在一个处理器上并发地执行多个线程成为可能,大大的增加了处理器的吞吐量(throughput),一些吞吐量的应用,如web应用,可以充分的并且很简单地利用片上多核处理器代理的优势,详见关于提高处理器吞吐量的文章。但是,对于另外一些对延时敏感,需要高性能的应用,就不是那么容易直接利用多核带来的性能提升。

这些程序分为两类,一类是原来单核心处理器上的串行程序,这些程序不可以直接通过多线程手段在多核处理器上获得更高的性能,为了利用多核所能带来的性能提高,有两种方法可以提高这类程序的性能:第一种是通过增加一个辅助线程(helper thread),辅助线程要比主线程跑地快一点,但是可以跳过一些代码,功能主要是为主线程完成一些预取操作,比如将数据从主存搬到cache上;第二种是通过猜测多线程(thread-level speculation,TLS)来提高串行程序的性能,猜测多线程通过在执行过程中将一些原来的串行比较容易并行化的代码(如循环)的动态地分配给几个线程执行,从而提高程序的执行速度,但是猜测多线程会带来额外的消耗,一是线程分配的消耗,另外就是猜测失败重新执行的消耗。这部分内容详见以后会写的关于降低处理器单任务延时的文章。

第二类程序就是一些本来就是针对多核处理器设计的多线程程序,对于这类程序,可以直接将不同的线程映射到不同的处理器核心,但是,该类程序会因为不同的线程间的数据依赖以及共享资源的竞争导致不能取得理想的加速比。

该书电子pdf版:

Chip Multiprocessor Architecture Techniques to Improve Throughput and Latency

CMP读书笔记一:CMP的提出

2010年10月17日 sigma 没有评论 5,625 views

这段时间,天天上午睡觉,下午去实验室,晚上三国杀,很久没有静下心来看书了,感觉继续这样下去会不行的。于是打算开始看些体系结构领域相关的书籍,为了提高效率,尽量写写读书笔记。

我选的第一本书是《Chip Multiprocessor Architecture:Techniques to Improve Throughput and Latency》。这是一本刚出不久的,关于片上多核处理器(Chip Multiprocessor,CMP)的设计技术的书,由Kunle Olukotun,Lance Hammond,James Laudon合著的,其中前两位作者都是斯坦福TCC(Transactional coherency and consistency)小组的大牛,第三位作者Sun公司的工程师,Sun公司是我最敬佩的技术类公司,没有之一,只是可惜死了。这本书主要关注的是如何提高处理器的吞吐量以及降低延时。里面涉及了很多新的技术(包括一些没有在工业界实现的技术,如线程级预测TLS-Thread Level Speculation、事务内存-TRANSACTIONAL MEMORY),个人觉得对做多核芯片和并行程序设计的人来说还是不错的一本书。

本书的第一章回顾了整个CPU的发展史,从指令集并行(Instruction-Level Parallelism,ILP)引出了线程级并行(Thread-Level Parallelism),从而导出了CMP的话题。

2006年之前,CPU的性能基本上是按着摩尔定律发展的,这得益于两个方面,一个是集成电路的发展,另外是处理器结构的优化,如超标量技术(Superscalar),动态流水线技术(Dynamic Pipeline),乱序执行技术(Out-of-order Execution)。

但是,在2006年左右,摩尔定律出现了一次危机,ILP也几乎走到了尽头,主要原因是:

  • 集成电路已经发展到了极限,再要提高集成度非常困难,尤其是现在28nm的情况下。
  • 功耗问题的突出,为了提高单核心的速度,提高ILP,现在的处理器花了很大一部分面积用于这些技术的调度,如动态流水线的调度,乱序执行的调度,这些面积的功耗已经远远超过了运算器件的功耗。导致处理器的效率(性能功耗比)急剧下降。
  • 设计验证难度的增加,要想在单核情况下提高处理器的性能,需要设计更复杂的超标量乱序执行动态流水线结构,这导致芯片的设计,尤其是验证呈指数增加,很难再一两年内设计出一款商业的芯片。
    于是,学术界和工业界就提出了更粗粒度的并行,线程级并行TLP。于是有了多核处理器的诞生,多核处理器的主要思想就是,一个芯片内集成几个核,每个核可以做的简单点,每个核的性能功耗比就能做的比较好,从而总的性能功耗比也得到了提高。
    之前的单核超标量处理器的并且,主要都是在ILP层面,通过多发射,分支预测技术,只能处理器一些基本的,很小的并行块,无法进行线程级甚至任务级的并行。各种粒度的并行和各种体系结构的关系如下图:

image

接着作者举了个CMP和Uniprocessor的比较的例子,并做了性能,效率的比较分析。

最后,作者指出了本书主要讨论的问题,一个处理器的吞吐量,一个是延时。前者主要针对并行粒度大,并行度高的应用,如互联网应用;后者主要针对一些延时敏感的应用,如各种实时系统以及各种桌面应用。

无觅相关文章插件,快速提升流量