Accelerating multi-media processing by implementing memoing in multiplication and division units

ABSTRACT

This paper proposes a technique that enables performing multi-cycle (multiplication, division, square-root …) computations in a single cycle. The technique is based on the notion of memoing: saving the input and output of previous calculations and using the output if the input is encountered again. This technique is especially suitable for Multi-Media (MM) processing. In MM applications the local entropy of the data tends to be low which results in repeated operations on the same datum.The inputs and outputs of assembly level operations are stored in cache-like lookup tables and accessed in parallel to the conventional computation. A successful lookup gives the result of a multi-cycle computation in a single cycle, and a failed lookup doesn't necessitate a penalty in computation time.Results of simulations have shown that on the average, for a modestly sized memo-table, about 40% of the floating point multiplications and 50% of the floating point divisions, in Multi-Media applications, can be avoided by using the values within the memo-table, leading to an average computational speedup of more than 20%.

REFERENCES

• 1: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 2: http:///www.intel.com/design/
• 3: http:~//www.digital.com/info
• 4: http://www.sgi.com/MIPS/products/rl0k
• 5: http://www.mot.com/SPS/PowerPC/products
• 6: http://www.sun.com/microelectronics/datasheets
• 7: http:/l/www.hp.com/wsg/strategies
• 8: Michie D., "Memo Functions and Machine Learning," Nature 218, pp 19-22, 1968.
• 9: L. Sterling and E. Shapiro, "The Art of Prolog, ~nd Ed.", MIT Press Cambridge MA, 1992.
• 10: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 11: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 12: Peter Soderquist , Miriam Leeser, An Area/Performance Comparison of Subtractive and Multiplicative Divide/Square Root Implementations, Proceedings of the 12th Symposium on Computer Arithmetic, p.132, July 19-21, 1995
• 13: Atkins, D.E. "Higher-radix division using estimates of the divisor and partial reminders," IEEE Trans. on Computers C-17:10, 925-934,1968.
• 14: S. Richardson, "Exploiting Trivial and Redundant Computation", Proc. of the 11th Syrup. on Computer Arithmetic, pp. 220-227, July 1993.
• 15: S. Oberman, M. Flynn, "Reducing Division Latency with Reciprocal Caches", Reliable Computing, Vol 2, no. 2, pages 147-153, April 1996.
• 16: Walter J. Price, A Benchmark Tutorial, IEEE Micro, v.9 n.5, p.28-43, September 1989 [doi>10.1109/40.45825]
• 17: http://www.netlib.org/benchweb
• 18: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 19: Robert F. Cmelik , David Keppel, Shade: A Fast Instruction Set Simulator for Execution Profiling, Sun Microsystems, Inc., Mountain View, CA, 1993
• 20: D. Argiro and C. Gage, "Khoros User's Manual," U. of New Mexico, 1991.
• 21: Manoj Franklin , Gurindar S. Sohi, Register traffic analysis for streamlining inter-operation communication in fine-grain parallel processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.236-245, December 01-04, 1992, Portland, Oregon, United States
• 22: Anil K. Jain, Fundamentals of digital image processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 23: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• 24: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 25: J. Bradley Chen , Anita Borg , Norman P. Jouppi, A simulation based study of TLB performance, Proceedings of the 19th annual international symposium on Computer architecture, p.114-123, May 19-21, 1992, Queensland, Australia

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Design, Measurement, Performance, Theory