（计算机软件与理论专业论文）面向多核的并行虚拟机的研究与实现.pdf

太原理工大学硕士研究生学位论文 i 面向多核的并行虚拟机的研究与实现 摘 要 硬件发展模式从以前的提高cpu主频速度转变为现在的增加cpu内核 数量，注定了软件开发技术的变革。软件的性能再也不可能因为硬件的简 单升级而带来显著提高。想要发挥多核的威力，就要求程序开发人员转变 串行化的程序设计思维方式，转而变成并行的程序设计思维方式。但传统 的并行支撑技术都难于掌握，易于出错，学习曲线陡峭，使得并行技术难 于普及。 本文提出了一种虚拟机模型（sapvm），该模型采用对象与消息的概 念，提供了一个抽象的底层指令系统，该系统的所有方法调用都被抽象成 异步消息调用，每个对象都有独立的内存空间，所有的发送到对象的消息 都被放置到一个消息队列中，依次被处理。 该模型把 cpu 内核抽象成一个计算节点，上面提到的对象被分发到不 同的计算节点上，由多个计算节点同时处理各自的对象上的消息队列。而 且在一个计算节点没有任何可以处理的消息时，它会申请从其他计算节点 上转移一些多余的对象来处理，从而实现了动态负载平衡。 另外本文还就如何实现 sapvm 做了各方面的阐述，包括开发语言和 可移植性方面的考虑，内存管理技术，类型与对象的实现，同步措施的运 用。在内存管理技术中，提出了多级内存分配结合类型缓存池的方案，使 得内存分配能快速而易用。对于内存回收则使用了跟踪句柄类型的数据操 作，实时更新其引用计数，当内存不足时，系统启动内存回收过程，把所 太原理工大学硕士研究生学位论文 ii 有引用计数为 0 的对象内存回收。 最后本文提出了一个基于 sapvm 的脚本语言，该语言专门针对 sapvm 设计，能极大发挥 sapvm 的性能。本文简单介绍了该脚本的语法和基本编 程技术，包括脚本支持的数据类型，流程控制和并行语句块的使用。 关键词：自适应,并行计算，虚拟机，多核 太原理工大学硕士研究生学位论文 iii research and implementation of multi-core oriented parallel virtual machine abstract hardware development mode has made great progress from accelerating main frequency of cpu to increase the number of cpu core. so, it is destined that software development technology reform will follow. software performance will no longer get prominent progress from the simple upgrade of hardware. to maximize the performance of multi-core, program developers must change their way of thinking while programming from serial to parallel. however, traditional parallel supporting technology is hard to use, easy to make mistakes and difficult to follow the zigzag study course. this makes parallel technology not prevailed yet. this paper proposed a kind of virtual machine model (sapvm). it uses object and message conception and provide a nonfigurative underlying instruction system. all methods invoking of the system has been abstracted into asynchronous message invoking. every object has is own memory space and all messages that send to object are put into a message queue, processed one by 太原理工大学硕士研究生学位论文 iv one. this model has interpreted cpu core as computing node. objects mentioned above are distributed to different computing nodes. those computing nodes process their own message queue at the same time. when any computing node has no message to process, it will get some objects from other nodes so that it realizes dynamic load balancing. besides, this paper interpreted every aspects of sapvm realization, including development language and portability, memory management technology, implementation of types and objects and the use of synchronization measures. in memory management technology, we integrated multi-tier memory allocation and type buffer pool to ensure memory allocation more rapidly and easy to use. as to the memory recovery, we use data manipulation of tracking handle type. it can real-time update reference count and start memory recovery process and then retrieve all memory that has been occupied by zero-referenced objects when memory space is low. in the end, this paper gave a script language that based on sapvm. it is specially designed for sapvm and can maximize the performance of sapvm. this paper briefly introduced its grammar and basic programming technology, including data types supported by the scripts, flow control and the use of parallel blocks. key words: self-adaptive, parallel computing, virtual machine, multi-core 声声 明明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所 取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体己经发表或 撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本声明的法律责任由本人承担。 论文作者签名： 日期： 关于学位论文使用权的说明关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其中包括：学校有 权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其 它子复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以 学术交流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容（保密学位论文在解密后遵守此规定） 。 作者签名： 日期： 导师签名： 日期： 太原理工大学硕士研究生学位论文 1 第一章 绪论绪论 1.1 并行计算理论与技术 并行计算（parallel computing）一般是指同时使用多个计算资源同时进行计算以解 决实际问题的过程。这里的计算资源，可以是一台计算机，或者是一台多处理器计算机 上的一颗 cpu， 或者是一台多核计算机上的一个内核。这些计算资源通过高速网络或者 总线相连，它们互相协作，共同完成一个比较庞大的计算任务。 并行计算一直以来被用来快速解决大型且复杂的计算问题，而且常常使用价格昂贵 的大型向量机。随着 cpu 多核化的迅速发展，使用多个“廉价”计算资源取代大型计算 机成为可能。而且随着 pc 领域内的多核化计算日益发展1，pc 领域也越来越需要引入 并行计算技术，以帮助软件开发人员能充分挖掘多核化带来的性能提升。 1.1.1 硬件体系 并行技术从硬件体系上有费林分类2。费林分类有四种：sisd (single instruction single data) ，simd(single instruction multiple data)，misd (multiple instruction single data) ，mimd (multiple instruction multiple data)。misd 在现实中不存在，只是为了分 类的完整性 。 a.sisd(单指令流单数据流) 图 1-1 单指令流单数据流 fig.1-1 single instruction single data instructions processor processor input data output data 太原理工大学硕士研究生学位论文 2 图1-2 单指令流多数据流 fig.1-2 single instruction multiple data c.mimd(多指令流多数据流) 图1-3 多指令流多数据流 fig.1-3 multiple instruction multiple data 1.1.2 软件体系 并行技术从软件抽象层次上可归结为以下几种： （1）并行 api， （2）并行预编译技 术， （3）并行语言技术。并行 api 里最为重要和基础的便是多线程 api3，多线程技术 通过启动多个线程来一起工作，它们之间的协调采用共享内存和锁机制来控制。现在几 乎所有的操作系统都提供了原生多线程 api，而各种高级语言都提供了一定包装后的语 control unit process input data control unit process input data control unit process output data input data output data output data instructions control unit processor instructions output data input data processor processor output data input data output data input data 太原理工大学硕士研究生学位论文 3 言级的 api 类库，比如 c+的 mfc 中就提供了 cthread，cmutex 等包装类4，而 jave 及 dotnet 下也都提供了抽象了的线程对象。而 intel 公司最新出品的 tbb(threading building blocks)56是由 intel 公司针对多核平台开发的一组开源的 c+模板库。该库基 于标准 c+语言编写，因此它可以广泛地被用于任何处理器、任何操作系统以及任何标 准 c+编译器。 另一种并行 api 是基于消息传递的， 最为知名的便是 mpi27。 mpi(message passing interface )是 1994 年 5 月发布的一种消息传递接口。它实际上是一个用于定义消息传递 接口的标准，它有多个实现版本，而且几乎所有的并行计算机厂商都支持这个标准，所 以是目前广泛使用的一个并行编程环境。mpi 的最新扩展为 mpi-2，它提供了超过 200 个函数用来提供消息传递服务，大大简化了并行编程的难度。 最典型的并行预编译技术非openmp28莫属。openmp是由openmp architecture review board牵头提出的，并已被广泛接受的，用于共享内存并行系统的多线程程序设 计的一套指导性注释 （compiler directive） 。 openmp支持的编程语言包括c、 c+和fortran 语言； 而sun compiler， gnu compiler和intel compiler等编译器都支持openmp。 openmp 使用pragma指令来提供并行意图的描述， 程序员只需要使用这些指令来描述自己的意图 即可，由编译器来根据这些意图进行程序的并行化编译，并自动加入同步互斥处理。当 所使用的编译器不支持并行编译，它会忽略这些指令，而使用通常的串行化编译模式。 并行语言则多是专为大型向量机而设计的，比如：向量fortran语言。而号称面向并 发的erlang语言在多核下执行是真正意义上的并行。 而sun公司在07年发布了一直研究已 久的fortress语言，fortress是定位于系统并行机制的研究语言。 1.1.3 多核下的并行计算技术 从戈登摩尔（gordon moore）提出著名的摩尔定律（是指 ic 上可容纳的晶体管数 目，约每隔 18 个月便会增加一倍，性能也将提升一倍）以来，软件行业一直享受着硬 件发展带来的性能增长的好处，即可以通过简单升级硬件来解决某些软件性能问题。 然而，随着 cpu 制作工艺的物理极限的到来，cpu 主频的提高已然不再象以往容 易了。面对更加高昂的开发费用，高能耗，散热这些难题，cpu 开发厂商不得不另辟蹊 径，从提高 cpu 主频转向了多核技术。世界两大 cpu 开发商 intel 和 amd 公司都相继 推出了自己的双核 cpu，而在不远的将来，集成有几十个到几百个内核的 cpu 将成为 主流。 片上多核处理器(cmp)9是在一个芯片上集成多个微处理器核心，从而提高计算能 太原理工大学硕士研究生学位论文 4 力。 每个微处理器核心实质上都是一个相对简单的单线程微处理器或者比较简单的多线 程微处理器，而且这多个核心往往都具有独立的高速缓存和共享的高速缓存，核间通过 高速总线连接在一起，这样多个微处理器核心就可以互相协作，并行地执行程序代码， 因而具有了较高的线程级并行性。 cmp 分为同构和异构两类，同构是指 cmp 内部每个核的结构都是相同的，而异构 则正好相反，是指内部的核结构不是都一样的。 同构 cmp 中的内核一般都是通用处理 器内核，而异构 cmp 中则包含有通用处理器、dsp、asic、媒体处理器，vliw 处理 器等针对通用领域和特定领域不同的内核。 硬件发展模式的改变也对软件开发领域产生了重大影响， 正如 c+程序设计领域屈 指可数的大师之一的 herb sutter 几年前所讲的，“免费的午餐结束了”。传统的程序，大 部分属于串行执行模式，而这种软件享受不到多核的好处，软件由此成为了系统性能的 瓶颈。面对多核的冲击，大部分程序员不得不考虑开始学习并行开发技术，而最常见的 并行开发技术就是多线程编程，但多线程编程的学习曲线比较陡峭，同时又难于调试， 而臭名昭彰的死锁问题更是令大部分开发人员望而生畏。 所以随着多核技术的快步发展，整个软件业也更加急迫需要易于使用、能充分发挥 多核优势的并行计算技术。 1.2 虚拟机技术 1.2.1 虚拟机技术概述 虚拟机是个很宽泛的概念， 通常人们接触到的虚拟机概念有 vmware 那样的硬件模 拟软件，也有 jvm 这样的介于硬件和编译程序之间的软件。这里我们指的是后者。象 vmware 这样的虚拟机是指模拟一台具有完整配置的计算机（包括 cpu、内存、硬盘， 甚至网卡）的系统软件。模拟出来的计算机运行在一个完全隔离的环境中。你可以通过 虚拟机软件在一台物理计算机上模拟出一台或几台虚拟的计算机， 这些虚拟计算机除了 是由软件模拟的以外，其他的方面和真正的计算机表现是一样的，例如你可以给每台虚 拟计算机安装不同的操作系统和应用程序，也可以访问网络资源等等。虽然对于系统管 理员来说，这个虚拟机软件只是运行在物理计算机上的一个应用程序，但是对于在虚拟 机中运行的应用程序而言，它就是一台真正的硬件。 而我们这里的虚拟机更多的是指一台抽象的计算机，它并不需要模拟硬件的细节， 只需要提供一个抽象的虚拟机规范，通常定义一个指令集、和内存管理方案，对于更加 太原理工大学硕士研究生学位论文 5 高级一点的虚拟机还包括：线程模型、元数据定义等。这台虚拟的机器在任何平台上都 提供给编译程序一个的共同的接口。编译程序只需要面向虚拟机，生成虚拟机能够理解 的代码，然后由解释器来将虚拟机代码转换为特定系统的机器码执行。后面非特别指出 的“虚拟机”都是特指这样的虚拟机。 虚拟机的使用由来已久，pascal 语言使用的内嵌解释引擎便是一种采用了叫做 p-code 指令系统的虚拟机，而 basic 语言同样采用了这一技术。因为这种指令的操作码 占用一个字节，以至于后来把这种指令系统统称为字节码。 由于早期的语言往往特性简单，所以相应的虚拟机的结构也比较简单，跟现实中的 机器比较相像，而且指令也比较低级，虚拟机的设计更多体现在解释器的效率优化上， 典型的如 forth 语言的 threading code10技术的使用。 随着 cpu 主频的提高，以及软件开发复杂度的提高，各种高级语言应运而生，而 伴随着这些语言产生了更加通用的虚拟机平台，为了支持高级语言特性，这些虚拟机的 指令集更加高级，性能更加优越。 最为人熟知和广泛使用的通用虚拟机包括 sun 公司推出的虚拟机 jvm 和 microsoft 公司的 dotnet 虚拟机。jvm 当初是专为 java 语言而设计的，随着时间的推移，它也成 为了众多其他高级语言的通用虚拟机。 而 dotnet 虚拟机在设计之初就是作为一个通用虚 拟机平台来设计的，所以它上面支持的高级语言数量之众和 jvm 相比毫不逊色。 另一个定位为通用虚拟机的项目是 perl6 的 parrot 虚拟机，这个虚拟机的出现是因 为 perl 语言原有运行环境已不能适应 perl 的发展， 而 python 语言也出现了这样的问题， 所以两个社区集中力量一起启动了 parrot 项目，parrot 的定位是作为所有动态语言的通 用虚拟机，目前它还在发展之中。 除了通用虚拟机外，还有其他专有语言的虚拟机。 lua5.0 就内置了这样一个专用虚拟机，它简单、小巧、高效而又强大。lua 语言现 在已广泛应用于游戏软件工业，许多游戏都在使用 lua 语言搭建游戏逻辑框架，例如目 前最为经典的网络游戏魔兽世界就大规模的使用了 lua 语言。lua 从一个不知名的 小语种跻身于游戏软件业的主流语言，可以说它的虚拟机机制功不可没。 另一个不得不说的便是 erlang 语言的虚拟机。 erlang 是一种通用的面向并发的编程 语言，它由瑞典电信设备制造商爱立信所辖的 cs-lab 开发，目的是创造一种可以应对 大规模并发活动的编程语言和运行环境。erlang 问世于 1987 年，经过十年的发展，于 1998 年发布开源版本。erlang 是运行于虚拟机的解释性语言。它的虚拟机能处理大量的 轻量级进程的快速切换，这使 erlang 的高效并发成为可能。 太原理工大学硕士研究生学位论文 6 随着多核的普及，虚拟机技术也在向并行技术上靠拢，在 2008 的 javaone 技术大 会上，sun 官方就公布了关于虚拟机和并行机制的项目正在进行中的消息。 1.2.2 虚拟机模型的构成 虚拟机是一台抽象的计算机，如果把整个虚拟机看成一个能处理数据的黑盒子的 话，对外只需要定义一个输入和输出就可以满足计算机的抽象。实际上，通过给虚拟机 设定一套指令系统， 就能满足这个条件。 即把一个指令流输入虚拟机， 虚拟机经过计算， 有选择的执行某些具有输出功能的指令流，这样就实现了计算机的输入和输出。 而且作为黑盒子内部的各个部件也都是围绕着如何实现和优化指令系统而进行运 作。可见，虚拟机的指令系统是整个虚拟机的关键所在，虚拟机的内部结构也随着指令 系统的不同而不同。 一个指令系统主要有三个要素，1）指令的长度。指令的长度可以是固定的，也可以 是不固定的，即根据每个指令的需要不同，设定不同的长度。固定长度的指令系统执行 效率要高一些，而且处理数据对齐也更容易些，但会造成空间的浪费，因为我们指令的 长度必须设定为指令中需要最大空间的指令的长度，而大部分指令不需要那么大空间。 可变长度的指令系统，正好相反，它可以大大节省存储空间，但效率更低一些。2）指 令的编解码方式。一个指令集由有限条指令构成，每条指令必须有一个唯一的编码供系 统识别，另外指令中还需要空间来保存输入数据和输出数据的地址，那么这三个部分在 指令中怎么安排空间，设定几个输入，几个输出，就是编解码要解决的。3）内存地址 的访问方式。如果一个虚拟机是 32 位的，那么它的内存地址应当是 32 位的，如果我们 直接使用 32bit 的地址来描述输入变量和输出变量，那么指令长度将会变得很大。实际 上，我们大部分情况下都是设定一块空间，按照线性关系，给这个空间中的每个 32 位 变量一个唯一的编码，我们的大部分指令都是以这个空间内的变量作为输入和输出（这 些变量被叫做寄存器） ，那么我们对这块空间的编码长度就要远远地小于 32 位，这时的 虚拟机叫做寄存器式虚拟机。如果设定的这块空间没有进行编码，而是作为一个计算栈 来使用，那么这时的虚拟机就是栈式虚拟机。 实际上，指令系统的这几个要素是互相联系，互相制约的。比如，栈式虚拟机，计 算指令就不需要在指令中显式地指出输入变量地址和输出变量地址， 那么它的指令长度 自然会更加短小，如图 1-4 所示。 太原理工大学硕士研究生学位论文 7 图1-4 栈式虚拟机加法指令的执行过程 fig.1-4 process of implementation about .add instruction 1.2.3 几种经典虚拟机 目前，广泛使用的虚拟机主要有java虚拟机、dotnet虚拟机、erlang虚拟机、lua虚 拟机等。下面简单介绍一下这几种虚拟机的特点。 （一）java 虚拟机1112。java 语言的一个非常重要的特点就是与平台的无关性，而 使用 java 虚拟机是实现这一特点的关键。java 虚拟机由五个部分组成:一个指令集、一 组寄存器、一个栈、一个堆(可垃圾回收)、一个方法区域。java 虚拟机规范针对这五部 分作出一定的要求,但不会限制死它的实现细节，所以在不同的软硬件平台下，java 虚拟 机的实现不会完全相同。 1.java 指令集 java 虚拟机的指令集拥有大约 248 个指令。java 虚拟机属于栈式虚拟机，所以指令 集中的许多指令都非常短小，往往只有操作码，没有操作数，操作码只占用一个字节， 所以 java 的指令也被称为字节码。 java 虚拟机是依赖于指令的操作码来进行解释执行的， 虚拟机执行引擎首先加载一 条指令，根据这条指令的操作码，来确定它后面是否有操作数，有几个操作数，然后解 释执行，完成后加载下一条指令，如果是跳转类指令的话，会根据虚拟机的计算结果来 确定下一条指令的地址，如果是其他指令，则当前指令之后的第一条指令被作为下一条 指令来执行。虚拟机的解释引擎核心的执行过程如下: for(;程序未结束;) 取下一条指令; switch（操作码） .push 1 .push 2 .add 1 .push 1 .push 2 .add 1 2 .push 1 .push 2 .add 3 栈顶 栈顶 栈顶 太原理工大学硕士研究生学位论文 8 case 操作码 1：解释此指令；break； case 操作码 2：解释此指令；break； default：异常处理； 2.寄存器 java 虚拟机中的寄存器用来保存虚拟机的运行状态,是物理 cpu 中寄存器的一种抽 象。java 虚拟机的寄存器共有四种:1）pc 寄存器，是 java 程序计数器，保存着下一条 要执行的指令的地址，2）optop 寄存器，保存着操作栈顶端的地址，3）frame 寄存 器，保存着当前方法的执行环境的地址，4）vars 寄存器，保存着当前方法局部变量 区的起始地址。这些寄存器都是 32 位的。 由于 java 虚拟机是栈式虚拟机,所以在 java 虚拟机中不包含用于存储计算变量的通 用寄存器。以上寄存器都是保存状态的专用寄存器。 3.栈 在 java 虚拟机的执行过程中，每调用一个函数执行，会在栈上建立一个栈帧，一个 栈帧中包括三个区域:局部变量区、运行环境区、操作数区。 (1)局部变量区。 每一个 java 方法都使用一个固定大小的局部变量集，这些变量在 内存中线性存储，占用一个固定大小的内存空间。vars 寄存器中存放这这块内存区域 的首地址，访问这些局部变量集中的某个变量，只需要给出一个相对于 vars 寄存器中 的地址的偏移量。局部变量都是 32 位的，但是长整数和双精度浮点数实际上占据了两 个局部变量的空间,访问这些类型的变量时， 必须按照它所占的第一个局部变量的索引号 来寻址。而且在虚拟机规范中，对于 64 位的数据也没有强制要 64 位对齐。因为 java 虚拟机中的计算指令的操作数都存放在栈中，所以在需要以局部变量作为操作数时，必 须把局部变量加载到栈中， 因此 java 虚拟机提供了把局部变量中的值装载到操作栈的指 令, 也提供了把操作栈中的值写入局部变量的指令。 (2)运行环境区。 在运行环境中保存着用于动态链接、方法返回以及异常处理的信 息。用于动态链接的信息包括包括一个引用符号表，在一个 class 文件中，调用一个方 法是以符号的形式描述的，当调用方法时，虚拟机引擎会加载相应的 class 文件，并把 相应的符号解析成真正的内存地址。动态链接的方式使得此类与其它相关类相互独立， 只要相关类已经存在的函数的签名没有变化，就不会影响此类。 太原理工大学硕士研究生学位论文 9 另外，在一个方法调用另一个方法时，运行环境会保存调用时的指令地址，在调用 正常返回后，系统会恢复到调用指令之后的下一条指令，继续执行。而如果在一个方法 执行过程中发生了异常，那么就会用到异常处理。 在运行环境中，专门保存着方法可以处理的异常信息，及异常处理程序的入口，也 就是说当异常发生后，虚拟机会寻找与异常相匹配的 catch 块入口地址，并转到 catch 块内部的第一条指令开始执行。 (3)操作数栈。 在 java 虚拟机中， 操作数栈扮演着寄存器的角色， 并且它是 32 位的。 它既被用于存放参与运算的输入数据和输出数据， 也被用于存放函数调用时的参数和返 回值与返回地址。例如：在 java 虚拟机中，加法的操作过程如下：a.把加数压入栈中， b.把被加数压入栈中，c.执行加法指令，此指令把栈顶的数和栈顶之下的另一个数相加， 并把它们弹出栈外，再把计算结果压入栈顶。 在 java 虚拟机中，大部分指令都有类型限制，也可以说，对于不同的数据类型， 都有一个只用于此数据类型的指令子集。例如加法操作，针对于不同的数据类型，就有 好几个版本。大部分数据类型都小于或等于 32 位，可以放置在栈内的一个位置，而对 于长度大于 32 位的数据，可以占用更多的位置。例如 double 类型，它会占用栈中两个 位置。 (4)堆。 java 中的堆是一块可以动态分配的内存区域,类的实例(对象)的空间就是在堆 中分配的。java 虚拟机中的堆具有无用单元收集能力，当程序中动态分配的内存不再使 用时，它会自动回收，这减轻了程序员进行内存管理的压力，也降低了因为内存泄露而 造成的风险。 java 虚拟机规范中对无用单元收集算法不做硬性要求,而由虚拟机实现者根 据系统的需求使用合适的算法。 (5)方法区。方法区存放的实际上是类信息，包括，类的元数据，方法的指令序列， 常量池等。可以认为方法区是 class 文件中的信息在内存中存放的区域。 （二）dotnet 虚拟机。跟 java 虚拟机相比，dotnet13虚拟机更多的是一个抽象机， 因为它实际上没有真正的解释器，它的后端是一个 jit 编译器，当程序执行的时候，实 际上是由 jit 编译器动态把中间代码编译成机器码来执行。 dotnet 虚拟机同样也定义了一套字节码，称之为 msil14（微软中间语言），这套 指令和 jvm 一样是基于堆栈的，另外它为了支持多种高级语言，还制定了一套类型规 范，称之为通用类型系统。 dotnet虚拟机更多的是以一种整体框架的概念来描述这个抽象机。dotnet提供了一 个运行时环境，叫做公用语言运行时15（common language runtime），是一种执行环 太原理工大学硕士研究生学位论文 10 境，它支持相对较多的数据类型和语言特性。它还为msil的执行提供支撑，是一种可 控的执行环境。clr是这个框架中跟虚拟机概念最为接近的部件。clr是 .net framework 的基础。在dotnet平台中，clr扮演着一个全能的管理者角色，它提供内存 管理、 线程管理以及远程处理等核心服务， 并且还强制实施严格的类型安全检查。 在clr 环境内执行的代码称为托管代码，反之则称为非托管代码。 （三）lua虚拟机 lua 语言是一门广泛应用于游戏工业界的动态脚本语言。它的虚拟机小巧、高效。 lua 虚拟机是第一个被广泛采用的寄存器式虚拟机，寄存器式虚拟机要比堆栈式寄存器 更复杂些， 但却也更加高效， 因为它能避免堆栈式虚拟机大量的压栈和出栈操作16。 lua 唯一的数据表述方式便是关联表，当关联表的 key 类型为整型类型时，lua 虚拟机会在 内部使用真正的数组来优化， 从而提高执行效率17。 另外 lua 虚拟机支持动态数据类型， 也就是说，变量是没有类型的，类型仅和值绑定，这是通过给变量增加一额外的类型标 签来描述数据类型。 lua 虚拟机设计之初，就是定位于小巧简单，可移植的，可嵌入的，高效的脚本运 行平台。实际上 lua 语言和 lua 虚拟机是一体的，整个 lua 是以标准 c 编写而成的， 为了保证 lua 可以在各种不同的 c 编译器及平台上顺利编译和运行， lua 不能使用一些 依托于特定的编译器或者平台的编程技巧，例如被称作为 direct threaded code 的技巧。 随着 lua 在不同平台（包括一些 64 位平台和一些 16 位平台）上的各种编译器下顺利 通过编译，其可移植性多年来持续稳定17。 （四）erlang 虚拟机 erlang 最初是由爱立信设计的，基于这家公司的行业背景因素， erlang 从一开始就是针对通讯领域应用设计的（比如用于开发交换机内部的交换协议程 序等），因此非常适合于构建分布式，并发计算系统18。使用 erlang 编写出的应用程 序通常由成千上万的轻量级进程组成，这些进程之间通过消息传递相互通讯。而这种轻 量级的进程间上下文切换的代价很小，比起线程切换要高效得多了。使用 erlang 来编写 分布式应用要简单的多，因为它的分布式机制是透明的：对于程序来说并不知道自己是 在分布式运行。 erlang 运行时环境是一个虚拟机，有点像 java 虚拟机，这样代码一经编译，同样可 以随处运行。它的运行时系统甚至允许代码在不被中断的情况下更新。另外如果你需要 更高效的话，字节代码也可以编译成本地代码运行。 erlang 语言号称是面向并发的语言，同时它还是一种函数式语言。它能支持大量并 发，同时还具有系统热部署能力。这都需要有一个强有力的虚拟机的支撑，而它的虚拟 太原理工大学硕士研究生学位论文 11 机能非常好地支持它的语言特性，比如它内置了轻量级进程模型，使得 erlang 能轻易创 建多达几百 m 的进程，而高效的进程切换机制使得 erlang 能应付大量并发。 函数式语言来源于 lambda 演算理论19，lambda 演算形式系统已被证明和图灵机等 价，也就是说我们现有的机器能做到的事情，通过 lambda 演算形式系统同样能表达出 来， 这就为函数式语言奠定了实现的理论基础。 第一个公认的函数式语言是 lisp 语言20， 而后又出现了诸如 ml 语言，haskell 语言2223，ocaml 语言等众多函数式语言,微软公 司推出的新的 f#语言就是一种 ml 语言的方言。函数式语言主要的特点就是引用透明 性，这就保证了它没有副作用。而它可以同时从两个方向上规约，又使它是天然的可以 并行执行的语言1921。 随着多核技术的普及， 函数式语言被业界认为是潜在的有力的并 行解决方案之一。 而由于函数式语言的理论基础是 lambda 演算，跟现实中的机器体系结构相差太远， 所以就出现了多种抽象机技术，用来作为函数式语言和真实机器的中间抽象层。最典型 的就是 secd machine(stack environment code dump)24以及 g-machine25。 1.3 论文的研究内容和组织结构 本文的研究目的是以多核技术的快速发展为背景，用虚拟机的方法，去构建一个易 用、高效，可扩展的并行平台。此平台包括虚拟机以及虚拟机之上的并行脚本语言。 论文首先介绍了并行计算的硬件体系和软件体系。在硬件体系中，主要介绍了费林 分类之下的三种硬件结构。 而在软件体系下， 主要介绍了当前用于并行计算的软件平台， 包括并行 api、并行预编译技术以及并行语言技术，还介绍了多核体系的特点，和在多 核技术快速发展的大背景下对于并行软件技术的迫切需要。 接着介绍了虚拟机技术。包括虚拟机的概念，虚拟机的构成，以及对多个经典虚拟 机的结构和特点做了详细介绍。这些虚拟机包括 java 虚拟机、dotnet 虚拟机、lua 虚拟 机以及 erlang 虚拟机,这些都是当前软件业正在广泛使用的成熟的产品。象 java 虚拟机 和 dotnet 虚拟机都是通用的虚拟机，被广泛使用于大型网站平台、商业系统的构建中。 lua 虚拟机主要用于游戏业中，而 erlang 虚拟机被广泛应用在电信业。 然后针对多核化的趋势，提出了一个基于多核的并行虚拟机模型sapvm，详细 说明了该虚拟机模型的结构，包括指令系统、内存管理以及并行机制。另外详细讲解了 用于构建 sapvm 的几种关键设计和技术，包括底层的多线程间的通讯、基于该虚拟机 的数据结构、异常的处理方案和面向对象的内部表示等等。 太原理工大学硕士研究生学位论文 12 最后还提出了针对该虚拟机设计的并行脚本语言 windbell，阐述了 windbell 的语法 和高级语义。 论文总共分为五章，具体安排如下： 第一章，绪论。介绍了并行计算的硬件体系和软件体系，引入了多核化的概念，同 时阐述了针对多核化技术趋势的并行软件平台的建设的迫切性和重要性。 第二章， 基于多核的并行虚拟机模型sapvm。提出了一个面向多核的并行虚拟机 模型。介绍了该模型的结构和原理。 第三章，sapvm 的实现与优化。介绍了用于在实现 sapvm 中的关键技术和优化 方法。 第四章，基于 sapvm 的并行脚本语言。面向 sapvm，提出了一个具有高级语义 的并行脚本语言，详细介绍了该语言的语法和语义。 第五章，总结和展望。 太原理工大学硕士研究生学位论文 13 第二章二章 基于多核的并行虚拟机模型基于多核的并行虚拟机模型sapvm 2.1 sapvm 概述 目前，大部分被广泛使用的虚拟机模型，都是针对单核系统设计的。这些虚拟机不 管是指令系统，还是内存管理，都没有针对多核进行设计优化。它们对于并行的支持基 本上都是靠提供一个线程库来进行。 根据它们指令系统的不同，又分为两大类：1）栈式虚拟机，2）寄存器虚拟机。这 两种虚拟机各有优缺点，栈式虚拟机的指令比较短小，因为它的操作数基本都在栈中， 所以大部分指令都不需要指出操作数的地址，而只使用一个字节。而且，因为栈的操作 简单，不象寄存器虚拟机那样，需要编译程序去考虑寄存器的分配，从而大大简化了编 译器的开发难度。但栈式虚拟机因为需要频繁的入栈和出栈操作，效率会明显降低。寄 存器虚拟机则同栈式虚拟机的情况恰恰相反，它执行效率较高，但编译复杂。 在实际的使用当中， 这两种虚拟机都有相应的产品。 比如 java 虚拟机的各种实现基 本上都属于栈式虚拟机，微软的 dotnet 虚拟机也属于栈式虚拟机，而 parrot 虚拟机和 lua 虚拟机都属于寄存器虚拟机。 象 java 和 dotnet 都提供了线程类库， 它们提供了一组类来抽象线程及其同步操作。 但这些对并行的支持，并没有体现出虚拟机的优越性，它们没有提供一个更好的并行操 作接口，而是沿用了传统编程模型中最为原生的线程方法，或者仅仅是对这种原生方法 的一个简单的面向对象包装而已。 采用多线程进行并行程序的开发，难度是比较大的，首先程序的编写者需要分清楚 程序哪部分是并行的，哪部分是串行的，把并行的部分分配到相应的线程上，其次要考 虑清楚哪些资源需要进行同步，在访问这些资源的时候，都要有同步操作，最后还要避 免死锁的发生，另外多线程程序的调试相对于单线程程序要困难的多，因此采用线程来 开发一个稍微复杂点的并行程序，都是一个相当大的挑战，需要程序员拥有足够多的经 验和技巧，而对于相当大部分的程序员来说，是不具备这些经验和技巧的，所以在传统 编程领域，复杂的多线程程序的编写，是一个相对高级的议题。 在多核 pc 普及之前，虽然这种多线程的开发技巧是难于掌握的，但这并不是一个 多大的问题，对于大部分程序员，他们并不需要掌握这种技巧。因为对于大部分单核下 的程序，多线程下能完成的工作，都可以使用单线程来完成，而且效率更高，只是在需 太原理工大学硕士研究生学位论文 14 要高响应，和并发响应的时候才需要使用多线程。但是在多核系统下，多线程可以分配 到多个 cpu 核上运行，所以会得到更高的执行效率，如果还象以前一样只使用单线程来 编写程序，就得不到多核的好处，这就迫使在多核环境中的程序开发人员不得不学习多 线程开发技能，然而上面已经提到这种开发方式是具有相当大的难度的，实际上这阻碍 了多核技术的使用。 针对多线程开发模式的不足，本文从降低并行程序难度和提高可扩展性出发，提出 了一种可扩展的并行虚拟机模型sapvm（self adapting parellel virtual machine） 。 在介绍 sapvm 之前，我们先介绍两个重要的定理：1）阿姆达尔定律 2）古斯塔夫 森定律 。 阿姆达尔定律 26： s=1/(a+(1-a)/n) s：加速比 a：串行程序所占的比例 n：并行处理结点个数 当 n时，极限加速比 s 1a，这也就是加速比的上限。 这个定律描述了加速比受制于一个程序中的串行部分， 即只要当一个程序中拥有串 行成分，那么当处理节点达到一定数量后，不管再增加多少个处理节点，都不会提高此 程序的加速比。无疑阿姆达尔定律是悲观的，因为只要我们程序中的串行比例一定，加 速比的提升只在一定数目的处理节点数目下起作用，超过这个数目后，加速比不会再提 高了，但实际上这个定律有个前提，就是认为计算任务的规模是一定的，那么当去掉这 个前提就产生了另一个定律：古斯塔夫森定律。 古斯塔夫森定律 27： s= n + (1-n)*a s：加速比 a：串行程序所占的比例 n：并行处理结点个数 从这个定律发现，加速比和并行处理的结点数成正比。也就是说，我们可以通过不 断地扩大计算规模而获得更高的加速比，对于多核技术，无疑这是个好消息。 sapvm 从设计之初就是针对多核的，所以它内部结构可以充分体现多核的优越性。 太原理工大学硕士研究生学位论文 15 sapvm 内部以计算节点来抽象 cpu 内核，每个计算节点运行在一个线程之上。所以当计 算节点数与 cpu 内核相等时，实际上这些计算节点是在真正的并行执行。每个计算节点 内部拥有一个轻量级进程队列（本文中将以“进程”简称，操作系统中的进程在本文中 被称作“操作系统进程” ，以和本文中的轻量级进程进行区分） ，每个进程内部有一个消 息队列，计算节点遍历整个进程队列，然后处理每个进程队列的第一个消息，处理完的 消息会被返回给发送消息的进程。 实际上 sapvm 里的进程跟传统进程概念是有很大区别的，sapvm 里的进程是对象被 激活时处理其消息所需的最小环境，即 sapvm 里进程包含：1）对象数据 2）类数据 3） 待处理消息队列。当一个对象接收到一个或多个消息时，系统会建立一个进程，然后把 这个进程和对象绑定到一起，这个对象便被激活；当待处理消息全部被处理完后，这个 对象和进程解除绑定，对象重新回到睡眠状态。引入这一机制的原因是，sapvm 里面每 个对象都处于不同的进程空间当中，如果一开始就为