Patent ID: 8074219
Filing Date: 2011-12-06
Classification: G06F

Abstract:
1. A computer-readable storage medium having computer-executable instructions for causing a computer to perform steps comprising: re-writing a complex data parallel operation to contain data parallel operations that introduce partitioning and merging, the re-writing comprising analyzing the complex data parallel operation to label the data parallel operations as logical reordering, physical reordering, or both logical and physical reordering, and according to the labels identifying the data parallel operations as operation types comprising logical reordering, physical reordering, or both logical and physical reordering, wherein a physical reordering operation type reorders corresponding elements in physical storage without affecting the logical ordering of corresponding elements, a logical reordering operation type logically reorders corresponding elements without affecting ordering of the elements in physical storage, and a logical and physical operation type both logically reorders corresponding elements and reorders the corresponding elements in physical storage; processing each resulting partition in parallel resulting in respective data outputs; based on the identified operation types, establishing logical order information during the execution of data parallel operations; performing an order preservation process that facilitates order preservation in all of the operations that consume output from a logical reordering operation closest to a merge operation that merges output of the operations, wherein if no operations are identified as physical or logical reordering operations, and if an ordering requirement is determined to be present, then input data relative ordering among the elements is preserved during the merge operation; and merging the data outputs back into one output stream using a final merge process that preserves a desired logical ordering of the complex data parallel operation.