Abstract

Table of Contents

Abstract

Table of Contents

Introduction

Architectural Enhancements

SIMD Techniques

Data Path Considerations

Instruction Set Overview

Arithmetic

Conversion and Reordering

Memory

Other

Software Support

Extension Summary

Performance Analysis

Test Software

Methodology

Results

animabob

maplay

Conclusion

References

Appendix A: Tested Configurations

Compilers:

Flags:

animabob

maplay

Machine Configurations:

Introduction

Rapid advances in semiconductor process technology have created an opportunity for microprocessor manufacturers to reverse this trend. Submicron design rules of 0.35 and 0.1 um have left designers with exceptionally small die sizes with staggering gate counts. Such gains in gate count have allowed many microprocessor vendors to offer 64-bit versions of their processors in the same or smaller die area as their 32-bit counterparts. Beyond this, vendors have been unable to put this new found abundance of gates to further use. This is particularly true with RISC processors because of their lean logic cores. Hence, the response has typically been to increase the size of the on-chip caches.

Vendors have begun to realize however that this extra chip area and gate windfall can be used to implement a minimal set of multi-media extensions capable of accelerating media-intensive applications at little cost. Currently, four major vendors have shipped or are poised to ship microprocessors which have on-chip support for media processing--the processing and manipulation of digital media data types. With the advent of these media enhanced microprocessors comes the promise of significant gains in media-rich applications.

In the remainder of this paper we investigate the architectural opportunities that have allowed vendors to implement media processing on their microprocessors. Next, we cover the intrinsics of the instruction set enhancements that have been made by four vendors to their microprocessors. In particular, we look at Hewlett-Packard's Multimedia Architectural Extensions (MAX-2), Intel's Multimedia Extensions (MMX), MIPS Technologies' MIPS V instruction set and Digital Multimedia Extensions (MDMX), and Sun Microsystem's Visual Instruction Set (VIS). Finally, we look at both a qualitative and quantitative performance analysis of these media enhanced processors by modifying some code for several applications to take advantage of an extension set. We use MIPS's MIPS V and MDMX enhancements to do so.

Architectural Enhancements

The disappointing performance is not due to a flawed architecture or lack of raw computational power, but is rather due to the processor's inefficiency in dealing with digital media data types.

For example compact disc-quality digital audio uses 16-bit integer data; far smaller than a 64-bit machine word. As another example, digital video often uses red-green-blue (RGB) triplets or red-green-blue-alpha (RGBA) quadruplets, each component of which is an 8-bit integer. The inefficiency enters into play when we consider that these processors may perform only a single operation on a single set of operands in one instruction, yielding only a single result. As shown in Figure 1, with a 64-bit processor, operations on 16-bit audio samples leave 75% of the operand space unused.

Figure 1. Example of the wasted operand space in current micro-processors.
A 16-bit integer add operation is shown; the operand values are in hexadecimal.

If the usage of this wasted operand space could be maximized, the processing bandwidth of these processors could increase several-fold when operating on multimedia data types. To accomplish this, processor designers have looked to processing models found in vector processors and massively parallel multiprocessors. These techniques are discussed in the next section.

Another problem undermining the performance of today's processors in media-rich applications is that there is no support at the instruction level for the intrinsic operations which often form the inner loops of a wide range of media-based applications. True to the RISC design of many of these processors, these intrinsics are currently coded in a series of simple instructions on floating point or integer data types.

However, each of these current instructions incurs a latency of at least one cycle. By treating multimedia operations differently from floating point and integer operations the same RISC principles may be applied to derive a minimal set of operations at the instruction level that support multimedia operations. What designers have found is that many of these operations may be implemented with a latency of a single cycle, thereby reducing the amount of work performed in inner loops.

SIMD TECHNIQUES

By looking at Fig. 1, it is easy to see how we could add three additional 16-bit values to each source register, thereby obtaining four results in the destination register. Take again the example of a RGBA quadruplet. Each 8-bit component can be thought of as a subword of a 32- or 64-bit machine word. By implementing subword parallelism, these subwords can be packed into the space of a single word, and subsequent operations may be performed on the entire word. In this manner, utilization and bandwidth increase by an amount proportional to the number of subwords.

In theory, any number of arbitrarily sized subwords could be allowed. However, by keeping the sizes of subwords regular we can limit the number of possible combinations. This serves to keep the hardware as simple and fast as possible. Intel allows 2 32-, 4 16-, or 8 8-bit subwords; Hewlett-Packard allows only 4 16-bit subwords; MIPS allows 4 16- or 8 8-bit subwords¹; and Sun allows 2 32- or 4 16-bit subwords.

