Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Patent
1997-04-28
2000-07-11
Banankhah, Majid A.
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
709104, 709107, G06F 1582
Patent
active
060887168
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.
REFERENCES:
patent: 4298954 (1981-11-01), Bigelow et al.
patent: 5204965 (1993-04-01), Guthery et al.
patent: 5487167 (1996-01-01), Dinallo et al.
patent: 5568614 (1996-10-01), Mendelson et al.
patent: 5684953 (1997-11-01), Hummel
patent: 5790893 (1998-06-01), Polge et al.
UNIX System Laboratories, Programmer's Guide: Streams, pp. 2-9 to 2-19, 1992.
F. Lau et al, "Propagating Buffer: a New Approach to Deadlock Freedom in Store-and-forward Networks", IEEE, pp. 804-807, 1991.
M. Coli, et al, "An Adaptive Deadlock and Livelock Free Routing Algorithm", IEEE, pp. 288-295, 1995.
M. Ade, et al, "Buffer Memory Requiremetns in DSP Applications", IEEE, pp. 108-123, 1994.
Lasser Clifford A.
Stanfill Craig W.
Ab Initio Software Corporation
Banankhah Majid A.
Lao Sue
LandOfFree
Method for preventing buffer deadlock in dataflow computations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for preventing buffer deadlock in dataflow computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for preventing buffer deadlock in dataflow computations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-552392