第5章文件切分方案评价模型研究与构建

5.文件切分方案评价指标体系的建立
1 

对于一个较大的基因序列文件,应将其切分为若干个小的文件,然后对
切分后的文件进行两两比对[1]。假设将一个较大的基因序列文件切分为
m 
个大小相同子文件,
m 
值的不同即切分文件个数不同会对分布式集群的
存储性能、计算性能、节点的平均计算量产生影响。因此,建立文件切分方案
评价指标体系,通过分析评价指标对文件切分方案进行优劣评价,即寻找最
优的切分方案。文件最优的切分方案就是确定文件切分个数m,使得文件分
发到分布式集群中的各个节点后,进行基因序列比对的总体效率最优。要使
得切分方案最优就要保证文件分发后,在满足数据本地化的前提下,达到分
布式集群中各个节点的计算负载均衡、存储量最小和节点平均计算量最小。
因此,影响分布式集群总体效率的指标包括以下3个方面。

(1)计算负载均衡———集群中各个节点上分发到的任务量均衡,避免出
现任务量上的节点先执行完成等待其他节点的情况。此处假定任务量与文
件大小之间关系表达式为rw=f(size)。
(2)节点存储量最小———集群中各个节点上分发到的存储量越小越好且
不超过计算机存储上限,使得整个集群占用的存储空间最小。
(3)节点平均计算量最小———集群中各个节点上的计算量越小越好,使
得整个集群的总体计算量最小。
文件分发后进行序列比对的集群总体效率最优设计问题是一个多目标

·128· 


第5章文件切分方案评价模型研究与构建

规划问题,要实现影响分布式集群总体效率的3个指标整体效果的最大化。
因此首先需要对3个指标实现归一化处理。

当文件的切分份数
m 
值确定之后,当前文件切分方案下的节点平均任务
计算量、当前节点的任务计算量、节点平均存储量、当前节点的存储量、计算
量下限(当前文件切分方案下各节点中分配的最小计算量)和节点平均计算
量可以通过第2章构建的文件分发模型式(2-16)求得。

在寻找到相关影响指标的同时要对相关数据进行归一化处理[2]。

(1)负载均衡的归一化处理。假设在文件切分数量为k(1,2,…,m) 
时的各节点平均任务计算量为rnk 
,表示当前节点的任务计算量, 
k=

r则不同切分数量下的当前任务负载均衡的归一(i) 化(k) 处理公式如式(5-1)所示。

Σ(n) |rik 
-rnk|

i=1

(1,m) 51)

k=2,…,(
maxΣ(n) |rik 
-rnk| 

=

(2)节点存储量的(k) 归(i) 一(1) 化处理。假设在文件切分数量为k(k=1,2,…, 
m)时的各节点最小存储量为cnk 
则不同切分数量下的存储最小化归一化处
理公式如式(5-2)所示。
min,
(1,m) 52)

nk

cmin 

k=2,…,(

nk

maxcmin 

(3)节点平均计算量归一化处理。在不同的当前文件切分方案下节点的(k) 
的平均计算量是不同的,假设jmn jk

i表示在不同切分数量下的计算量下限,n

为当前分发方案下的节点平均计算量,则节点的平均计算量的归一化处理公

式如式(5-3)所示。
jnk 
-jmin (5-3)

jmin 

·129· 


全比较问题数据分发策略研究

5.利用层次分析法建立文件切分模型
文件切分方案以确定切分后文件的个数
m 
为目的来测定负载均衡、存储

量和节点的平均计算量这3个指标,整个过程均需要评价者的参与。层次分

析法是一种需要评价者做出相应反应或指示的综合评价方法,在层次分析法

中,首先需要将与决策有关的元素划分到目标层、准则层、方案层[3-5],并在此

基础之上进行定性和定量分析。层次分析法包括以下5个基本步骤。

步骤1:建立层次结构模型。

步骤2:构造成对比较阵。

步骤3:计算权向量并做一致性检验。

步骤4:计算组合权向量并做组合一致性检验。

步骤5:进行决策。

根据层次分析法的基本过程,首先对文件切分方案建立层次结构模型, 

在建立层次结构模型之前,需要根据3.

1节中的分析与描述构建层次分析法
所需的因素集。所谓因素集就是将所有影响研究对象的因素集合起来。一
般以
U 
表示集合,假设影响因素有
n 
个,因素集就表示为
U 
={u1,u2,…, 

un},i1,n)

