A sample implementation for parallelizing Divide-and-Conquer algorithms on the GPU.

Area of Science:

• Computer Science
• Parallel Computing
• Algorithm Design

Background:

• Divide-and-Conquer (D&C) is a key programming pattern for efficient algorithms.
• Parallelization of D&C algorithms has been achieved on various systems.
• A generic paradigm for parallelizing D&C on Graphics Processing Units (GPUs) was developed by Tzeng and Owens.

Purpose of the Study:

• To provide a publicly available GPU implementation of the QuickHull algorithm.
• To serve as a sample and guide for parallelizing D&C algorithms on GPUs.
• To facilitate the development of efficient GPU implementations for D&C algorithms.

Main Methods:

• Following the generic paradigm proposed by Tzeng and Owens.
• Developing a new GPU implementation of the QuickHull algorithm.
• Conducting experimental evaluations to demonstrate practicality.

Main Results:

• A practical and publicly available GPU implementation of QuickHull was successfully created.
• The implementation demonstrates the effectiveness of the proposed parallelization strategy.
• Experimental results validate the efficiency and utility of the GPU implementation.

Conclusions:

• The developed GPU implementation of QuickHull is practical and serves as a valuable guide.
• The research facilitates easier development of efficient GPU-based D&C algorithms.
• This work contributes to the field of parallel algorithm design on modern hardware.