24 May 2011

Datatypes based on 8bit chunks cut cost, but what about analysis?

Prior to the launch by IBM of its System/360, there was no consensus on what should be the basic word-length of a computer.

According to Werner Buchholz – credited with coining the word 'byte' with a 'y' to prevent accidental mutation to 'bit' – the plan was to make what is now a basic unit of computing much more flexible. During the development of Stretch – System/360's predecessor – a byte could be any packet of bits from one to eight. The Stretch architecture made it possible to address memory down to the bit level.

But Stretch was expensive and IBM needed a cheaper way to build a mainframe. One of the casualties was the programmable byte: the engineers settled on 8bits as the best compromise. Since then, we have constructed data types on a byte-by-byte basis, not because they were the best options, but because they offered the greatest memory efficiency.

From that basic word, we obtained the core datatypes of C, such as the short, int and long, together with a not entirely consistent interpretation of how they should be implemented. Typically, an int is the natural word-length of a processor: for example, 4bytes on a 32bit machine. However, this is not generally the case on an 8bit microcontroller, as an int with a maximum range of 256 values has limited usefulness.

Instead, an int will often be defined to be 2bytes long. This can lead to performance problems if int variables are used indiscriminately in a program, because 2byte operations are often much slower than native 8bit instructions. For loop counters and values known to have a small range, it often makes sense to declare them as char, but not short, variables. Somewhat confusingly, short and int datatypes are generally both 2byte.

A long is twice the size of an int. The C99 standard also has the concept of the long long: as you would expect, it has double the bytes of a long. Because of the ease with which you can implement addition and subtraction for signed numbers, two's complement is the method generally used to encode negative numerals. Generated by inverting each bit position and then adding one, the addition of a pair of two's complement variables provides the same bit pattern as the addition of two unsigned numbers with equivalent bit patterns.

For example 1 plus -2 provides the value -1 in two's complement, or 255 in unsigned form, if you assume the use of byte-wide variables. The data in an int does not have to be an integer. The radix point can be anywhere inside the variable – the programmer just needs to understand where it is and scale values as needed. The two's complement scheme still works for these formats.

Despite its efficiency, the widespread use of fixed-point two's complement representations followed some years after the development and use of its main numeric counterpart: floating-point. It was not until System/360 arrived that two's complement began to spread across the industry.
More than 20 years earlier, in the late 1930s in Berlin, Konrad Zuse built the Z1, a binary mechanical computer that used floating-point arithmetic, a format that splits the datatype into three parts to allow a much wider range of numeric values to be stored, albeit with less overall precision – at very high and low values, the gap between numbers becomes somewhat larger than a equivalent, very long fixed-point representation.

Of the three parts of a floating-point number, the first – typically a single bit – holds the sign bit. The second is reserved for the exponent. In today's machines, a single-precision, 32bit floating-point number – a float in C – stores the exponent as an unsigned 8bit value. There also has to be a way of representing negative exponents. Instead of using a value based on complements, the number is biased.

In today's floating-point formats, the exponent has to have 127 subtracted from the stored byte to come up with the right value. So, a value of 129 gives you an exponent of two. As a result, positive exponents have a leading 1, rather than negative numbers in two's-complement form. The remaining 23bit of a single-precision number is used for the fraction, or mantissa, the number to be multiplied by the exponent to give the actual number.

But there is a further complication: numbers are normalised, so they are always represented as 1.f, where f is the fraction. This makes it possible to leave out the leading one and, in effect, store 24bit of data using a 23bit value. Normalisation introduces an overhead, although this is only apparent in software-emulation libraries, as hardware can perform the search for the leading bit very quickly.

Because of normalisation, it is also necessary to compare exponents as well as mantissas to ensure the right result, even when the two values are close to each other. Although floating-point numbers are stored differently to fixed-point, many processors will convert them on the fly so they can use two's complement arithmetic to process them. Andrew Donald Booth developed an efficient way of multiplying numbers represented by two's complement in 1951 (see fig 1).



Since then, many presentations at the International Solid State Circuits Conference and other seminars have covered high-speed floating-point units that use variants of Booth's algorithm. For years, computer makers developed and used their own floating-point representations, which made it difficult to port code between architectures, particularly as certain combinations of mantissa and exponent are often used as special numbers, such as infinity, and error codes to flag up potential problems.

In the mid-1980s, while developing the 8087 coprocessor, Intel proposed the idea of developing a standard for floating-point numbers. This turned into IEEE754, which is now used by practically all microprocessor-based implementations. The standard defines several precision classes, such as the 32bit single-precision and the 64bit double-precision formats, as well as infinity, positive and negative zero and the not-a-number (NaN) code.

The NaN can be used by programs to catch errors using a simple trap handler in place of more extensive checkup code. In IEEE754, special numbers sit at either end of the exponent scale. For example, in a single-precision float, the maximum exponent is limited to +127 – using a bias value of +127 – so that 128 can be used to encode infinity and NaN codes.

At the other end, -127 (encoded as zero in the exponent field) is used to denote zeroes and numbers that do not have normalised mantissa values. These subnormal or denormalised numbers – often called 'denormals' by programmers – help to handle underflow. Without denormals, you cannot represent a number smaller than 1.0 x 2127. Any result smaller than that would be converted to zero during the normalisation stage used to keep the significand in its 1.f form.



