MSB-First Interval-Bounded Variable-Precision RealTime Arithmetic Unit
DOI:
https://doi.org/10.5614/itbj.ict.2010.4.1.2Abstract
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.
Downloads
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.
