A distributed multi-threaded data partitioner with space-filling curve orders

Sasidharan, Aparna

Permalink

https://hdl.handle.net/2142/101580 Copy

Description

Title

A distributed multi-threaded data partitioner with space-filling curve orders

Author(s)

Sasidharan, Aparna

Issue Date

2018-07-13

Director of Research (if dissertation) or Advisor (if thesis)

Snir, Marc

Doctoral Committee Chair(s)

Snir, Marc

Committee Member(s)

• Kale, Laxmikant
• Fisher, Paul
• Dubey, Anshu

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Shared Memory, Pthreads, Distributed Memory, MPI, Adaptive Mesh Refinement, Space-filling Curves, Load Balancing, Kd-trees, Intel KNL Performance

Abstract

The problem discussed in this thesis is distributed data partitioning and data re-ordering on many-core architectures. We present extensive literature survey, with examples from various application domains - scientific computing, databases and large-scale graph processing. We propose a low-overhead partitioning framework based on geometry, that can be used to partition multi-dimensional data where the number of dimensions is >=2. The partitioner linearly orders items with good spatial locality. Partial output is stored on each process in the communication group. Space-filling curves are used to permute data - Morton order is the default curve. For dimensions <=3, we have options to generate Hilbert-like curves. Two metrics used to determine partitioning overheads are memory consumption and execution time, although these two factors are dependent on each other. The focus of this thesis is to reduce partitioning overheads as much as possible. We have described several optimizations to this end - incremental adjustments to partitions, careful dynamic memory management and using multi-threading and multi-processing to advantage. The quality of partitions is an important criteria for evaluating a partitioner. We have used graph partitioners as base-implementations against which our partitions are compared. The degree and edge-cuts of our partitions are comparable to graph partitions for regular grids. For irregular meshes, there is still room for improvement. No comparisons have been made for evaluating partitions of datasets without edges. We have deployed these partitions on two large applications - atmosphere simulation in 2D and adaptive mesh refinement in 3D. An adaptive mesh refinement benchmark was built to be part of the framework, which later became a testcase for evaluating partitions and load-balancing schemes. The performance of this benchmark is discussed in detail in the last chapter.

Graduation Semester

2018-08

Type of Resource

text

Permalink

http://hdl.handle.net/2142/101580

Copyright and License Information

Copyright 2018 Aparna Sasidharan

Owning Collections