×

Parallel processing of an ordered data stream

  • US 8,996,556 B2
  • Filed: 06/05/2009
  • Issued: 03/31/2015
  • Est. Priority Date: 06/05/2009
  • Status: Active Grant
First Claim
Patent Images

1. A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:

  • storing the ordered input data stream, including storing as part of the input data stream an order key for each of the input data elements, wherein the order keys indicate a total order of all of the input data elements in the ordered input data stream;

    processing the stored ordered input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements;

    storing the plurality of sets of output data elements in a plurality of buffers along with an associated order key for each output data element, each buffer associated with one of the worker units;

    outputting an ordered output data stream while the input data stream is being processed in a parallel manner with the plurality of worker units by outputting selected output data elements from the plurality of buffers in an order that is based on the order keys stored in the plurality of buffers;

    generating a data structure that includes a plurality of entries, each entry associated with one of the buffers and identifying a next output data element to be output from its associated buffer based on the order keys stored in the buffers; and

    selecting output data elements to be output from the buffers based on output data elements identified by the data structure.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×