基于模糊聚类的集群研究和实现

VIP免费

3.0 高德中 2024-11-19 5 4 540.21KB 56 页 15积分

侵权投诉

摘要

随着 Internet 的发展，出现了大量计算机在绝大多数时间都是空闲的情况，

这是巨大的浪费，如何减少这样的浪费，充分利用现有的计算机资源是我们追求

的目标。而有效地组织现有的计算机是比较困难的，网络技术为此提供了一个很

好的方法。多集群网络是利用现有局域网内的计算机，把这些计算机划分组成多

个并行装置。由于每个节点计算机的计算能力不同，如何有效的组织这些计算机

是个难点。本文利用模糊聚类的方法，研究多个计算机计算节点聚类，同时研究

负载平衡问题，使最后的聚类结果很好的实现负载平衡。

在多个计算机构成的网格环境下，为了提高多机群网格的异构资源的利用率，

提出了一个数据负载均衡模型。该模型涉及的关键技术包括：TCP/IP 协议，Java

多线程技术，Socket 通信技术，并行程序设计技术，计算机集群及基于消息传递

的并行程序编程技术，模糊数学等。

在多个计算机构成的网格环境下，为了提高多机群网格的异构资源的利用率，

提出了一个基于模糊聚类的集群模型。研究的工作主要包括：1.构建异构的计算

机集群。2.确定计算机的评价参数，主要根据计算机的计算能力，存储能力，通

信能力，网络性能等因素来表示计算机的综合性能，再按照该综合性能划分计算

机集群，从而实现计算机集群内的计算机的综合性能相近，进而达到动态负载平

衡的目的。3.模糊聚类算法：应用模糊数学中的模糊相似矩阵理论对计算机分类

并在计算各个计算机的隶属度的过程中，创新的提到利用对计算机各个属性的权

值来影响聚类，从而使聚类更加灵活的适应于最后的并行任务。4.针对聚类的结

果进行相关试验以及相关分析。

关键词：计算机集群模糊聚类负载平衡并行计算

ABSTRACT

With broad development of Internet, the most computers are idle on most time. Our

aim is to end the obvious and tremendous waste. So how to manage and use it

effectually is an important task for people. Network technology provides strong support

for parallel computing . Utilizing mutiple computer clusters to construct mutiple

clusters grid which actualize parallel computing is an effective approach. And then it is

a tough problem how to apart and management them. The paper gives a way to solve it,

whose main purpose is to separate the computers into different groups in which the

computers are the most similar by the calculating following the Fuzzy theory. The value

of the weighted value is modifiable, which following the characters of the computer can

affect the Fuzzy set as you want.Because of heterogeneous characteristic of node of

mutiple clusters,its capability imbalance,it makes more difficult to realize parallel

computing. Load balancing is one of hot research questions.

To improve heterogeneous resource’s using efficiency in multi-cluster grid that is

constructed by multi-computers,a data load balance model based Fuzzy is proposed.The

key technology about the model are including TCP/IP protocol, multiple thread

technology, Socket communication technology, Parallel Computing , Cluster and

MPI(Message Passing Interface),and Fuzzy Mathematics and so on.

Research work are including as follows: 1. The construction of the Clusters which

contains heterogeneous computers. 2.Find out the characters of the computer in which

how to describe the computer. The evaluating parameters are fixed on which are used to

computing ,storage and communication, the net which the computer belong to, then the

cluster partition is in accordance with the integrative capability, and the purpose of load

balance can be achieved. 3. Fuzzy Cluster Algorithm: the partition of the cluster follow

the Principle of Fuzzy Similarity Matrix. The algorithm take in the weigh following

each character to mark the different value when to calculate the degree of the similarity

of the computers. 4.The experimens are about the algorithm and the interrelated

analyses.

Key Word：Cluster , Fuzzy , Load Balancing , Parallel Computing

