SWITCHING ALGORITHMS DURING A RUN TIME COMPUTATION

• US 20120290615A1
• Filed: 05/14/2012
• Published: 11/15/2012
• Est. Priority Date: 05/13/2011
• Status: Abandoned Application

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Micro Focus LLC (Open Text Corporation)
• Inventors: Bear, Charles Edward, LAMB, Andrew Allinson
• Application Number:
  US13/470,762
• Publication Number:
  US 20120290615A1
• Time in Patent Office: Days
• US Class Current: 707/770
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A system and method for switching algorithms during a run time computation, the method including configuring hardware of a networked cluster of processing elements, each processing element with a memory hierarchy, to perform a first-tier algorithm on input data, the input data having cardinality and stored on one or a plurality of nodes in the networked cluster. Performing at least a portion of a second-tier algorithm and determining whether to complete the second-tier algorithm and perform a third or subsequent tier algorithm, the determination dependent on cardinality. Automatically passing data to an output if the cardinality of the second-tier algorithm is greater than a threshold cardinality, and passing the data back to the second-tier algorithm or to one or a plurality of subsequent algorithms, in response to the cardinality being less than the threshold, and automatically passing the data to an output at the completion of the data processing.

Claims

1. A method of switching algorithms during a run time computation, the method comprising:

configuring hardware of a networked cluster of processing elements, each processing element coupled to one or a plurality of levels of memory hierarchy, to perform a first tier algorithm on input data, the input data having cardinality and stored on one or a plurality of nodes in the networked cluster;

performing a least a portion of a second tier algorithm;

determining whether to complete the second tier algorithm and perform a third or subsequent tier algorithm, the determination dependent on a threshold of cardinality;

automatically passing data to an output if the cardinality of the second tier algorithm is greater than a threshold cardinality; and

,

passing the data back to the second tier algorithm or to one or a plurality of subsequent algorithms, in response to the cardinality being less than the threshold, and automatically passing the data to an output at the completion of processing by the second tier algorithm or to one or a plurality of subsequent algorithms.

2. The method of claim 1, wherein the threshold of cardinality of the second tier algorithm is configured to be equal to or less than a percentage of the cardinality of the input.

3. The method of claim 1, wherein one or a plurality of the algorithms are grouping algorithms.

4. The method of claim 1, wherein one or a plurality of the algorithms are hashing algorithms.

5. The method of claim 1, wherein one or a plurality of subsequent algorithms are more sophisticated than the first and second tier algorithms.

6. The method of claim 1, wherein the number of algorithms is correlated with the levels of memory hierarchy employed by the networked cluster.

7. A non-transitory computer readable medium to execute a query to find distinct values in a table column, comprising instructions, which when executed cause a processor to perform a first tier algorithm on input data, the input data having cardinality and stored on one or a plurality of nodes in a networked cluster, each node coupled to one or a plurality of levels of memory hierarchy;

and,

performing a least a portion of a second tier algorithm,

determining whether to complete the second tier algorithm and perform a third or subsequent tier algorithm, the determination dependent on a threshold of cardinality;

automatically passing data to an output if the cardinality of the second tier algorithm is greater than a threshold cardinality; and

,

passing the data back to the second tier algorithm or to one or a plurality of subsequent algorithms, in response to the cardinality being less than the threshold, and automatically passing the data to an output at the completion of processing by the second tier algorithm or to one or a plurality of subsequent algorithms.

8. The non-transitory computer readable medium of claim 7, configured to set the threshold of cardinality for the second tier algorithm to be equal to or less than a percentage of the cardinality of the input.

9. The non-transitory computer readable medium of claim 7, wherein one or a plurality of the algorithms are grouping algorithms.

10. The non-transitory computer readable medium of claim 7, wherein one or a plurality of the algorithms are hashing algorithms.

11. The non-transitory computer readable medium of claim 7, wherein one or a plurality of subsequent algorithms are more sophisticated than the first and second tier algorithms.

12. The non-transitory computer readable medium of claim 7, wherein the number of algorithms to be run is correlated with the levels of memory hierarchy employed by the networked cluster.

13. A system for switching algorithms during a run time computation, the system comprising:

hardware within networked cluster of processing elements, each processing element with its own memory hierarchy, to perform a first tier algorithm on input data, the input data having cardinality and stored on one or a plurality of nodes in the networked cluster each node coupled to one or a plurality of levels of memory hierarchy;

one or a plurality of processors performing a least a portion of a second tier algorithm;

one or a plurality of the processors determining whether to complete the second tier algorithm and perform a third or subsequent tier algorithm, the determination dependent on a threshold of cardinality;

one or a plurality of the processors automatically passing data to an output if the cardinality of the second tier algorithm is greater than a threshold cardinality; and

,

one or a plurality of the processors passing the data back to the second tier algorithm or to one or a plurality of subsequent algorithms, in response to the cardinality being less than the threshold, and automatically passing the data to an output at the completion of processing by the second tier algorithm or to one or a plurality of subsequent algorithms.

14. The system of claim 13, wherein the threshold of cardinality for the second tier algorithm is configured to be equal to or less than a percentage of the cardinality of the input.

15. The system of claim 13, wherein one or a plurality of the algorithms are grouping algorithms.

16. The system of claim 13, wherein one or a plurality of the algorithms are hashing algorithms.

17. The system of claim 13, wherein one or a plurality of subsequent algorithms are more sophisticated than the first and second tier algorithms.

18. The system of claim 13, wherein the number of algorithms to be run is correlated with the levels of memory hierarchy employed by the networked cluster.