Parallel processing method and system using a lazy parallel data type to reduce inter-processor communication

A parallel processing method for executing a parallel program comprising:

• distributing elements of a collection oriented data type across processors in a parallel computer, such that each of the processors has local elements of the collection oriented data type;
• in each processor, performing data parallel operations locally on the local elements of the processor;
• marking the collection oriented data type as unbalanced when a data parallel operation causes the elements to be unbalanced across the processors;
• when making a function call on the collection oriented data type, checking to determine whether the collection oriented data type is not balanced, and if not, redistributing the elements of the collection oriented data type across the processors so that the elements of the collection oriented data type are balanced across processors before executing the function call;
• and
• when redistribution is required, inserting programming code into the parallel program to redistribute the elements before the function call occurs.

A computer readable medium comprising:

• a preprocessor for converting a parallel program written in a programming language with control parallel and data parallel operations to an imperative, sequential programming code and calls to a message passing interface for inter-processor communication on a parallel computer;
• wherein the preprocessor is operable to insert a check function into the translated program to test whether a collection oriented data type is in a lazy state and to insert code for redistributing the collection oriented data type when it is in a lazy state;
• a compiler for compiling the imperative programming code and the calls to the message passing interface generated by the preprocessor;
• a message passing interface run-time library for performing the calls to the message passing interface;
• a parallel language run-time library including code for redistributing the collection oriented data type when it is in a lazy state;
• and
• a linker for linking the compiled imperative programming code and calls to the message passing interface with the message passing interface run-time library and the parallel language run-time library.

A parallel processing method for executing a parallel program comprising:

• subdividing a group of processors into subgroups, with one sub-group per parallel function call;
• distributing elements of a collection oriented data type across the processors in a group, such that each of the processors has local elements of the collection oriented data type;
• in each processor, performing data parallel operations locally on the local elements of the processor;
• deferring distribution of the local elements on each processor to another processor until an operation is performed on the collection oriented data type requiring that the elements be re-distributed;
• translating the parallel program into imperative programming code and calls to a message passing interface;
• for an operation on the collection oriented data type that require a re-distribution of the elements across processors, inserting programming code into the translated program for redistributing the elements before the operation is performed.