Wide-Area Grid Cluster for Parallel Optimization

我们使用所谓的网格技术来构建一队计算节点，将其作为计算集群节点在广域网上的聚合，并使用这种集群资源联邦来尝试解决规模空前的非凸二次优化问题，使其可以从整个Internet访问。更具体地说，我们开发了一种称为连续凸松弛方法(SCRM)的算法，该算法在很大程度上基于使用大量的SDP(Semidefinition Programming，SDP)子求解器，该算法本身被称为SDPA，是一种使用内点方法的非常快速的SDP求解器。通过在网格上高效地展开SDP求解器，我们证明了我们可以非常有效地求解非常大规模的非凸二次问题，获得近似线性的加速比。为此，我们已经建立了一支PC集群车队，分布在多个地点，包括TiTech Oo-Okayama校区、TiTech Suzukake-dai校区和京都大学。我们有…更多的人已经能够使用128个处理器实现近100倍的加速。关键问题不仅是算法问题，而且是使用NINEF GridRPC系统进行高效编程的问题。为了应对网格上数百个任务的大规模并行执行，必须对其进行广泛的修改并开发新的编程方法。更具体地说，我们使用工作共享方法将SDPA和OpenMP并行化，从而为网格上的每个集群获得近乎完美的并行加速比。此外，我们还根据问题的数据结构以及问题矩阵中非零元素的“形状”自动选择最佳求解器的过程。然后利用分布在全国各地的256个节点的集群，利用NINEF 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