Nguyen Truong: Geometric and Graph Algorithms on Kestrel

We study the two-dimensional convex hull problem and rectangular clipping algorithms, and the designs and performances of these algorithms on Kestrel, a parallel processor developed at UC Santa Cruz. The convex hull problem is of interests in computer vision, while clipping algorithms are of fundamental importance in graphics rendering. We propose a new CH algorithm that is specifically designed for linear SIMD machines, and takes advantage of the Systolic Shared Registers employed by Kestrel. We have yet to prove the linear complexity of this algorithm, although many test cases have allowed us to believe the algorithm is bounded. Real-time results on Kestrel will be gathered and analyzed. We take advantage of the apparent data-parallelism in the clipping algorithm, and performs all 512 (the number of processors on Kestrel) clipping operations simultaneously. We implemented Cohen-Sutherland and Liang-Barsky clipping algorithms in C, and on Kestrel, and will compare the sequential performance to the parallel one once data are collected. Base on crude analysis, we approximate an improvement by a factor of 10 for Liang-Barsky over Cohen-Sutherland on Kestrel. It is also interesting to note the Cohen-Sutherland is outperformed by the simple brute-force approach, since it contains many conditionals in its implementation. Our immediate future works are to prove the complexity bound for the convex hull algorithm, and run test cases on the Kestrel board. Long term works may involve implementing other graphics-related algorithms on Kestrel, giving it enough firepower for rendering applications.