The availability of dedicated computation in silicon has been responsible for the explosive growth of consumer applications that require transmission and storage of data of various forms. Sophisticated algorithms implemented in hardware make it possible to encode, compress and encrypt data to facilitate both the communication and storage of such data at much higher levels of performance. ANSI C/C++ is the language of choice for developing and numerically refining algorithms.
Some algorithms inherently operate on integers (as in a Reed-Solomon encoder) or operate on values that are ideally real (as the coefficients of a digital filter) and that are approximated using floating-point or fixed-point types. In the early phases of algorithm development, the C floating-point type float or double are often used as they provides a large dynamic range that is suitable for many applications Fig 1.
1. Modeling a FIR filter using the C-built-in type 'float'.
(Click this image to view a larger, more detailed version)
The algorithm is then numerically refined to use fixed-point arithmetic to reduce the complexity of the final hardware or software implementation. In hardware, constraining the integer or fixed-point arithmetic to the smallest bit width possible is essential to meet performance, area, and power requirements. If the implementation is to utilize DSP processors, constraining the arithmetic to the available integer or fixed-point arithmetic allows the use of the least expensive processor for the given application.
Modeling fixed-point arithmetic may be done using either floating-point or integer data types that are built-in in the C language. Doing so, however, requires explicit coding and is limited to the largest integer and floating-point types available in C: 64-bit integers or 53-bit mantissas. These limits translate into more complex limits for the bit widths of the operands. For instance, multiplying two 33-bit numbers surpasses the numerical range of a 64-bit C integer. Fig 2 shows the FIR filter but with the precision of variable temp constrained to a fixed-point accuracy of 15 bits, 10 of which are integer bits. In two's complement representation, bits to the right of the LSB are thrown away (quantization mode is truncation) and bits to the left of the MSB are thrown away (overflow mode is wrap). It should be noted that the models using float (or double) are limited in precision, and are not synthesizable. Also the exact bit-accurate definition of rounding modes is difficult for operators such as division, since the built-in floating-point rounding will be applied first.
2. Modeling fixed-point behavior using 'float'.
(Click this image to view a larger, more detailed version)
While many algorithms can be written using the precision of native C datatypes, it is highly desirable to support arbitrary-length integer and fixed-point arithmetic, much in the same way hardware description languages (HDLs) such as VHDL and Verilog support logic vectors of arbitrary lengths. Increasingly the C/C++ language is used as input to High-Level Synthesis and Verification tools and flows and it is essential that the language be equipped with a library of data types that cover the needs for a wide range of current and future applications. The support of arbitrary-length types enables a uniform definition of the behavior of the data types and of algorithmic IP written using them. Uniform semantics avoid complicated corner cases that are a result of artificial implementation limits.
Algorithmic C datatypes
Algorithmic C (AC) datatypes are a class-based C++ library that provides arbitrary-length integer and fixed-point types. These free, openly-accessible types provide a number of advantages including uniform and well-defined semantics as well as runtime speeds that approach the speed of built-in C/C++ data types. The algorithmic data types also provide a speedup of 10× or more in runtime compared to the comparable types in SystemC. The datatypes can be used in any C++ or SystemC specification and have fully synthesizable semantics.
Semantics
Uniformity and consistency of semantics are key to avoiding functional errors in the algorithm. The following example, based on the author's own experience, illustrates the point:
The variable ActLength was known to between 1 and 255, so in case synthesis was not able to figure out the range (and optimize accordingly), its declaration was changed from int to the more constrained type sc_uint<8>. Synthesis gave better results, but the design no longer simulated correctly (this was one change out a whole set of numerical refinements that were done at once). After some debugging, the source of problem was found: the comparison k >= ActLength becomes a comparison between an int (signed) and an unsigned long long (64-bit unsigned integer which is the base type of the sc_uint type). The explanation: the C/C++ integer promotion rules prescribe that the int operand is promoted to an unsigned long long before the comparison is performed. For instance, if k had a value of –1, after promotion to unsigned long long, it would become 2^64 – 1.
Corner cases in semantics may be quite subtle and bit-width dependent. For example, one may try to extend the bit-widths of an existing algorithm, only to find out that results are not quite what are expected. There also could be platform dependencies. For example 1 << 32 (both operands are of type int, result is of type int) could be expected to return 0, but in most platforms/compilers it returns 1 (no shift, since only the lower five bits of the second operand are taken into account). When the first operand is a 64-bit integer, platform dependencies tend to show up more frequently. The primary problem is that the C/C++ standards do not specify the behavior when the shift value (second operand) is outside of the range 0-to-31 for 32-bit integers and outside 0-to-63 for 64-bit integers. Unfortunately, datatypes such as sc_int / sc_uint do not shield users from such platform dependencies.
The Algorihtmic C Datatypes were designed to provide uniform and consistent semantics so that they are predictable. For example, mixing signed an unsigned operands deliver the expected results. The types are arbitrary-length so there are no corner cases introduced by precision limits. All operations – including shifts and division – have been fully and consistently defined. Mixing types gives predictable results. For example, the expression x+y and y+x will return the same result when x is a C built-in type and y is an AC type.
