Українська   Русский
DonNTU   Masters' portal

Abstract

Contents

Introduction

Today modern computer hardware component operates various operations on numbers that can be represented in two formats – in general and floating–point numbers. Occurrence and accumulation of computational errors in arithmetic floating–point operations is an integral part of modern computing, since the numbers in IEEE754 format represent a finite set, which is displayed on an infinite set of real numbers and step number equal to the least significant digit: h = 2Em-off. Thus the graph representation of the error and looks as shown in Figure 1. Therefore relevant and in demand is the solution to the problem of accuracy and reliability of computing by minimizing errors, their accounting and control when working with numbers in floating point format.

Figure error representation

Figure 1 – Figure error representation

In [1, p. 196-210] considered the problem of computing, caused by using the IEEE 754 standard, and provides a classification of errors with examples produce "unexpected" results. Analysis of the material showed that the format of floating point numbers can not be accurately bring real number in mind that the format contains a set of finite values (bit grid points) which is impossible to imagine an infinite set of real numbers. This factor is the main and most important disadvantage of the floating standard format that is supported and investigated in a segment of the scientific publications, for example in [2; 3].

Among other solutions to this problem include the possibility of transition from the number of "points on a number line" to the number of interval, as evidenced by the development of interval analysis [4] and the spread interval approaches for solving a wide range of applications [5]. Interval approach allows to consider computational errors, and also solves the problem of computer representation and processing of irrational (including transcendental) numbers. In studies [6; 7] highlighted the lack of transition to machine slots, as when entering values boundaries interval number in a computer memory it is necessary to re–use the real number format is the standard format floating–point single or double precision. Also disadvantages include possible growth interval.

In a series of scientific papers, the most significant of which are in [1] and [7] proposes a solution of the problem. The authors have developed postbinary representation and processing of numerical data, postbinary rounding, as well as suggest appropriate number formats.

The aim of this work is to analyze the possibilities postbinary represent numbers. Identification and analysis of the appropriateness of postbinary numbers in interval arithmetic. Within the designated analysis should offer configuration arithmetic logic unit (ALU) as an essential part of a specialized math coprocessor [8].

1. Current situation

Today, to represent numerical information floating point using the IEEE 754 standard. This standard is used in both hardware and software implementations in arithmetic. The first standard was adopted in 1985, the last option is adopted in 2008. In the revised standard from 2008 retained all binary formats from the original standard, and added three more basic standard (one binary and two decimal).

Working with floating point IEEE 754 is a reflection on mathematics theoretically set of real numbers. Therefore, it seems logical to call the number provided in the IEEE 754 standard, but this term does not reflect the actual properties of the IEEE 754 standard.

IEEE 754 standard defines the number representation of numbers in the form and extent of the mantissa. Standard representation has mantissa and the degree indicating the binary exponent of the extreme left digit mantissa. In this standard specifies formats for presenting the lengths shown in Table 1.

Table 1 – Formats for lengths

Name Common name BaseDigit E min E max E max Emax Dec
binary 16 Half precision 2 -14 +15 3.31 4.51
binary 32 Single precision 2 -126 +127 7.22 38.23
binary 64 Double precision 2 -1022 +1023 15.95 307.95
binary 128 Quadruple precision 2 -16382 +16383 34.02 4931.77
decimal 32 10 -95 +96 7 96
decimal 64 10 -383 +384 16 384
decimal 128 10 -6143 +6144 34 6144

The first thing that stands out in this table – length mantissas. Dozens exact decimals are superfluous. Nowadays metrology can measure the speed of light, and so far only a ten-digit accuracy. The technique is used by a number, usually not exceeding five decimal places. Because most of the properties mantissas standard IEEE754, especially in formats and double extended precision, virtually meaningless and is a so–called information noise. We can conclude that modern computing, based on the standard floating point IEEE754 is just noise processing. As a consequence, the output of the computing are unreliable and noisy. Isolation of a substantial part of these noises floating point man performed (for example, when planning a programmer output results) by intuition and not based on solid mathematical rules and algorithms.

Thus, the mathematical model with floating numbers may be adequate and workable only if they controlled the calculation error.

To implement this control can be used postbinary representations of numbers, and the use of interval mathematics. Value of interval arithmetic is to obtain the most reliable solutions of the original problems, taking into account possible changes of input and output values associated with the inaccuracy of floating point arithmetic. But it should be noted that for complex calculation results may be unsatisfactory, primarily because of too long intervals obtained.

One possible solution to this problem lies in the transition to postbinary computing. In this case it is possible to use the maximum technological advance that has accumulated within the interval arithmetic, but to eliminate or minimize some of the problems of interval analysis, such as those associated with the contradiction between accuracy of representation themselves boundaries interval values and factual inaccuracy of the data that they represent.

2. Postbinary representation Data

In this case it is advisable to use a single format postbinary interval (pbinary128/32ip) and double (pbinary256/64ip) accuracy [7, c. 216]. The structure of a single–precision format is shown in Figure 2.

Structure format pbinary128/32ip (Index p – postbinary coding; S, E and M – the sign of the field, of the order and mantissa; MF and CF – modifier and format code)

Figure 2 – Structure format pbinary128/32ip (Index p – postbinary coding; S, E and M – the sign of the field, of the order and mantissa; MF and CF – modifier and format code) [7, p. 207]

To encode tetralogiki in modern binary logic were proposed compliance:

Referring to Figure 2, the reporting format has two parts (conventionally left – left border, the range [127:68] and right – right border, the range [67:8]) for the description of the respective boundaries of the interval. For repose data format used in this postbinary encoding principles, and as a code system used tetracode [7, c. 53-59].

