Tree structured variable priority arbitration implementing a rou

Details Tree structured variable priority arbitration implementing a rou Tree structured variable priority arbitration implementing a rou

1993-08-27

1994-04-05

Harrell, Robert B.

Boots, shoes, and leggings

395325, 3642426, 3642428, 3642429, 364DIG1, 36493701, 36494092, 3649408, 364DIG2, 3408255, 370 54, 370 63, G06F 1337, H04Q 1100

Patent

active

053013336

ABSTRACT:
An inventive arbiter controls access to a resource in a high speed computer or telecommunications network. The arbiter is capable of performing round-robin scheduling for N requests with P possible priority levels with a sublinear time complexity. The high arbitration speed is achieved through use of a tree structure with a token distribution system for implementing the round-robin scheduling policy.

REFERENCES:
patent: 3353160 (1967-06-01), Lindquist
patent: 4314335 (1982-02-01), Pezzi
patent: 4347498 (1982-08-01), Lee et al.
patent: 4621342 (1986-11-01), Capizzi et al.
patent: 4672536 (1987-06-01), Giroir et al.
patent: 4924380 (1990-05-01), McKinney et al.
patent: 4953081 (1990-08-01), Feal et al.
patent: 4980854 (1990-12-01), Donaldson et al.
patent: 5025370 (1991-06-01), Koegel et al.
patent: 5053942 (1991-10-01), Srini
patent: 5060139 (1991-10-01), Theus
patent: 5072363 (1991-12-01), Gallagher
patent: 5088024 (1992-02-01), Vernon et al.
"The Design of Nectar:A Network Backplane for Heterogeneous Multicomputers", E. A. Arnould et al., ASPLOS-III Proc. 3rd Int'l Conf. on Archit. Support for Prog. Lang. and Oper. Systems, pp. 205-216, Boston, MA, Apr. 3-6, 1989.
"An O((log N).sup.2) Control Algorithm", T-Y Feng et al., Proc. of Conf. on Parllel Processing, pp. 334-340, 1985.
"A Self-Routing Benes Network and Parallel Permutation Algorithms", D. Nassimi et al, IEEE Transaction on Computers, vol. C-30, No. 5, pp. 332-340, May 1981.
"Performance Measurements on a 128-Node Butterfly Parallel Processor", W. Crowther et al., Proc. 1985 Int. Conf. Parallel Processing, pp. 531-540, Aug. 1985.
"The IBM Research Parallel Processor (Prototype (RP3):Introduction and Architecture", G. F. Pfister et al., Proc. of Int'l Conf. on Parallel Processing, pp. 764-771, 1985.
"How to Emulate Shared Memory", A. G. Ranade, IEEE Symposium on Foundation of Computer Science, pp. 185-194, 1987.
"Non-Von's Performance on Certain Data base Benchmarks", B. K. Hillyer et al., IEEE Transactions on Software Engineering, vol. 12, No. 4, pp. 577-583, Apr. 1986.
"Multicomputers: Message-Passing Concurrent Computers", W. C. Athas et al, IEEE Computer, pp. 9-24, Aug. 1988.
"Multi-Level Shared Caching Techniques for Scalability in VMP-MC", D. R. Cheriton et al., ACM Symposium on Computer Architecture, pp. 16-24, 1989.
"GAMMA-A High Performance Dataflow Database Machine", D. DeWaitt et al., Proc. of the VLDB Conf. Japan, pp. 228-237, Aug. 1986.
"The Wisconsin Multicube: A New Larger-Scale Cache Coherent Multiprocessor", J. Goodman et al., IEEE International Symposium on Computer Architecture Conference, pp. 422-432, 1988.
"The Knockout Switch": A Simple Modular Architecture for High-Performance Packet Switching, Y.S. Yeh et al., IEEE Journal on Selected Areas in Comm., vol. SAC-5, No. 8, pp. 1274-1282, Oct. 1987.
"A Survey of Interconnection Networks", T-Y Feng, Computer, pp. 5-20, Dec. 1981.
DBC/1012 Data Base Computer "Concepts and Facilities", CO2-0001-05 Release 3.1, pp.2-1-2-
"Parallel Processing the Cm* Experience", E. Gehringer et al, Digital Press, pp. 11-13, 1987.
"Applications of Self-Routing Switches to LATA Fiber Optic Networks", C. Day et al., Int'l Switching Symposium, Phoenix Arizona, Mar. 1987.
"Starlite: A Wideband Digital Switch", A. Huang et al., Proc. of Globecom '84, pp. 121-125.
"Distributed Round-Robin and First-Come, First-Serve Protocols and Their Application to Multiprocessor Bus Arbitration", M. K. Vernon et al, The ACM 15th Ann. Int'l. Symp. on Computer Arch., 1988.
"Arbitration and Control Acquisition in the Proposed IEEE 896 Futurebus", D. M. Taub, IEEE Micro, vol. 4, No. 4, pp. 28-41, Aug. 1984.
"A Fully Distributed Arbiter for Multi-processor Systems", G. Cioffi et al, Microprocessor and Microprogramming, vol. 11, pp. 15-22, 1983.
"High-Speed Bus Arbiter for Multiprocessors", A. B. Kovaleski, IEE Proc. vol. 130, Pr, E, No. 2, pp. 49-56, Mar. 1983.
"A Variable Priority Arbiter for Resource Allocation in Asynchronous Multiprocessor Systems", Bogdan Lent, Microprocessing and Microprogramming, vol. 9, pp. 299-307, 1982.
"Arbiter Designs for Multiprocessor Interconnection Networks", Joseph K. Muppala et al, Microprocessing and Microprogramming, vol. 26, pp. 31-43, 1989.

Affiliated with

Also associated with

Rating

Tree structured variable priority arbitration implementing a rou does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Tree structured variable priority arbitration implementing a rou, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree structured variable priority arbitration implementing a rou will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-520254