US 6,651,083 B1Granted

Distributed service request system for providing fair arbitration using token passing scheme to resolve collisions

AssigneeTexas Instruments Incorporated

InventorsIain Robertson, Amarjit S. Bhandal, John Keay

Life of this patent

Estimating the term…

Loading patent…

Abstract

A transfer request bus (25) is described which is suitable for use in a data transfer controller processing, multiple concurrent transfer requests despite the attendant collisions which result when conflicting transfer requests occur. Transfer requests are passed from an upstream transfer request node (318) to downstream transfer request node (300) and thence to a transfer request controller with queue (320). At each node a local transfer request can also be inserted to be passed on to the transfer controller queue. Collisions at each transfer request node are resolved using a token passing scheme wherein a transfer request node possessing the token allows a local request to be inserted in preference to the upstream request.

Claims19

Dependent claims

A method of scheduling service requests from a plurality of nodes, each capable of generating a service request, said method comprising the steps of:

disposing the plurality of nodes in a chain having an upstream most node and a downstream most node, said downstream most node connected to an application device capable of servicing the service requests;
sequentially passing a token among the plurality of nodes from the upstream most node to the downstream most node following the chain, said token passing from the downstream most node to the upstream most node in a loop;
determining at each node whether a service request is received from a next upstream node;
determining at each node whether that node generates a service request;
determining at each node whether that node holds the token;
passing a service request received at one of the plurality of nodes from a next upstream node to a next downstream node if that node does not generate a service request, the downstream most node passing the service request to the application device;
passing a service request received at one of the plurality of nodes from the next upstream node to the next downstream node if that node generates a service request and that node does not hold the token;
passing a service request generated by a node to the next downstream node if that node generates a service request and does not receive a service request from the next upstream node;
and
passing a service request generated by a node to the next downstream node if that node generates a service request and that node holds the token.

7 more elements

A data processing apparatus comprising:

an application device capable of servicing requested data processing operations in response to corresponding service requests;
a plurality of nodes disposed in a chain having an upstream most node and a downstream most node, each of said plurality of nodes having
an operation unit capable of generating service requests,
a token input for receiving a token from a next upstream node in said chain, said token input of said upstream most node receiving said token from said downstream most node,
an upstream service request input for receiving a service request from a next upstream node in said chain, said upstream most node not receiving any signal on said upstream service request input,
a local service request input for receiving a service request from said operation unit,
a token output for supplying said token to a next downstream node in said chain, said downstream most node supplying said token to said token input of said upstream most node,
a downstream service request output for supplying a service request to a next downstream node in said chain, said downstream most node supplying said service request to said application device,
a control block connected to said token input, said token output, said upstream service request input, said local service request input and said downstream service request output, said control block operative to
pass said token from said upstream most token input to said downstream token output,
pass a service request received at said upstream service request input to said downstream service request output if that node does not generate a local service request, the downstream most node passing the service request to the application device;
pass a service request received at said next upstream service request input to said downstream service request output if that node generates a local service request and that node does not hold the token;
pass a local service request to said downstream service request output if that node generates a local service request and does not receive a service request from said upstream service request input;
and
pass a local service request to said downstream service request output if that node generates a local service request and that node holds the token.

12 more elements

Dependencies are inferred from the claim text.