Computer graphics processing and selective visual display system – Computer graphics display memory system – First in first out
Reexamination Certificate
1999-09-27
2003-05-20
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics display memory system
First in first out
C345S542000, C345S545000, C345S546000, C711S110000
Reexamination Certificate
active
06567094
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention is a method for controlling the delivery of data to multiple hardware processing units, which perform document image processing. The processing units (PU's) communicate with each other by accessing a shared memory via streams. Each memory access transfers a two dimensional patch of data. Avoidance of shared memory hazards is simplified by the stream ring linked list data structure.
In a typical digital image processing system, a main memory originally contains the source image, and several individual processing units may be needed to process the data in discrete steps before the output image can be printed. In the typical case each processor would have its own process, such as image enhancement, color space transformation, color correction, etc. It would calculate the location of the data in memory, access the data, process the data and then calculate the location in memory that the data must be loaded back into. The processors would also have to prevent memory hazards, such as not allowing data to be fetched by a next processing unit before it has been written by the previous one. Each processing unit is burdened by the computational overhead, and the complexity of the processors is increased.
SUMMARY OF THE INVENTION
In this system, a number of sections of main memory are separated into circular image FIFO buffers, each buffer is associated with one write stream into the buffer and one or more read streams out of the buffer. Each stream is either a write stream or a read stream and provides a sequence of data in the form of small blocks called patches to or from a processing unit from or to a buffer. A single stream control unit (SCU) is used to control all streams. A processor may utilize one or more read streams, and send data out using one or more write streams. A buffer may provide data to one or more processors, but the system is normally limited to having only one stream of data being written into each buffer from one processor. Conceptually, the SCU contains a table of stream descriptions, one entry per stream. Each entry contains all the static and dynamic state associated with a particular stream. This descriptor specifies the patch size and shape, the data source and destination, and a pointer to the location in the buffer where the current data transfer is taking place. The SCU also contains a state machine for executing a process based on this data. As each data transfer is processed, the descriptor line is updated.
To avoid hazards, the SCU has to ensure that, for example, old data is not over-written by new data before it is used. This is accomplished by providing the parameter line of each stream with a pointer identifying the parameter line of the stream that it must follow. For example, if a first PU is loading data into a buffer, and then that data is being sent to a second PU, the reader must not access data until the writer has put the current data into the buffer. Likewise, the writer must not load new data over old data in the circular FIFO buffer that has not been used yet. To prevent this, the write point is forced to follow the read point and the read point is forced to follow the write point. To prevent one from overtaking the other, each of the two stream parameter lines contain pointers to the other line and either stream will be stalled if stepping forward would overtake the other. For the case where there are several readers of a single buffer, each is assigned a relative position, each parameter line is provided with a pointer to the reader or writer that is leading it, and a stream will be stalled if necessary to prevent any one from overtaking any other.
This system simplifies the process by having a central stream control unit handle all of the overhead, which results in two advantages. The first is a saving of time. The SCU is fast enough to process all of the memory computations in real time, so that the pipelined PU's can process data without interruption. They simply request a data transfer and will be allowed to receive or send. The second is a saving in hardware. The single SCU needs only one copy of the hardware that otherwise would have to be provided in all PU's. Because of these advantages, the SCU and PU's can be constructed on a single device.
An additional advantage of this arrangement is that since each control parameter is in the form of a table entry, the entire system is under software control, so that every aspect of the process, such as patch size and data path, can be changed in real time.
REFERENCES:
patent: 4561051 (1985-12-01), Rodman et al.
patent: 5634034 (1997-05-01), Foster
patent: 6047334 (2000-04-01), Langendorf et al.
patent: 6278838 (2001-08-01), Mendenhall et al.
Ball James L.
Claassen Stuart L.
Curry Donald J.
Kasle David B.
Thayer Todd W.
Bella Matthew C.
Monestime Mackly
Xerox Corporation
LandOfFree
System for controlling read and write streams in a circular... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for controlling read and write streams in a circular..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for controlling read and write streams in a circular... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3051216