MSB-First Interval-Bounded Variable-Precision RealTime Arithmetic Unit

Yusrila Y. Kerlooza, Yudi S. Gondokaryono, Agus Mulyana

Abstract


This paper presents a paradigm of real-time processing on the lowest level of computing systems: the arithmetic unit. The arithmetic unit based on this principle containing addition, subtraction, multiplication and division operations is  described.  The  development  of  the  computation  model  is  based  on  the  Soft Computing and the Imprecise Computation paradigms, combined with the MSBFirst  and  the  Interval  Arithmetic  techniques.  Those  paradigms  and  techniques give  the  arithmetic  unit  design  the  ability  to  compute  with  precisions  as  a function  of time available or accuracy needed. The predictability of processing time and result’s accuracy are obtained by means of processing granularity of k bits and by  using look-up tables. We present an evaluation of  the operation in time  delay  and  computation  accuracy  that  shows  significant  performance improvement over conventional arithmetic unit architecture, that is,  the ability to produce  intermediate-result  during  execution  time,  to  give  certainty  in computation  accuracy  even  before  the  process  finish  time  by  providing  two intermediate-results,  which  act  as  the  lower  and  upper  bound  of  the  real  and complete computation result, and finally, gain high computation accuracy from the early time of the execution process.


Full Text:

PDF

References


Laplante, P.A., Real-Time Systems Design and Analysis, IEEE Press Wiley Interscience, 2004.

Zadeh, L.A., Soft Computing and Fuzzy Logic, IEEE Software, 11, pp. 48-56, Nov. 1994,

Liu, J.W.S., Lin, K., Shih, W., & Yu, A.C., Algorithms for Scheduling Imprecise Computations, Computer, 24, pp. 56-68, May. 1991.

Lim, C.C. & Zhao, W., Performance analysis of dynamic multitasking imprecise computation system, IEE Proceedings of Computers and Digital Techniques, 138, pp. 345-350, Sep. 1991.

Liu, J.W.S., Shih, W.S., Lin, K., Bettati, R. & J. Chung, Imprecise Computations, Proceedings of the IEEE, 82, Jan. 1994.

Huang, X. & Cheng, A.M.K., Applying imprecise algorithms to real-time image and video transmission, Proceedings of the Real-Time Technology and Applications Symposium, pp. 96, 1995.

Shih, W. & Liu, J.W.S., Algorithms for Scheduling Imprecise Computations with Timing Constraints to Minimize Maximum Error, IEEE Transactions on Computers, 44, pp. 466, , Mar. 1995.

Mora-Mora, H., Mora-Pascual, J., Garcia-Chamizo, J.M. & JimenoMorenilla, A., Real-time arithmetic unit, Real-Time Systems, 34, pp. 53-79, 2006.

Kuspriyanto & Kerlooza, Y.Y., Multiple Operand Real-Time Adder, Proceeding of SIK 2003, 2003.

Kuspriyanto & Kerlooza, Y.Y., Menuju Prosesor Waktu-Nyata: Dual Algorithms Real-Time Adder, Prosiding Seminar on Electrical Engineering (SEE), Univ. Ahmad Dahlan Yogyakarta, 2003.

Kuspriyanto & Kerlooza, Y.Y., Keandalan Unit Multioperand MSB-First Real-Time Adder Pada Operasi Penjumlahan Data Acak, Proceeding: Seminar on Intelligent Technology and Its Applications 2004 (SITIA'2004), 2004.

Kuspriyanto & Kerlooza, Y.Y., Towards New Real-Time Processor: The Multioperand MSB-First Real-Time Adder, Proceedings of the EUROMICRO Systems on Digital System Design (DSD'04), pp. 524 529, Aug. 2004.

Kerlooza, Y.Y. & Kuspriyanto, Towards Real-Time Processor: Multioperand MSB-First Minimax Addition, International Conference on Electrical Engineering and Informatics (ICEEI2007), 2007.

Kerlooza, Y.Y. & Kuspriyanto, Towards Real-Time Processor: The Implementation of Multioperand MSB-First Adder Arithmetic Unit on the Computation of y =Σ ai bi, International Conference on Electrical Engineering and Informatics (ICEEI2007), Jun. 2007.

Kerlooza, Y.Y. & Kuspriyanto, Real-Time dan Adjustable Computing, eIndonesia Initiative 2008 (eII2008), May. 2008.

Nielsen, A.M. & Kornerup, P. MSB-First Digit Serial Arithmetic, Journal of Universal Computer Science, 1, 1995.

Moore, R.E. & Yang, C.T., Interval analysis I, Lockheed Missiles and Space Co., 1959.

Moore, R.E., Interval Arithmetic and Automatic Error Analysis in Digital Computing, Department of Mathematics, Stanford University, Stanford, California, 1962.

Boche, R.E., An Operational Interval Arithmetic, IEEE-Illinois Inst. of Tech.-Northwestern Univ., Univ. of Illinois. Abstract of a paper given at National Electronics Conference, 1963.

Deng, Z. & Liu, J.W., Scheduling real-time applications in an open environment, in Proceedings of the 18th IEEE Real-Time Systems Symposium, IEEE Computer, Society Press, pp. 308–319, 1997.

Lu, Mi., Arithmetic and Logic in Computer Systems, John Wiley & Sons Inc., 2004.

Wallace C.S., A Suggestion for a Fast Multiplier, IEEE Transaction on Computers, 13, pp. 14-17, 1964.

Parhami, B., Computer Arithmetic: Algorithms and Hardware Designs, Oxford University Press, USA, 1999.




DOI: http://dx.doi.org/10.5614%2Fitbj.ict.2010.4.1.2

Refbacks

  • There are currently no refbacks.


Contact Information:

ITB Journal Publisher, LPPM – ITB, 

Center for Research and Community Services (CRCS) Building Floor 7th, 
Jl. Ganesha No. 10 Bandung 40132, Indonesia,

Tel. +62-22-86010080,

Fax.: +62-22-86010051;

e-mail: jictra@lppm.itb.ac.id.