System and method for parallel processing prediction
View Patent ↗Systems, methods, and computer program products are provided for space-time complexity speedup for computer algorithms in terms of processing time as a function of dataset size and type, showing serial, sub-linear, linear and superlinear speedup. Serial and parallel effects can be processed and calculated from a decomposed algorithm's sequential functional components, allowing the identification and use of the parallelizable components.
1. A method of parallel processing prediction for software, comprising:
receiving a software algorithm;
determining a plurality of execution pathway components for the software algorithm;
determining a plurality of input workload attributes related to processing times of the plurality of execution pathway components;
defining a plurality of initial input dataset values having one or more associated workload attributes based on the plurality of execution pathway components;
defining a plurality of workload scaling factors to facilitate prediction of the processing times of the plurality of execution pathway components;
defining a plurality of scaled processing time prediction functions based on the plurality of initial input dataset values for the plurality of execution pathway components
defining a plurality of speedup prediction functions based on the plurality of scaled processing time prediction functions;
dynamically scaling a plurality of current input dataset values based on the plurality of workload scaling factors; and
outputting how many of a plurality of computer processing elements will be used based on the scaled plurality of current input dataset values.
2. The method of claim 1 , further including processing and calculating the speedup of the software algorithm.
3. The method of claim 1 , further including determining if one or more of the plurality of execution pathway components are serial components.
4. The method of claim 1 , further including determining if one or more of the plurality of execution pathway components are parallel components.
5. The method of claim 1 , further including determining if one or more of the plurality of execution pathway components are mixed serial and parallel components.
6. The method of claim 1 , further including determining and flagging serial overhead of the software algorithm using time complexity.
7. The method of claim 1 , wherein the plurality of computer processing elements includes a plurality of computer processor cores.
8. The method of claim 1 , wherein the plurality of computer processing elements includes a plurality of computer processors.
9. A method of parallel computer processing prediction, comprising:
receiving a software algorithm;
determining a plurality of execution pathway components for the software algorithm;
determining a plurality of time scaling factors for the plurality of execution pathway components;
determining scaled workload prediction functions based on scaled workload timings for the plurality of execution pathway components;
dynamically scaling processing times based on the time scaling factors for the plurality of execution pathway components; and
determining input values for a plurality of computer processing elements based on the scaled processing times.
10. The method of claim 9 , further including identifying a polynomial based on one or more scaled dataset sizes and timings.
11. The method of claim 9 , further including determining if one or more of the plurality of execution pathway components are serial or parallel components.
12. The method of claim 9 , further including determining and flagging overhead computing resources.
13. The method of claim 12 , wherein the overhead computing resources includes computing memory.
14. The method of claim 12 , wherein the overhead computing resources includes computing bandwidth.
15. The method of claim 9 , wherein the plurality of computer processing elements includes a plurality of computer processor cores.
16. The method of claim 9 , wherein the plurality of computer processing elements includes a plurality of computer processors.