Convergence analysis in multithreaded programs
US9134979B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Feb 6, 2013 |
| Grant date | Sep 15, 2015 |
| Priority date | — |
| Expiry date | Mar 20, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/456
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A basic block within a thread program is characterized for convergence based on mapping the basic block to an indicator subnet within a corresponding Petri net generated to model the thread program. Each block within the thread program may be similarly characterized. Each corresponding Petri net is enumerated to generate a corresponding state space graph. If the state space graph includes an exit node with an odd execution count attribute, such as by Petri net coloring, then the corresponding basic block is divergent. The corresponding basic block is convergent otherwise. Using this characterization technique, a thread program compiler may advantageously identify all convergent blocks within a thread program and apply appropriate optimizations to the convergent blocks.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.