资源描述
Title,PCA L16 Chp7.,*,Wu Spring 04 USTC,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,Parallel C,omputer Architecture并行计算机体系结构Lecture 16,概要,复习第14讲,基于目录高速缓存一致性协议,放松的存储一致性模型,并行文件系统,工作站机群上的文件系统,并行应用一般要处理很大的数据集,I/O系统应该能允许并行应用中协作化的操作。,因此需要设计一个高性能的文件系统来简化进程间的协作，高效地利用所有资源，并且对用户是透明的。,考虑机群系统最根本的两个特点：,大量资源：如磁盘、内存等。,并行存取多个磁盘来提高传输带宽；,利用机群系统中的内存，建立大的文件系统缓冲区来提高性能；,高速互连网络,允许系统依赖远地节点完成某些任务。例如，现在的一些系统依赖远地节点的内存来保存本地节点中放不下的高速缓存块。,软件RAID,软件逻辑RAID：,将RAID的思想用在机群中，将数据分布在机群系统的多个磁盘中。,软件RAID表现就象RAID 5，并且与RAID具有相同的优缺点,与RAID的区别，就是文件系统需要负责分布数据和维护容错级别。,条块组Stripe Group：,将机群系统所有的磁盘组成一个逻辑RAID,向所有磁盘写的大的写操作非常困难，导致很多小写操作。但在RAID 5，小的写操作效率差。因此，系统就不能充分利用所有磁盘的写带宽。,节点的网络连接的带宽有限，不能够同时读/写所有磁盘，只能利用局部磁盘性能。,发生故障的可能性大。奇偶校验机制不够，可能同时多个磁盘故障。,解决方法是将数据条块化分布到磁盘的一个子集上条块组。,系统需要执行的小的写操作数目大量减少。,网络连接的带宽与条块组中磁盘的集合带宽相匹配，充分利用资源。,系统中允许多个磁盘失效，只不过不能是属于同一条块组的多个磁盘。,代价：减少了磁盘存储容量和有效带宽，因为每个条块组都必须有一个存放奇偶校验块磁盘，而在原来的方法中整个系统只要一个存放奇偶校验块的磁盘。,日志结构的文件系统Log-structure Filesystem,日志结构的文件系统提高磁盘速度。,根本假设：高速缓存满足读操作的比例是很高的，因此磁盘的通信量主要是由写操作决定。如果能够改善写操作的执行，顺序执行所有写操作，就可防止寻道和查找时间，能极大提高磁盘性能。,日志结构文件系统的根本思想：使大局部写操作是按顺序执行。,日志结构文件系统中，将整个文件系统作为一个日志来实现。日志结构的文件系统在每次块被写到一个文件时都将数据块加到日志的末尾，同时将以前写的块置为无效。这种方法允许每个文件被顺序写入；不管写的块顺序，因此提供了更快的写速度。,降低读性能的代价换来很高的写性能，增加了复杂性。,块按照写时的顺序分配使文件以随机顺序在磁盘中分散放置。,增加一个单独的垃圾去除程序来扫描文件系统、移除无效块。,需要一个复杂的缓存/查询机制来支持高效的查询，并且每个文件的块位置信息必须保存起来。,缓存,利用局部性原理,多级缓存：能够在不同的层次利用缓存机制。效劳器或客户端磁盘控制器、操作系统、I/O库、用户程序,缓存一致性问题：,放松的文件共享语义：对话语义，增加了程序员负担,一致性算法：实现Unix语义。不缓存写操作，,令牌：写之前必须获得令牌。令牌的回收，租约。,粒度：文件，文件块，自定义,协同缓存：,如不同的缓存间没有协作，不能充分利用所有的缓存空间；一个节点需要的文件块，已经缓存在另一个节点的缓存中了，从该缓存读提高系统的性能。,第一个实现协同文件缓存的系统是xFS。,根本思想：机群中每个节点分配一局部主存作为文件缓存。协同缓存算法利用所有这些主存来创立一个大型的、机群范围的文件缓存。当客户不命中局部文件缓存时，转向远地客户的存储器去取数据。,数据预取,预取：真正存取数据块之前就将其读入内存。,并行预取：每个节点独立的预取数据。One-block-ahead 或 Stride,透明通知预取：用户向I/O系统提供一些存取文件情况的提示信息，系统利用这些信息，能够更好进行预取。,积极预取：一旦当磁盘准备好后，就进行预取，将内存中最远的将来才用到的数据块替换出去。,表6.6 采用积极预取算法得到的预取调度序列一览表,时间,T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11,T12,服务块,F1,A1,B2,C1,D2,E1,F1,块1,F1,F1,F1,D2,D2,D2,D2,D2,D2,F1,F1,F1,块2,B2,B2,B2,B2,B2,B2,B2,E1,E1,E1,E1,E1,块3,A1,A1,A1,C1,C1,C1,C1,C1,C1,C1,I/O接口,传统的I/O接口不能表达数据并行、协同化操作等概念，开发一种新的I/O接口来表达这些新的语义信息.,共享文件指针:,全局共享文件指针,分布共享文件指针,跨步存取模式：,简单的跨步存取操作,嵌套的跨步操作,Berkeley NOW,主动消息Active Message：实现低开销通信的一种异步通信机制。,在消息头部控制信息中携带一个用户级子例程称作消息处理程序的地址。当信息头到达目的节点时，调用消息处理程序从网络上抽取剩下的数据，并把它集成到正在进行的计算中。,GLUnix：全局层Global LayerUnix,运行在工作站标准Unix之上的一个软件层，支持可用性和单一系统映像,易于实现、可移植性、有效性、鲁棒性。,xFS：无效劳器文件系统,文件效劳的功能分布到机群的所有节点上,软件RAID,协同式文件缓存,分布管理,IBM SP2系统,机群体系结构,标准环境,标准编程模型,系统可用性,精选的单一系统映像,高性能开关 HPS 多级网络,宽节点、窄节点和窄节点2,网络接口,系统软件,分布式共享存储系统,共享存储器分布于各节点之中，节点之间通过可扩放性好的互连网络相连。,在物理上分布存储的系统上逻辑地实现共享存储模型,对于程序设计者隐藏了远程通信机制，保持了方便性和可移植性。,DSM系统底层分布式存储具有可扩放性和代价有效性,分布式的存储器和可扩放的互连网络增加了访存带宽，但却导致了不一致的访存结构,共享存储系统的体系结构,无高速缓存结构：Cray-XMP，YMP-C90 向量机，大型机，早期分布式共享存储机器,共享总线结构：SMP UMA 小型商用效劳器,CC-NUMA结构:,COMA结构：,NCC-NUMA结构：,共享虚拟存储SVM结构：,CC-NUMA结构,高速缓存一致的非均匀存储访问系统：,共享存储器分布于各节点之中。,节点之间通过可扩放性好的互连网络相连，每个处理器都能缓存共享单元，,通常采用基于目录的方法来维持处理器之间的高速缓存一致性。高速缓存一致性的维护是这类系统的关键，决定着系统的可扩放性。,Stanford大学的DASH和FLASH，MIT的Alewife，以及SGI的Origin 2000等。,COMA,结构,唯高速缓存存储结构:,共享存储器的地址是活动的，存储单元与物理地址别离，数据可以根据访存模式动态地在各节点的存储器间移动和复制。,每个节点的存储器相当于一个大容量高速缓存，数据一致性也在这一级维护。,优点是在本地共享存储器命中的概率较高。其缺点是当处理器的访问不在本节点命中时，由于存储器的地址是活动的，需要一种机制来查找被访问单元的当前位置，因此延迟很大。,目前采用唯高速缓存结构的系统有Kendall Square Research的KSR1和瑞典计算机研究院的DDM。此外，COMA结构常用于共享虚拟存储SVM(Shared Virtual Memory)系统中,共享虚拟存储,SVM,结构,SVM(Shared Virtual Memory)系统，又称为软件DSM系统，,SVM系统在基于消息传递的MPP或机群系统中，用软件把分布于各节点的多个独立编址的存储器组织成一个统一编址的共享存储空间。,优点是在消息传递的系统上实现共享存储的编程界面，但主要问题是难以获得满意的性能,与硬件共享存储系统相比，SVM系统中较大的通信和共享粒度(通常是存储页)会导致假共享及额外的通信；,在基于机群的SVM系统中，通信开销很大。基于SVM系统的并行程序通信量通常比基于消息传递的并行程序的通信量大。,SVM系统的实现,在操作系统上改进，如Ivy、Mermaid、Mirage和Clouds等；,由运行系统来支撑，如CMU Midway、Rice Munin、Rice TreadMarks、Utah Quarks、DIKU CarlOS、Maryland CVM和JIAJIA等；,从语言级来实现，如MIT CRL、Linda和Orca等。,混合实现的分布式共享存储系统，其根本思想是结合软硬件实现的分布式共享存储系统的优点。,Overview,关于论文辩论与考试,Review of Lec14,基于目录高速缓存一致性协议,放松的存储一致性模型,高速缓存一致性问题的解决,硬件不支持高速缓存一致性(NCC-NUMA结构),为了防止一致性问题，共享数据被标识为不可高速缓存的，只有私有数据才能被高速缓存,好处在于仅需要很少的硬件支持就足够,缺点在于：,支持透明的软件高速缓存一致性的编译机制非常有限，基于编译支持的软件高速缓存一致性是不太现实的。,如果没有高速缓存一致性，那么在与访问远地单字所需的同等开销下系统将失去获取并使用一个高速缓存行中多个字的优点。当每次访问远地主存只能获得一个单字时，共享存储所具有的空间局部性的优点就荡然无存了。,如果可以同时处理多个字如一个高速缓存行时，那么诸如预取等延迟容忍技术效果才能更好。,Context for Scalable Cache Coherence,Realizing Pgm Models,through net transaction,protocols,-efficient node-to-net interface,-interprets transactions,Caches naturally replicate,data,-coherence through bus,snooping protocols,-consistency,Scalable Networks,-many simultaneous,transactions,Scalable,distributed,memory,Need cache coherence protocols that scale!,-no broadcast or single point of order,解决方法:目录协议,显式地包含状态向量,与存储块状态相联系,记录每个存储块的状态,未命中，与目录通信,决定高速缓存拷贝的地址,决定将要进行的操作,确定协议以保持同步,一个高速缓存一致性系统必须:,提供状态集,状态转移图,以及动作,管理一致性协议,(0)决定何时调用一致性协议,(a)找出其他高速缓存上的存储模块的信息以决定将要进行的操作,是否需要同其他高速缓存拷贝进行通信,(b)确定其他拷贝的地址,(c)与这些拷贝通信 (使无效/更新),在所有的系统中都使用同样的方法进行(0),存储块的状态保存在高速缓存中,假设未命中那么调用协议,不同的方法通过(a)到(c)区分开来,基于总线的一致性,(a),(b),(c)都是通总线播送实现,访存失败的处理器发出一个“寻找信号,其他的对该信号做出响应并采取必要的动作,在规模不同的网络上都可实现,向所有处理器播送,并使它们做出响应,Conceptually simple,but broadcast doesnt scale with p,
展开阅读全文