Method for preventing buffer deadlock in dataflow computations
US6088716A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 28, 1997 |
| Grant date | Jul 11, 2000 |
| Priority date | — |
| Expiry date | Apr 28, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/524
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A buffer deadlock prevention technique for dataflow computations. The invention that implements the following algorithm: (1) providing a supplemental buffer for each input of a "downstream" program; (2) partitioning the inputs of each downstream program into disjoint input sets, such that two inputs are in the same input set if and only if such inputs come, either directly or indirectly, from a common upstream program; (3) attempting to read data into a downstream program from an "upstream" program via an input I in an input set; (4) if no data is currently available from input I, and if any other input J in the same input set has data available, then reading into the downstream program available data from each such input J and storing such that data in the supplemental buffer corresponding to such input J until such time as available data is exhausted on all such inputs J or data becomes available on input I.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.