DATA PATH CONSIDERATIONS

MIPS and Sun both implement their multimedia extensions on processors which support a 64-bit architecture and were not encumbered by the restrictions Intel faced. Three additional features of the floating point data path make implementation there attractive [16]. First, it leaves the integer data path and registers free for address and branch computation. Second, many of the operations used in the multimedia extensions are multi-cycle and therefore more suitably map into the control structure of the floating point data path. Finally, altering the integer data path to support multimedia extensions would likely lengthen the critical path length by adding additional gate levels, forcing the designers to increase the processor's cycle time--an ill affordable design and marketing option in today's marketplace.

The importance of the first and third issues is clear. By implementing the multimedia enhancements on the integer side, contention for its functional units would increase greatly because of the frequent address calculations and variable manipulations performed there. Every time the usage of the shared data path and register set changes, the state of the registers must be saved and the integer registers reloaded. This implies a fairly large latency if it must be done frequently. By using the floating point data path and registers, which are utilized significantly less, such latencies can be minimized.

Hewlett-Packard has taken an approach opposite of the other three vendors and has implemented MAX-2 on the integer data path. They did so for several reasons. First, their designers felt that the area savings gained by not replicating integer functional units in the floating point data path outweighed the disadvantage of sharing the integer data path with address and variable calculations [8]. Second, by profiling a variety of multimedia applications, they found that 3D graphics are fairly floating point intensive. Hewlett-Packard then reasoned that it would be an obvious benefit to have both floating point and multimedia instructions executing concurrently.

Instruction Set Overview

Beyond these trivial modifications, vendors have further extended their instruction set architectures to include instructions supportive of primitive operations common to many media-based applications. However, the number and complexity of these instructions vary somewhat between the vendors.

Hewlett-Packard and MIPS have opted to adhere closely to the RISC design principles upon which their processors are based and have included a fairly simple and general set of new instructions. Any of these are applicable to any application performing operations on subword data types. Sun, however, has opted to include a slightly more aggressive set of instructions which include operations for motion estimation, edge boundary processing, and volume rendering.

In general, the instructions implemented in the various multimedia extensions can be divided into four instruction classes: arithmetic, logical, data conversion and reordering, and memory. In the following subsections, we discuss the various classes of instructions and highlight those implementations or instructions that are of particular interest.

ARITHMETIC

An interesting feature of the addition and subtraction operations offered is that of signed and unsigned saturating arithmetic [6, 8, 14]. In unsigned saturating arithmetic, rather than overflowing bit n into bit n+1, the result is clamped to the largest allowable value in the n-bit subword. Similarly, if underflow occurs, the value is clamped to zero in the unsigned case. Saturating arithmetic is useful for 3D rendering algorithms which employ Gourad shading or is beneficial in alpha blending operations [12].

Hewlett-Packard also offers an average instruction, commonly used in blending algorithms, which computes the arithmetic mean of two operands and then rounds the results. The rounding is performed to ensure precision over repeated average instructions. Although such an average operation could be easily implemented on other architectures with a vector add followed by a vector right shift, Hewlett-Packard has been able to implement it with a single cycle latency at no increase in overall cycle time.

MIPS's MIPS V and MDMX extensions offer perhaps the most flexible and varied choice of arithmetic operations. In addition to subword addition, subtraction, and multiplication, MIPS V also allows a variety of concurrent operations on two IEEE 754 single-precision floating point numbers in a single instruction. These paired-single [8] operations double the potential bandwidth of all single-precision floating point computations on MIPS processors supporting the MIPS V ISA. An additional option on subword integer computations is the ability to perform vector/scalar arithmetic. With this option, the first input register contains a vector of subwords. Using the select field of the instruction, a single subword is selected from the second source register and is used as a scalar in the operation on the vector. A similar effect can be accomplished with traditional ISAs through a series of logical operations. In [10] an example is shown in which an 88% reduction in static instruction count is realized by using a vector/scalar multiplication. By using the permute instruction in Hewlett-Packard's MAX-2 as discussed below, this effect could be replicated--requiring only an additional instruction over the MIPS approach.