目  录
摘要
ABSTRACT
第一章  绪论.....................................................................................................................1
第二章  相关技术概述.....................................................................................................4
§2.1  可扩展的并行计算机体系结构.......................................................................4
§2.2  机群技术...........................................................................................................7
§2.3  网格技术...........................................................................................................9
§2.4  负载平衡.........................................................................................................12
§2.5  并行计算.........................................................................................................13
第三章  主要关键技术...................................................................................................17
§3.1  TCP/IP 协议....................................................................................................................17
§3.2  多线程技术.....................................................................................................19
§3.3  Socket 通信技术.............................................................................................22
§3.4  MPI..................................................................................................................26
§3.4.1  MPI 简介..............................................................................................26
§3.4.2  MPI 核心函数......................................................................................27
第四章  模糊聚类算法及实现.......................................................................................32
§4.1  模糊聚类算法.................................................................................................32
§4.1.1  算法相关背景.......................................................................................32
§4.1.2  数学模型...............................................................................................32
§4.1.3  算法有效性证明.................................................................................................32
§4.2  模糊聚类的算法实现.....................................................................................39
§4.2.1  类的设计及函数说明...........................................................................39
§4.2.2  代码实现...............................................................................................40
§4.3  模拟实验.........................................................................................................................50
第五章  试验及其分析...................................................................................................53
§5.1  试验环境.........................................................................................................53
§5.2  试验步骤.........................................................................................................53
§5.2.1  聚类计算机...........................................................................................53
§5.2.2  分配任务...............................................................................................54
§5.3  实验结果..........................................................................................................................55
第六章  结束语...............................................................................................................62
参考文献.........................................................................................................................63

第一章绪论

现实情况中，绝大多数时间里机器是空闲的，造成了计算能力的很大浪费，

在Windows 下用任务管理器或其他的Linux 平台的工具（例如 top，xload）观察

CPU，会看到CPU 的使用率常见在 1～2%。事实上，如果有更多的计算机，这种浪

费会加剧，在一个有 300 台计算机的部门里，CPU 的空闲率是惊人的。然而这些部

门还是需要强大的服务器用来编译或模拟计算，这样的情况还会加剧，不止需要

一台，因为随着用户的增加，即使是 8个CPU 的服务器，满负荷时也不能把任务

交给另外的空闲服务器，因为用户很少会改变习惯去登陆另外一台服务器。如果

能利用现有的计算资源，把空闲的 CPU 利用起来，或者能让服务器智能的迁移负

荷，这会是一件很开心的事情[1][2]。

随着串行时代辉煌的夕阳，不久就会迎来并行时代的朝霞[1][2]。随着社会的进

步，生活方式的改变我们对计算能力的要求空前的强大。无论硬件如何发展，似

乎摩尔定律也从理论上达到了极限[3][10]，这似乎对于我们对计算能力的需求永远

望尘莫及。而且对于强大计算能力的需求的平民化，似乎对于那为了科研的巨型

高成本计算机也只能望梅止渴。这样，需要一种既要具有强大计算能力又要具有

价格的优势，而且要尽量容易的实现的计算形式。这正好是计算机集群的特点[1]

[2]。

20 世纪 80 年代，出现了三种趋势，集群计算才获得了发展的动力，这

三种趋势分别是：高性能微处理器，高速网络和高性能分布计算机的标准工具。

第四个可能的发展趋势是对计算能力的需求的几何数量的增大，这种用于计算科

学和商业应用的计算，对于传统超级计算机来说是高成本低收益的。随着现代技

术的发展和各种计算机部件的商品化，集群系统（由PC 机，工作站或共享存储多

处理器 SMP 构成）成为价格合理的吸引人的并行计算工具。并行计算由使用传统

专用超级计算机平台，如 Cray\SCI T3E，转向了使用廉价、通用目的的以单处理

器或多处理器的PC 机或工作站为部件的松耦合的集群系统。这种趋势有很多好处，

包括可以按照给定任务建立承担大型主页和负载的计算机平台[1][2]。

突破单机计算能力限制的一个根本途径是实现并行计算[1-4]。自上个世纪 90

年代以来，并行计算得以空前的飞速发展，一方面，由于单处理机的计算速度不

