Method for handling an overflow condition in a processor

A method for handling an overflow condition in a processor is disclosed. A first plurality of signal data is packed into a first memory location so as to form a first word. A second plurality of signal data is packed into a second memory location so as to form a second word. A bitwise operation is then performed between the first word and the second word to produce a result. The result of the operation is then stored in a k bit memory location so as to form a third word. The third word is then shifted left (k-9) bits. A bit mask is then obtained by arithmetic shifting the third word right (k-1) bits. A logical OR operation is then performed between the bit mask and the result.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention relates to a method for handling an overflow 
condition in a processor. 
2. Background of the Invention 
Modern computers having a superscalar architecture are able to execute 
several instructions concurrently. The superscalar approach, however, 
depends on the ability to execute multiple instructions in parallel. The 
instructions following a branch instruction have a procedural dependency 
on the branch instruction and cannot be executed until the branch is 
executed. This is true regardless of whether the branch is taken or not. 
Known bottlenecks to issuing multiple instructions include such control 
dependencies. Parallel processing is extremely important in operation 
intensive processes, particularly in real time digital video and audio 
processing. For example, in a conventional system, operations on two 
8-pixel vectors are typically performed one pixel at a time. However, this 
method requires multiple clock cycles to complete. 
Graphics and video processing are operation intensive. At the same time, 
high-speed processing is particularly important in the areas of video 
processing, image compression and decompression. Furthermore, with the 
growth of the "multi-media" desktop, it is imperative that processors 
accommodate high-speed graphics, video processing, and image 
compression/decompression to execute multimedia applications. With the 
rise in demand for these electronic devices, large quantities of data must 
be manipulated. 
Signals requiring manipulation often contain an enormous amount of 
information. For example, a digital NTSC signal generates approximately 
10.4 million pixels per second. Since each pixel contains information for 
three colors, the total amount of information is more than 30 million 
pieces of data per second. At a CPU clock rate of 200 MHz, only 20 clock 
cycles are available for processing each pixel. This results in less than 
seven clock cycles available per color component. Moreover, in order to 
provide a smooth transition during real-time video processing, it is 
necessary to process each frame prior to its display. Therefore, 
processing speed is particularly important in real-time signal processing 
applications. 
Manipulation of video and image signals is required in many applications, 
including video and image processing functions. When video signals are 
manipulated, the result may exceed a desired upper range signal magnitude. 
For example, in many applications, acceptable pixel values range from 0 to 
255. Therefore, an "overflow" occurs when the magnitude of a resulting 
video signal is greater than 255. 
Referring now to FIG. 1, a flow diagram illustrating a method for handling 
overflow in saturation mode during the processing of video signal data 
according to the prior art is shown. At step 10, a data byte from a first 
group of video image data is loaded into a first memory location. At step 
12, a data byte from a second group of video image data is loaded into a 
second memory location. Next, at step 14, the data byte from the first 
group of video image data is added to the data byte from the second group 
of video image data. At step 16, the processor causes the result of step 
14 to be written into a third memory location. Next, at step 18, the 
result is compared with an upper range signal magnitude. If the result 
exceeds the upper range signal magnitude, the upper range signal magnitude 
is transferred to the third memory location at step 20. If the sum does 
not exceed the upper range signal magnitude, execution of the final write 
operation is bypassed at step 22. The step following the branch, or 
comparison step, has a procedural dependency on the branch and cannot be 
executed until the branch is executed. This is true regardless of whether 
the branch is taken or not. A need exists in the prior art for a method 
for handling an overflow condition in a processor without the use of a 
branch. 
BRIEF DESCRIPTION OF THE INVENTION 
The present invention is directed to a method for handling an overflow 
condition in a processor. This method is achieved without the use of a 
branch instruction, resulting in a substantial increase in computation 
speed. 
A first group of signal data and a second group of signal data are selected 
to be processed. A bitwise operation is performed between the first group 
of signal data and the second group of signal data to produce a result. 
The result is stored in a k-bit memory location. Next, the result is 
shifted left (k-9) bits. Next, an arithmetic shift right (k-1) bits is 
performed upon the shifted result to create a bit mask. A logical OR is 
then performed with the bit mask and the result to obtain a signal 
magnitude. 
According to a preferred embodiment, the first group of signal data and the 
second group of signal data comprise n bits. Therefore, if the result is 
greater than an upper range signal magnitude (2.sup.n -1), the signal 
magnitude comprises the upper range signal magnitude. Otherwise, the 
signal magnitude will contain the unaltered result.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
Those of ordinary skill in the art will realize that the following 
description of the present invention is illustrative only and not in any 
way limiting. Other embodiments of the invention will readily suggest 
themselves to such skilled persons. 
According to a preferred embodiment, a first group of n bit signal data is 
added to a second group of n bit signal data to produce a result within 
the signal magnitude range of 0-(2.sup.n -1). This method is achieved 
without the use of a branch instruction. Therefore, a substantial increase 
in computation speed is achieved when used in a system capable of parallel 
processing. 
One such system is the UltraSC system. At any given time, the UltraSC 
is capable of executing as many as nine instructions simultaneously. 
Furthermore, dynamic branch prediction is used to speed the processing of 
branches. However, elimination of branch instructions is desirable since 
rnispredictions are inevitable. 
Referring now to FIG. 2, a block diagram of a representative Central 
Processing Unit implementing the present invention is shown. A Central 
Processing Unit (CPU) 24 is presented which comprises a Floating Point 
Unit 26, an Integer Execution Unit 28, a Prefetch and Dispatch Unit 30, a 
Memory Management Unit 32, a Load Store Unit 34, an External Cache Unit 
36, a Memory Interface Unit 38, and a Graphics Unit 40. The UltraSC 
graphics unit uses integer registers for addressing image data and 
floating point registers for manipulating image data. 
Pixel information in UltraSC consists of four 8-bit or 16-bit integer 
values stored in UltraSC's 64-bit registers. These four values 
represent the color (RGB) and intensity information for a pixel of a color 
image. Intermediate results for advanced image manipulation are stored as 
16- or 32-bit, fixed-data values. These fixed-data values provide enough 
precision for filtering and image computations on pixel values. Conversion 
from pixel data to the intermediate-fixed data may be achieved through the 
use of an expand operation, which converts the pixel information to a 
higher precision format for advanced graphics operations. For example, 
four 8-bit unsigned integers may each be converted to a 16-bit fixed 
value. The four 16-bit results may then be stored in a register. 
Similarly, the larger fixed data can be converted back to pixel data 
through the use of a pack instruction. For example, a 16- or 32-bit value 
can be clipped or truncated down to an 8-bit value. Both the packing and 
expand instructions are executed in one cycle. 
Instructions that execute complex graphics operations can dramatically 
increase a processor's throughput. It would be extremely beneficial to 
reduce the number of operations required by these processes. Through 
introducing instructions which execute in one cycle, a processor can 
directly support 2-D, 3-D image and video processing, MPEG-2 image 
decompression and audio processing. Moreover, through the elimination of 
branches, the advantages of a system capable of parallel processing can be 
fully realized. 
According to a presently preferred embodiment of the present invention, 
reduction of a signal magnitude to an upper range boundary in case of 
overflow is achieved without the use of a branch instruction. This method 
may be applied in the areas of video processing. For example, motion 
estimation requires computation of the sum of absolute differences between 
pixels in a current block and pixels in a reference block. Similarly, this 
method may be used in image processing functions. For example, the method 
may be used to calculate the absolute value of an image, or pixel of an 
image. Assignment of a boundary value upon occurrence of an overflow 
avoids obtaining a pixel having a brighter color intensity than desired. 
Similarly, those of ordinary skill in the art will readily recognize that 
audio signal data can be processed in a similar manner. In addition, the 
presently preferred embodiment of the present invention may be implemented 
in linear algebra functions. For example, this method may be used to 
calculate the sum of absolute values of two vectors. However, one of 
ordinary skill in the art will recognize that this method may be utilized 
in other applications. 
Referring now to FIG. 3, a flow diagram of a presently preferred embodiment 
of the present invention is shown. At step 42, a first group of n bit 
signal data is loaded into a first memory location. At step 44, a second 
group of n bit signal data is loaded into a second memory location. 
Alternatively, the first group of signal data and the second group of 
signal data may contain different numbers of bits. Next, at step 46, a 
bitwise operation is performed between the first group of signal data and 
the second group of signal data to produce a result. For example, the 
first group and the second group of data may manipulated through various 
means, such as addition or multiplication. At step 48, the result of step 
46 is stored in a third k-bit memory location. Thus, the (n+1) bit of the 
third memory location indicates whether an overflow condition has 
occurred. At step 50, the result is shifted left (k-9) bits. Thus, the 
(n+1) bit is moved to the place of the k bit, or sign bit. As a result, 
vacated bits 1 through (k-9) are filled with zeros. Next, at step 52, an 
arithmetic shift right (k-1) bits is performed upon the shifted result 
obtained in step 50 to obtain a bit mask. This arithmetic shift to the 
right fills the k most significant bits of the bit mask with the value of 
the sign bit. Thus, the bit mask will contain a "1" if an overflow has 
taken place, and "0" if the overflow has not occurred. At step 54, a 
logical OR is performed with the bit mask and the result of step 46 to 
obtain a signal magnitude within the signal magnitude range of 0-(2.sup.n 
-1). The method is completed at step 56. Therefore, if the result is 
greater than an upper range signal magnitude (2.sup.n -1), the signal 
magnitude comprises the upper range signal magnitude. Otherwise, the 
signal magnitude will contain the unaltered result. 
Thus, if an overflow has occurred, all bits of the signal magnitude are set 
to "1". However, if an overflow has not occurred, the lower n bits of the 
signal magnitude comprises the unaltered result of step 46. Thus, in the 
event of an overflow, the lower n bits of the signal magnitude will 
contain an upper range signal magnitude equal to (2.sup.n -1). For 
example, where n=8 for 8 bit signal data, the upper range signal magnitude 
equals 255. 
This method allows reduction of the sum of signal data to an upper range 
signal magnitude in case of overflow at a computation speed greater than 
may be achieved with a method requiring a branch instruction. Therefore, 
the present invention provides substantial benefits over the method 
typically used for boundary reduction in saturation mode. Moreover, this 
method is particularly enhanced when implemented on a computer capable of 
parallel processing. 
According to one alternative embodiment, the method of the present 
invention may be included in a Field Programmable Gate Architecture 
(FPGA). Similarly, according to another alternative embodiment, an 
integrated circuit design program such as VHDL may be used to create an 
equivalent integrated circuit. Those of ordinary skill in the art will 
readily recognize that the construction of logic circuits to perform 
bitwise OR operations, shift operations, and addition operations are well 
known in the art. 
While embodiments and applications of this invention have been shown and 
described, it would be apparent to those skilled in the art that many more 
modifications than mentioned above are possible without departing from the 
inventive concepts herein. The invention, therefore, is not to be 
restricted except in the spirit of the appended claims.