Mathematical model of stored logic based computation. (English) Zbl 1205.68024
Summary: Emerging VLSI and ULSI integration technologies provide new possibilities for developing computational paradigms based on memories with pre-calculated data. A memory can behave like a processor with complete functionality by simulating a classic Turing machine. By means of this stored logic based architecture, the processor adopts a simple and regular internal organization. In addition, it makes the most of the inherent features in the memories and offers the possibility of reconfiguration by writing new results inside of it. This paper reviews different possibilities to use memory elements to perform computations that would replace combinational logic processing of a given function. In this research, a computational model based on stored logic is described and interesting issues concerned with memory utilization in processing are analyzed. A small functional unit based on these notions is presented.
MSC:
| 68M07 | Mathematical problems of computer architecture |
References:
| [1] | P.P. Chu, Computation theory in a digital systems course, in: ASEE/IEEE Frontiers in Education Conf., 2002.; P.P. Chu, Computation theory in a digital systems course, in: ASEE/IEEE Frontiers in Education Conf., 2002. |
| [2] | Simon, D. R., On the power of quantum computation, SIAM Journal on Computing, 25, 1474-1483 (1997) · Zbl 0883.03024 |
| [3] | Woods, D.; Naughton, T. J., An optical model of computation, Theoretical Computer Science (2004) |
| [4] | ISSCC Roundtable, Embedded memories for the future, IEEE Design and Test of Computers, 20, 4, 66-81 (2003) |
| [5] | S. Borkar, Exponential challenges, exponential rewards — the future of Moore’s law, in: IFIP WG 10.5 Conference on Very Large Scale Integration of System-on-Chip, 2003.; S. Borkar, Exponential challenges, exponential rewards — the future of Moore’s law, in: IFIP WG 10.5 Conference on Very Large Scale Integration of System-on-Chip, 2003. |
| [6] | Areibi, S., A first course in digital design using VHDL and programmable logic, (ASEE/IEEE Frontiers in Education Conference, vol. 31 (2001)), 19-23 |
| [7] | Calazans, N. L.V.; Moraes, F. G., Integrating the teaching of computer organization and architecture with digital hardware design early in undergraduate courses, IEEE Transaction on Education, 44, 109-119 (2001) |
| [8] | Chandrakasan, A.; Bowhill, W. J.; Fox, F., Design of High-Performance Microprocessor Circuits (2001), IEEE Press |
| [9] | Hennessy, J. L.; Patterson, D. A., Computer Architecture: A Quantitative Approach (2002), Morgan Kaufmann · Zbl 0752.68014 |
| [10] | Schulte, M. J., Optimal initial approximations for the Newton-Raphson division algorithm, Computing, 53 (1994) · Zbl 0809.65004 |
| [11] | Oberman, S. F.; Flynn, M. J., Division algorithms and implementations, IEEE Transaction on Computers, 46, 8, 833-854 (1997) |
| [12] | Lang, T.; Montuschi, P., Very high radix square root with prescaling and rounding and a combined division/square root unit, IEEE Transactions on Computers, 48, 8, 827-841 (1999) · Zbl 1392.68049 |
| [13] | Antelo, E.; Lang, T.; Bruguera, J. D., Computation of \(\sqrt{} x / d\) in a very high radix combined division/square-root unit with scaling, IEEE Transactions on Computers, 47, 2, 152-161 (1998) · Zbl 1392.68038 |
| [14] | M. Ito, N. Takagi, S. Yajima, Efficient initial approximation and fast converging methods for division and square root, in: 12th IEEE Symp. Computer Arithmetic, 1995, pp. 2-9.; M. Ito, N. Takagi, S. Yajima, Efficient initial approximation and fast converging methods for division and square root, in: 12th IEEE Symp. Computer Arithmetic, 1995, pp. 2-9. |
| [15] | H. Hassler, N. Takagi, Function evaluation by table look-up and addition, in: Proc. 12th IEEE Symp. Computer Arithmetic, 1995, pp. 10-16.; H. Hassler, N. Takagi, Function evaluation by table look-up and addition, in: Proc. 12th IEEE Symp. Computer Arithmetic, 1995, pp. 10-16. |
| [16] | Wong, W. F.; Goto, E., Fast evaluation of the elementary functions in single precision, IEEE Transactions on Computers, 44, 3, 453-457 (1995) · Zbl 1040.68513 |
| [17] | P.T.P. Tang, Table Look-up algorithms for elementary functions and their error analysis, in: IEEE Symposium on Computer Arithmetic, 1991.; P.T.P. Tang, Table Look-up algorithms for elementary functions and their error analysis, in: IEEE Symposium on Computer Arithmetic, 1991. |
| [18] | D.M. Priest, Fast table-driven algorithms for interval elementary functions, in: IEEE Symposium on Computer Arithmetic, 1991.; D.M. Priest, Fast table-driven algorithms for interval elementary functions, in: IEEE Symposium on Computer Arithmetic, 1991. |
| [19] | Remes, E., Sur un procédé convergent d’approximations successives pour déterminer les polynômes d’approximation, Comptes Rendus Mathématique. Académie des Sciences. Paris (1934) · JFM 60.0211.03 |
| [20] | W.G. Horner, Philosophical Transactions of the Royal Society of London in 1819.; W.G. Horner, Philosophical Transactions of the Royal Society of London in 1819. |
| [21] | Lee, D.-U.; Mencer, O.; Pearce, D. J.; Luk, W., Automating optimized table-with-polynomial function evaluation for FPGAs, (International Conference on Field-Programmable Logic and its Applications. International Conference on Field-Programmable Logic and its Applications, LNCS, 3203 (2004)), 364-373 |
| [22] | Wong, W. F.; Goto, E., Fast evaluation of the elementary functions in simple precision, IEEE Transactions on Computers, 44, 3, 453-457 (1995) · Zbl 1040.68513 |
| [23] | Ercegovac, M. D.; Lang, T.; Muller, J.; Tisserand, A., Reciprocation, square root, inverse square root, and some elementary functions using small multipliers, IEEE Transaction on Computers, 49, 7 (2000) · Zbl 1392.65119 |
| [24] | M.J. Schulte, J.E. Stine, Symmetric bipartite tables for accurate function approximation, in: 13th IEEE Symposium on Computer Arithmetic, 1997.; M.J. Schulte, J.E. Stine, Symmetric bipartite tables for accurate function approximation, in: 13th IEEE Symposium on Computer Arithmetic, 1997. |
| [25] | Gal, S., Computing elementary functions: a new approach for achieving high accuracy and good performance, (Accurate Scientific Computations. Accurate Scientific Computations, Lecture Notes in Computer Science, vol. 235 (1986)), 1-16 · Zbl 0605.65011 |
| [26] | Gal, S.; Bachelis, B., An accurate elementary mathematical library for the IEEE floating point standard, ACM Transaction on Mathematical Software, 17, 1, 26-45 (1991) · Zbl 0900.65034 |
| [27] | J. Voider, Binary computation algorithms for coordinate rotation and function generation, Convair Report IAR-1 148 Aeroelectrics Group, 1956.; J. Voider, Binary computation algorithms for coordinate rotation and function generation, Convair Report IAR-1 148 Aeroelectrics Group, 1956. |
| [28] | R. Andraka, A survey of CORDIC algorithms for FPGA based computers, in: International Symposium on Field Programmable Gate Arrays, 1998.; R. Andraka, A survey of CORDIC algorithms for FPGA based computers, in: International Symposium on Field Programmable Gate Arrays, 1998. |
| [29] | Chen, T. C., Automatic computation of exponentials, logarithms, ratios and square roots, Numerical Computation, 16 (1972) · Zbl 0257.68057 |
| [30] | J.S. Walther, A unified algorithm for elementary functions, in: Spring Joint Computer Conference, 1971, pp. 379-385.; J.S. Walther, A unified algorithm for elementary functions, in: Spring Joint Computer Conference, 1971, pp. 379-385. |
| [31] | Mora-Mora, H.; Mora-Pascual, J. M.; García-Chamizo, JM.; Jimeno-Morenilla, A., Real-time arithmetic unit, Real-Time Systems, 34, 1, 53-79 (2006) · Zbl 1103.68305 |
| [32] | Mora-Mora, H.; Mora-Pascual, J.; Sánchez-Romero, J. L.; García-Chamizo, J. M., Partial product reduction by using look-up tables for \(M \times N\) multiplier, Integration, The VLSI Journal, 41, 4 (2008) |
| [33] | Rajsuman, R., Design and test of large embedded memories: an overview, IEEE Design and Test of Computers, 18, 3, 16-27 (2001) |
| [34] | Parhami, B., Computer Arithmetic. Algorithms and Hardware Designs (2000), Oxford University Press |
| [35] | DasSarma, D.; Matula, D. W., Measuring the accuracy of ROM reciprocal tables, IEEE Transactions on Computers, 43, 8, 932-940 (1994) · Zbl 1066.68501 |
| [36] | Parhami, B., Alternate memory compression schemes for modular multiplication, IEEE Transaction Signal Processing, 41, 1378-1385 (1993) · Zbl 0775.65030 |
| [37] | J.A. Piñeiro, M.D. Ercegovac, J.D. Bruguera, High-radix logarithm with selection by rounding, in: IEEE ASAP Conference, 2002.; J.A. Piñeiro, M.D. Ercegovac, J.D. Bruguera, High-radix logarithm with selection by rounding, in: IEEE ASAP Conference, 2002. |
| [38] | H. Nambu, K. Kanetu, K. Higeta, M. Usami, T. Kusonoki, K. Yamaguchi, N. Homma, A 1, 8 ns Access, 550 Mhz 4, 5 Mb CMOS SRAM, in: IEEE ISSCC, 1998.; H. Nambu, K. Kanetu, K. Higeta, M. Usami, T. Kusonoki, K. Yamaguchi, N. Homma, A 1, 8 ns Access, 550 Mhz 4, 5 Mb CMOS SRAM, in: IEEE ISSCC, 1998. |
| [39] | Wada, T.; Rajan, S.; Przybylski, S. A., An analytical access time model for on-chip cache memories, IEEE Journal of Solid-State Circuits, 27, 8 (1992) |
| [40] | S. Carr, Memory hierarchy management, Ph.D. Thesis, Rice University, 1993.; S. Carr, Memory hierarchy management, Ph.D. Thesis, Rice University, 1993. |
| [41] | R. Zimmermann, Binary adder architectures for cell-based VLSI and their synthesis, Ph.D. Thesis, Swiss Federal Institute of Technology, 1997.; R. Zimmermann, Binary adder architectures for cell-based VLSI and their synthesis, Ph.D. Thesis, Swiss Federal Institute of Technology, 1997. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
