IJPAM: Volume 96, No. 2 (2014)

A GRAPH COMPUTATION ON FPGA-BASED PLATFORM

Tai-Chi Lee
Department of Computer Science and Information Systems
Saginaw Valley State University
7400 Bay Road, University Center, MI 48710, USA


Abstract. In this paper, we first exploit the nature of parallel computations in the matrix multiplications, where the computational complexity of purely software approach vs. hardware/software code-sign are compared. Then the significance of entries of powers of adjacency matrix for a given graph is presented, which led to the determination of a bipartite graph. The calculations for the powers of an adjacency matrix are computational intensive. Even with a high speed computer, the computations of powers of a matrix in general can be a long process and time consuming. So a desirable hardware implementation of matrix multiplication using FPGA-Based computing platform is proposed, see [5]. Because the highly parallel nature of matrix multiplication it makes an ideal application for using such platform. The computations are done in parallel by multipliers and adders, which are implemented on multiple FPGA boards. The major challenge of this task is I/O interfaces between PC and FPGA board. In our approach, Our matrix multiplier is modeled in VHDL and runs on an ARC-PCI FPGA board, see [1]. The purpose of the software part of our co-design system is to provide I/O to the hardware, see [3], [6]. This part is implemented on a PC with a C program and a device driver to communicate with the board. We present the performance comparison of our co-design and purely software implementation, as well as the performance comparison of existing parallel implementations.

Received: December 26, 2013

AMS Subject Classification: 68W10, 68U10

Key Words and Phrases: graph, VHDL, FPGA, co-design, multiplier, cycle

Download paper from here.




DOI: 10.12732/ijpam.v96i2.2 How to cite this paper?

Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2014
Volume: 96
Issue: 2
Pages: 175 - 188


Google Scholar; zbMATH; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).