Display Refresh System Having Reduced Memory Bandwidth

The present invention relates generally to display systems for computers, and more particularly to computer display refresh systems.

Increasingly, computer operating systems and application programs are becoming more graphic intensive. Bit-mapped graphics and graphical user interfaces (GUIs) can require a large rate of data transfer to update the computer display, particularly at higher resolutions and color depths.

Computer display images are typically stored and manipulated in a display memory. The data comprising the screen image itself can be conceptualized as being stored in a portion of the display memory called the screen memory. The screen memory is continually updated by a controller (usually a graphics controller under the control of a microprocessor). In a graphics mode, the screen memory size and configuration is dependent upon the resolution and bit depth of the display image. Resolution is usually defined as the number of pixels displayed, i.e. 640.times.480, 800.times.600, 1024.times.768 and others. The "bit depth" is the number of bits provided for each pixel. A larger number of bits per pixel permits a greater selection of simultaneous screen colors.

The CRT display image is repeatedly updated through a display refresh operation. Display refresh involves transferring each pixel of the display image from the display memory to an output, once per frame. For displays having high resolutions and/or large bit depths, display refresh consumes a large amount of the total available display memory bandwidth, reducing the memory bandwidth available to the controller for other purposes (the "available update bandwidth") such as updating and manipulating the display image. This results in slower display performance for users.

It is known in the prior art to overcome bandwidth reduction due to display refresh by increasing overall memory bandwidth, employing larger bus widths or faster memory bus operating frequencies. Such solutions require an overall system upgrade however. Additional memory bandwidth has also been achieved by utilizing specialized memory devices such as multi-port random access memories (often called VRAMs in video applications). However, such approaches result in systems of increased COSTS.

It is therefore desirable to arrive at a solution that reduces required display refresh bandwidth, thereby increasing available update bandwidth without incurring substantial additional costs or requiring a significant change in overall system design. By reducing required refresh bandwidth the performance of interactive graphics displays can be improved.

It is an object of the present invention to provide a graphics display system with increased available update bandwidth that does not require a substantial amount of additional memory.

It is another object of the present invention to provide a graphics display system that reduces the amount of display memory bandwidth required for display refresh.

According to the present invention the display image of a computer system is stored as a plurality of screen lines, each screen line being composed of a number of consecutive bit groups (referred to herein as addressable units). The system further includes a redundancy memory having a redundancy row line corresponding to each screen line. Each redundancy row line stores redundancy data that includes a "repeat bit" for every addressable unit in a screen line. The value of the repeat bit indicates whether or not the addressable unit is identical to the previous addressable unit. The repeat bit takes one of two states; SKIP (meaning identical to the previous addressable unit) or NONSKIP (meaning different than the previous addressable unit).

During a refresh operation each screen line is read from screen memory in consecutive addressable units. If the screen line has not been written to by the controller since the redundancy data were last computed, the redundancy data are used by a repeating circuit to repeat those addressable units that match their immediately preceding identical addressable unit, instead of fetching said addressable unit from the display memory. A NONSKIP bit indicates a new data word must be fetched from the display memory.

If the screen line has been written to since the last redundancy data were computed, the redundancy data are possibly inaccurate and therefore are not used. Rather, each addressable unit in the screen line is read and displayed. During this operation the redundancy data for that screen line are recomputed and written to the redundancy memory.

An advantage of the present invention is that it takes advantage of the large areas of constant color or regular patterns common to many GUIs.

Other objects and advantages of the invention will become apparent in light of the following description thereof.

FIG. 1 is a block schematic diagram illustrating a preferred embodiment of the present invention.

FIG. 2 is a block schematic diagram illustrating the screen memory and the redundancy data memory of the preferred embodiment of the present invention.

FIG. 3 is a block schematic diagram illustrating the row valid detect section of the preferred embodiment of the present invention.

FIG. 4 is a block schematic diagram illustrating the redundancy data section of the preferred embodiment of the present invention.

FIG. 1 shows a block schematic diagram of a display refresh system 10. The display refresh system 10 includes, generally, a screen memory 12, a row valid detect section 14, a redundancy data section 16, a refresh address modify section 18, a data output repeat section 20, and a redundancy detect section 22. In the preferred embodiment, the screen memory 12 is a portion of a total display memory 24.

