存档

‘读书笔记’ 分类的存档

程序/进程的前世今生

2012年2月8日 sigma 5 条评论 6,031 views

在这篇文章中,将介绍下程序从源码,到目标文件,到二进制码,再到装载,运行以及退出的整个过程,简称程序/进程的前世今生。

首先,区分一下程序和进程的概念。程序是一个静态的概念,而进程是一个动态的概念。程序一般是指从源码到二进制码这些过程的实体(勉强简称为前世),而进程则是从装载,到执行,到推出的实体(勉强简称为今生)。维基百科对两个概念的定义为:

程序的定义:

计算机程序或者软件程序(通常简称程序)是指一组指示计算机或其他具有讯息处理能力装置每一步动作的指令,通常用某种程序设计语言编写,运行于某种目标体系结构上。

进程的定义:

行程(英语:Process,中国大陆译作进程,台湾译作行程)是计算机中已执行程序的实体。行程本身不会执行,是线程的容器。程式本身只是指令的集合,行程才是程式(那些指令)的真正执行。

对于上面进程的定义,个人觉得有点问题(不仅仅是大陆台湾叫法不同的问题),我认为应该是”进程是计算机已执行程序的实体。对于多线程程序,程序可能存在多个同时执行的指令流和控制流,称为线程。程序本身知识指令的集合,进程才是那些指令的真正执行”。

下面,就开始介绍程序/进程的前世今生,由于内容较多,在这里只是介绍前世今生的各个阶段,各个阶段的详细介绍,后面有空的话,并且觉得有必要的话,会单独写一文。不废话,转入正题,程序/进程大致需要经过以下阶段完成其前世今生(以C语言以及Linux进程为例): 阅读全文…

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

2011年4月10日 sigma 9 条评论 4,460 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,371 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,058 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收购了!)。

处理器的存储子系统(三)– 页表和TLB

2011年1月22日 sigma 4 条评论 17,880 views

之前一时冲动,说要写三篇关于处理器存储系统的文章,之前写过了概述Cache,其实写到后面就不太想写了,但是想到不写岂不自己打自己嘴巴,只好硬着头皮把最后一篇关于页表和TLB的写完。既然是硬着头皮写,其质量也就不敢保证了,有错误也在所难免,各位看官需要自行甄别。

Cache的那篇文章中已经讲到,为了区分不同进程的存储空间,现在多任务的操作系统以及处理器都需要支持虚地址(Virtual Address, VA)实地址(Physical Address, PA)转化,虚实地址转换主要分为两种:

  1. 由于整个系统的进程数不定,每个进程所需要的内存不定,以及进程切换的不确定性,因此,虚实地址转化不能简单的将某个连续大内存块映射到某个进程(Coarse-grained),必须采取更细粒度(Final-grained)的映射,即将一些可能不连续的小内存块(比如4K大小)一起映射到进程,形成一块连续的虚拟地址。为了记录这些映射信息,需要页表(Page)。但是页表的导入引入了新的问题,那就是每次访存变成了两次,一次查询页表,得到物理地址,第二次通过物理地址取数(事实上有办法把这两个过程部分并行起来,详见Cache的那篇)。为了提高查询页表的速度,现在的处理器都为页表做了一个小Cache,叫做旁路转换缓冲(Translation lookaside buffer, TLB)。
  2. 直接映射,比如直接将64位的虚拟地址高位抹去,得到物理地址。这主要用于操作系统启动时的那块内存区域。主要是由于系统刚启动时,第1种转化所需要的页表,TLB没有初始化(页表,TLB其实都是操作系统管理的,倘若还用第一种,就陷入了鸡生蛋,蛋生鸡的死循环了),只能用这种最简单粗暴的办法。
    由于第二种比较简单,在这里主要讲一下第1种虚实地址转化,即通过页表和TLB进行虚实地址转化。
    用固定大小的页(Page)来描述逻辑地址空间,用相同大小的页框(Frame)来描述物理内存空间,由操作系统实现从逻辑页到物理页框的页面映射,同时负责对所有页的管理和进程运行的控制.用页表进行虚实地址转化的基本原理如下图:
     

    首先,用虚地址的高位(叫做虚页号,Virtual Page Num,对应着一个小内存块)查询页表,得到其物理页框(Physical Page Frame)地址,然后用物理页框地址和虚地址的低位(偏移量,Page offset)得到物理地址。其中上面的偏移量决定了每个页表项的大小,在现代通用处理器中,一般为4K。

    理论上,页表里面表项的数目和虚地址的高位数目有关,等于虚地址高位所能表示的最大值。因此,其数目非常可观,为了减少页表大小,出现了多级分页技术。

    当进行虚实地址转化时,查询页表发现页表不在主存,就会出现缺页例外(Page fault)。缺页中断需要操作系统把所需要的页表文件加载入主存,然后继续查询,这会消耗大量时间。

    即使页表在主存中,查询也会消耗大量的时间,因此,利用局部性原理,现代处理器在其内部实现了一个页表的高速缓存,即TLB。当虚实地址转化时,先去TLB中查询页表是否存在,只有不存在时(此时发生TLB miss例外),再去主存中查询,当主存中还没有时,直接去物理存储查询(此时发生缺页例外)。

    现代分页技术中,几个最关键的问题是:

    一是如何提高TLB命中率,一种办法是加大TLB大小,这种办法很好理解,第二种办法是加大页大小,这样同样大小的存储区域所需要的页表数目大大减少,相当与增大了TLB。

二是如何减少缺失的损耗,其中的一种方法是增加一个类似于victim cache的victim TLB。

三是如何让虚实地址转化和访存并行起来,起码和访问Cache并行起来,方法是实现虚地址Cache,详见Cache篇

第四个是如何实现低功耗的TLB,现在有很多解决方案,比如说进行TLB预比较,增加一级TLB等。

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