Adaptive methods and rectangular partitioning problem
Proccedings of the Scalable High Performance Computing Conference-SHPCC-92, Williamsburg, VA, USA, ss.409-415, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Basıldığı Şehir: Williamsburg, VA, USA
- Sayfa Sayıları: ss.409-415
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Partitioning problems for rectangular domains having nonuniform workload for mesh-connected SIMD architectures are discussed. The considered rectangular workloads result from application of adaptive methods to the solution of hyperbolic differential equations on SIMD machines. A new form of the partitioning problem is defined in which sub-meshes of processors are assigned to tasks, each task being a discretized rectangular sub-domain. The work per processor (i.e. the work density) is balanced among the K sub-rectangular meshes of processors. First, a formalization of the 1D problem is given and a O(Kn3) time and (Kn2) space optimal algorithm is proposed. A more efficient heuristic algorithm is also given for the 1D problem. Finally 2D heuristics is developed by projecting the weights onto a 1D array.