Method and apparatus for arbitrating on an acyclic directed graph

摘要

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 acknowledgement 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 asserts 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 initilialization may be triggered by any node upon detection of a necessitating error or addition or removal of a connection to an existing node.