Programmatic iteration scheduling for parallel processors
US6438747B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 20, 1999 |
| Grant date | Aug 20, 2002 |
| Priority date | — |
| Expiry date | Aug 20, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/452
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A parallel compiler maps iterations of a nested loop to processor elements in a parallel array and schedules a start time for each iteration such that the processor elements are fully utilized without being overloaded. The compiler employs an efficient and direct method for generating a set of iteration schedules that satisfy the following constraints: no more than one iteration is in initiated per processor element in a specified initiation interval, and a new iteration begins on each processor element nearly every initiation interval. Since the iteration scheduling method efficiently generates a set of schedules, the compiler can select an iteration schedule that is optimized based on other criteria, such as memory bandwidth, local memory size of each processor element, estimated hardware cost of each processor element, etc. The iteration scheduling method is useful for compilers where the underlying architecture is fixed, as well as for an automated processor array synthesis system where the nested loop is converted into a set of parallel processes for synthesis into a parallel processor array.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.