Parallelization scheme for generic reduction
US7620945B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 16, 2005 |
| Grant date | Nov 17, 2009 |
| Priority date | — |
| Expiry date | Dec 5, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/45
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
One embodiment of the present invention provides a system that supports parallelized generic reduction operations in a parallel programming language, wherein a reduction operation is an associative operation that can be divided into a group of sub-operations that can execute in parallel. During operation, the system detects generic reduction operations in source code. In doing so, the system identifies a set of reduction variables upon which the generic reduction operation will operate, along with a set of initial values for the variables. The system additionally identifies a merge operation that merges partial results from the parallel generic reduction operations into a final result. The system then compiles the program's source code into a form which facilitates executing the generic reduction operations in parallel. By supporting the parallel execution of such generic reduction operations in this way, the present invention extends parallel execution for reduction operations beyond basic commutative and associative operations such as addition and multiplication.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.