Adaptive methods and rectangular partitioning problem


ÖZTURAN C., Szymanski B., Flaherthy J.

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.