Since the structure postbinary interval boundaries for each format is identical, calculation unit ALU to support this format could be designed so that a single sample time one border of each of the two operands to perform arithmetic (or, more precisely, the interval) and logical operations. This approach corresponds to the execution of classical interval operations [4, p. 31-32]. And provides a reduction in hardware cost to build this postbinary interval arithmetic logic unit, since the actual number of used blocks may be halved.

3. Hardware model

To develop hardware model postbinary interval ALU (hereinafter ALU, PIALU) was chosen design language VHDL – hardware description language integrated circuits, which is the base language in the development of modern computing equipment. In the future, the use of VHDL for the block in question will allow to design FPGA–solutions that initially make productive research model of the device (getting waveform modeling unusual situations), and the subsequent – to fulfill its physical implementation.

The current version of PIALU assumes implementation of the four basic interval operations such as addition, subtraction, multiplication and division. Scheme PIALU displayed in Figure 3.

Block diagram of PIALU

Figure 3 – Block diagram of PIALU

Block diagram in Figure 3 is a generalized nature, but give a good idea of some of the quantitative and qualitative indicators developed by the computing device.All register into a PIALU blocks (First Operand, Second Operand, ACC) have full structural correspondence format pbinary128/32ip. Block Compare – a comparator capable of comparing two tetrakodovyh words and block Rounder – the block in which the postbinary rounding [1, p. 211-219]. Block ChOperation allows you to select the type of operation (complex, subtraction, multiplication, division) and multiplexers MX, depending on the operation and the signs of the operands, you can bring to the adder Sum operands in order. The circuit also used shifter Shifter, the flags Flags, counter CT. Battery ACC is used to implement postbinary multiplication [1, p. 254-255].

Job odnotetritnogo adder with brute force the original data is shown in Figure 4, which is fully consistent with Table postbinary addition [1, p. 103]. Where:

Time diagram of tetra–adder (animation: 670x370px, 17 frames, 3 cycles, 50kb)

Figure 4 – Time diagram of tetra–adder
(animation: 670h370px, 17 frames, 3 cycles, 50kb)

4. Expected results

The final step is to obtain a complete hardware model PIALU that will perform basic arithmetic operations (addition, subtraction, multiplication, division) with numbers represented in postbinary interval format 128/32ip, and further implementation on an FPGA board, as the implementation on the custom LSI is very expensive.

Hardware logic model will trace features postbinary arithmetic, the behavior of each individual unit when you get different sets of initial data, to evaluate the effectiveness postbinary approach.

Since, for the construction of the hardware model used language VHDL, it will move to implement the project on FPGA–solutions available in the laboratories of Donetsk National Technical University (Xilinx Spartan–3E Starter Kit). Testing and debugging for FPGA–board approach will allow for the next phase of development – physical realization of PIALU.

Conclusions

The analysis of the current state of computing floating point. Consider using interval arithmetic and especially their implementation postbinary. Proposed Use postbinary interval formats single and double precision for organizing computer's floating–point. Grounded design and implementation postbinary interval arithmetic–logic unit. Announced plans for the future.

In writing this abstract master's work is not yet complete. Final completion: December 2014. Full text of the work and materials on the topic can be obtained from the author or his manager after that date.

References

  1. Аноприенко А. Я. Тетралогика, тетравычисления и ноокомпьютинг. Исследования 2010–2012. / А. Я. Аноприенко, С. В. Иваница — Донецк: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2012. — 308 с.
  2. Юровицкий В. М. IEEE754–тика угрожает человечеству МФТИ, РГСУ, Москва. — Electronic resource. – Mode of access: http://www.yur.ru.
  3. IEEE 754 – стандарт двоичной арифметики с плавающей точкой. — Electronic resource. – Mode of access: http://www.softelectro.ru/teoriy.html.
  4. Добронец Б. С. Интервальная математика: Учеб. пособие / Б. С. Добронец; Краснояр. гос. ун–т — Красноярск, 2004. — 216 с.
  5. Moore R. E. Introduction to interval analysis. / R.E. Moore, R.B. Kearfott, M.J. Cloud — Philadelphia: SIAM, 2009. — p. 223.
  6. Аноприенко А. Я., Иваница С. В. Интервальные вычисления и перспективы их развития в контексте кодо–логической эволюции. / А. Я. Аноприенко, С. В. Иваница. // Научные труды Донецкого национального технического университета. Серия «Проблемы моделирования и автоматизации проектирования динамических систем» (МАП–2010). Выпуск 8 (168): Донецк: ДонНТУ, 2010. — С. 150–160.
  7. Аноприенко А. Я. Постбинарный компьютинг и интервальные вычисления в контексте кодо–логической эволюции. / А. Я. Аноприенко, С. В. Иваница — Донецк: ДонНТУ, УНИТЕХ, 2011. — 248 с.
  8. Анопрієнко О. Я. Принцип роботи, структура і моделювання блоку перетворювача форматів у складі постбінарного співпроцесора. / О. Я. Анопрієнко, С. В. Іваниця, С. В. Кулібаба // Міжнародний науково–технічний журнал «Інформаційні технології та комп’ютерна інженерія», № 1 (26). — Вінниця, 2013. — С. 59–65.
  9. Kahan W. Lecture Notes on the Status of IEEE Standard 754 for Binary Floating–Point Arithmetic / W. Prof. W. Kahan — Elect. Eng. & Computer Science, Berkeley, 1997 — р. 30.