A portion of the screen memory 12 of the preferred embodiment is set forth in FIG. 2. The screen memory 12 includes a number of screen rows 26, with each screen row 26 representing a line of a display image. In the embodiment shown in the figure, the display image represented has a resolution of 640.times.480 with a pixel depth of eight (8) bits. It is understood that the embodiment illustrated could be configured for many different display modes and the resolution of 640.times.480 is intended to be illustrative only. At 640.times.480 resolution each screen row is composed of 5,120 bits. The screen memory 12 is shown divided into eight bit groups representing pixel color, referred to herein as pixel color data. The various pixels are shown as Cn, where different values of n represent different eight bit combinations signifying color. In FIG. 2, the pixel data for the first 40 pixels and the last four pixels of screen rows 0, 1 and 479 are shown.

As is well known in the art, the data of the screen memory 12 are addressable by a row and column address. In the preferred embodiment, the screen memory 12 is addressable in 32-bit groups, or the equivalent data of four consecutive pixels. For the purposes of this description the 32-bit groups will be referred to hereinafter as "addressable units" (AUs). Thus, each screen row 26 of the example set forth in FIG. 2 has 160 AUs. The AUs are identified by their screen row number and column number. Further, a fixed, integral number of AUs are defined herein as "redundancy units" (RUs). In the preferred embodiment one AU is equal to one RU.

Referring now to FIG. 3 the row valid detect section 14 is set forth in more detail. As shown in the figure, the row valid detect section 14 includes a row valid buffer 30, a first row address translator 32, a second row address translator 34, an address comparator 35, a row status selector 36 and a strike detect register 37. The row valid buffer 30 includes a one bit storage location for storing a row status bit corresponding to each screen row 26 in the screen memory 12. Each bit can take either of two values; "VALID" or "INVALID" (shown as "T" and "V" respectively, in the figure). For the screen memory 12 example of FIG. 2, the row valid buffer 30 includes 480 bit locations.

The first row address translator 32 receives a write command WR, and a write address ADD.sub.WR as inputs. The write command and write address are generated by a controller during a write operation to the display memory 24. The first row address translator 32 translates the write address and provides it to the row valid buffer 30 and the address comparator 35. If a the write address corresponds to a screen row 26, the row status bit in the row valid buffer 30 corresponding to the screen row 26 written to is set INVALID. In this manner, a record is maintained of any write operations to any of the screen rows 26. Upon start-up, all of the row status bits of the row valid buffer 30 are set INVALID. In the example shown in FIG. 3, status bits are identified as "RF" where Y is the screen row 26 number. Therefore, in the example set forth, screen rows 0-2 and 4-8 currently have a valid status, while screen row 3 is invalid.

The second row address translator 34 receives a refresh address as an input, shown as ADD.sub.REF. Like the first row address translator 32, second row address translator 34 translates the refresh address and if it corresponds to a screen row 26, the screen row number information is provided as an input to the row status selector 36. According to the input from the second row address translator 34, the row status selector 36 latches the value of the row status bit (i.e., VALID or INVALID) that corresponds to the screen row 26 selected by the refresh address. This latched value is provided as an output from the row status selector 36. Following the latching operation, the row status bit within the row valid buffer is "reset" to VALID. For example in FIG. 3, if the refresh address is for screen row 2 (R2), this is detected by the second address translator 34 and the screen row number is provided to the row status selector 36. The row status selector 36, in turn, latches, and provides as an output, the VALID bit value for R2. Conversely, on the next refreshed row (row three) the INVALID row status bit is latched and provided as an output at the row status selector 36, and the row status bit is reset to VALID.

The address comparator 35 and a strike detect register 37 operate to detect when a screen row 26 that is currently being refreshed is written to by the controller. Such an event is referred to herein as a "lightning strike." The strike detect register 37 is a one bit register that is held at one of two states; STRIKE or NOSTRIKE. The strike detect register 37 receives the current refresh address as an input, and upon a change in row address (indicating a new row is to be refreshed) is set to NOSTRIKE. A second input to the strike detect register 37 is provided by the address comparator 35. The current refresh row and write address are provided as inputs to the address comparator 37. In the event these addresses are the same, a lightning strike has occurred, and the address comparator 35 provides an output that changes the strike detect register 37 to the STRIKE status. The status of the strike detect register 37 is provided as an output to the redundancy data section 16. A lightning strike also affects the row status bit initially latched by the row valid buffer 30. As shown in FIG. 3 the row status selector 36 receives the strike detect register 37 as an input. If the row status bit initially latched is VALID, a lightning strike will change the latched value to INVALID.

