ICA3PP 2000 Hong Kong December 11-13 2000 The 4th International Conference on Algorithms and Architecture for Parallel Processing ICA3PP 2000 Hong Kong December 11-13 2000 第四届“算法、结构及并行处理”国际会议 汇报分3部分： 会议概况； 并行与分布处理的发展； 部分会议论文

会 议 承 办 单 位 Deakin University, Australia City University of Hong Kong, Hong Kong The Croucher Foundation IEEE Hong Kong Section Deakin”di:kin” 第1届Brisbane布里斯班[澳大利亚东部港市](昆士兰州首府) 第2届Singapore(新加坡) 第3届Melbourne墨尔本(为澳大利亚东南部港市) ICA3PP 2000 xcyin@dislab.nju.edu.cn

1 概 述 收到来自15个国家的127篇文章 每篇文章经至少3人审阅 录用60篇 1 概 述 收到来自15个国家的127篇文章 每篇文章经至少3人审阅 录用60篇 (+4，Special session on High-Performance Data Management +9，poster papers) 高性能数据管理的主题主要是Data mining(数据挖掘) or KDD(knowledge discovery in databases) ICA3PP 2000 xcyin@dislab.nju.edu.cn

1 概述(续)——主题 Architectures, Algorithms and Networks 1 概述(续)——主题 Architectures, Algorithms and Networks Parallel Architectures and Parallel I/O Systems Interconnection Networks and Routing Parallel Algorithms Distributed Scheduling and Load Balancing Systems and Applications 本次会议涉及并行与分布计算的两大主题：一是体系结构、算法和网络，一是系统与应用 体系结构、算法和网络：         并行体系结构和并行I/O系统 互联网和路由 并行算法的设计、分析和实现（其中包括数值和非数值并行算法、同步和异步算法以及分布式算法。算法的实现、改进、时空性能分析，可扩展性分析。遗传算法GA——Genetic Algorithm、进化算法Evolution Algorithm的并行化）        分布式调度和负载平衡 ICA3PP 2000 xcyin@dislab.nju.edu.cn

1 概述(续)——主题 Systems and Applications 1 概述(续)——主题 Systems and Applications Tools and Environments for Parallel and Distributed Software Development High-performance Scientific Computing Parallel and Distributed Databases Cluster Computing Distributed and Parallel Operating Systems and Middleware Fault-tolerant Computing Parallel Processing on Web-based Systems 系统与应用：          并行和分布式软件开发工具和环境          高性能科学计算          并行和分布式数据库          机群系统       分布和并行操作系统和中间件          容错计算          基于Web的并行处理系统及应用 分成14个session，3组；123并行… ICA3PP 2000 xcyin@dislab.nju.edu.cn

1 概述(续)——Guest Speakers On-line Algorithms for Management of Heterogeneous Resource in Scalable Computing Clusters Amnon Barak, Hebrew Uni. of Jerusalem, Israel Parallel Processing and Stochastic Search: An Application in Nonlinear Constrained Optimization Benjamin Wah, Uni. of Illinois at Urbana-Champaign (President of IEEE CS) Making Internet, A Parallel Processing Machine, Faster, Cheaper, and Better Wei Zhao, Texas A&M Uni. Heterogeneous—异类；Stochastic—随机；Constrained--约束 可扩放计算机群上异类资源管理的on-line算法（ 以色列耶路撒冷希伯来人大学） 并行处理和随机搜索在非线性约束最优化中的应用（伊利诺斯州立大学） 使因特网这个并行处理机器变得更快、更便宜、更好（德克萨斯A&M大学） ICA3PP 2000 xcyin@dislab.nju.edu.cn

2 回顾—— 并行与分布计算技术的发展 PVP(或VPP)：Cray YMP 90、NEX SX 3、Fujitsu VP 2000等； 2 回顾—— 并行与分布计算技术的发展 PVP(或VPP)：Cray YMP 90、NEX SX 3、Fujitsu VP 2000等； SMP：SGI Power Challenge、Sun SPARC Center 2000、曙光1号等； MPP：Intel Paragon、IBM SP 2、Cray T3D、曙光1000、曙光2000等； DSM：Sequent的NUMA-Q、HP的SPP、SGI的Origin系列 Clusters Computational Grid Meta computing 并行和分布计算技术自20世纪60年代中期和70年代后期分别出现以来，经历了如下的演变过程： SIMDPVP并行向量处理机（共享） ；SMP对称多处理机（共享）；MPP大规模并行处理机；DSM分布共享存储； 并行和分布系统研制过程中，系统的规模可扩展性和可编程性已成为一对主要矛盾。SMP具有可编程性，不易扩展；MPP具有可扩展性，不易编程；而DSM是SMP和MPP的优势互补的产物。 (典型的DSM—Tread Marks) 计算机机群系统(Clusters)，由NOW/COW演变而来；具有“单一系统形象(single system image)”的工作站机群，特别是同构的，其本质与MPP (如IBM SP2是用机群技术构建的MPP) 。 连接分布在不同地点的各类同构或异构计算机形成的计算格网(Computational Grid) 基于Web的全球范围的元计算 ICA3PP 2000 xcyin@dislab.nju.edu.cn

2 回顾(续)——结构特性比较 属 性 PVP SMP MPP DSM COW MIMD 商用 单地址 多地址 UMA 结构类型 专用定制 2 回顾(续)——结构特性比较 属 性 PVP SMP MPP DSM COW 结构类型 MIMD 处理器类型 专用定制 商用 互连网络 定制交叉开关 总线，交叉开关 定制网络 商用网络 通信机制 共享变量 消息传递 地址空间 单地址 多地址 系统存储器 集中共享 分布非共享 分布共享 访存模型 UMA NORMA NUMA PVP并行向量处理机 ；SMP对称多处理机；MPP大规模并行处理机；DSM分布共享存储； UMA均匀存储访问；NUMA非均匀存储访问；NORMA非远程存储访问 ICA3PP 2000 xcyin@dislab.nju.edu.cn

2 回顾(续)——访存模型 DSM ICA3PP 2000 xcyin@dislab.nju.edu.cn 2 回顾(续)——访存模型 （单地址空间共享存储器）的多处理机系统； （多地址空间非共享存储器）的多计算机系统 NORMA非远程存储访问 UMA均匀存储访问；NUMA非均匀存储访问； PVP并行向量处理机 ；SMP对称多处理机； COMA全高速缓存存储访问； CC-NUMA高速缓存一致性非均匀存储访问（采用目录方式来保持各Cache之间数据一致性 ） MPP大规模并行处理机；DSM分布共享存储； DSM ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——两个侧重点 一是如何减少结点机间的通信开销 二是有关计算机机群的工作环境 一是使用新的高速网，如ATM、快速Ethernet、以及用户自行设计的专用互联网(如Myrinet) 二是设计新的精简通信协议，减少传统通信协议的层次，以减少通信开销 二是有关计算机机群的工作环境 主要研究编程环境、任务调度、负载平衡以及全局资源的管理和使用等 机群系统研究的两个侧重点 Myrinet[mirinet] ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——高效的通信系统 机群系统一般使用通用局域网连接 目前常用的局域网技术大体可以分成两类： 一类是共享介质网络，最常见的是10 Mbps或100Mbps的Ethernet； 另一类是开关网络，如155 Mbps/622 Mbps的ATM、640 Mbps/1.28Gbps的Myrinet和100 Mbps的交换式Ethernet 目前，通信系统的研究方向主要是在减小往返延迟和提高链路带宽的利用率上，实现方法有精简协议处理、开发新的通信机制和减少系统开销 在不考虑网络负载的情况下，一般使用点-点的应用程序的可见带宽和往返延迟来衡量通信系统的性能。 应用程序可见带宽说明了网络的长消息包的传输性能，虽然由于网络技术的飞速发展，网络的物理链路越来越快，但是应用程序的可见带宽比链路速度要小得多，主要原因有网卡接口的硬件限制、协议处理开销和操作系统开销。例如，Myrinet的物理链路是双向的640 Mbps，而在TCP/IP协议上点-点的应用程序可见带宽只有38 Mbps。 往返延迟是1字节或0字节数据消息包的往返传输时间，它说明了网络短消息包的传输性能。 ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——并行程序设计环境 目前研制的机群系统大多支持PVM和MPI ，在支持语言、容错及工具等方面都不完善 需要相应支持工具，比如并行调试器、性能评测工具、并行化辅助工具，它们对程序得开发效率与运行效率都有重要得作用 PVM、MPI等基于Message Passing方式的并行程序设计环境为并行程序的设计和运行提供一个整体系统和各种辅助工具。它们的功能包括提供统一的虚拟机、定义和描述通信原语、管理系统资源、提供可移植的用户编程接口和多种编程语言的支持。 目前研制的机群系统大多支持PVM和MPI，除了适应广泛的硬件平台和编程方便等特点之外，它们都是免费软件，所以在支持语言、容错及工具等方面都不完善，许多研究机构和大学正在做这方面的研究工作。 开发并行应用程序要比开发串行程序困难得多，它涉及多个处理器之间的数据交换与同步，要解决数据划分、任务分配、程序调度和性能评测等问题，需要相应支持工具，比如并行调试器、性能评测工具、并行化辅助工具，它们对程序的开发效率与运行效率都有重要的作用。目前，提供工具较完善的系统有FAUST、Express、TOPSYS和VIDE。 ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——多种并行语言的支持 已有的机群系统大多支持FORTRAN、C和C++，实现方法： 目前机群系统并行程序设计语言的研究： 主要是使用原有顺序编译器链接并行库函数，比如PVM、MPI， 加入预编译，比如Multi-thread C，MPC++ 目前机群系统并行程序设计语言的研究： 扩展原有顺序语言，提供广泛的并行语言支持，例如，清华大学可扩展机群系统的ADA、MPC++ 提供全新的并行语言，比如Occam 研究自动化并行编译方法，直接将顺序程序编译成并行代码，如UIUC的Polaris、Stanford的SUIF、复旦大学的AFT 、南大 并行程序设计语言是并行系统应用的基础，已有的机群系统大多支持FORTRAN、C和C++，实现的方法主要是使用原有顺序编译器链接并行库函数，比如PVM、MPI，或者加入预编译，比如Multi-thread C，MPC++。 目前机群系统并行程序设计语言的研究主要在三个方面：扩展原有顺序语言，提供广泛的并行语言支持，例如，清华大学可扩展机群系统的ADA、MPC++；提供全新的并行语言，比如Occam；研究自动化并行编译方法，直接将顺序程序编译成并行代码，如UIUC的Polaris、Stanford的SUIF和复旦大学的AFT。 ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——全局资源的管理与利用 有效地管理系统中的所有资源是机群系统的一个重要方面，常用的并行编程环境PVM、MPI等对这方面的支持都比较弱，仅提供统一的虚拟机 例：UC Berkeley的NOW项目中提出，在一般操作系统(Unix、Linux、Windows NT)之上建立一个全局Unix——GL Unix，以解决机群系统中的所有资源管理，包括组调度、资源分配和并行文件系统 UC Berkeley加州大学伯克利分校 有效地管理系统中的所有资源是机群系统的一个重要方面，常用的并行编程环境PVM、MPI等对这方面的支持都比较弱，仅提供统一的虚拟机。 主要原因是结点的操作系统是单机系统，不提供全局服务支持，同时也缺少有效的全局共享方法。 UC Berkeley的NOW项目中提出，在一般操作系统(Unix、Linux、Windows NT)之上建立一个全局Unix——GL Unix，以解决机群系统中的所有资源管理，包括组调度、资源分配和并行文件系统。一般认为其中的并行文件系统对提高系统的性能潜力最大，即提高I/O性能较之提高CPU速度更能增强并行系统的性能。 随着网络技术的发展，通信延迟越来越小，网络访问比本地磁盘访问要快得多。在155 Mbps的ATM网络上，读取其他结点的内存的100 MB的时间是读取本地磁盘的1/5。现在的工作站和高档PC机都配有相当多的内存(64 MB或更多)，整个机群系统的全部内存是一个很大的资源，利用其它结点的空闲内存作为本地结点的虚拟内存和文件缓存，可以节省相当多的访盘时间。 ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——其他方面的研究 广播、多播等全局操作的高效实现 DSM并行模型的支持 并行I/O的研究 ICA3PP 2000 xcyin@dislab.nju.edu.cn

