Wide-Area Grid Cluster for Parallel Optimization

我们采用所谓的网格技术来构建一个舰队的计算节点作为一个计算集群节点的聚合在广域网上，并使用这种“联邦集群资源”试图解决非凸二次优化问题的前所未有的规模，并使其访问从整个互联网。更具体地说，我们开发了一种称为SCRM（连续凸松弛法）的算法，该算法在很大程度上基于使用大量的SDP（半定规划，SDP）子求解器，其本身称为SDPA，是一种使用内点方法的非常快速的SDP求解器。通过在网格上有效地展开SDP求解器，我们证明了我们可以非常有效地解决非常大规模的非凸二次问题，实现几乎线性的加速。为此，我们在Titech Oo-okayama Campus、Titech Suzukake-dai Campus和京都大学等多个校区构建了PC集群。我们 ...更多信息 已经能够使用128个处理器实现近100倍的加速。关键的问题不仅是算法，但使用Ninf GridRPC系统的高效编程，这必须进行广泛的修改，以及新的编程方法必须是4 eyeloped，以科普大规模并行执行的数百个任务在Grid.More具体来说，我们并行SDPA与OpenMP使用工作共享方法，以实现近乎完美的并行加速网格上的每个集群。此外，我们还根据问题的数据结构以及问题矩阵中非零元素的“形状”自动选择最佳求解器。然后利用分布在全国各地的256个节点的集群，并使用Ninf GridRPC中间件，我们构建了一个“优化求解器服务器”，实现了上述良好的加速比。这一结果不仅为基准问题创造了几项世界纪录，而且在未来几年内将导致更大规模的网格研究。少

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