断提高，并行计算机的体系结构趋于成熟，数据传输网络的标准化和传输速率的

大幅提升，使得并行计算机的研制周期能够从几年到几个月，为研制并行计算机

系统创造了有利条件。另一方面，推动并行计算发展的主要动力来自于国际上的

一些重要研究计划。如美国 HPCC 计划，美国 ASCI 计划。，但高性能大规模并行

计算机费用高、成本高，一般用户难以承受，而机群[5-7]计算可以提供高性价比的

高性能计算服务。典型的机群系统有曙光 2000/3000 , IBM SP 系列,Beowulf 机

群等。网格[8-11]( Grid) 是利用高速国际互联网或专用网络把地球上广泛分布的计

算资源、存储资源、通信资源、网络资源、软件资源、数据资源、信息资源、知识资源

等连成一个逻辑整体, 最终实现用户在网格这个虚拟组织环境上进行资源共享和

协同工作消除信息孤岛和资源孤岛。

现在正处于集群的黄金发展阶段，产生了一些有影响力的集群模型，各有千

秋，有的对应于特殊任务，有的有很好的扩展性，有的负载平衡很好[1][2]。这样，

逐渐会形成比较健全的集群标准，而如何划分集群[7][16][17]，也就是根据计算机的

一些特点，把相似的计算机组合在一起，使集群更好的管理和实现负载平衡[1][2]

基于模糊聚类的集群研究和实现

等一些问题更科学，在这方面还没有比较成熟的方法，这个课题就是根据一些计

算机的某些属性和计算任务的特点来寻找一种使集群的划分得尽量科学的方法。

最近几年，网格技术成为业界研究的热点，其具备兼容异构资源的能力，为

我们构建异构集群带来了新的理论和技术支撑。由于 INTRANET 上的计算机的 CPU、

内存、磁盘、网络参数[3][10]各不相同，所以简单地把它们连接在一起构成的系统不

是集群。必须对它们进行聚类、划分，形成不同计算类型逻辑计算机集群[1][2]，然

后分配计算任务。为了有效的划分集群，我们提出了基于模糊聚类的集群模型

(Fuzzy-based Cluster Model)的研究和实现，该模型对整合现有的空闲计算资

源构成计算装置有现实意义。

随着计算机集群技术的广泛应用,大规模并行计算也呈现在社会的各个领域。

因而如何有效的管理和高效的计算这些计算机集群是摆在人们面前的一个重要任

务。网格计算[12-16]为并行计算提供了强有力的支持。利用多个计算机机群[17-18]构建

多机群网格来实现并行计算是一个有效的途径。由于多机群的节点具有异构特性

能力的不均衡性，致使并行计算系统实现比较困难。其中负载平衡问题是一个研

究的热点。有关负载平衡的文献[19-23]有很多。文献[19]提出一个分布式数计算的负载

分配策略。在分布式计算中, 计算程序常需要在多台计算机上运行, 其中每台计

算机完成一个子任务, 它们相互合作共同完成整体计算任务。当计算任务总是平

均分配给各个节点计算机或网格时（MPICH2 的默认分配任务方法）, 会引起某些

性能差的计算机的计算任务过载, 从而影响整个集群或网格的处理能力处理能力。

针对这一实际问题, 分析了分布式平行程序的特点以及现有负载处理方法, 建立

了问题的规划模型, 提出了基于模糊聚类的分布式负载分配策略。

该模型利用模糊数学中的模糊相似矩阵原理对计算机聚类，计算机的数学模

型用向量<k1,k2,k3,k4,k5>其中 ki为计算机属性，在聚类过程中的任意的两个计

算机的隶属度的计算中，均加入各个属性的权值，权值是由最后的具体并行计算

机任务给出，使隶属度的计算更加关注某些属性，而使最后的聚类也更加偏重于

这些属性，这些属性就是最后计算并行任务时的最关键属性，而使并行计算任务

得到最高的效率。在聚类过程中，对应模糊相似矩阵的聚类阀值也由最后的具体