Finally, to prevent the growth of operands from a smaller storage width to a larger computational width during instruction execution, the results of subword integer operations may be optionally saved to a private 192-bit accumulator on the MIPS processor under MDMX. If such an option were exercised, the results of operations on 4 16-bit subwords are promoted to 4 48-bit subwords. The results of 8 8-bit subwords are promoted to 8 24-bit subwords. A special instruction is then required to retrieve the results from the accumulator.

CONVERSION AND REORDERING

Figure 2. Examples of the merge high instruction (a) and
Hewlett-Packard's MAX-2 permute 2331 (b) instruction.

MEMORY

An exceptionally powerful operation offered in Sun's VIS is the 64 byte block load or store. This operation transfers 64 bytes between a region of memory and a set of eight consecutive floating point registers [16]. A unique feature of the transfer is that it reads or writes around the cache. Because the transfer avoids the cache, the transfer latency is dictated entirely by the access time of main memory. This operation is useful in situations in which a series of read-modify-write operations must be performed on a large block of data. In such a case, the transferred data would normally displace useful data in the cache, yet would be never used again. However, with the block transfer no cached data is displaced and the coherency of blocks matching those transferred is transparently maintained.

OTHER

Edge. The edge operation may be useful in generating masks for the partial store operation, which always begins a store on an 64-bit aligned boundary. Such masks are required in writing to non-aligned memory addresses, a requirement frequently encountered in scan-line-based rendering algorithms [16]. By setting the appropriate mask bits with the edge instruction, the partial store instruction is forced to write only to those locations enabled by the mask.

Array. The array operation enables efficient caching of and access to 3D data sets such as those used in volume rendering. The operation accomplishes this by converting a set of 3D fixed-point coordinates to a blocked-byte address. The blocked-byte address format attempts to increase the likelihood that a single cache line will contain a data element's nearest neighbors, thereby enhancing the performance of 3D image processing operations.

The 3D fixed-point coordinates are stored in a single 64-bit register. The array instruction then takes that register as an input and outputs a memory offset. The offset may then be added to the base address of the data volume, producing the address of the desired 3D data element. However, for array instructions, the limitation that the volume be of the dimensions NxNxM is imposed, where N = 2n x 64, M = m x 32, 0 <= n <= 5 and 1 <= m <= 16. These size limits are imposed so that subvolumes of an entire volume will fit within an UltraSPARC cache line or memory page.

Pixel distance. The pdist instruction implements a pixel distance calculation, such as that frequently used in MPEG video compression. The instruction performs a calculation according to Eq. 1, computing the absolute difference between 8-bit subwords in two registers and accumulating that difference.

(1)

Software Support

Regardless of whether the programmer chooses to call assembly instructions directly or call them from C macros, he or she must be prepared for a significant amount of additional coding effort. Because no high-level language support is offered, the programmer must assume the role and responsibility of many of the usual compiler tasks. In addition, none of the checks typically performed in a high-level language are available for the multimedia instructions.

Extension Summary

Vendor	MIPS	Intel	Sun	HP
Architecture	MIPS V w/ MDMX	MMX	VIS	MAX-2
Extension Feature
Operands	3-4	2	3	3
Vector Registers	32 FP	8 FP	32 FP	32 Integer
Integer Storage Sizes
8 8-bit
4 16-bit
2 32-bit
Integer Computation Sizes
8 8-bit	8- or 24-bit
4 16-bit	16- or 48-bit
2 32-bit
Arithmetic Operations
Vector/Scalar
Accumulation
Saturation
Vector Floating Point
Multiply
Multiply Add
Other Operations
Align/Expand/Pack	A,E,P	E,P	A,E,P	A
Merge/Permute	M	M	M	M,P
Distance

Table 2. Feature summary and comparison of various multimedia-extended instruction set architectures.

Performance Analysis

TEST SOFTWARE

METHODOLOGY

• Static instruction count
• Dynamic instruction count
• Floating point operation count
• Integer operation count

Using these test data sets, Table 2 summarizes the baseline performance metrics obtained by prof for each application.

Although, the most ideal performance gains might be realized by recoding both applications in their entirety, Amdahl's law as stated in Eq. 2, dictates that the greatest speedup will be realized by optimizing the most frequently executed sections of code.

(2)

To ascertain which procedures should be modified, the cumulative procedure call data reported by prof were used. In the following two sections, we discuss which procedures were modified and how those modifications were made. Finally, we present the changes in the metrics shown in Table 2 due to the modifications.

RESULTS

animabob

Using prof, we can obtain a report of the most heavily used lines of code, correlated to their high-level source statements. Table 4 lists those source lines accounting for at least 0.10% or more of usage.

