Efficient splitting and mixing of streaming-data frames for processing through multiple processing modules
First Claim
1. A method for processing frames of streaming data through modules in a digital computer, comprising:
- constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data;
dividing the graph to define a pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, at least one of the modules being a restructuring module and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules;
providing a common memory area accessible to the modules within the pipe for storing streaming data;
constructing a composite frame nesting tree specifying composite frames comprising nested subframes;
allocating composite frames in the common memory area in accordance with the composite frame nesting tree, wherein the allocating of the composite frame includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;
transporting the streaming data through different ones of the modules in the group in different ones of the subframes; and
restructuring the data among at least some of the subframes in the restructuring module.
2 Assignments
0 Petitions
Accused Products
Abstract
Streaming data is processed through one or more pipes of connected modules including mixers and/or splitters. The data is carried in composite physically allocated frames having virtual subframes associated with different ones of the splitters, mixers, and other transform modules. Nesting trees and pipe control tables represent the structure of the pipes. A frame allocator is assigned to a particular module in a pipe. Rather than issuing a control transaction to all modules when any one of them completes an operation upon its source data, a control manager requests a module to begin its operation only when all of its input subframes have become available. Frame control tables record when any module has completed an operation, and a pipe control table lists which modules provide data to which other modules.
144 Citations
72 Claims
-
1. A method for processing frames of streaming data through modules in a digital computer, comprising:
-
constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data; dividing the graph to define a pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, at least one of the modules being a restructuring module and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; providing a common memory area accessible to the modules within the pipe for storing streaming data; constructing a composite frame nesting tree specifying composite frames comprising nested subframes; allocating composite frames in the common memory area in accordance with the composite frame nesting tree, wherein the allocating of the composite frame includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;transporting the streaming data through different ones of the modules in the group in different ones of the subframes; and restructuring the data among at least some of the subframes in the restructuring module. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A method for processing frames of streaming data through multiple modules disposed in a pipe in a digital computer, comprising:
-
constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data; dividing the graph to define the pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, at least one of the modules being a restructuring module and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; constructing a composite frame nesting tree specifying a composite frame comprising multiple nested subframes; allocating a composite frame in accordance with the composite frame nesting tree, wherein the allocating of the composite frame includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;performing operations upon the subframes in any of the modules sourcing data to the restructuring module; after completion of the operations for all of the subframes sourcing data to the restructuring module, issuing a control transaction to the restructuring module; and performing operations upon the subframes sources to the restructuring module in response to the control transaction. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
-
-
26. A method for processing frames of streaming data through modules including multiple restructuring modules in a digital computer, comprising:
-
constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data; dividing the graph to define the pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, at least one of the modules being a restructuring module and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; constructing at least one composite frame nesting tree specifying composite frames comprising nested subframes; assigning a single allocator to one of the modules; allocating composite frames in accordance with the at least one composite frame nesting tree wit respective ones of the restructuring modules, wherein the allocating of the composite frames includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;transporting the streaming data through different ones of the modules in the group in different ones of the subframes; and restructuring the data among the subframes in the restructuring modules. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A method for processing frames of streaming data through modules including multiple restructuring modules connected in a pipe in a digital computer, comprising:
-
constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data; dividing the graph to define the pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; constructing at least one composite frame nesting tree specifying at least one composite frame comprising multiple nested subframes; allocating a composite frame in accordance with the at least one composite frame nesting tree for different ones of the restructuring modules, wherein the allocating of the composite frame includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;performing data-sourcing operations upon certain of the subframes in sources ones of the modules; when each of the data-sourcing operations has completed, determining whether one of the restructuring modules has all of the subframes required for it to perform an operation; if so, issuing a control transaction to the one restructuring module; and performing an operation in the one restructuring module after receiving a control transaction. - View Dependent Claims (39, 40, 41, 42, 43, 44, 45, 46, 47)
-
-
48. A computer system for processing streaming data, comprising:
-
a plurality of memory managers each configured to, at least; constructing at least one composite frame nesting tree specifying composite frames comprising nested subframes for containing streaming data; and allocating composite frames in accordance wit the at least one composite frame nesting tree, wherein the allocating of the composite frames includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;a flow manager for constructing a graph as a sequence of the modules for accepting and processing the streaming data to achieve desired output data, for dividing the graph to define a pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, including a plurality of the restructuring modules, and for assigning one of the memory managers to the pipe and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules. - View Dependent Claims (49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59)
-
-
60. A computer system for processing streaming data, comprising:
-
a plurality of modules for processing the streaming data, at least some of the modules being restructuring; a plurality of memory managers each configured to, at least; constructing at least one composite frame nesting tree specifying composite frames comprising nested subframes for containing streaming data; and allocating composite frames in accordance wit the at least one composite frame nesting tree, wherein the allocating of the composite frames includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;a flow manager for constructing a graph as a sequence of the modules for accepting and processing the streaming data to achieve desired output data, for dividing the graph to define a pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, including a plurality of the restructuring modules, and for assigning one of the memory managers to the pipe and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; and a control manager for issuing control transactions for initiating processing operations in the modules. - View Dependent Claims (61, 62, 63, 64, 65, 66, 67, 68, 69, 70)
-
-
71. A computer readable medium bearing instructions and data for causing a digital computer to execute a method for processing frames of streaming data through modules in a digital computer, the method comprising:
-
constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data; dividing the graph to define a pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, at least one of the modules being a restructuring module and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; providing a common memory area accessible to the modules within the pipe for storing streaming data; constructing a composite frame nesting tree specifying composite frames comprising nested subframes; allocating composite frames in the common memory area in accordance with the composite frame nesting tree, wherein the allocating of the composite frame includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;transporting the streaming data through different ones of the modules in the group in different ones of the subframes; and restructuring the data among at least some of the subframes in the restructuring module.
-
-
72. A computer readable medium bearing instructions and data for causing a digital computer to execute a method for processing frames of streaming data through multiple modules disposed in a pipe in a digital computer, the method comprising:
-
constructing a graph as a sequence of the modules for accepting and processing the frames of streaming data to achieve desired output data; dividing the graph to define the pipe according to performance parameters for each of the modules and the graph as a whole, wherein the pipe is a connected group of multiple ones of the modules, at least one of the modules being a restructuring module and wherein the performance parameters comprise parameters corresponding to operations performed by graph modules; constructing a composite frame nesting tree specifying a composite frame comprising multiple nested subframes; allocating a composite frame in accordance with the composite frame nesting tree, wherein the allocating of the composite frame includes a frame control table having an entry for each module in the pipe and a flag for each of the modules indicating whether a particular module has completed an operation upon the subframe;
setting of the flags whenever a module has completed an operation upon a subframe;performing operations upon the subframes in any of the modules sourcing data to the restructuring module; after completion of the operations for all of the subframes sourcing data to the restructuring module, issuing a control transaction to the restructuring module; and performing operations upon the subframes sources to the restructuring module in response to the control transaction.
-
Specification