Investigation into a Floating Point Geometric Algebra Processor

The widespread use of Computer Graphics and Computer Vision applications has led to a plethora of hardware implementations that are usually expressed using linear algebraic methods. There are two drawbacks with this approach that are posing fundamental challenges to engineers developing hardware and software applications in this area. The first is the complexity and size of the hardware blocks required to practically realize such applications – particularly multiplication, addition and accumulation operations. Whether the platform is Field Programmable Gate Arrays (FPGA) or Application Specific Integrated Circuits (ASICs), in both cases there are significant issues in efficiently implementing complex geometric functions using standard mathematical techniques, particularly in floating point arithmetic. The second major issue is the complexity required for the effective solution of complex multi-dimensional problems either for scientific computation or for advanced graphical applications. Conventional algebraic techniques do not scale well in hardware terms to more than 3 dimensional problems, so a new approach is desirable to handle these situations. Geometric Algebra (GA) promises to unify the different approaches used in vector algebra, trigonometry, homogeneous coordinates and quaternion algebra into a single framework. Geometric Algebra provides a rich set of geometric primitives to describe points, lines, planes, circles and spheres along with simple algebraic operations instead of points and lines alone as in a conventional algebra. This ability to carry out direct operations on this rich set of primitives enables GA to be a powerful tool for solving a wide variety of problems in computer vision, graphics and robotics. In all these areas, performance is a key issue, therefore hardware architecture of GA is considered essential to meet the stringent performance requirements for these applications. In this thesis, a detailed review of the influential research in the development of GA along with the necessary fundamentals of GA is given. Subsequently a review of background relating different implementation strategies provides an important element in understanding the specific requirements and thereby developing the hardware architecture. Based on this study, an architecture was developed that is modular and scalable to higher dimensions for geometric algebra processing. In this architecture, the designer can easily specify the floating point resolution, the order of the computation and also configure the trade-offs between the hardware area and speed. The modularity and the flexibility of the interface of the architecture also provides a platform where the designer can quantify the clock cycles to the number of resources that they may have in hand for any GA based application. This architecture has been designed not only to be a stand alone core, but can also be configured and used as a coprocessor to a larger system. To demonstrate the performance and flexibility of the GA architecture presented in this thesis, the hardware has been tested extensively using a standard image processing application. The performance results obtained from these experiments are comparable to the results obtained using existing methods. It is also shown through derivations and also from the experiments that the convolution operation in the image processing application with the GA based rotor masks, belong to a class of linear vector filters. This linear vector filter can be applied to image or speech signals where vector filtering is of fundamental interest. This opens up a range of research opportunities to the growing field of color image processing. This work has explored the totally new area of GA hardware with novel aspects including the grade tracking, configurability and linearity of the hardware. From a software point of view and application development, this work has explored the development of a platform with compiler support and easier programming methods specific to the GA hardware in an FPGA based platform. This has further enabled and increased the practical significance of the work by verifying the GA techniques in a variety of real world designs. Therefore, from both points of view it has advanced the state-of-art and has opened up opportunities for further research in GA hardware