ui(=2,…,表示的因素具有程度不同的模糊性。文件切分方案评
价的影响因素有负载均衡、存储量、平均计算量,因此因素集
U 
={u1,u2, 
u3}, 即U={负载均衡,存储量,平均计算量}。

模糊综合判定可分为一级模糊综合判定[6]和多级模糊综合判定[7]。本

书主要使用一级模糊综合判定。一级模糊综合判定的基本方法和步骤

如下。

1. 
建立因素集
因素集是以影响判定对象的各种因素为元素所组成的一个普通集合,通
·130· 


常用U 表示,即U ={u1,u2,…,um },ui(i=1,2,…,m )代表影响因素,这些
因素可以是模糊的,也可以是非模糊的,但它们对因素集U 的关系,要么ui∈ 
U ,要么ui .U ,二者必居且仅居其一,因此因素集本身是普通集合。
2.建立权重集
权重是一个相对的概念,是针对某一个指标而言的。某一个指标的权重
是指该指标在整体评价中的相对重要程度。一般来说,各个因素的重要程度
是不一样的。因此,应根据各因素的重要程度赋予相应的权重ai (i=1, 
2,…,m ),并要求Σm 
i=1
ai=1,ai >0。由各权重所组成的集合A =(a1,a2,…, 
an)称为因素权重集,简称权重集。
3.建立备择集(评价集、评语集) 
备择集是评判者对评判对象可能作出的各种总的评判结果所组成的集
合,通常用V 表示,即V ={v1,v2,…,vn},vi 表示各种可能的评判结果,如评
判一个教师的素质,评判结果可分为很好、好、一般和差,则备择集V ={很好, 
好,一般,差}。
4.单因素模糊评价
单独从一个因素出发进行评判,以确定评判对象对备择元素的隶属程
度,称为单因素模糊评判。
设评判对象按因素集中第i 个因素ui 进行评判,对备择集中第j 个元素
vi 的隶属程度为rij,则按第i 个因素ui 评判的结果为
Ri =(ri1,ri2,…,rin) (i=1,2,…,m ) 
以各单因素评判结果为行组成的矩阵,称为单因素评判矩阵,即
·131· 
第5章 文件切分方案评价模型研究与构建

R =(rij)= 
r11 r12 … r1n 
r21 r22 … r2n 
. . . 
rm1 rm2 … rmn 
é
.
êêêêêêê 
ù
.
úúúúúúú 
单因素评判矩阵是一个难点,主要是确定隶属度往往带有主观性,常用
确定隶属度的方法有专家打分法、线性函数法(三角形法和梯形法)等。
5.模糊综合评判
模糊综合评判就是综合考虑所有因素,得出正确的评判结果。
从单因素评判矩阵R 可以看出:R 的第i 行反映了第i 个因素隶属于备
择集各元素的程度,而R 的第j 列反映了所有因素隶属于备择元vj 的程度, 
若用第j 列元素之和Rj =Σm 
i=1
rij,j=1,2,…,n 来反映所有因素的综合影响, 
则并不能够同时考虑各因素的重要程度。若考虑到权重集,则便能合理地反
映所有因素的综合影响,因此,F 综合评判可表示为
B =A*R =(a1,a2,…,am )* 
r11 r12 … r1n 
r21 r22 … r2n 
. . . 
rm1 rm2 … rmn 
é
.
êêêêêêê 
ù
.
úúúúúúú 
=(b1,b2,…,bn) 
bj={b1,b2,…,bn}称为F 综合评判指标,简称评判指标。bj 的含义是: 
综合考虑所有因素的影响时,评判对象对备择元vj 的隶属度。
在B=A*R 中,运算“*”的取法不同,结果也不完全相同,但相差不大。
“*”的取法主要有如下几种: 
模型Ⅰ:M(∧,∨)bj=∨m 
i=1(ai∧rij)(j=1,2,…,n) 
这里“∧”“∨”表示取小、取大运算。
模型Ⅱ:M(·,∨)bj=∨m 
i=1(ai·rij)(j=1,2,…,n) 
·132· 
全比较问题数据分发策略研究

这里“·”是普通乘法。
模型Ⅲ:M(∧,..)bj =min1,Σm 
i=1(ai ∧rij) (j=1,2,…,{ n)} 
模型Ⅳ:M(·,..)bj =min1,Σm 
i=1{ (ai·rij) (j=1,2,…,n)} 
模型Ⅴ:指数模型bj=∧m 
i=1
rai 
ij 
模型Ⅰ是一种制约性主因素突出型模型,不宜应用于因素太多或太少的
情况。模
型Ⅱ和模型Ⅲ与模型Ⅰ比较,能较好地反映单因素评价结果和因素的
重要程度。
模型Ⅳ不仅考虑了所有因素的影响,而且保留了单因素评判的全部信
息,该模型称为加权平均型模型,在实践中常常用该模型。
模型Ⅴ的最大特点是评判对象的综合评判指标等于所有rai 
ij 的最小值, 
因此为了有效提高评判对象的综合评判指标,务必全面改善所有单因素指标
才能达到目的,该模型是一种制约性全面促进型模型。在实际应用时,根据
问题的要求,选择恰当的模型进行运算。
6.评判指标的处理
对评判指标bj ={b1,b2,…,bn},可根据以下几种方法确定评判对象的
具体结果。
(1)最大隶属度法[8]。若bl=max{b1,b2,…,bn},则评判结果隶属于vl。
(2)加权平均法[9]。取以bj 为权重,对各个备择元素vj 进行加权平均
的值为评判结果,即
V = Σn 
j=1
bjvj 
Σn 
j=1
bj 
·133· 
第5章 文件切分方案评价模型研究与构建

此法要求将vj 中非数量性备择元素数量化。
(3)F 分布法[10]。对bj 进行归一化,令b=Σn 
j=1
bj ,则第i 个指标归一化
处理之后的和B'i为
B'i=
b1b
+
b2b
+ … +
bn 
b =b'1
+b'2+ … +b'n 
这样,b'j反映了评判对象在所评判的特性方面的分布状态,即所占的百分比。
通过分析得知,对文件切分方案评价的目标为对文件切分方案优劣进行
综合评价,将其作为递阶层次结构最高层的元素。采用一种文件切分方案, 
在分布式集群环境下按照第2章式(2-12)和式(2-16)所示的文件分发模型实
现文件分发之后,完成所有文件的两两比对任务,分布式集群整体性能是评
价该切分方案优劣的唯一标准。影响分布式集群整体性能的主要因素包括
各个节点的计算负载是否均衡、各个节点被分配文件存储量是否最小和各个
节点的平均计算量是否最小3方面,即文件切分方案综合评价所需要考虑的
准则。负载均衡U1、存储量U2、节点平均计算量U3 这3个指标共同构成了
准则层元素的集合,上述准则对目标实现的重要程度可能不同,但是彼此之
间独立,不存在支配关系,因此它们是有优先级顺序的同级关系。确定文件
切分的个数m 作为实现对文件切分方案优劣进行综合评价这个目标的措施
方案,即将文件切分为大小尽可能均匀的k(k=1,2,…,m )份,放置在层次结
构模型的最底层。
明确各个层次的因素及其位置后,将它们之间的关系用连线连接起来, 
构成递阶层次结构,如图5.1所示。
假设3个目标U1、U2、U3 的重要程度分别为a1、a2、a3,这3个系数可以由层
次分析方法等确定得出,则当前文件切分方案的评价模型如式(5-4)所示。
min k 
.
è
....
a1 Σn 
i=1 
|rik -rnk| 
max k Σn 
i=1 
|rik -rnk| 
+a2 
cnk 
min 
max k 
cnk 
min 
+a3
jnk -jmin 
jmin 
.
.
÷÷÷÷
(5-4) 
·134· 
全比较问题数据分发策略研究

图5.1 递阶层次结构图 
同样对各个子指标也通过专家打分的方式获取到对应的权重。特别地, 
如果假定3个目标的重要程度是相等的,则目标函数变成如式(5-5)所示。
min k 
.
è
....
13
Σn 
i=1 
|rik -rnk| 
max k Σn 
i=1 
|rik -rnk| 
+13
cnk 
min 
max k 
cnk 
min 
+13
jnk -jmin 
jmin 
.
.
÷÷÷÷
(5-5) 
由于3个目标同等重要,因此无须进行构造成对比较矩阵,也无须进行步
骤三、步骤四。
5.3 文件切分最优个数的确定
在确定文件切分评价模型后,根据现有节点个数n 及不同切分数量可以
筛选出最优的文件切分数量m 。其具体确定公式如式(5-6)所示。
m = opt
.
è
....
min k 
.
è
....13Σn 
i=1 
|rik -rnk| 
max k Σn 
i=1 
|rik -rnk| 
+13
cnk 
min 
max k 
cnk 
min 
+13
jnk -jmin 
jmin 
.
.
÷÷÷÷ 
.
.
÷÷÷÷ 
(5-6) 
文件切分个数m 值确定算法具体计算步骤如下。
第一步:利用式(2-12)所示文件分发模型确定最优的均衡化任务分配方
·135· 
第5章 文件切分方案评价模型研究与构建

全比较问题数据分发策略研究

案,并计算出分布式集群中计算量最大节点的总计算量cmax。

第二步:利用式(2-16)所示文件分发模型计算获得分布式集群中在每个
节点的最大计算量不变的情况下,使得各个节点的总存储量最小化的任务重
新分发方案。

第三步:在当前分布式集群中节点数量
n 
不变的情况下,进一步计算不
同切割数量下的相关优化结果的取值。

第四步:利用3.并利用相关评价方法

1节中的方法处理各项优化数据, 
计算出最优
m 
值。
文件切分个数
m 
值确定算法相关伪代码详细描述见表5.

1。

表5.
m 
值确定算法相关伪代码详细描述

1 

输入:假定的m值
输出:集群存储占用总和、计算量总和、误差总和

%定义并初始化变量参数
n←分布式集群数量
s←文件大小
m←切分文件数量
fori=m1tom2do 

m←i+n;

%将文件切分为m等
份
s←1/m*ones(m,1)
;
%在当前切分数量下计算出最优任务指派方
案


[eut,ei,eutsqk,cx]aksignn(m,s);

rsldcrsl1,csd←tsa_n,
x←reutlntrsl1(


sl1(:,egh(eut1,:))); 
y←abs(x-sum(x)/length(x));
%计算在当前切分数量下计算量r1,计算量误差r2和存储量总和r3 
r1(2(3(←sx,sd

i),i),x);

rri)um(y,cendfor 
q←三个目标的权重;
%标准化处理
rsrsrs1←normalizerrr

3,2,d(3,1,2);
%总体评价结果
reuslt←q(1)*rs3+q(2)*rs2+q(3)*rs1; 

·136· 


第5章文件切分方案评价模型研究与构建

在文件切分个数
m 
值确定的实验中基于计算的方便,假定将一个充分大
的基因序列文件等份的切分成
m 
份,并通过相关理论寻找最优的
m 
取值。
假定分布式集群中节点数量分别为3、4、5的不同切分大小情况下,计算获得
了存储大小总和、计算量总和、误差总和大小等相关数据的取值情况及其对
应评价结果。具体结果见表5.表5.4。

2、3和表5.

表5.节点数为3时对应评价结果

2 

m 
取值(n=3) 4 5 6 7 8 9 10 
存储大小总和0.75 0.6 67 0.722 
0.714286 1 1 1 
计算量总和0 0.3 3 
0.6 67 1 1.3 3 
1.6 67 2 
误差总和大小0 0.8 0 0 1 0 0 
评价分值0.250 0.54 
0.3 
0.405 0.89 0.61 
0.67 

表5.节点数为4时对应评价结果

3 

m 
取值(n=4) 5 6 7 8 9 10 11 
存储大小总和0.8 0.833 
0.809524 0.833 
0.8 89 1 1 
计算量总和0 0.25 0.5 0.75 1 1.25 1.5 
误差总和大小1 0.41667 1.071429 0 0 0.5 0.27273 
评价分值0.60 
0.472 0.738 0.4 
0.519 0.78 0.742 

表5.节点数为5时对应评价结果

4 

m 
取值(n=5) 6 7 8 9 10 11 12 
存储大小总和1 0.857143 0.825 0.833 
0.84 0.84545 
0.9 
计算量总和0 0.2 0.4 0.6 0.8 1 1.2 
误差总和大小0 0.964286 0.5625 1 0 0 0.5625 
评价分值0.3 
0.63 0.574 0.78 0.502 0.560 0.821 

·137·