并行任务决定，而使聚类更加合理且符合并行任务的计算要求。在聚类之后给每

个聚类分配任务的策略可根据各个聚类的平均计算能力分配任务，这个评估度量

也应该根据具体的并行任务定量给出。得出最后的分配函数之后，就可具体分配

并行任务，然后计算了。

最后文中对于该分配策略给出了试验相应的结果及其试验分析。试验表明在

复杂网络情况下的计算机在计算并行计算任务时应该被合理划分，而且基于模糊

聚类的划分是一种有效划分。该模型充分考虑到负载平衡的各个方面，方便给出

根据各种并行计算任务特点的分配策略，从而在划分集群时有更好的灵活性，可

以形成根据具体计算问题的定量分配策略，具体分配策略由使用者给出。该模型

只是给出了模型的一般形式，具体的参数可以在具体的使用时给出，所以具有较

好的动态性、可扩展性。

第二章相关技术概述

§2.1 可扩展的并行计算机体系结构

并行计算机随着微处理芯片的发展，已经进入了一个新时代。目前并行计算

机的性能已经接近100TFLOPS，1000TFLOPS 的并行计算机正在规划之中。

根据指令流和数据流的不同，通常把计算机系统分为四类:

单指令流单数据流（SISD）；单指令流多数据流（ SIMD）

多指令流单数据流（MISD）；多指令流多数据流（ MIMD）

并行计算机系统除少量早期的、专用的SIMD系统外，绝大部分为MIMD系统。目前主

要的并行计算机系统有五种：并行向量机（ PVP，Parallel Vector

Processor）；对称多处理机（SMP,Symmetric Multiprocessor）；大规模并行

处理机（MPP，Massively Parallel Processor）；机群（Cluster）；分布式共

享存储多处理机（DSM，Distributied Shared Memory）。这五类计算机系统代表

了当今世界并行计算机的主要体系结构。简单介绍一下SMP、DSM、MPP。

⑴对称多处理机系统SMP

图2.1是对称多处理机系统的简单结构，它由处理单元、高速缓存、总线或交

叉开关、共享内存以及I/O 等组成。

Error: Reference source not found

图2.1 对称多处理机系统

SMP具有如下特征：

①

对称共享存储：系统中的任何处理机均可直接访问任何内存模块的存储

单元和I/O模块连接的I/O设备，且访问的延迟、带宽和访问成功率是一致的。所有

内存模块的地址单元是统一编码的，各个处理机之间的地位相同。操作系统可以

运行在任意一个处理机上。

②单一的操作系统映像：全系统只有一个操作系统驻留在共享存储器中，它

根据各个处理机的负载情况，动态分配各个处理机的负载，并保持每个处理机的

负载平衡。

③局部高速缓存及其数据一致性：每个处理机均有自己的高速缓存，它们可

以拥有独立的局部数据，但是这些数据必须保持与存储器中的数据是一致的。

④低通信延迟：各个进程根据操作系统提供的读/写操作，通过共享数据缓

CPU

Cache

总线或交叉开关

Memory Memory

CPU

Cache

CPU

Cache

I/O

…

...

…

...

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要随着Internet的发展，出现了大量计算机在绝大多数时间都是空闲的情况，这是巨大的浪费，如何减少这样的浪费，充分利用现有的计算机资源是我们追求的目标。而有效地组织现有的计算机是比较困难的，网络技术为此提供了一个很好的方法。多集群网络是利用现有局域网内的计算机，把这些计算机划分组成多个并行装置。由于每个节点计算机的计算能力不同，如何有效的组织这些计算机是个难点。本文利用模糊聚类的方法，研究多个计算机计算节点聚类，同时研究负载平衡问题，使最后的聚类结果很好的实现负载平衡。在多个计算机构成的网格环境下，为了提高多机群网格的异构资源的利用率，提出了一个数据负载均衡模型。该模型涉及的关键技术包括：...

展开>> 收起<<

基于模糊聚类的集群研究和实现.doc

共56页,预览6页

还剩页未读，继续阅读

基于模糊聚类的集群研究和实现

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: