Wide-Area Grid Cluster for Parallel Optimization

用于并行优化的广域网格集群

基本信息

批准号：
12480068
负责人：
MATSUOKA Satoshi
金额：
$ 8万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12480068/
关键词：
Grid Wide -Area High -Performance Ninf Cluster Numerical Optimization Semi-Definite Programming SDP Non-Convex Quadratic Optimization SCRM クラスタ計算機並列化 Gridコンピューティング性能評価

项目摘要

We employ the so-called Grid technology to construct a fleet of compute nodes as an aggregation of computing cluster nodes over a wide-area network, and using such "federation of cluster resources" attempt to tackle non-convex quadratic optimization problems of unprecedented scale, and made it accessible from throughout the Internet. More specifically, we developed an algorithm called SCRM (Successive Convex Relaxation Method) which is heavily based on using large numbers of SDP (Semidefinite Programming, SDP) subsolvers, which itself is called SDPA and is a very fast SDP solver using the Interior Point Methods. By efficiently spreading out the SDP solvers over the Grid we showed that we can solve non-convex quadratic problems of very large scale very efficiently, achieving almost linear speedup. For this purpose, we have constructed a fleet of PC clusters spread out throughout several locations, including Titech Oo-okayama Campus, Titech Suzukake-dai Campus, and Kyoto University. We h … More ave been able to achieve nearly 100-fold speedup using 128 processors. The key issue was not only the algorithm but efficient programming using the Ninf GridRPC system, which had to be modified extensively as well as new programming methodologies had to be 4eyeloped in order to cope with massive parallel execution of hundreds of tasks over the Grid.More specifically, we parallelized SDPA with OpenMP using worksharing methodology to achieve nearly perfect parallel speedup for each cluster on the Grid. Also, we automated the process of selecting the best solver based on the data structure of the problem as well as the "shape" of the non-zero elements in the problem matrix. Then using the 256 nodes worth of clusters spread out over the -country, and using the Ninf GridRPC middleware, we constructed a "optimization solver server", achieving good speedup as mentioned above. The result not only set several world records for benchmark problems but also lead to even larger Grid research in the coming years. Less

我们采用了所谓的网格技术来构建计算节点的车队，作为在大区域网络上的计算群集节点的聚集，并使用这种“集群资源联合会”试图解决非convex二次优化问题的前所未有的规模，并使其可以从整个Internet上访问。更具体地说，我们开发了一种称为SCRM（连续的凸弛豫方法）的算法，该算法是基于使用大量SDP（半芬矿编程，SDP）亚种的算法，该算法本身称为SDPA，它是一种使用内点方法的SDP求解器。通过有效地将SDP求解器分配到网格上，我们表明我们可以非常有效地解决非常大规模的非凸二次问题，从而实现了几乎线性的加速。为此，我们建造了一组PC群集，包括Titech Oo-Okayama校园，Titech Suzuki-Dai校园和京都大学。我们……更多的Ave能够使用128个处理器实现近100倍的速度。 The key issue was not only the algorithm but efficient programming using the Ninf GridRPC system, which had to be modified extensively as well as new programming methods had to be 4eyeloped in order to cope with massive parallel execution of hundreds of tasks Over the Grid.More specifically, we parallelized SDPA with OpenMP using workshop methodology to achieve nearly perfect parallel speedup for each cluster on the Grid.此外，我们根据问题的数据结构以及问题矩阵中非零元素的“形状”选择了最佳求解器的过程。然后，使用256个节点的群集散布在 - 乡村，并使用NINF Gridrpc中间件，我们构建了一个“优化的求解器”服务器，实现了良好的加速，如上所述。结果不仅设定了一些世界记录的基准问题，而且在未来几年内导致更大的网格研究。