System for controlling read and write streams in a circular FIFO buffer

• US 6,567,094 B1
• Filed: 09/27/1999
• Issued: 05/20/2003
• Est. Priority Date: 09/27/1999
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ball, James L., Thayer, Todd W., Claassen, Stuart L., Kasle, David B., Curry, Donald J.
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): Monestime, Mackly
• Application Number:
  US09/405,984
• Time in Patent Office: 1,331 Days
• Field of Search: 345/539, 345/558, 345/545, 345/546, 345/540, 345/542, 711/110, 711/117
• US Class Current: 345/558
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's
• CPC Class Codes: G06T 1/60 Memory management

Abstract

A distributed digital imaging processing system having a number of processing units and circular FIFO buffers connected together using data transforming streams. Processing units read data from buffers using a transforming read streams. These read streams reorder the buffer data to form patches representing neighborhood pixels and may provide the same data multiple times. After processing a patch, a processing unit writes the resultant patch into a buffer using a transforming write stream which reorders the data into the storage format of the buffer. Several buffers can feed a single processor and one processor can feed several buffers. All the details of each data stream (buffer, current buffer location, patch size, access pattern) are stored in a table entry, along with a pointer to the data stream that it must follow in the buffer to avoid the hazards of reading and writing data out of order. In the case where a buffer has multiple read streams, requiring read streams to maintain a particular order reduces the work necessary to check for either a write or read hazard to comparing the location of a stream with it'"'"'s leader. A single state machine computes from each table entry all addresses for all data transfers between the processors and buffers, and updates the table entry after each cycle. Since table entries define the streams which link processors to memory, communication paths between processors is completely under software control.

Claims

1. A system for controlling read and write streams in a circular FIFO buffer, comprising:

a circular FIFO buffer having a circulating write point where the data is to be written into the buffer followed by one or more circulating read points where data is to be read from the buffer;

the movement of the read and write points being constrained to maintain their relative order as all proceed through the buffer by each determining the position of the one read or write point immediately ahead of itself to determine whether it may proceed;

wherein each data write causes the data written into the buffer to be reordered in the buffer,

wherein the data is in the form of an image having edges, a patch is defined as a number of pixels in each direction from a current pixel and wherein a stream transform is adapted to ignore pixels that are written outside the edge of the image.

2. A system for controlling read and write streams in a circular FIFO buffer, comprising:

a circular FIFO buffer having a circulating write point where the data is to be written into the buffer followed by one or more circulating read points where data is to be read from the buffer;

the movement of the read and write points being constrained to maintain their relative order as all proceed through the buffer by each determining the position of the one read or write point immediately ahead of itself to determine whether it may proceed;

wherein each data read causes the transferred data to be reordered from the buffer memory and the same data may be read one or more times;

wherein the data is in the form of an image having edges, a patch is defied as a number of pixels in each direction from a current pixel, and wherein the stream transform is adapted to pad the patch for pixels that are outside the edge of the image with a predetermined values or values which are computed from pixels near the edge of the image.

3. A distributed data processing system, comprising:

a circular FIFO buffer having a circulating write point where the data is to be written into the buffer followed by one or more circulating read points where data is to be read from the buffer;

the movement of the read and write points being constrained to maintain their relative order as all proceed through the buffer by each determining the position of the one read or write point immediately ahead of itself to determine whether it may proceed;

two processors, each adapted to produce a data write stream request or a read stream request to indicate the need to write data to or read data from the buffer, and

a stream controller, responsive to a data request, for

a) identifying a stream associated with the request;

b) identifying a source or destination buffer;

c) determining a location where data is to be written or read in the buffer;

d) ensuring that data will not be written into a buffer location until previous data is no longer needed for reading, and that a location will not be read out until all data needed has been written into the buffer; and

e) issuing memory control information to a memory controller to irate the data transfer;

wherein the stream controller maintains a linked list of table entries for each data stream comprising a pointer to the current point in the buffer where data is being written or read, and a pointer to the table entry of the data stream which must precede it, to prevent a following stream overtaking a leading stream, and

wherein a buffer'"'"'s write stream is first in his linked list and all read streams for the buffer are ordered to follow it so that a last read stream becomes a leader for the buffer'"'"'s write stream forming a circular list, and so that the write stream can check that old data has been read by the last read stream before reusing the location for new data.

4. The system of claim 3 where links to followers are maintained in each table entry to allow fast servicing of blocked transfers.