Area Efficient Architecture And Algorithm For Evaluation Of Arithmetic Expressions

V. Saravanan*, M. Vadivel**
* Research Scholar, SRR Engineering College, Chennai, India.
** Research Scholar, Sathyabama University, Chennai, India.
Periodicity:September - November'2011
DOI : https://doi.org/10.26634/jele.2.1.1585

Abstract

This paper presents an algorithm and architecture that facilitate the area-efficient evaluation of arithmetic expressions using deeply pipelined floating-point cores. Due to technological advances, it has become possible to implement ?oating point cores on FPGAs in an effort to provide hardware acceleration for the myriad applications that require high performance ?oating-point arithmetic. However, in order to achieve a high clock rate, these ?oating-point cores must be deeply pipelined. Due to this deep pipelining and the complexity of ?oating-point arithmetic, ?oating-point cores use a great deal of the FPGA’s area. It is thus important to use as few ?oating-point cores in architecture as possible. However, the deep pipelining makes it difficult to reuse the same ?oating-point core for a series of ?oating-point computations that are dependent upon one another. Our Results show the correctness of the algorithm and that the performance achieved is far superior to that of other techniques. Beyond area efficiency, this design has several benefits, including high throughput and a low memory space requirement. Because it only needs to receive one input per clock cycle, it also has a low I/O bandwidth requirement. Because of the low area and the low bandwidth requirement, it is possible to implement multiple copies of the architecture in a single design.

Keywords

floating point, pipelined, bandwidth.

How to Cite this Article?

V. Saravanan and M. Vadivel (2011). Area Efficient Architecture And Algorithm For Evaluation Of Arithmetic Expressions. i-manager’s Journal on Electronics Engineering, 2(1), 58-64. https://doi.org/10.26634/jele.2.1.1585

References

[1]. D. Bader, S. Sreshta, & N. Weisse-Bernstein (2002). “Evaluating arithmetic expressions using tree contraction: A fast and scalable parallel implementation for symmetric multiprocessors (SMPs),” In Proceedings of the 9th International Conference on High Performance Computing, ser Lecture Notes in Computer Science, vol. 2552, December, pp63–75.
[2]. L. Zhuo & d V. K. Prasanna, (2005). “Design tradeoffs for BLAS operations on reconfigurable hardware,” in Proceedings of the 34th International Conference on Parallel Processing, June.
[3]. “Sparse matrix-vector multiplication on FPGAs,” in Proceedings of the Thirteenth ACM International Symposium on Field-Programmable Gate Arrays, February. 2005.
[4]. A. V. Kozlov & J. P. Singh, (1994). “A parallel Lauritzen- Spiegelhalter algorithm for probabilistic inference,” in Supercomputing '94: Proceedings of the ACM/IEEE conference on Supercomputing, 1994, pp. 320-329.
[5]. M. Penner & V. K. Prasanna, (2001). “Cache friendly implementations of transitive closure,” In Proceedings of International Conference on Parallel Architectures and Compilation Techniques, September.
[6]. G. L.Miller and J. H. Reif, (1985). “Parallel tree contraction and its application,” In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, October, pp. 478–489.
[7]. R. Cole & U. Vishkin, (1988). “The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time,” Algorithmica, Vol. 3, pp. 329–346,
[8]. A. M. Gibbons & W. Rytter, (1989). “Optimal parallel algorithms for dynamic expression evaluation and context- free recognition, ” Information and Computation, Vol. 81, pp. 32–45.
[9]. J. J´ aJ´ a, (1992). An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company,
[10]. B. Pradeep and C. S. R. Murthy, (1994). “Parallel arithmetic expression evaluation on reconfigurable meshes,” Computer Languages, Vol. 20, No. 4, pp. 267–277.
[11]. F. E. Sevilgen, S. Aluru, & N. Futamura. (2005). “Parallel algorithms for tree accumulations, ” Journal of Parallel and Distributed Computing, Vol. 65, No. 1, pp. 85–93,
[12]. G. Lienhart, A. Kugel, & R. Manner, (2002). “Using floating-point arithmetic on FPGAs to accelerate scientific N-body simulations,” In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. IEEE Computer Society Press, April, pp. 182–191.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.