A Novel Method For Hardware Acceleration Of Convex Hull Algorithm On Reconfigurable Hardware

Download or read book A Novel Method for Hardware Acceleration of Convex Hull Algorithm on Reconfigurable Hardware written by Kris Min and published by . This book was released on 2021 with total page 25 pages. Available in PDF, EPUB and Kindle. Book excerpt: This paper presents a novel, high speed implementation of Andrew's Convex Hull Monotone Chain software algorithm on a FPGA. Convex hull, in its simplest form, is the smallest convex polygon that contains a set of discrete points with many applications in engineering, mathematics, and science. The convex hull algorithm in it's best case has a linear time complexity, assuming data points are sorted. Our implementation targets the Zynq System on Chip platform. We accelerate the software algorithm by designing components that can work in parallel. This involves using burst transfer, dynamic branch prediction, and resource sharing. Our approach achieves a speed up of 2.18 for 4 levels of parallelism at a 100 MHz clock. Higher speed up can be attained by increasing the levels of parallelism. To the best of our knowledge, our proposed method is the only available hardware accelerated implementation that truly optimizes the hull processing datapath. This is in contrast with other competitive software acceleration which reduce the number of data points to be processed using additional preprocessing steps or increase the speedup by using high speed interface.