Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1306909831.pdf (1.44 MB)

ETD Abstract Container

Abstract Header

Load-Balancing Spatially Located Computations using Rectangular Partitions

Bas, Erdeniz Ozgun
http://rave.ohiolink.edu/etdc/view?acc_num=osu1306909831

Abstract Details

2011, Master of Science, Ohio State University, Computer Science and Engineering.
Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. Particle-in-cell simulators, ray tracing and partial differential equations are some of the applications with spatially located workload. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Balancing the load does not guarantee to minimize the total runtime of an application. In order to achieve that, one must also take into account the communication cost. Rectangle shaped partitioning inherently keeps communications small, yet one should proactively minimize them. The algorithms we propose are tested in simulation on a wide set of instances and compared to state of the art algorithm. Results show that m-way jagged partitions are low in total communication cost and practical to use.
Umit V. Catalyurek, PhD (Advisor)
Radu Teodorescu, PhD (Committee Member)
105 p.
Computer Science
matrix partitioning; load balancing; rectangular partitioning; scientific computing; high performance computing; parallel computing

Recommended Citations

Citations

  • Bas, E. O. (2011). Load-Balancing Spatially Located Computations using Rectangular Partitions [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306909831

    APA Style (7th edition)

  • Bas, Erdeniz. Load-Balancing Spatially Located Computations using Rectangular Partitions. 2011. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1306909831.

    MLA Style (8th edition)

  • Bas, Erdeniz. "Load-Balancing Spatially Located Computations using Rectangular Partitions." Master's thesis, Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306909831

    Chicago Manual of Style (17th edition)

osu1306909831
513
© 2011, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.