Referring now to FIG. 4, the redundancy data section 16 is set forth in more detail, and is shown to include a redundancy memory 38, a horizontal redundancy buffer (hereinafter "HR buffer") 40, a run length encoder 42, a buffer pointer 44, and a buffer adder 46. In the preferred embodiment, as shown in FIG. 1, the redundancy memory 38 is part of the total display memory 24.

Referring once again to FIG. 2, a more detailed depiction of the redundancy memory 38 is shown in conjunction with its corresponding screen memory 12. The redundancy data memory 38 includes a redundancy data row 48 corresponding to each screen row 26 in the screen memory 12. In a similar fashion each redundancy data row 48 includes a bit location corresponding to each RU in the screen row 26. In the example of FIG. 2, the redundancy data memory 38 has 480 redundancy data rows 48, with each redundancy data row 48 having 160 bits. It is understood that the redundancy data memory 38 is configurable, with a larger screen memory 12 having a larger corresponding redundancy data memory 38.

In FIG. 2, the bit locations within the redundancy data memory 38 are identified as "RB" and each include a row and column number that corresponds to the RU that the bit represents. Each RB is either a SKIP bit ("1") indicating that the RU it represents is identical to the previous RU in that screen row 26, or a NONSKIP bit ("0") indicating that the RU it represents is different than the previous RU within the screen row 26.

Referring once again to FIG. 2, the relationship between the screen rows 26 and their corresponding redundancy data rows 48 is shown in detail. In the preferred embodiment, the first bit of every redundancy data row 48 is always a NONSKIP bit (0) as it represents the first RU of a screen row 26 and there is no previous RU to compare it with. Thus, bits RB.sub.00, RB.sub.10, and RB.sub.479,0 of FIG. 2, are all NONSKIP bits (0s). In the example of FIG. 2, AU.sub.01, AU.sub.02, AU.sub.03, and AU.sub.04 all have the same pattern as AU.sub.00 (C0 C0 C0 C0). Accordingly, RB.sub.01, RB.sub.02, RB.sub.03 and RB.sub.04 are each SKIP bits (1s). Because AU.sub.05 (C0 C1 C1 C3) is different than AU.sub.04, bit RB.sub.05 is a NONSKIP bit (0) indicating no repetition in RU value. In this fashion each redundancy data row 48 contains redundancy data for its corresponding screen row 26. The manner in which the redundancy data are gathered for each redundancy data row 48 will be discussed in more detail herein.

Referring once again to FIG. 4 it is shown that the HR buffer 40 is coupled to the display memory 24 by data bus MD. By way of the MD data bus, the HR buffer 40 receives data from the redundancy data memory 38. In the preferred embodiment the HR buffer 40 receives the data of one redundancy data row 48. Thus, for the example of FIGS. 2 and 4, the HR buffer 40 holds 160 bits. In FIG. 4, the data of the first redundancy data row (row 0) is shown loaded in the HR buffer 40. It is understood that while the HR buffer 40 in the example in FIG. 4 stores 160 bits, the total capacity of the HR buffer 40 is sufficient to handle larger redundancy data row 48 sizes that correspond to higher display image resolutions.

As shown in FIG. 4, the HR buffer 40 is coupled to the run length encoder 42. The run length encoder 42 computes from the data in the HR buffer 40 a run length value that is the number of times an RU value is repeated consecutively in a screen row 26. In the preferred embodiment, the run length encoder 42 reads data from the HR buffer 40 according to a buffer position provided by the buffer pointer 44. A run length is then computed as the total of a first NONSKIP bit (0) and any SKIP bits (1s) that follow. For example, referring now to FIG. 4, assuming the buffer pointer 44 is pointing to the first position in the HR buffer 40, the run length encoder 42 will read the first run of bits, 01111, stopping at the next encountered NONSKIP bit (0, the sixth bit in the HR buffer 40). As mentioned previously, the first run of bits is encoded into "run length" corresponding to the NONSKIP bit (always a single "0") and the total number of SKIP bits that follow (in this case four). Thus, 01111 is encoded to 5. The run length, shown as "RL," is then provided as an output from the run length encoder 42. The run length encoder 42 is then ready to compute the next run length. The buffer pointer 44 is advanced to the next NONSKIP bit by feeding the run length to the buffer adder 46 which advances the buffer pointer 44 a number of bit locations equal to the run length. In this manner successive run lengths are computed and output from the run length encoder 42. Once all the run lengths have been read from the HR buffer 40 the data of the next redundancy data row 48 are loaded.