for (i = 0, l = iy; i < nx; ++i, l += 4)
  {
    c2[i] = ctab + 4*cd[i];  
    v2[l] = pp; 
  }

glColor4fv(c1[0]);
glVertex3fv(v1);
glColor4fv(c2[0]);
glVertex3fv(v2);

glColor4fv(c1[2]);
glVertex3fv(v1+ 8);
glColor4fv(c2[2]);
glVertex3fv(v2+ 8);

glColor4fv(c1[1]);
glVertex3fv(v1+ 4);
glColor4fv(c2[1]);
glVertex3fv(v2+ 4);

glColor4fv(c1[3]);
glVertex3fv(v1+12);
glColor4fv(c2[3]);
glVertex3fv(v2+12);

c1 += 4; v1+= 16; c2 += 4; v2 += 16;

for (i = j = 0; j < 256; i += 4, ++j)
  {
    ctab[i  ] = cmap[j][0];
    ctab[i+1] = cmap[j][1];            
    ctab[i+2] = cmap[j][2]; 
    ctab[i+3] = cmap[j][3];
  }

c2 = cbuf + c2b;

for (i = nx / 4; i; --i)

for (j = 0; j < ny; ++j, cd += nx)

for (j = 1; j < ny1; ++j)
  {
    qdraw[j] = face[j-1] | face[j];
    build[j] = qdraw[j]  | face[j+1];
  }

switch (build[j])

i = c1b; c1b = c2b; c2b = i;

switch (qdraw[j])

if (nx & 0x1)

if (nx & 0x2)

glEnd()

maplay

The bulk of the code in compute_pcm_samples() is comprised of 16 case bodies in a switch statement, all of which share nearly identical code. The code for one of these case bodies is shown in Box 1.

 vp = actual_v + actual_write_pos;
 
 for (; i < 32; ++i)
   {
     floatreg = *vp * *dp++;    floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
     floatreg += *--vp * *dp++; floatreg += *--vp * *dp++;
 
     pcm_sample = (int)(floatreg * scalefactor);

     if (pcm_sample > 32767)
       {
         ++range_violations;
 
         if (floatreg > max_violation)
           max_violation = floatreg;
         pcm_sample = 32767;
       }
     else if (pcm_sample < -32768)
       {
         ++range_violations;
 
         if (-floatreg > max_violation)
           max_violation = -floatreg;
         pcm_sample = -32768;
       }
 
     buffer->append (channel, (int16)pcm_sample);
     vp += 15;
   }

Conclusion

Two different media-based applications were profiled and assessed for their optimizability using the MIPS V and MDMX extensions. The tests on the two different applications verify our assertion that not all multimedia applications will benefit from these extensions. In particular, our results with animabob show that offering support for these extensions in system level libraries and drivers offer a large potential for performance increases to a large number of applications in a transparent manner without requiring recoding and recompilation of user programs. The lack of high-level language and compiler support for these extensions further solidifies this argument. At the same time, our results with maplay demonstrated that performance improvements of 20% are possible with a modest amount of coding effort. Further, the high usage of floating-point operations in maplay suggests that MIPS may have a significant advantage in performance by offering vector floating point operations.

References

Appendix A: Tested Configurations

COMPILERS:

FLAGS:

animabob

maplay

MACHINE CONFIGURATIONS³:

Name	agate.lcse.umn.edu
Manufacturer	Silicon Graphics
Product	Power Onyx
Processors	4 194 MHz CPUs: MIPS R10000 Revision: 2.4 FPUs: MIPS R10010 Revision: 0.0
Data cache size	32 KB
Instruction cache size	32 KB
Secondary unified cache size	1 MB
Main memory size	2048 MB, 8-way interleaved
Operating system	IRIX-64
Version	6.2
Initialized state	Multi-user

Name	viskan.lcse.umn.edu
Manufacturer	Silicon Graphics
Product	Indy
Processors	1 150 MHz CPU: MIPS R5000 Revision: 1.0 FPU: MIPS R5000 Revision: 1.0
Data cache size	32 KB
Instruction cache size	32 KB
Secondary unified cache size	N/A
Main memory size	64 MB
Operating system	IRIX
Version	6.2
Initialized state	Multi-user

---

Are you having trouble reading the images in this document?
Download a PostScript version of this paper.

---

Last Modified Sun Jan 19 00:10:00 CST 1997 Grant Erickson / erick205@umn.edu

The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.