3 Cluster——典型机群系统 名称 系统特点 NOW 非服务器工作站网络，主动消息、协同文件系统、全局Unix扩展 Tread Marks 软件实现的分布共享存储的工作站机群 NSCP 在通过因特网互连的3个本地机群系统上进行元计算 Globus 在由ATM连接的北美17个站点的WAN上开发元计算平台和软件 Pearl Cluster 用ATM连接，基于Unix服务器和工作站，应用于分布式多媒体和元计算 Tread [tred] Marks由Rice [rais]研制； NSCP(国家可扩放机群计划)由Chicago, Maryland, Pennsylvania共同发起； Globus由Argonne研制； Pearl Cluster(珍珠机群)由香港大学开发; 又如：Virginia的Legion计划，意在美国本土的国家虚拟计算机设施上开发元计算软件 ICA3PP 2000 xcyin@dislab.nju.edu.cn

Efficient deployment of shared memory models on clusters of PCs using the SMiLEing HAMSTER approach Martin Schulz (Germany) SMiLE(Shared Memory in a LAN-like Environment) HAMSTER(Hybrid-DSM based adaptive and modular shared memory architecture) 这篇文章提出了一种用软件和硬件混合的方法实现机群系统的共享存储。 尽管易用，共享存储方式在机群体系结构中尚未有效地实现。仅在与机器(如SMP或用户构造的CC-NUMA)紧密相关的体系结构上，共享存储方式在硬件和相应操作系统支持下才看作是自然的。 在机群中，一般不再有这种支持，因此，共享存储器的使用绝大部分是限制在软件DSM系统。此外，软件DSM系统与机器紧密相关，一般仅支持单一的程序设计模式和API，与消息传递的两个标准的API(MPI和PVM)不同，不同存储器和任务模式的系统都带有其自己的API。其结果是大幅度减少了可移植性和潜在的可重用性，也急剧增加了学习的难度。 为了有效地解决这些问题，一个通用机群范围全局存储器抽象的共享存储结构是需要的，允许快捷和简单的任意程序设计模型的实现。这个结构能有效地提供创建共享存储模式的所有任务，包括存储管理、同步、一致性控制等。 HAMSTER提供了一个在机群体系结构上带有最少的硬件DSM支持的共享存储程序设计一般的结构：底层是通过高速SAN(system area network)组合的运行Linux和Windows NT的PC机群；核心是基于SCI-VM(Scalable Coherent一致性 Interface- Virtual Memory的)混合DSM；中间层提供共享存储程序设计模型的各个独立的管理服务模块(如机群配置控制、任务管理、同步管理、一致性控制、存储器管理)；上层提供HAMSTER接口；顶层为任意共享存储器模型、共享存储应用。 ICA3PP 2000 xcyin@dislab.nju.edu.cn

