上海理工大学学报第２７卷第１期Ｊ．ＵｎｉｖｅｒＳｉｔｙｏｆ她ｈａｉ五ＤｒｓｃｉｅｎｃｅａｎｄＴｅｃｈｎ０１０９ｙＶ０１．２７№．１２００５文章编号：１００７—６７３５（２００５）０１—００７９—０４面向机群并行计算的分组通信模型陈庆奎１，那丽春２（１．上海理工大学计算机工程学院，上海２０００９３；２．上海理工大学现代化教育中心，上海摘要：提出了一个计算机机群环境下的分组通信算法，防止通信峰值阶段通信冲突对机群执行效率的影响．给出了完全图通信的形式化定义，构造了基于分组机制的完全图通信模型的实现方法．分析和实现表明，该模型有效地解决了计算机机群环境下通信峰值所造成的集群效率低下的问题，适用于机群的数据密集型并行计算．关键词：计算机机群；分组通信；冲突；完全图通信中图分类号：ＴＰ３９３文献标识码：ＡＧｒｏｕｐｉｎｇｃｏｍｍｕｎｉｃａｔｉｏｎｍｏｄｅＩｆｏｒｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｉｎｃｌｕｓｔｅｒＣＨＥＮ（１．僦姆Ｐ矿伤砷“灯励砌蒯昭，吼妇瓜移∥跳咖ｉ弦Ｓ砌蹴ｎ砝融蝴，跳咖ｉ２０００９３，吼ｉ撇；２．Ｍ越溯苏癌正池瑚ｆｉ朔Ｃ锄￡盯，Ｕｈｉｚ盯菇￡），０，踟增勉ｉ向，＆锄埘ｎ以仉魄咖，鼢嘞面２００Ｄ９３，Ｇｈｉ撒）Ａｂｓｔｒａｃｔ：ＡＱ畸乜ｉ１，ＮＡＬ－－ｃｈ一ｇ工ｏｕｐｉｎｇ∞ｍ砌ｍｉｃａｔｉｏｎＡｆｏｒｍａｌｄｅｆｉｎｉｔｉｏｎａｂＯｕｔｔｈｅ唧１ｅｔｅｇｒ印ｈｉｃＳ黜ｕｎｉｃａｔｉｏｎｏｎｍ。ｄｅｌｆｏｒｈａｎｄｌｉｎｇｔｈｅ００ｒｌｆｌｉｃｔｉｎｃ。ｍｐｕｔｅｒｃｌｕｓｔｅｒｉｓｄｉＳｃｕｓｓｅｄ．ｉｓｇｉｖｅｎ．Ｔｈｅｉｍｐｌ锄ｅｎｔｍｅｔｈｏｄｏｆｃ（ｍ叩ｌｅｔｅｇｒａｐｈｉｃｓｃ（ｍｍｌｕｎｉｃａｔｉｏｎｂａｓｅｄｇｒ（ｍｐｉｎｇｍｅｃｈａｎｉＳｒｎｉｓｓｔｕｄｉｅｄ．Ｔｈｅａｎａｌｙｓｉｓａｎｄｅ】【ｐｅ矗一ｍｅｎｔｒｅｓｕｌｔｓｈａｗｔｈａｔｔｈｉｓｍｏｄｅｌｅｆｆｅｃｔｉ、，ｅｌｙｒｅｓｏｌｖｅｔｈｅｐｒｏｂｌａｎｏｆｌｏｗｅｆｆｉｃｉｅｎｃｙｄｕｒｉｎｇｔｈｅｐｅａｋｏｏｍ—ｍＬＨｌｉｃａｔｉｏｎｉｎｏＯｍｐｕｔｅｒｃｌｕｓｔｅｒ．ＩｔＫｅｙｃａｎｂｅｆｉｔｆ６ｒｔｈｅｄａｔａ＿ｉｎｔｅｎＳｉｖｅｐａｒａｌｌｅｌ∞ｍｐｕｔｉｎｇ．ｗｏ喇ｓ：ｃ０７７ｚ抛￡盯ｃＺ“ｓ据ｒ；ｇ．ｒｏ“乡ｉ咒ｇ∞ｍｍ“扎ｉ∞￡幻扎；∞，卵ｉ以；∞优ｐＺ啦盯口加ｉ∞ｃＤｍｍ“咒ｉ∞￡ｉｏ扎只处理数据的一部分，同步工作只发生在数据需要随着信息技术的飞速发展和Ｉｎｔｅｍｅｔ应用的日益普及，信息爆炸已经成为当今信息技术产业界和学术界所面临的急需解决的主要问题．并行计算技术和分布式计算技术、计算机机群技术和网格技术都是解决该问题的有效途径．其中，计算机机群技术Ｌ１Ｊ以其良好的可扩展性、强大的并行Ｉ／Ｏ能力及非常高的性能价格比等特性受到了学术界和工业界交换时．在这种模型中，数据交换时会产生通信的峰值．当进行数据密集交换并且通信量很大时，将导致冲突，冲突将会浪费通信资源、降低机群的性能．典型的数据密集交换的例子是并行ＪＯＩＮ操作幢Ｊ的关系元组重分配阶段．目前有关高效通信方面的研究很多，文献［３］提出了一种适合机群通信的协议ｘＴＲ；文献［４，５］提出了利用多个物理通信设备的多通路通信机制．本文给出一个基于ＩＰ协议和普通宽带网络的分组通讯模型，该模型利用现有的网络的广泛青睐．机群系统中通常使用中、粗粒度并行．数据型并行计算是一种极有代表意义的计算模型．数据并行型计算是以数据并行方式来工作的，机群中的计算节点异步地执行同样的操作，但每个节点收稿日期：２００４—０６—０８带宽、优化通信过程，达到高效通信的目的．该模型基金项目：上海市教委发展基金资助项目（０３ＧＫｌｌ；０４ＥＢ２１）；上海市自然科学基金资助项目（０４ＺＲｌ４１００）作者简介：陈庆奎（１９６６一），男，教授．万方数据８０上海理工大学学报２００５年第２７卷已成功地应用于机群并行数据库原形系统，实践表明该模型具有良好的扩展性、可移植性，并且有效地支持数据密集交换通信．１数据并行型计算定义ｌ（计算机机群）一个计算机机群（ＣＣ，ｍ—ｐｕｔｅｒａｕｓｔｅｒ）为一个４元组ＣＣ（拖，ＣＳ，Ｎ，Ｒ），其中，拖为机群主控制器；ＣＳ为所有计算节点的集合｛Ｃ１，Ｃ２，…，Ｇ｝．本文所讨论的机群乡均为偶数；Ｎ为连接网络的集合，连接网络是高速交换网；Ｒ为连接规则．每个ＣＳ中的计算节点具有的处理器和外存储器．同时，为了描述方便，假设ＣＳ中的每个计算节点的结构和能力（ＣＰＵ、ＭＥＭＯ—ＲＹ、ＤＩＳＫ及ＮＥＴＷＯＲＫ）是相同的．由于Ｎ和Ｒ对本算法研究影响不大，本文简记ａＣ（姚，ＣＳ）．算法１（数据并行型计算）机群Ｏｃ（拖，Ｃｓ）上的一个数据并行型计算过程．ａ．在地上执行过程①计算任务规模、分解为子任务；②启动所有ＣＳ中的计算节点；③７ｚ＝子任务数；④ｉ＝１；⑤分解数据Ｄａｔａ为Ｄｌ，Ｄ２，…，Ｄ口；⑥发送瑰到Ｇ（１≤愚≤ｐ）；（ＤＷｈｉｌｅｉ＜扎ｄｏ⑧驱动Ｇ（１≤忌≤ｐ）同时求解子任务ｉ；⑨同步Ｇ（１≤尼≤ｐ）对子任务ｉ的求解；⑩ｉ＝ｉ＋１；①Ｅｎｄ、池ｉｌｅ；④回收Ｇ（１≤愚≤ｐ）的计算结果并合成；⑩通知Ｇ（１≤尼≤ｐ）结束计算；⑨结束本次计算．ｂ．在Ｇ（１≤忌≤ｐ）上执行过程①接收初始数据；②Ｗｈｉｌｅ未接到拖的结束命令ｄｏ③接收子任务ｉ；④计算子任务ｉ；⑤Ｇ与其他计算节点Ｇ（１≤歹≤ｐ，歹≠”同步交换数据；⑥Ｅｎｄｗｈｉｌｅ；⑦发送计算结果到拖；⑧结束本次计算．在过程ａ、ｂ中，计算节点Ｇ（１≤忌≤声）执行的所有子任务都是一样的，只是操作的数据集不同．例万方数据如，并行关系数据库的ＪＯＩＮ操作【２Ｊ就是数据并行型计算．定义２（通信峰值问题）基于机群的数据并行型计算所面临的问题是通信峰值问题，所谓通信峰值问题就是在并行计算过程中，周期性地出现机群节点间大规模多对多的完全图通信问题．定义３（完全图通信）所谓完全图通信就是ＣＳ中每个计算节点都要向其他咒一１个计算节点发送数据，同时又要从其他咒一１个节点接收数据，在ＣＳ的任意两点间都有一个逻辑信道，所有逻辑信道构成一个痧个节点的完全图．图１表示４个计算节点的完全图通信．算法１中ｂ过程的第⑤步所述的阶段就是通信峰值阶段．图１完全图通信Ｆｉｇ．１Ｇ）ｎｌｄｅｔｅｇｒａｐ｝ｌｉｃＳ∞ｍｍｕｎｉｃａｔｉｏｎ定义４（计算节点过程模型）机群ＣＣ（Ｍａ，ＣＳ）上的每个计算节点的过程模型可以定义成一个６元组Ｇ（ＣＰ、ＳＰ、ＲＰ、Ｃｂｕｆ、ＳＢｕｆ、ＲＢｕｆ），其中ＣＰ、ＳＰ、ＲＰ分别为本地计算进程、数据发送进程、数据接收进程，Ｃｂｕｆ、ＳＢｕｆ及ＲＢｕｆ为３个进程所对应的数据缓冲区．一般情况下ＣＢｕｆ比较大，而Ｃｂｕｆ、ＳＢｕｆ比较小．图２反映了各个部件间的关系．图２计算节点模型Ｆｉｇ．２ＭＯｄｅｌ０ｆｃｏｍｐｕｔｉｎｇｎＯｄｅ从定义２和定义３可知，一个数据并行型并行计算的通信峰值问题会带来如下问题：ａ．物理信道拥挤造成的通信冲突、阻塞，致使底层数据包丢失．ｂ．接收缓冲区溢出．第１期陈庆奎，等：面向机群并行计算的分组通信模型８１ｃ．多对一通信的相互阻塞．ｄ．无效传输．在基于可靠的数据传输机制下，由于冲突、阻塞所导致的对同一数据报的重复发送，除正确收到的那一个外，其余是无效的传输．ｅ．死锁．由于两个或两个以上的计算结点相互等待通信的应答，而构成一个环，产生死锁．ｆ．降低了机群的可扩展性．由于无序的峰值通信，致使上述问题随着机群规模的扩大越来越严重．目前解决峰值通信的问题一般有下面几个方法：ａ．优先级方法对ＣＣ的每一计算结点Ｇ（１≤尼≤夕），都赋予一个权，当发生冲突时，权大的计算节点优先发送．权可据各个计算结点的地位而定．这种方法的缺点是权的定义往往和实际通信情况不符．ｂ．通信量方法各个计算结点把自己的信息量通知给拖，姚按照一定的策略进行均衡运算，对具有很大数据量的计算结点赋予较高的优先权，可以缩短传输阶段的并行响应时间．这种方法的缺点是由于尬的同步介入，影响了并发性能．ｃ．随机延迟各计算结点一旦发生冲突，便延迟一个随机时间，然后再执行通信操作．如再度发生冲突则应增大ｄ．分组通信将计算结点Ｑ（１≤忌≤痧）分成ｍ个组，每组定义５（主动队列和被动队列）主动队列（ＡＱ）万方数据息时，有Ｇ∈ＰＱ，处于被动队列中的计算节点又叫被动计算节点．两个队列分别用两个数组ＡＱ［］、尸Ｑ［］表示．队列的长度分别用ＡＱ，鹏表示．由于主动队列的长度决定着通信阶段的通信量，所以假设主动队列的长度ＡＱ，为一个常数，其可以通过机群的综合能力来计算．为了清晰描述，假设机群ＣＣ的计算节点的个数ｐ恰好是ＡＱｆ的整数倍．定义６（选播对象队列）对于主动队列ＡＱ中的每个计算节点，都有一个它所选播的计算节点集合ＢＱ（１≤ｉ≤ＡＱｆ），这个集合就是选播对象队列．队列的长度为ＢＱ．本文介绍的分组通信模型是基于ＡＱ、ＰＱ的，所有分组调度工作都是在拖上进行．２．２Ｍａｓｔｅｒ分组过程算法１中ａ过程的第⑨步的同步过程细化如下．算法２（算法１中ａ过程的第⑨步）ａ．初始化被动队列．ＰＱ按照ＣＳ中的计算节点在机群中的编号次序，把所有计算节点加入被动队列，ＰＱ［］＝｛Ｃ１，Ｃ２，…，ｑ｝．ｂ．构造主动队列按照各个计算节点的本地子任务完成的时间先后顺序，把相应的计算节点移入主动队列；当主动队列满时，停止移入，剩下的仍然留在被动队列中．ｃ．排序被动序列对留在被动序列中的计算节点，按照各个计算节点的本地子任务完成的时间先后排序，并平移到队首，这样最早完成本地子任务计算的被动节点处于被动队列的前面．ｄ．构造选播对象队列ＢＱｆ＝［ｐ／ＡＱｆ］；／＊选播对象队列长度＊／ＦＯｒｉ＝１，…，ＡＱｆｄｏ／＊初始化ＢＱｆ＊／ＢＱｉ＝声Ｅｎｄｆｏｒ：Ｆｏｒｉ＝１，…，ＡＱｆｄｏ／＊构造ＡＱ￡个ＢＱ＊／ｉ＝ｉ；／＊指向被动队列的指针＊／Ｆｏｒ忌＝１，…，ＢＱｆｄｏ／＊构建第ｉ个ＢＱ＊／ＢＱｉ＝ＢＱ￡＋｛ＰＱ［Ｊ］｝；歹＝歹＋ＡＱｚ；Ｅｎｄｆｏｒ：／＊确定主动元素所属的ＢＱ＊／Ｉｆｉ＜ＡＱ，ｔｈｅｎ延迟时间．这种方法具有盲目性．有ｇ＝Ｌｐ／ｍＪ个结点，分别设为Ｇｌ，Ｇ２，…，嚷．各组Ｇｉ（ｉ＝１，２，…，ｐ）内实施上述３种方法之一；当组Ｇｉ（ｉ＝１，２，…，夕）通信完成后，再重新分组通信．分组通信的优点是：适当的组的大小可以减少高层冲突的次数；建立多个组进行并行通信，可以提高物理信道的利用率；组的大小及组的个数可以根据硬盘、ＣＰＵ及信道的速度来计算优化值；具有极高的可扩展性．２分组通信模型２．１准备工作和被动队列（ＰＱ）是保存机群０Ｃ（地，ＣＳ）中的每个计算节点在并行计算过程中的状态的两个队列．当计算节点Ｑ（１≤足≤ｐ）既可以发送信息又可以接收信息时，有Ｇ∈ＡＱ，处于主动队列中的计算节点又叫主动计算节点；当计算节点Ｇ（１≤志≤声）只能接收信上海理工大学学报２００５年第２７卷ＢＱ￡＝ＢＱｉ＋｛ＡＱ［ｉ＋１］｝；ＥｌｓｅＢＱｉ＝ＢＱｉ＋｛ＡＱ［１］｝；Ｅｎｄｉｆ：Ｅｎｄｆｏｒ．ｅ．监控完全数据交换Ｏｆ＿０；／＊决定每个主动计算节点对应的选播对象队列的偏移指针＊／①Ｗｈｉｅｌ０ｆ＜ＡＱｚｄｏ②发送ＡＱ和ＢＱ到ＣＳ／＊第ｏｆ＝睡ｔ次对应＊／Ｆｏｒｉ＝１，…，ＡＱ￡ｄｏＫ＝ｍ。ｄ（ｉ＋０ｆ，ＡＱｆ）；／＊模除＊／发送Ｂｑ到计算节点ＡＱ［ｉ］；／＊主动节点ＡＱ［ｉ］对应选播对象队列Ｂｑ＊／Ｅｎｄｆｏｒ：③启动所有主动节点按照｛ＢＱｌ，ＢＱ２，…，ＢＱＡＱ，｝通信；④ＲｅｐｅａｔｄｏＵ『ｎｔｉｌ所有主动节点完成本次通信；⑤０ｆ－Ｏｆ＋１；／＊修改对应次数＊／⑥Ｅｎｄｗｈｉｌｅ；／＊完成了本次主动队列的到所有节点的通信＊／ｆ．调整主动队列备份主动队列ＡＱＢＡＫ＝ＡＱ；取被动队列ＰＱ前ＡＱ个元素，按原序加入主动队列；把ＰＱ中的剩下元素向队列头部移动ＡＱｚ个位置；把ＡＱＢＡＩ（按原序加入被动队列尾部．ｇ．启动下轮通信Ｉｆ（所有计算节点都作为主动节点完成了ｅ过程）ｔｈｅｎ通信阶段结束；Ｅ１ＳｅＧｏｔｏ（ｄ）；ｃｓ计算节点过程计算结点Ｑ在算法１的ｂ过程修正如下．算法３（改进的算法ｌｂ）①接收初始数据；②Ｗｈｉｌｅ未接到地的结束命令ｄｏ；③接收子任务￡；万方数据④计算子任务￡；⑤Ｗｈｉｌｅ子任务￡的通信未结束ｄｏ⑥ｗｈｉｌｅ＾钇的算法２未结束ｄｏ⑦从拖接收计算节点状态信息ＡＱ［ｉ］，Ｂｑ；／＊对应算法２中ｅ过程的第②步＊／⑧ＩｆＧ是被动节点ｔｈｅｎ⑨启动接收进程ＲＰ；⑩Ｅｎｄｉｆ；①ＩｆＱ是主动节点ｔｈｅｎ＠启动接收进程ＲＰ；⑩把ＢＱ＾传给进程ＳＰ，并启动ＳＰ；⑩Ｅｎｄｉｆ；⑩监控ＳＰ和Ｉ冲，直到它们结束；⑩通知地本次通信结束；／＊对应算法２中ｅ①Ｅｎｄ、ｖｈｉｌｅ；⑩Ｅｎｄ、Ⅳｈｉｌｅ；／＊子任务ｉ的通信＊／⑨通知Ｍ口子任务ｉ通信结束；⑨Ｅｎｄｗｈｉｌｅ；④发送计算结果到拖；④结束本次计算．定理ｌ算法２所描述的分组通信过程实现了痧个计算节点的完全图通信问题．证明在算法２中ｄ过程构造的选播对象队列的调整变动，所有的计算节点都在主动队列中存在定理２算法２所描述的分组通信过程是均衡的．证明在算法３的第⑥～⑨步过程中，ＣＣ中本文在并行关系数据库原型系统ＨＰＤ科５Ｊ的研（下转第８６页）过程的第④步＊／２．４分析与实现集ＢＱ＝｛ＢＱｌ，ＢＱ２，…，ＢＱ蛔，｝覆盖了ＣＳ；同时在每一次变动的过程中，主动队列的所有的计算节点都和ＢＱ通信．又因为经过ＡＱｆ一１次主动队列中过，并且完成了通信．所以，算法２所描述的分组通信过程，实现了ｐ个计算节点的完全图通信问题．最多存在ＡＱｆ个主动节点，即只有ＡＱｆ个计算节点发送消息；每个主动和被动节点只接收来自一个节点的信息，所以大大地减少了冲突．算法２所描述Ｅｎｆ｛汗．２．３的分组通信过程是均衡的．究和实现过程中，应用了该分组通信模型．实践表明，在并行ＪＯＩＮ的数据重新划分阶段，该模型的效率比优先级方法、通信量方法及随机延迟提高了２．５～３倍．上海理工大学学报２００５年第２７卷准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废．因此，存在一种新的评估指标，即Ｆ１测试值试验研究．试验结果表明，Ｋ一近邻决策的分类效果要优于最近邻决策的分类效果．参考文献：ｎ测试值＝焉筹鬻表１分类查全率、准确率及Ｆ１值［１］姚天顺．自然语言理解［Ｍ］．北京：清华大学出版社，１９９５．本方案试验结果所得查全率、准确率和Ｆ１值如表１所示．眨１Ｊｂ１Ｊ％战学刚，林鸿飞，姚天顺．中文文献的层次分类方法Ｔａｂ．１昀删ｉｏｎ删Ｉｒａｔｉｏ，Ｆ１［Ｊ］．中文信息学报，１９９９，１３（６）：２０～２５．ＳａｌｔｏｎＧ，ＷｏｎｇＡ，ＹａｎｇＣ．ＡｖｅｃｔｏｒＳｐａｃｅｍ。ｄｄｆｏｒａｕ—ｒａｔｉｏ，ｐ嫩ｉｓｉｏｎＦ１值８５．７８３．２ｔ０蚴ｔｉｃ圳ｅ）（ｉ１１９［Ｊ］．Ｇ聊ｍ“，ｚ泐￡幻埘矿ＡＣＭ，１９７５，１８（１１）：６１３～６２０．■１ＪＳａｌｔｏｎｖａＩ哦准确率９５．５９２．７分类方法Ｋ．近邻法最近邻法查全率７７．８７５．５Ｇ．Ａ甜幼凇斑了ｋ￡№已ｓ矗以ｇ［Ｍ］．ＮｅｗＹｏｒｋ：Ａｄｄｉｓｏｎ—Ｗ签Ｌｅｙ，１９８９．ｂ１Ｊ陆１ｊｐ１Ｊ随１Ｊ萱菁，吴立德．基于向量空间模型的文档分类系统［Ｊ］．模式识别与人工智能，１９９８，１１（２）：１４７～１５３．２结论文本自动分类是文本数据挖掘中一个很重要课题，本文根据网络信息文献的特点，提出了一种与语种无关的、机器学习的文本自动分类模型，并分别进行了基于最近邻决策和Ｋ一近邻决策的分类效果萱菁，吴立德．于语种的文本分类方法［Ｊ］．中文信息学报，２０００，１４（６）：１～７．吴立德．大规模中文文本处理［Ｍ］．上海：复旦大学出版社，１９９７．何新贵，彭甫阳．中文文本的关键词自动制取和模糊分类［Ｊ］．中文信息报，１９９９，１３（１）：９～１５．（上接第８２页）３结论在基于机群的并行计算实现中，解决通信峰值的有效手段就是分组通信．把无序或简单顺序的通信过程分解为若干均衡的通信子过程，不仅解决了冲突问题，还增加了机群的可扩展性．本文的研究和实践证明了这一点．参考文献：［Ａ］．李建中．数据库研究与发展９５［Ｃ］．哈尔滨：哈尔［３］№ｔｒａ力印０ｒｔ舯呶）。。１４．０印ｅｃｉｆｉ洳［Ⅱｊ／０Ｌ］．ｈ却：／／、＾删．∞．ｓａＩ斌ａ．ｇｗ／）印，２００４—１２．［４］ＫｉｍＪｕｎｓｅＯｎｇ，ＤａｖｉｄＪ．ｕｔｉｌｉｚｉｎｇＨｅｒｔｅｒｏｇ明ｅ。ｕｓＮｅｔ—ｗｏｒｋｉｎＤｉｓｔｒｉｂｕｔｅｄＣ０ｎｌｐｕｔｉＩ】ｇＳｙｓｔｅｎｌ【ＡＪ．Ｉｎ：ｈ纫＾，衄一滨工程大学出版社，１９９５，９５～１００．￡面眦ＺＳ胛伽砌ｍ伽Ｈ动％厅胛撇，珊Ｄ如￡，．汤“￡耐Ｐｒｅｓｓ，１９９７，Ｇ唧抛矗增［Ｃ］．ＬＯＢＡｌ锄ｉｔ０６：ＩＥＥＥ—Ｃｓ３３６～３４５．［５］李建中，孙文隽，陈庆奎．并行关系数据库原型系统［１］ＰｆｉｓｔｅｒＧ．Ｒ￡靶扭ｒ曲０，ａ伽６船［Ｍ］．ＮＪ：Ｐｒ朗ｔｉｃｅｅｄ．，１９９８．ＨＡＬＬ阿ｔ，２ｎｄ栅的数据查询语言和系统结构［Ｊ］．计算机科学，１９９８。（１０）：２８２～２８５．［２］陈庆奎，李建中．集群并行环境下的并行ＪＯＩＮ算法万方数据