In the preferred embodiment, the run length encoder 42 can encode a maximum run length of 16 bits (the data representing 16 RUs), with the run length output being four bits wide. In the event the run length exceeds 16 bits in length, the 17th bit will be treated as if it is a NONSKIP bit.

Referring once again to FIG. 4, it is shown that the run length encoder 42 receives the status of the row status bit latched by the row status selector 36. It is recalled that the status of this bit indicates whether or not the currently refreshed screen row 28 has been written to (INVALID state) or not (VALID state) since the last time the redundancy data for the screen row were computed. If the status is VALID the run length encoder 42 and HR buffer 40 operate in the manner previously described. If the status in INVALID, however, the redundancy data section 22 generates new redundancy data from the current, screen row 26 and inputs it into the HR buffer 40. In addition, for an INVALID status the data within the HR buffer 40 are ignored by the run length encoder 42 and the run length encoder 42 defaults to outputting run lengths of one.

New redundancy data are generated and input into the HR buffer 40 by the INVALID status enabling a comparator input (CMP) to the HR buffer 40. When enabled, CMP writes redundancy data into the HR buffer 40. In the preferred embodiment, this is performed one bit at a time. At the beginning of the refresh of a given screen row 26, the buffer pointer 44 points to the staff of the HR buffer 40. When the CMP is enabled, as a bit of data is received from the CMP it is written into the first bit location of the HR buffer 40. By operation of the buffer adder 46, the buffer pointer 44 is advanced one location according to the run length encoder output (always one when the current row is INVALID). The HR buffer 40 is then ready to receive the next bit from the CMP. The generation of the CMP signal will described at a later point herein.

In addition to the MD and CMP inputs, the HR buffer 40 also receives the status of the strike detect register 37 (either STRIKE or NOSTRIKE). Once the HR buffer 40 contains the redundancy data for an entire screen row 26 the newly acquired redundancy data are either written to the redundancy data memory 38 or ignored depending upon the status of the strike detect register 37. A STRIKE status indicates that the screen row 28 from which the redundancy data have just been acquired has been written to during refresh. As a result, there is no guarantee the data within the HR buffer 40 are valid. Accordingly, the data within the HR buffer 40 are ignored and refresh operation continues with the next screen row 26. A NOSTRIKE status indicates that the screen row 28 has not been written to and the redundancy data within the HR buffer 40 represent the data within the refreshed screen row 26. Accordingly, the data are written to the redundancy data row 48 corresponding to the refreshed screen row 26.

Referring once again to FIG. 1, the refresh address modify section 18 of the preferred embodiment will now be described in detail. Refresh addresses are provided by the refresh modify section 18 to sequentially indicate which RUs are to be read from the screen memory 12. The refresh address modify section 18 of the preferred embodiment is shown to include a refresh adder 50 and a refresh address pointer 52. The refresh address pointer 52 provides a refresh address (ADD.sub.REF) in response to refresh positioning information (REFPOS in FIG. 1) and an adjusted address (ADD.sub.REF+). The refresh positioning information indicates the position of the screen memory 12 within the display memory 24, and includes a left upper corner address, screen width, and any row pitch information for the screen. The positioning information is well known in the art and so will not be discussed in any further detail herein. The refresh adder 50 receives a previous refresh address and a run length as inputs. The refresh adder 50 increases the refresh address according to the run length value to arrive at the adjusted refresh address.

The operation of the refresh address modify section 18 of the present invention is best understood in comparison to conventional refresh addressing schemes. Conventional refresh addressing schemes result in AUs for each screen row being addressed from the left column of each screen row to the right column, in a consecutive fashion. In contrast, in the present invention the refresh address skips redundant data by operation of the refresh adder 50. In the preferred embodiment, the refresh adder 50 increases the column address in the given screen row 26 by a number of columns equal to the run length, rather than simply incrementing the column address as is done in a conventional scheme. Assuming there are at least some RU repetitions in a given screen line, the number of times the screen memory 12 must be addressed during a refresh operation is reduced. In the case where large amounts of the display image are of uniform color or pattern, this reduction is significant.

