Method and apparatus for processing data with multiple processing modules and associated counters

• US 6,560,606 B1
• Filed: 05/04/1999
• Issued: 05/06/2003
• Est. Priority Date: 05/04/1999
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: MetraTech
• Inventors: Young, Derek M.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/305,176
• Time in Patent Office: 1,463 Days
• Field of Search: 707/1-206, 709/203, 709/220, 709/224, 709/229, 709/201, 709/106, 709/104, 709/102, 709/100, 705/34, 379/9, 379/10
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

For communication services, a metering and processing system for processing metered information incorporates configurable processing modules and a configuration manager. The system can by readily and flexibly configured, responsive to operator directions, to process metered information to meet the needs of data consumers, such as NSPs and ISPs. Each processing module performs a specific sub-part of a computation on the metered information, and the configuration manager generates a configuration file for specifying the order of operation, computation sub-part, and other operational parameters for the individual processing modules. A mechanism is provided for tracking and enforcing the ordering of data processing by the processing modules so as to take into account dependencies between them.

Claims

1. A computer program product comprising computer-readable media, and computer-executable program code stored on the media for ordering execution of a plurality of processing modules in a processing system, in which each processing module may be dependent on a number of other ones of the processing modules, the program code comprising:

A) first program code for associating a counter with each of a plurality of processing modules, each counter providing a count;

B) second program code for conditioning the count of each counter to indicate a number of processing modules executed, on which the associated processing module depends;

C) third program code for executing the associated processing module when the counter indicates that the processing modules on which the associated processing module depends have been executed

D) fourth program code for loading the counter with a value indicative of the number of processing modules on which the associated processing module is dependent;

E) fifth program code for decrementing the counter as each of the number of processing modules is executed;

F) sixth program code, responsive to the counter reaching a preselected value, for causing the associated processing module to execute the data; and

G) seventh program code for sorting the processing modules in accordance with the dependency values of the counters, causing execution of at least one processing module having a counter dependency value of zero, and resorting the processing modules in accordance with decremented counter values reflecting the prior execution.

2. Apparatus for ordering the processing of data by a plurality of processing modules that receive input data and are controlled to process the input data and generate output data in which at least one processing module requires, as input data to start processing, the output data of a number of other processing modules, the apparatus comprising:

a counter associated with each processing module, including the one processing module, each counter having a count value;

a dependency manager that comprises a database that stores initial count values for each counter and that initializes the count value of the counter in the one processing module to the number of other processing modules;

a count conditioning mechanism that monitors each of the other processing modules and changes the count value of each counter when each of the other processing modules generates output data; and

an execution manager that controls the one processing module to process data when the count value of the counter in the one processing module reaches a threshold indicating that all of the other processing modules have generated output data.

3. The apparatus in accordance with claim 2 wherein the dependency manager comprises a sorter that sorts the count values by initial value.

4. The apparatus in accordance with claim 3 wherein the execution manager comprises a first plurality of threads that control all processing modules to start processing data where the sorted count value indicates no other processing module output data is required to start processing.

5. The apparatus in accordance with claim 4 wherein the dependency manager further comprises a resorter that is responsive to the completion of data processing by the data processing modules started by the execution manager for resorting the count values.

6. The apparatus in accordance with claim 5 wherein the execution manager comprises a second plurality of threads that control all processing modules to start processing data where the resorted count value indicates no other processing module output data is required to start processing.

7. The apparatus in accordance with claim 2 wherein the count conditioning mechanism comprises an incrementer that increments the count value when each of the other processing modules generates output data.

8. The apparatus in accordance with claim 2 wherein the count conditioning mechanism comprises a decrementer that decrements the count value when each of the other processing modules generates output data.

9. Apparatus for ordering the processing of data by a plurality of processing modules that receive input data and are controlled to process the input data and generate output data in which at least one processing module requires, as input data to start processing, the output data of a number of other processing modules, the apparatus comprising:

a counter associated with the one processing module, the counter having a count value;

a dependency manager that initializes the count value to the number of other processing modules;

a count conditioning mechanism that monitors each of the other processing modules and changes the count value when each of the other processing modules generates output data; and

an execution manager that controls the one processing module to process data when the count value reaches a threshold indicating that all of the other processing modules have generated output data and that controls a plurality of processing modules to process data in parallel.

10. A method for ordering the processing of data by a plurality of processing modules that receive input data and are controlled to process the input data and generate output data in which at least one processing module requires, as input data to start processing, the output data of a number of other processing modules, the method comprising:

A) associating a counter with each processing module, including the one processing module, each counter having a count value;

B) initializing the count value to the number of other processing modules and storing initial count values for each counter in a database;

C) monitoring each of the other processing modules and changing the count value when each of the other processing modules generates output data; and

D) controlling the one processing module to process data when the count value reaches a threshold indicating that all of the other processing modules have generated output data.

11. The method in accordance with claim 10 wherein step (C) comprises sorting the count values by initial value.

12. The method in accordance with claim 11 wherein step (D) comprises (D1) spawning a first plurality of threads that control all processing modules to start processing data where the sorted count value indicates no other processing module output data is required to start processing.

13. The method in accordance with claim 12 wherein step (C) further comprises resorting the count values in response to the completion of data processing by the data processing modules started in step (D1).

14. The method in accordance with claim 13 wherein step (D) comprises spawning a second plurality of threads that control all processing modules to start processing data where the resorted count value indicates no other processing module output data is required to start processing.

15. The method in accordance with claim 10 wherein step (B) comprises incrementing the count value when each of the other processing modules generates output data.

16. The method in accordance with claim 10 wherein step (B) comprises decrementing the count value when each of the other processing modules generates output data.

17. A method for ordering the processing of data by a plurality of processing modules that receive input data and are controlled to process the input data and generate output data in which at least one processing module requires, as input data to start processing, the output data of a number of other processing modules, the method comprising:

A) associating a counter with the one processing module, the counter having a count value;

B) initializing the count value to the number of other processing modules;

C) monitoring each of the other processing modules and changing the count value when each of the other processing modules generates output data; and

D) controlling the one processing module to process data when the count value reaches a threshold indicating that all of the other processing modules have generated output data and controlling a plurality of processing modules to process data in parallel.