Patent
1992-12-21
1997-05-13
Lee, Thomas C.
395300, 395731, G06F 1314, G06F 13362, G06F 13368
Patent
active
056301731
ABSTRACT:
A bus arbitration scheme is implemented in a system where an arbitrary assembly of nodes on a system bus have been resolved into an acyclic directed graph. The hierarchical arrangement of nodes has one node designated a root while all other nodes have established parent/child relationships with the nodes to which they are linked. Each node may have a plurality of connected child ports with a predetermined acknowledgment priority scheme established. Fair bus access arbitration provides for bus granting in a sequence corresponding to the predetermined port priorities allowing all nodes a turn on the bus. The root node may always assert its priority access status to gain bus access which is useful for accommodating a root node which requires isochronous data transfer. Alternatively, a token passing arbitration scheme may be implemented where the token for bus access is passed around the nodes according to the above-described predetermined port priority scheme. Preemptive bus initialization may be triggered by any node upon detection of a necessitating error or addition or removal of a connection to an existing node.
REFERENCES:
patent: 4344134 (1982-08-01), Barnes
patent: 4485436 (1984-11-01), Austruy et al.
patent: 4698752 (1987-10-01), Goldstein et al.
patent: 4897833 (1990-01-01), Kent et al.
patent: 5018133 (1991-05-01), Tsukakoshi et al.
patent: 5027342 (1991-06-01), Boulton et al.
patent: 5301333 (1994-04-01), Lee
patent: 5353412 (1994-10-01), Douglas et al.
patent: 5434984 (1995-07-01), Deloddere et al.
Melen et al. "Distributed Protocols for Access Arbitration in Tree-Structured Communication Channels", IEEE 1988 pp. 1539-1546.
Even et al., "How to Keep a Dynamic Distributive Directed Graph Acyclic and Yet Grant All Requests of Edge Additions", Oct. 22-25, 1990, pp. 414-425.
Jovanovic, "Software Pipelining of Loops by Pipelining Srongly Connected Components", IEEE, 1991, pp. 351-365.
Belik, "An Efficient Deadlock Avoidance Technique", IEEE Transactions on Computers, Jul. 1990, pp. 882-888.
Chaudhary, "A Near Optimal Algorithm for Technology Mapping Minimizing Area Under Delay Constraints", ACM/IEEE Design Automation Conference, Jun. 1992, pp. 492-498.
Ravindran et al., "Multicase Models and Routing Algorithms for High Speed Multi-Service Networks", IEEE, 1992, pp. 194-201.
Neilson et al., "A Dag-Based Algorithm for Distributed Mutual Exclusion", IEEE, May 1991, pp. 354-360.
Bowie, "Distributed Operating Systems", Abstract, Computer Science Conference, Feb. 20, 1975, Washington, D.C., p. 24.
Cidon and Gopal, "Dynamic Tree Detection in Computer Network", Proceedings of IEEE, Infocom, Apr. 2, 1987, pp. 181-187, San Francisco, U.S.
Wu, et al., "Prototype of Star Architecture--A Status Report", AFIPS Conference Proceedings, Jul. 18, 1995, Chicago, U.S., pp. 191-201.
Bokhardi and Raza, "Augmenting Computer Networks", Proceedings of the 1984 International Conference on Parallel Processing, Aug. 24, 1984, Ohio, U.S., pp. 338-345.
Toshinori Sueyoshi, "Hierarchical Routing Bus", Systems and Computers in Japan vol. 16 (1985) No. 6, pp. 10-19.
Database Inspec. Institute of Electrical Engineers, Stevenage, GB, Inspec. No. 898064, Bowie `Distributed Operating Systems`, see abstract and Computer Science Conference, 20 Feb. 1975, Washington D.C., US. p. 24.
Apple Computer Inc.
Dinh D.
Lee Thomas C.
LandOfFree
Methods and apparatus for bus access arbitration of nodes organi does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for bus access arbitration of nodes organi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for bus access arbitration of nodes organi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1394859