About me
I'm a
postgraduate student in Computer Science under the supervision of Prof Tan Tiow-Seng.
Research Interests
I am
interested in General-Purpose computation on Graphics Processing Units (GPGPU),
Parallel Algorithms, Computational Geometry, Computer Vision and programmable graphics
hardware.
Research Projects
Parallel Banding Algorithm
Parallel Banding Algorithm
is a successor of Jump Flooding Algorithm (JFA) I had
been working on since Semester 2, 2008/2009. The algorithm is by then the fastest algorithm to
calculate the distance transform
/ Voronoi diagram
in both 2D and 3D accurately.
I was in charge of the experiment and the implementation using OpenCL.
Due to the fact that NVIDIA OpenCL was not offcially released by the submission deadline,
we did not include the OpenCL
implementation part in our final paper. Mr. Cao Thanh Tung, Mr. Anis
Mohamed and Prof. Tan Tiow-Seng were my colleagues. The project was
the first truly parallel algorithm to compute the exact Voronoi diagrams, and our later was
accepted by Interactive 3D Games and Graphics (I3D2010).
More....
GPU Gridsort
I began to work on
GridSort after the PBA project was done. As the
name suggests, GridSort is a
sorting algorithm
using a 2D grid data structure.
It is the first multi-way mergesort in parallel.
The algorithm has the theoretically optimal O(N logN) total work.
However, due to the work balancing problem and highly divergent warp assignment,
this algorithm runs 20% slower than the fastest parallel algorithm published by then.
It is possible that in the future programmer can specify the warp size in CUDA without
affecting the overall performance much, from which this algorithm can greatly benefit.
Also in theory, the approach adopted in this project can inspire other multi-way merge
sorting algorithms on the GPU.
More....
Parallel Union-Find
Parallel Union-Find is a GPU algorithm aiming to solve the
connected component labeling problem,
namely, given a 2D binary digital image, how to label
different connected components uniquely, where two vertices are said to be in
the same connected component if there is a path from one to another, formed
by a sequence of adjacent vertices in the binary digital image.
I adopted a dimensional reduction merge approach to solve this problem.
This method works on both 2D and 3D. It first labels 1D components
along one axis, and uses parallel reduction manner to merge 2 adjacent
rows into one row, until the 2D plane itself is merged into. For 3D, it
keeps merging 2 adjacent slices into one, until the 3D grid itself is merge
into. In 2D, the algorithm runs faster than the fastest component labeling algirothm
on GPUs published to date for large images(4096^2, 8192^2), neck to neck
for mid-sized image(2048^2), and slower for small images(512^2, 1024^2).
This algorithm can be trivially extended to arbitrary dimension.
More....
Auto-Alignment Mapper (working title)
The Auto-Alignment Mapper is a
template matching
algorithm.
Its main scope is integrated circuit images taken from microscope cameras.
It has various
image processing capabilities to identify the polygons from an inspection image
and use these polygons details to identify the location where inspection
image matches the design.
In current integrated circuit failure analysis, the alignment is done manual.
The operator only knows the approximate region of the mask view where the
sample inspection belongs to.
The operator then move to the corresponding design region and need to manually
find the similarities in the mask view polygons and the polygons in the inspection
image to overlay the inspection image over the design.
The process is time consuming and requires an expert operator to perform the task.
The Auto-Alignment Mapper is designed using edge-detection, Hough Transform and
several other techniques in computer vision to perform this task automatically.
More....