Patent
1996-09-24
1998-09-01
Lee, Thomas C.
39520006, G06F 1300, G06F 1338, G06F 1340
Patent
active
058022899
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: 4412285 (1983-10-01), Neches et al.
patent: 4698752 (1987-10-01), Goldstein et al.
patent: 4706080 (1987-11-01), Sincoskie
patent: 4811337 (1989-03-01), Hart
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: 5113523 (1992-05-01), Colley et al.
patent: 5138615 (1992-08-01), Lamport et al.
patent: 5150360 (1992-09-01), Perlman et al.
patent: 5301333 (1994-04-01), Lee
patent: 5353412 (1994-10-01), Douglas et al.
Melen, et al. "Distributed Protocols for Access Arbitration in Tree-Structured Communication Channels", IEEE (1988), pp. 1539-1546.
Toshinori Sueyoshi, "Hierarchial Routing Bus", Systems and Computers in Japan, vol. 16, No. 6, (1985), pp. 10-19.
Even, et al., "Hot 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 Strongly 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, 1985, 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., U.S. p. 24.
Apple Computer Inc.
Dinh D.
Lee Thomas C.
LandOfFree
Method for propagating preemptive bus initialization on an acycl 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 propagating preemptive bus initialization on an acycl, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for propagating preemptive bus initialization on an acycl will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-279697