Efficient splitting and mixing of streaming-data frames for processing through multiple processing modules

• US 7,869,440 B2
• Filed: 08/16/2005
• Issued: 01/11/2011
• Est. Priority Date: 05/12/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Woodruff, Bryan A., Sather, Dale A., Lisitsa, Rafael S., Shaw, George H. J.
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): RANDHAWA, MANDISH K
• Application Number:
  US11/204,683
• Publication Number:
  US 20050286552A1
• Time in Patent Office: 1,974 Days
• Field of Search: 370/468, 370/536, 370/477, 370/395.7, 370/465, 370/253, 370/412, 370/389, 370/392, 370/352, 709/231, 709/203, 709230-234, 709238-242, 709223-226, 710/100, 710/316, 710/317
• US Class Current: 370/395.7
• CPC Class Codes: G06F 15/8053 Vector processors

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.

Claims

1. A method for processing frames of streaming data through modules in a digital computer, comprising:

constructing a pipe as a connected group of multiple ones of the modules, at least one of the modules being a restructuring module that alters the frame structure of the data;

allocating composite frames having predefined subframes;

transporting the streaming data through different ones of the modules in the group in different ones of the subframes;

restructuring the data among at least some of the subframes in the restructuring module, wherein the restructuring includes altering the frame structure of the data; and

assigning an allocator for the composite frames to one of a farthest upstream restructuring module in the pipe or a farthest downstream restructuring module in the pipe.

2. The method of claim 1 where the composite frame is a physical frame in a memory.

3. The method of claim 2 where the subframes are virtual frames defined in the same memory as the physical frame.

4. The method of claim 1 where the allocator is assigned to the farthest upstream restructuring module in the pipe when the modules comprise at least one mixer.

5. The method of claim 1 where the allocator is assigned to the farthest downstream restructuring module in the pipe when every restructuring module among the modules in the pipe is a splitter.

6. The method of claim 1 further comprising constructing a frame nesting tree specifying how the data is to be restructured in the restructuring module.

7. A computer system for processing streaming data, comprising:

a plurality of filters for processing the streaming data, at least some of which are restructuring filters, wherein the restructuring includes altering the frame structure of the data;

a plurality of memory managers for allocating composite frames containing subframes for containing streaming data; and

a processor for executing a plurality of modules, the modules comprising;

a flow manager for constructing a graph having a pipe, the pipe including a plurality of the restructuring filters that alter the frame structure of the data, and for assigning one of the memory managers to a restructuring filter included in the pipe.

8. The system of claim 7 further comprising a memory for storing the composite frames.

9. The system of claim 8 where the subframes are allocated within the composite frames in the memory.

10. The system of claim 7 further including an input/output system.

11. The system of claim 10 where the input/output system implements one or more of the modules.

12. The system of claim 7 further comprising a pipe manager for constructing representations of the structures of the composite frames.

13. The system of claim 12 where one of the representations specifies locations of the subframes with respect to the composite frame.

14. The system of claim 12 where one of the representations specifies relationships of the modules within the pipe.

15. The system of claim 7 further including a control manager for transporting the streaming data through the modules in various ones of the subframes.

16. The system of claim 15 where the control manager issues a control transaction to one of the restructuring module for initiating processing of a subframe therein only when all of the subframes processed by that module become available.

17. The computer system of claim 7, wherein at least one of the restructuring filters specifies a pipe topology, and constructing the graph by the flow manager comprises constructing the pipe including the at least one of the restructuring filters based at least in part on the pipe topology.

18. The computer system of claim 7, wherein the flow manager assigns the one of the memory managers to one of a farthest upstream restructuring filter in the pipe or a farthest downstream restructuring filter in the pipe.

19. A computer memory device 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 including at least one restructuring module in a digital computer, the method comprising:

allocating a composite frame having multiple subframes;

performing operations upon the subframes in a plurality of modules sourcing data to the restructuring module;

for each of said plurality of modules, after completion of the operations upon the subframe for said module, checking whether all of the plurality of modules have completed their respective operations upon their respective subframes, and when all of said plurality of modules have completed their respective operations, issuing a control transaction to the restructuring module; and

performing operations upon the subframes sourced to the restructuring module in response to the control transaction.

20. The computer memory device of claim 19, further comprising:

for each of said plurality of modules, after completion of the operations upon the subframe for said module, setting a completion flag,

wherein checking whether all of the plurality of modules have completed their respective operations comprises checking the completion flag for each of the other modules among the plurality of modules and determining all of the plurality of modules have completed their respective operations when the completion flag for each of the other modules among the plurality of modules is set.