Digit pipelined arithmetic on fine-grain array processors

Chetana Nagendra, Robert Michael Owens, Mary Jane Irwin

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


In this paper, we present a novel scheme for performing fixed-point arithmetic efficiently on fine-grain, massively parallel, programmable architectures including both custom and FPGA-based systems. We achieve an O(n) speedup, where n is the operand precision, over the bit-serial methods of existing fine-grain systems such as the DAP, the MPP and the CM2, within the constraints of regular, near neighbor communication and only a small amount of on-chip memory. This is possible by means of digit pipelined algorithms which avoid broadcast and which operate in a fully systolic manner by pipelining at the digit level. A base 4, signed-digit, fully redundant number system and on-line techniques are used to limit carry propagation and minimize communication costs. p ]Although our algorithms are digit-serial, we are able to match the performance of the bit-parallel methods, while retaining low communication complexity. Reconfigurable hardware systems built using field programmable gate arrays (FPGA's) can share in the speed benefits of these algorithms. By using the organization of logic blocks suggested in this paper, problems of placement and routing that exist in such systems can be avoided. Since the algorithms are amenable to pipelining, very high throughput can be obtained.

Original languageEnglish (US)
Pages (from-to)193-209
Number of pages17
JournalJournal of VLSI Signal Processing
Issue number3
StatePublished - Apr 1995

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Electrical and Electronic Engineering


Dive into the research topics of 'Digit pipelined arithmetic on fine-grain array processors'. Together they form a unique fingerprint.

Cite this