The reduction in the number of display memory accesses during screen refresh is further understood by a description of the data output repeat section 20 of the preferred embodiment. Referring now to FIG. 1, the data output repeat section 20 is shown to include an output first-in-first-out buffer (FIFO) 54, a register repeater 56, and a serializer 58. The FIFO 54 includes a FIFO input 60, a FIFO output 62, and a number of FIFO registers 64. As shown in FIG. 1, each FIFO register 64 has two fields, a run length field 66 and a data field 68. The run length field 66 receives a run length from the redundancy data section 16, and the data field 68 receives an RU from the data bus, MD. In the preferred embodiment, the run length field 66 is 4 bits wide to accommodate the 4 bit encoded run length, and the data field 68 is 32 bits wide to accommodate one RU from the screen memory 12. During operation, the data within the FIFO registers 64 (the run length and RU) are clocked through the FIFO 54 together. The register repeater 56, situated at the FIFO output 62, extracts the FIFO register data one time and outputs the value of the RU in the last FIFO register 64 to the serializer 58 a number of times equal to the run length. When the register repeater 56 is outputting a given RU to the serializer 58 for the second or subsequent consecutive time, no further data are extracted from the FIFO 54. The serializer 58, well known in the prior art, divides each RU it receives into pixel depth (PIXDEP) bits and provides them as a serial output. Thus, where prior art designs would read consecutive, identical RUs from screen memory and write each to a FIFO, the present invention reads a single RU (and one bit redundancy codes for each RU) and write the RU to the FIFO 54 accompanied by a run length. As an example, for the screen memory illustrated in FIG. 2, a conventional refresh operation would write the data in five write operations, filling five conventional FIFO registers with the same data (C0 C0 C0 C0). In contrast, the preferred embodiment would make one write of (C0 C0 C0 C0) with an accompanying run length of 5, reducing the number of reads from the screen memory from five to one.

Referring once again to FIG. 1, the redundancy detect section 22 is shown to include a hold register 70 and a comparator 72. The comparator is controlled by the status of the row status bit latched by the row status selector 36. If the status is VALID, the comparator 72 is disabled, and correspondingly, the comparator signal CMP is disabled. If the status is INVALID the comparator 72 is enabled providing the CMP signal to the HR buffer 40. During the refresh operation for any given "invalid" row the redundancy detect section 22 receives the RU read from the screen memory 12 and compares it with the immediately previous RU to determine if the two are identical. The result of the comparison operation is used to generate the redundancy data provided by the CMP. In the preferred embodiment the comparator 72 receives one 32-bit input from the data bus MD, and another from the 32-bit hold register 70. The hold register 70 stores an RU read from the screen memory 12 after the comparison is complete. When a subsequent RU is output, it is compared by the comparator 72 with the data stored within the hold register 70. The comparator 72 generates a SKIP bit (1) output if the RUs are the same, or a NONSKIP bit output (0) if they are different. In this manner the CMP signal is generated.

In the preferred embodiment, all elements of the display refresh system 10, except for the display memory 24, are intended to be incorporated as part of a monolithic semiconductor graphics controller device. The display memory 24 is provided by an external bank of random access memory (RAM).

One skilled in the art would recognize that the present invention may accommodate higher resolutions that require more redundancy data in a single screen row than the HR buffer size and/or available redundancy row lengths can accommodate. In such a case, larger RU sizes could be used, with a correspondingly larger hold register and comparator size, or a smaller comparator executing multiple comparator operations. In another variation all AUs outside the range of the redundancy memory could be written to the FIFO in a conventional fashion (one AU at a time, run lengths defaulted to one). Along the same lines it is recognized that the particular arrangement of the preferred embodiment should not be read as limiting. As just one example, there could be two HR buffers, one for receiving redundancy data for a row refresh operation, the other for compiling redundancy data during row refresh, resulting in two entirely different read and write paths to and from the display memory.

Accordingly, as will be apparent to one skilled in the art, the invention has been described in connection with its preferred embodiments, s and may be changed, and other embodiments derived, without departing from the spirit and scope of the invention as set forth in the claims which follow.