Enhanced Optimization Scheme for Parallel PDE Solver of NSL
Shûichi Ichikawa, Takamitsu Kawai, Toshio Shimada · 1998
Authors have been developing a numerical simulation environment NSL [1], which automatically generates parallel PDE (partial differential equations) solver from high-level description of problem. Two of the notable features of NSL are boundary-fitted coordinate system and multi-block method. Physical domain is mapped onto a group of rectangular computational blocks, each of which is partitioned into one or more congruent sub-blocks. Each processor takes charge of a single sub-block. Static load balancing of such system can be modeled as a combinatorial optimization, which can be solved by branch-and-bound method [2][3]. However, in this model, the number of processors (n) is required to be greater than or equal to the number of blocks (m). This restriction can be a major obstacle to handle many blocks on a modestscale parallel computer. This paper presents an enhanced scheme that works regardless of the relationship between m and n, with additional performance improvement. Basic idea is that each processor handles a few sub-blocks instead of one. Assume that each processor is equivalent and in charge of the same number of subblocks. Let this number be k. The enhanced scheme is formulated as distributing kn virtual processors among m blocks and then allocating