Quantitative Complexity Analysis of Finite Number Systems for Customized Arithmetic Processors.
Shauchi Ong · Deep Blue (University of Michigan) · 1982
To implement high-performance arithmetic processors, one would like to explore and employ the advantages of number systems as well as the innovations in computer architecture and device technology. In the past, many investigations have been devoted to characterizing various number systems. However it is generally unclear which among the astronomical number of possible number systems is best suited for implementing a given arithmetic task. An approach to support the quantitative evaluation of alternate number systems with respect to a given application and realization technology is developed and evaluated. A finite number system is a triple consisting of a symbol set (elements are called "digit vectors"), an interpretation set, a mapping between these two sets, and a set of operators (digit vector algorithms) defined on its symbol set. A set of these digit vector algorithms is proposed for conducting the design of arithmetic processors. An arithmetic design language is proposed and implemented for describing and composing these algorithms both functionally and structurally. It also facilitates the time-space complexity evaluation of algorithms. A prototype of arithmetic design system is established to demonstrate the feasibility. This includes the development of the number system matrix which is a database consisting of digit vector algorithms written in the arithmetic design language for numerous number systems. Models of complexity measure which is relevant to the VLSI implementation are presented for comparing and evaluating algorithms. Using this prototype the time-space complexity analyses of fixed-point and floating-point operations including addition/subtraction, multiplication and elementary function are conducted. Many results are derived which illustrate important aspects in the design of arithmetic processors.