Parallel Programming with Object Groups—The TACO Approach J Nolte et al (Japan) TACO——Topologies and Collections 分布对象组是一种协调并行活动的有效方法 TACO是一种利用拓扑类和C++模板的重用在机群系统上进行分布式数据并行处理的纯模板库 collections(聚集) 分布对象组是一种协调并行活动的有效方法。TACO是一种利用拓扑类和C++模板的重用进行分布式数据并行处理纯模板库。 分布式对象组上collective(聚合)操作是协调并行计算和控制分布式资源的一种有效方法。 在大多数使用通信库数据并行语言(像MPI)中，组的概念一般只是一个抽象概念，程序员必须在没有任何可信控制的情况下依赖这个概念的有效实现。因为很难发现collections(聚集)的合适的实现，对所有应用背景和所有网络体系结构下都完成得很好。 TACO通过Topology类的可重用性，给程序员一个有效的在collections之上的控制方法，揭示collection的内部结构。 TACO的Topologies是作为分布式连接的对象集合通过指向对象的全局指针实现的。 TACO的collections(聚集)是基于分布式图的，因此一个collection(聚集)可有任意用户定义的拓扑（如n维网格、lists、树等） ICA3PP 2000 xcyin@dislab.nju.edu.cn

A Reduced Communication Protocol for Network of Workstations Weimin Zheng et al FMP(fast message passing protocol) 关键技术 缓冲区管理 DMA 避免死锁 局部通信 清华大学郑纬民 介绍其设计的机群系统的通信协议FMP的关键技术 ICA3PP 2000 xcyin@dislab.nju.edu.cn

A Software Development Methodology to Support Distributed Computing Clusters David Levine et al (USA) PARSA(Prism Parallel Technologies, Inc研制的软件开发环境) 本文提出对PARSA的改进，以使其适合于利用标准程序设计语言和库来开发分布式机群软件 Methodology方法学 ICA3PP 2000 xcyin@dislab.nju.edu.cn

Parallel and Distributed Knowledge Discovery on the Grid: A Reference Architecture M Cannataro and D Talia (Italy) 介绍基于Grid的并行与分布式数据挖掘PDKD的概念 给出PDKD一个参考结构 ICA3PP 2000 xcyin@dislab.nju.edu.cn

INTERESTINGS(1) 超立方体网络上的多点广播算法 洗牌交换网络的可重排性(rearrangeability) 2D Meshes中容错多点传送Wormhole(虫蚀)路由 无全局反馈的并行无线路由 Anycast服务的QoS路由算法 ICA3PP 2000 xcyin@dislab.nju.edu.cn

INTERESTINGS(2) 求复杂矩阵特征值的动态方程的并行实现 微积分代数方程(IDAE)松弛方法加速收敛的并行处理 线路图查询的有效并行处理方法 基于PC机群的最短路径算法 分布式环境中个人身份识别的并行生物统计学计算 利用HPF求解时间依赖的Maxwell方程的高效可扩放并行实现 HPF高性能Fortran ICA3PP 2000 xcyin@dislab.nju.edu.cn

Q&C Method for Solving Large Problems in Fixed Size Processor Array X.C. Yin, L. Xie 提出一种在固定大小的阵列上解决大问题的分解及调度的一般性方法，对于问题的并行算法以及给定大小的阵列，使用分治技术得到一个调度过程来调度所分解的计算和数据。 由于在阵列计算中，数据流穿过阵列时要在正确的时间被送到正确的处理机，这给在一个固定大小的阵列上求解任意大规模的问题带来困难。因而，在阵列并行计算中对数据的分解及调度都要根据具体的问题来进行。 提出一种在固定大小的阵列上解决大问题的分解及调度的一般性方法，对于问题的并行算法以及给定大小的阵列，使用分治技术得到一个调度过程来调度所分解的计算和数据。 这种方法适用于所有的递归算法，适用于各种不同拓扑结构及形状的无须局部存储器的处理机阵列。 ICA3PP 2000 xcyin@dislab.nju.edu.cn