Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Bit-level two’s complement matrix multiplication
Grover R., Shang W., Li Q. Integration, the VLSI Journal33 (1):3-21,2002.Type:Article
Date Reviewed: Oct 2 2003

Grover, Shang, and Li present a bit-level matrix multiply algorithm where products are not computed completely at the word level, but, instead, partial sums and carries in the products are sent to the accumulation operation, resulting in the removal of carry propagation from the critical path. This work extends earlier fixed-point work to fixed-point two’s complement numbers.

Bit-level dependence structures are developed for the matrix multiply algorithm, and used for mapping to a bit-level architecture. The design is proven to be time optimal and conflict free, and for word length p, the algorithm is shown to be O(log p) faster than word-level matrix multiply.

The paper is well structured, with the inclusion of background material, and the use of examples and figures to illustrate the method and hardware implementation. The text presents a good level of detail for the method, mapping, and implementation of the algorithm. This paper should be of interest to hardware developers, as well as to readers interested in algorithm design and analysis.

Reviewer:  M. Benson Review #: CR128323 (0401-0017)
Bookmark and Share
Would you recommend this review?
Other reviews under "Algorithms": Date
 Fifty years of P vs. NP and the possibility of the impossible
Fortnow L. Communications of the ACM 65(1): 76-85, 2022. Type: Article
Jun 27 2022
Integer summing algorithms on reconfigurable meshes
Nakano K., Wada R. Theoretical Computer Science 197(1-2): 57-77, 1998. Type: Article
Dec 1 1998
 New approach to design for reusability of arithmetic cores in systems-on-chip
Margala M., Wang H. Integration, the VLSI Journal 38(2): 185-203, 2004. Type: Article
Aug 17 2005

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 2004™
Terms of Use
| Privacy Policy