Technologies for efficient synchronization barriers with work stealing support
US9348658B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 12, 2014 |
| Grant date | May 24, 2016 |
| Priority date | — |
| Expiry date | Dec 12, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/4856
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Technologies for multithreaded synchronization and work stealing include a computing device executing two or more threads in a thread team. A thread executes all of the tasks in its task queue and then exchanges its associated task stolen flag value with false and stores that value in a temporary flag. Subsequently, the thread enters a basic synchronization barrier. The computing device performs a logical-OR reduction over the temporary flags of the thread team to produce a reduction value. While waiting for other threads of the thread team to enter the barrier, the thread may steal a task from a victim thread and set the task stolen flag of the victim thread to true. After exiting the basic synchronization barrier, if the reduction value is true, the thread repeats exchanging the task stolen flag value and entering the basic synchronization barrier. Other embodiments are described and claimed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.