Patent ID: 8387034

Claim:
A system that automatically decomposes an existing sequential program into one or more distributed programs that execute on multiple-processing elements of a computing system, the decomposition being performed without the knowledge of a user, the system comprising: a computer system comprising at least one processor and a plurality of processing elements; a target program in object code form, the target program written to run on a single processing element computer system; a plurality of strategies, the strategies including one or more of parallelization strategies and distribution strategies; a program having coded therein a means for: (a) encapsulating the target program with a run-time analyzer; (b) selecting one of the strategies from the plurality of strategies; (c) parallelization and distributing the target program according to the selected one strategy; (d) executing the target program by one or more of the processing elements; (e) recording execution results of the target program; and (f) if there are further strategies in the plurality of strategies, changing the selected one strategy to a next strategy from the plurality of strategies and repeat steps a-f; (g) comparing the execution results and selecting a best parallelization strategy having a best performance-oriented result; (h) parallelizing the target application using the best parallelization strategy with the best performance-oriented result; (i) analyzing a target data on which the target program is designed to operate; (j) if the target data is a contiguous dataset then: determining a number of available processing elements; copying at least part of the target program onto the available processing elements; dividing the target data into a number of data segments, the data segments being of a fixed-size or a variable size; executing the at least part of the target program on the available processing elements, each operating upon one of the data segments; combining the results from the available processing elements; (k) if the target data is burst data then: measuring an interval between bursts; measuring a computation time of the target program; if the interval between bursts is less than the computation time then determining the number of the available processing elements and distributing at least part of the target program over the available processing elements; if the interval between bursts is not less than the computation time then executing the program on one of the available processing elements; (l) if the target data is a continuous data stream then: determining the number of the available processing elements; duplicating at least part of the target program onto the available processing elements; and demultiplex the target data into the number of sub-streams, where the number of sub-streams matches the number of the available processing elements.