FPGA implementation of a Cholesky algorithm for a shared-memory multiprocessor architecture
Department of Electrical and Computer Engineering
Master of Science
Gerbessiotis, Alexandros V.
Solving a system of linear equations is a key problem in the field of engineering and science. Matrix factorization is a key component of many methods used to solve such equations. However, the factorization process is very time consuming, so these problems have traditionally been targeted for parallel machines rather than sequential ones. Nevertheless, commercially available supercomputers are expensive and only large institutions have the resources to purchase them or use them. Hence, efforts are on to develop more affordable alternatives. This thesis presents one such approach.
The work presented here is an implementation of a parallel version of the Cholesky matrix factorization algorithm on a single-chip multiprocessor built on an APEX20K series FPGA developed by Altera. This multiprocessor system uses an asymmetric, shared-memory MIMD architecture, built using a configurable processor core called Nios, which was also developed by Altera. The whole system was developed on Altera's SOPC Development Kit using the Quartus 11 development environment.
The Cholesky algorithm is based on an algorithm described in George, et al. . The key features of this algorithm are that it is scalable and uses a "queue of tasks" approach , which ensures dynamic load-balancing among the processing elements. The implementation also assumes dense matrices in the input.
Timing, speedup and efficiency results based on experiments run on uniprocessor and multiprocessor implementations are also presented.
njit-etd2003-046 (64 pages ~ 2,369 KB pdf)
Please complete this Feedback Form to inform us about your experience using this website. It will assist us in better serving your information needs in the future. Thank You!
Created March 17, 2004