System and Method for Parallel Processing Prediction

Abstract

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.

What is claimed is: 
     
         1 . A method of determining time complexity of software, comprising:
 receiving a software algorithm;   determining a plurality of parallel components for the software algorithm;   receiving a dataset for each of the plurality of parallel components;   determining one or more dataset splits for the dataset of each of the plurality of parallel components, and one or more timing values to process the plurality of parallel components; and   calculating a time complexity for each of the plurality of parallel components based on the one or more dataset splits of each of the plurality of parallel components and the one or more timing values.   
     
     
         2 . The method of  claim 1 , further including:
 receiving the time complexity calculation;   inverting the time complexity calculation;   receiving a desired processing time for the software algorithm; and   calculating a dataset size for each of the plurality of parallel components to produce the desired processing time.   
     
     
         3 . The method of  claim 2 , further including allocating a dataset to a plurality of processing elements. 
     
     
         4 . The method of  claim 2 , further including determining one or more processing elements required to meet the desired processing time. 
     
     
         5 . The method of  claim 2 , further including creating a parallel processing model. 
     
     
         6 . The method of  claim 2 , further including determining a maximum number of processing elements to process the dataset of one or more of the plurality of parallel components. 
     
     
         7 . The method of  claim 2 , further including determining a minimum processing time of the dataset for one or more of the plurality of parallel components. 
     
     
         8 . The method of  claim 1 , further including receiving one or more serial function codes of the software algorithm, calculating a processing time of the one or more serial function codes, and summing the processing times of the one or more serial function codes. 
     
     
         9 . The method of  claim 1 , further including receiving a time value unaccounted for, receiving a desired overhead time, and calculating an overhead time complexity. 
     
     
         10 . The method of  claim 9 , determining one or more communication channels required to meet the desired overhead time. 
     
     
         11 . The method of  claim 1 , further including searching for time complexity polynomial terms. 
     
     
         12 . The method of  claim 1 , further including searching for time space complexity polynomial terms. 
     
     
         13 . The method of  claim 1 , further including outputting how many of a plurality of computer processing elements will be used. 
     
     
         14 . The method of  claim 13 , wherein the plurality of computer processing elements includes a plurality of computer processor cores. 
     
     
         15 . The method of  claim 13 , wherein the plurality of computer processing elements includes a plurality of computer processors. 
     
     
         16 . A method of determining a speedup function of software:
 receiving a software algorithm;   determining a plurality of parallel components for the software algorithm;   receiving a dataset for each of the plurality of components;   determining one or more dataset splits for the dataset of each of the plurality of parallel components, and one or more timing values to process the plurality of parallel components; and   calculating a speedup function for each of the plurality of parallel components based on the one or more dataset splits and the one or more timing values.   
     
     
         17 . The method of  claim 16 , further including determining the speedup function based on the one or more dataset splits for one or more of the plurality of parallel components. 
     
     
         18 . The method of  claim 16 , further including:
 receiving the speedup function;   inverting the speedup function;   receiving a desired speedup value for the software algorithm; and   calculating the number of dataset splits for each of the plurality of parallel components to produce the desired speedup value.   
     
     
         19 . The method of  claim 16 , further including determining and flagging overhead computing resources. 
     
     
         20 . The method of  claim 16 , further including outputting how many of a plurality of computer processing elements will be used.