Gradual underflow loosens this restriction and makes it possible to represent significands in the form 0.f when the exponent is zero. There is a catch with gradual underflow: most hardware floating-point units do not support it directly. Instead, they trap to much slower software handlers. Even in architectures with hardware support, gradual underflow can be slow. Very often, denormals will be seen during software profiling as sudden dips in performance.

As a result, they are very unwelcome in most embedded-control and signal-processing situations. Because high-level software tools, such as Matlab and Simulink, generate code intended to run on IEEE754 compliant hardware, embedded coprocessors [generally] implement practically all of the standard. However, NaN and underflow should only arise as errors in control algorithms, so it makes sense to perform bounds checks on values in the loop, rather than risk a trap to underflow handling that may disrupt the system's performance.



Another trick is to use a 'denormal killer': a constant that, when added and subtracted from the mantissa will, because of its limited resolution, leave it set to zero if it has underflowed. Custom processors provide the opportunity to streamline the formats if gates are scarce, even offering scope for breaking with byte-oriented datatypes. Because of its relatively poor density – circuits often take up 20 times more die space than hardwired implementations – programmable logic is a good candidate for custom datatypes.

Low-energy processors will also benefit from less overhead in numeric processing. At Imperial College, Dr George Constantinides has been working on numerical analysis to focus high precision only where it is needed. Large savings in die space can be made by operating in the fixed-point space and tuning the word width at each point in the algorithm to use only as many bits as are necessary.

The downside is this puts the onus of numerical analysis – working out exactly how much precision is needed – on the system developer. Given the trend is towards automatically generated code – and floating-point formats are easier to deal with as they do not need the radix point to be adjusted manually in the way that fixed-point formats do – only systems that need high die or energy efficiency will go down this road.

However, more automated analysis of numeric formats should be achievable. Dr Constantinides has used linear system theory to analyse the impact of datapath error as noise and calculate the error that is injected by quantising to different levels of precision. An alternative is to move into different number systems, such as logarithms.

Code that needs a lot of sequential multiplies will benefit from a move into the log space, although errors introduced by converting from linear to logs have to be taken into account. Despite the long history of standard, byte-oriented formats, there is still plenty of space to be explored in numeric formats, particularly in embedded sensor-based systems that have to take energy and die cost into account, rather than the design considerations of a 50-year-old mainframe architecture.

Author
Chris Edwards

Supporting Information

Downloads
33930\P28-30.pdf

This material is protected by Findlay Media copyright
See Terms and Conditions.
One-off usage is permitted but bulk copying is not.
For multiple copies contact the sales team.

Do you have any comments about this article?


Add your comments

Name
 
Email
 
Comments
 

Your comments/feedback may be edited prior to publishing. Not all entries will be published.
Please view our Terms and Conditions before leaving a comment.

Related Articles

Four IDEs for Kinetis support

Freescale has named four tools as featured integrated development environments ...

Sensor market back on track

Emerging markets such as the Internet of Things, wearable electronics and the ...

NFC added to certification

The Wi-Fi Alliance has updated one of its more popular product certification ...

In-flight electronics get OK

Many will feel vindicated, others surprised and a few sceptics will still be ...

Electronics Design Show 2013

When Findlay Media launched the Engineering Design Show last year, the move was ...

Researchers race to develop 5G

Mobile device users in the UK are about to be offered mouth watering deals to ...

NI Trend Watch 2014

This report from National Instruments summarises the latest trends in the ...

Mobile OS architecture trends

In this whitepaper, Intel describes its investigations in the trends of mobile ...

A better way to cloud

This whitepaper explores the factors around the shifts in cloud computing, and ...

Audio receivers from Molex

A new family of balanced armature audio receivers has been introduced by Molex.

Bluetooth Smart modules

Murata has introduced the LBCA series of ultra low power, ultra low form factor ...

Wall charger interface ic

The CHY100 from Power Integrations is an ac/dc wall charger interface ic that ...

Future World Symposium 2014

29th - 30th April 2014, Twickenham Stadium, London

BEEAs 2013

9th October 2014, 8 Northumberland, London

Engineering Design Show 2014

22nd-23rd October 2014, Jaguar Exhibition Hall, Ricoh Arena, Coventry, UK

Electronics Design Show 2013

Take a look at some of the highlights from the 2013 Electronics Design Show and ...

LTE measurements made easy

The MD8475A signalling tester is an all-in-one base station simulator ...

Accurate fuel gauges

Impedance Track fuel gauges provide precise battery monitoring under all ...

Smartwatches and Sir Clive

All the excitement about smartwatches brings to mind the Sinclair Wrist ...

You will buy a smartwatch

The announcement yesterday by Google that it is extending Android into the ...

Sony’s slide continues

Not so long ago, if you asked the legendary 'man in the street' which consumer ...

Gregg Lowe, Freescale

Freescale's new ceo tells Graham Pitcher that, while he's not 'dancing' yet, ...

Menno Treffers, WPC chairman

There are now 110 consumer electronics products that are authorised by the ...

Aurelius Wosylus, AMD

Chris Shaw discusses AMD's latest low power processors with Aurelius Wosylus.