目录
Abstract
Key words
摘要
关键词
1动机与目标
2系统设计
3实现
4 基于脚本的通用Master模型
5实例分析
参考文献
【Abstract 】This paper proposes a lightweight metacomputing scheme,which supports the rapid implementation of distributed parallel computing,utilizing the platform-independence of Java and http://www.1daixie.com/ Master-worker computation model.A script-based generic Master model is also devised.It alsodiscusses system infrastructure and implementation with a simple example of matrix multiplication and finally gives a conclusion for it.
【Key words】Metacomputing； Master-worker ；Java
摘要：提出了一种轻量级的元计算方案，利用Java的 平台无关性以及Master-worker计算模型，支持迅速实现分布并行计算，并设计了一种基于脚本的通用Master模型。描述了该方案总体框架，简要介绍了利用该方案实现计算矩阵乘积的例子，最后作了分析与总结。
关键词：元计算；Master-worker ；Java
大规模的科学计算往往需要高性能的超级计算机才能完成，而随着硬件技术的发展与网络的普及以及带宽的扩展，越来越多的个人计算机构成了庞大的网络。这些个人计算机拥有一定的计算能力，而且大部分时间处于空闲或轻载的状态。如何有效利用这些闲置的计算资源，将其整合成高性能的计算网络来满足科学计算的需要，成为元计算(metacom-puting)或称Internet Computing 、Global Computing的重要研究课题。
目前元计算项目如Legion 、Globus等都在元计算的框架方面做了大量工作，集中于算法、调度与通信等方面，目标是提出高效率的计算模型。但计算资源的使用者要深入理解并行及分布编程模型，学习一套系统所提供的复杂的API；对计算资源的提供者而言，加入到元计算中往往不是完全自动的,也没有明确的安全机制,同时系统管理的开销也较大。
本文提出并研究了一种利用Java的 平台无关性与Web的易用性而实现的轻量级元计算方案，分析了其目标、框架结构、计算模型及实现，提出一种基于脚本的通用Master模型，给出了一个计算矩阵乘积的实例。并与类似系统作了比较分析。
1动机与目标
元计算与传统的并行计算有很多不同之处，其中最主要有两点：(1)Dynamic Availability(动态可用性)。可用的计算资源的数量，与分派到某一节点的计算量，都可能随时间而变化。参与者可以随时加入或离开(或崩溃)而无须通知。(2)Heterogeneity(异构性)。计算资源的物理特性如体系结构、操作系统、处理器速度、内存容量各不相同。
我们提出的轻量级元计算方案，其设计目标包括：
可存取性(Accessibility)：对于计算资源的提供者，应提供简单友好的界面，以及方便的、平台无关的资源共享机制，同时保障提供者的安全。
可编程性(Programmability)：对于一个计算应用,应提供简单的计算模型，使得开发者能便捷地实现一个分布并行的计算应用，无须过多关注资源位置、调度、容错等细节。
2系统设计
2.1计算模型
在元计算中，往往需要将一个计算任务进行分割并分发到多个节点执行，因此需要采用分布并行的计算模型，来开发计算应用或对原串行化的应用进行改写。
Master-worker模 型，又称Task-farmer模型。对每一个任务，只存在一个Master节点，负责任务初始化、子任务的分割、分发、与Worker节点通信、结果收集、汇总。有多个Worker节点,分别执行不同的子任务，并将结果返回给Master 节点，它由Master 进行控制，只与Master间进行通信，Worker之间没有直接的通信。
该模型适用于子任务之间没有或只有弱约束关系的计算应用，对于参数化的应用，开发者可以简单地将原数据集划分成互不相交的子集，不同的子任务执行相同的代码，对不同的数据子集进行运算，子任务间没有约束关系。将原串行化应用改写为分布并行版本，工作量很小，也无须分布式编程经验及知识。由于子任务都是独立完成，没有交互，避免了在元计算中常见的，由通信及同步带来的显著性能下降。
2.2 基于Java 与基于Web
Web 随着Internet的 迅速普及而具有广泛性，同时Web具有良好的人机界面，因此适合作为计算资源提供者的入口。
Java是一种平台无关的面向对象编程语言，个人计算机上通常装有Windows 或Linux两种操作系统，它们都能方便地支持Java ，便于计算资源的提供者进行开发。Java有两种形式：Java Application与 Java applet,前者在JRE(Java RuntimeEnvironment)中运行，后者在支持JVM(Java Virtue Machine)的浏览器中执行。
Java applet是一种自动下载到客户端运行的小程序，它具有一系列被称作sandbox(沙箱)的安全机制，包括：不能监听任何网络端口；不能与除宿主机外的任何主机建立连接；不能访问本地文件系统等。
由于Java的 平台无关性和Java applet的易用性与安全机制，分发、部署、维护简单，本方案采用Java applet形式分发代码。计算资源的提供者，只需要有一个支持JVM的浏览器，访问特定的页面，包含了计算应用的Java applet就自动下载到提供者机器上运行，执行计算任务，返回计算结果。整个过程完全自动，无须人工干预，免去了程序下载、安装、配置、执行，甚至是手动提交运行结果的复杂过程。Java applet的沙箱安全机制，能防止恶意代码破坏客户机，使提供者能安全地共享计算资源。
3实现
3.1 Master-worker的实现
计算资源的提供者是Worker，它是以分发到客户端、由浏览器自动执行的Java applet形式实现的。客户端只需简单地访问特定的URL ，就会在客户端生成一个Worker，来执行相应的子任务，并自动与Master通信，完成计算，返回计算结果。
计算资源的使用者是Master,它是一台提供HTTP服务的节点，以满足客户端通过访问特定页面实现计算的需要。Master 驻留在服务器上，根据客户端的请求，分发Javaapplet形 式的Worker代码，处理资源访问请求，收集计算结果并汇总，而且可以扩充调度、容错等机制。
Master可 以以CGI/Servlet/Java application形 式存在。CGI是平台相关的,有一定的响应延迟，而且会带来一定的安全隐患；Java application需要监听特定的端口，无法跨越防火墙，而且有相当的与HTTP 服务器整合的工作量。Servlet是平台无关的，其多线程特性提高了效率，且与HTTP服务器紧密整合，通过HTTP 服务器的80端口处理客户端请求，不受防火墙安全限制，其缺点是Servlet模块安装所带来的开销。我们采用Servlet来 实现Master。
3.2远程文件资源访问
在实际计算应用中，算法与数据往往是分离的，而且根据所采用的Master-worker 模型，各Worker执行的是同样的程序代码，不同的只是所处理的数据集。而沙箱机制禁止Javaapplet访问本地文件系统，因此必须提供远程文件访问方法，以使Java applet能访问位于服务器上的数据文件。
动态生成页面：Servlet是一种动态页面技术，能根据一定的策略，动态生成各不相同的HTML 文件。而Java applet能从其页面的PARAM标签中获得程序执行所需的参数，因此可以通过针对不同的Worker,动态生成带有不同PARAM标签的HTML， 嵌在该HTML文 件中的Java applet就能根据参数的不同，执行不同的子任务。但是这种方法只适用于小数据量的传输。
HTTP1.1 与被动FTP：在HTTP1.1 中，新增了POST等命令，可以读、写位于服务器上的文件。另外，FTP标准模式需要客户端被动打开端口，是不适合在Java applet中使用的，但FTP的被动模式支持服务器到服务器的文件传输，不需要被动打开端口，因此也可以在Java applet中模拟被动模式，来实现对位于服务器上的文件的访问。
我们用输入输出流来执行HTTP 或FTP请求并解释之。
块传输模式：子任务往往是针对特定的数据子集的，因此可以采用增量式的文件访问策略，即只访问数据文件中的特定部分，减少网络开销。HTTP1.1与 FTP都支持块传输模式，允许设定访问文件中的特定区段，可以用来实现增量式的数据访问，以下是部分代码，它是与具体应用无关的，可以通用。用输入输出流来执行HTTP 或FTP请求并接收应答。下面是一个部分存取远程文件的例子。
public void getPartialFile(Socket clientSocket,String file,byte
[Maxsize]data,int firstBytePos,int lastBytePos)throws
HTTPException{
try{//data check is omitted in this demo file
DataOutputStream out=new DataOutputStream(clientSocket.
getO-utputStream());
DataInputStream in=new DataInputStream(clientSocket.
getInput-Stream());
out.writeBytes("GET"+file+"/HTTP/1.1\r\n");
out.writeBytes("Host:"+host+"\r\n");
out.writeBytes("Accept:*/*\r\n");
out.writeBytes("Range:bytes="+firstBytePos.toString()+toString+"-
"+lastBytePos.toString()+"\r\n\r\n");
String response;
while((response=in.readline())!=null&&!response.equals(""));
cnt=in.read(data);
}catch(Exception e){
throw new HTTPException("Error:"+e.GetMessage());
}
}
4 基于脚本的通用Master模型
将Master与 具体应用分离：Master的主要职责是任务分割、分发、调度、监控、结果收集。这几部分任务都是与具体应用无关的，因此我们设计一个基于脚本的通用的Master,与任务相关的信息包含在由具体应用开发者提供的脚本文件中。脚本文件包括以下信息：子任务数目，子任务程序文件名，子任务所需访问的文件名，PARAM标签参数生成策略。将Master与具体应用分离，使得开发与部署更为简单。Master可以关注调度、容错等问题。
调度策略：采用简单的静态的Eager调度策略,维护一个空闲节点队列，将子任务分发给最先完成计算任务的节点。
容错：提供简单的容错机制，即若有节点失效，简单地将其未完成的任务分发给其它空闲节点即可。
可伸缩性：严格来讲Master-worker模型并不具有可伸缩性，因为子任务的数目是确定的。但是针对一些特定算法，仍然可以通过程序结构上的一些方法来实现有限的可伸缩性。以下是一个将二重循环并行化的例子：
…
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
a[i][j]+=b[i][j];
…
改写后的分布并行版本：
for(int i=S;i<m;i+=R)
for(int j=0;j<n;j++)
a[i][j]+=b[i][j];
S 和P 是Java applet 的参数，针对一个计算任务，P是并行粒度，即子任务个数；S 是各子任务ID，标识针对不同的数据子集的操作。
5实例分析
我们在PIII700、 128MB内存的个人计算机上实现了一个原型系统，系统中有两种操作系统：Windows 与Linux,其中服务器上用Apache+Tomcat 提供HTTP 与Servlet服务。客户机上是IE5.5或 Netscape Navigator4.2浏览器。
我们开发了一个计算矩阵乘积的实验程序。实验结果表明，对于矩阵相乘这种算法而言，我们的方案能随着节点数目的增加，获得近似线性的加速。
6相关工作及总结
Bayanihan[1]与Javelin[2]也是基于Java的元计算系统，但它们都采用了复杂的RMI 技术来实现Worker 与Master间的通信，而我们的方案是基于Servlet与 HTTP 或FTP的，轻量、易于实现，提出的基于脚本的通用Master方案也有助于将具体应用与通信、调度、容错等细节分离，减少开发者的工作量。针对现有计算应用而言具有一定的实用价值。
参考文献
1 Sarmenta L F G.Volunteer Computing[Ph.D.Thesis].MassachusettsInstitute of Technology,2001-03
2 Cappello P.Javelin:Internet-based Parallel Computing Using Java.Proc.of ACM Workshop on Java for Science and EngineeringComputation,1997-06
3 HTTP1.1.http://www.ietf.org/rfc/rfc2616.txt,1999