Method and apparatus for arbitrating requests at two or more levels of priority using a single request line

Claim 3

A method according to claim 1, wherein said first device comprises a host CPU and said second device comprises a video controller, and wherein said shared resource comprises a video frame buffer.

Claim 4

A method according to claim 1, wherein said second predetermined logic level is opposite of said first predetermined logic level.

Claim 5

A method according to claim 3, wherein said second device, after bringing said access request signal to said first predetermined logic level at the first time, maintains said access request signal at said first predetermined logic level until said first access request has been granted or until said second device brings said access request signal to said second predetermined logic level at said second time, whichever occurs first.

Claim 6

A method according to claim 3, wherein the priority level of said second device in the arbitration is increased in response to said second device bringing said access request signal to said second predetermined logic level at said second time, wherein said second device, after bringing said access request signal to said first predetermined logic level at the first time, maintains said access request at said first predetermined logic level until said second device brings said access request to said second predetermined logic level at said second time, and wherein said second device, after bringing said access request signal to said second predetermined logic level at the second time, returns said access request signal to said first predetermined logic level and maintains it at said first predetermined logic level until said first access request has been granted.

Claim 7

A method according to claim 1, further comprising the step of granting control of said resource to said second device in accordance with the arbitration.

Claim 8

A method according to claim 6, wherein said second device maintains said access request signal at said first predetermined logic level while said second device has control of said resource, further comprising the step of returning control of said resource to said first device in response to said second device bringing said access request signal to a third predetermined logic level being opposite of said first predetermined logic level while said second device has control of said resource.

Claim 9

A method according to claim 6, further comprising the step of asserting a preemption signal to said second device in response to an access request from said first device while said second device has control of said resource.

Claim 10

A method according to claim 1, further comprising the steps of: granting control of said resource to said second device in response to negation of a first resource utilization signal from said first device while said first access request has said first priority level or said second priority level in the arbitration; and granting control of said resource to said second device in response to negation of a second resource utilization signal from said first device while said first access request has said second priority level in the arbitration but not while said first access request has said first priority level in the arbitration.

Claim 11

A method according to claim 9, wherein said first device performs a series of at least one access to said resource while said first device has control of said resource and said first resource utilization signal is asserted, and wherein said first device deasserts said second resource utilization signal after each of said accesses.

Claim 14

A method according to claim 11, wherein said first and second predetermined logic levels are opposite logic levels.

Claim 15

A method according to claim 11, further comprising the step of: while said host has control of said memory, shifting control of said memory to said device in response to said device request signal sampled at said first logic level with said first host utilization signal sampled deasserted.

Claim 16

A method according to claim 11, further comprising the steps of: while said host bus has control of said memory, transitioning to said device low priority request state a second time in response to said device request signal sampled at said first logic level with said first host utilization signal sampled asserted; and while in said device low priority request state the second time, shifting control of said memory to said device in response to said first host utilization signal sampled deasserted.

Claim 17

A method according to claim 11, further comprising the step of, while said device has control of said memory, shifting control of said memory to said host in response to said device request signal sampled at a third predetermined logic level.

Claim 18

A method according to claim 15, wherein said first and second predetermined logic levels are opposite logic levels, and wherein said third predetermined logic level is the same as said first predetermined logic level.

Claim 19

A method according to claim 11, further comprising the steps of: while said device has control of said memory, transitioning to a host preemption state in response to said first host utilization signal sampled asserted with said device request signal sampled at a fourth predetermined logic level; and while in said host preemption state, shifting control of said memory to said host in response to said device request signal sampled at a fifth predetermined logic level.

Claim 20

A method according to claim 17, wherein said first and second predetermined logic levels are opposite logic levels, and wherein said fourth logic level is the same as said first logic level and said fifth logic level is the same as said second logic level.

Claim 23

A method according to claim 19, wherein said first and second logic levels are opposite logic levels.

Claim 24

A method according to claim 19, wherein said step of transitioning to a high priority request state comprises a step of transitioning to a high priority request assertion substate of said high priority request state, and wherein said step of bringing said device request signal to a second predetermined logic level for at least one clock cycle comprises the steps of: maintaining said device request signal at said second predetermined logic level while in said high priority request assertion substate; while in said high priority request assertion substate, transitioning to a high priority request pending substate in response to said device grant signal sampled deasserted; and maintaining said device request signal at said first predetermined logic level while in said high priority request pending substate.

Claim 25

A method according to claim 19, further comprising the steps of: while in said idle state, transitioning to said low priority request state a second time in response to said high priority request signal sampled asserted; and while in said low priority request state, taking control of said resource in response to said device grant signal sampled asserted.

Claim 28

A method according to claim 23, wherein said first and second logic levels are opposite logic levels.

Claim 29

A method according to claim 23, further comprising the steps of: while in said idle state, transitioning to said low priority request state a second time in response to said low priority request signal sampled asserted; and while in said low priority request state, taking control of said resource in response to said device grant signal sampled asserted.

Claim 30

A method according to claim 23, further comprising the step of: while in control of said resource, releasing said resource and transitioning to said idle state in response to said low priority request signal and said high priority request signal both sampled deasserted.

Claim 31

A method according to claim 26, further comprising the step of maintaining said device request signal at a third predetermined logic level while in control of said resource, and wherein said step of releasing said resource comprises the step of bringing said device request signal to a fourth predetermined logic level, opposite of said third predetermined logic level.

Claim 32

A method according to claim 27, wherein said first predetermined logic level is the same as said third predetermined logic level and said second predetermined logic level is the same as said fourth predetermined logic level.

Claim 33

A method according to claim 23, further comprising the steps of: while in control of said resource, transitioning to a preemption state in response to said device grant signal sampled deasserted with at least one of said low and high priority request signals sampled asserted; asserting a preemption request to said device while in said preemption state; and while in said preemption state, releasing said resource and transitioning to said idle state in response to said low priority request signal and said high priority request signal both sampled deasserted.

Claim 34

A method according to claim 23, wherein said shared resource comprises a memory and said device comprises a video controller, said video controller having a FIFO buffer for buffering frame buffer data to be transmitted to a display, wherein said video controller asserts said low priority request signal whenever at least a predetermined number p entries in said FIFO are empty, and asserts said high priority request signal whenever at least a predetermined number q entries in said FIFO are empty, q>p.

Claim 35

Arbitration apparatus for use with a shared resource, a first device and an additional device, comprising a central arbiter having a first request input line coupled to said additional device, said central arbiter having circuitry which: in response to a first predefined event received by said central arbiter via said first request input line, arbitrates among said devices in a first arbitration for control of said resource with said additional device at a first priority level relative to said first device; and which in response to a second predefined event received by said central arbiter via said same first request input line after receipt by said central arbiter of said first predefined event, terminates said arbitration and arbitrates among said devices in a second arbitration for control of said resource with said additional device at a second priority level relative to said first device, said first and second priority levels being different.

Claim 36

Arbitration apparatus for use with a shared resource, a first device and an additional device, comprising a central arbiter having a first request input line coupled to said additional device, said central arbiter having circuitry which: in response to a first predefined event received by said central arbiter via said first request input line, arbitrates among said devices in a first arbitration for control of said resource with said additional device at a first priority level relative to said first device; and which in response to a second predefined event received by said central arbiter via said same first request input line after receipt by said central arbiter of said first predefined event, terminates said arbitration and arbitrates among said devices in a second arbitration for control of said resource with said additional device at a second priority level relative to said first device, said first and second priority levels being different.

Claim 37

Apparatus according to claim 31, for use further with a further device, wherein said central arbiter further has a second request input line coupled to said further device, and wherein said circuitry arbitrates among said first device, said additional device and said further device in each of said first and second arbitrations.

Claim 38

Apparatus according to claim 31, wherein said first predefined event received by said central arbiter via said first request input line comprises a signal on said first request input line being sampled by said circuitry at a first predefined logic level.

Claim 39

Apparatus according to claim 33, wherein said second predefined event received by said central arbiter via said first request input line comprises said signal on said first request input line being sampled by said circuitry at a second predefined logic level being opposite of said first predefined logic level.

Claim 40

Apparatus according to claim 34, wherein, after receiving said second predefined event, said circuitry ignores all subsequent logic level transitions in said signal on said first request input line until said additional device is granted control of said resource in said second arbitration.

Claim 41

Apparatus according to claim 31, wherein said second priority level is higher than said first priority level.

Claim 42

Apparatus according to claim 31, wherein in said first arbitration said central arbiter shifts control of said resource from said first device to said additional device in response to a first predefined resource utilization condition of said first device, and wherein in said second arbitration said central arbiter shifts control of said resource from said first device to said additional device in response to the earliest to occur of said first predefined resource utilization condition and a second predefined resource utilization condition.

Claim 43

Apparatus according to claim 37, wherein said first predefined resource utilization condition comprises negation by said first device of a first utilization signal coupled to said central arbiter, and wherein said second predefined resource utilization condition comprises negation by said first device of a second utilization signal coupled to said central arbiter.

Claim 44

Apparatus according to claim 37, wherein said shared resource comprises a memory, wherein said first device asserts a first utilization signal to said central arbiter when said first device is accessing said memory and also when said first device desires access to said memory, wherein said first device asserts a second utilization signal to said central arbiter while said first device is accessing said memory, said first device negating said second utilization signal in conjunction with completion of each access of said memory by said first device, wherein said first predefined resource utilization condition comprises negation by said first device of said first utilization signal, and wherein said second predefined resource utilization condition comprises negation by said first device of said second utilization signal.

Claim 45

Apparatus according to claim 31, wherein said central arbiter further has a first grant output line coupled to said additional device, and further has circuitry which, after one of said first and second arbitrations, grants control of said resource to said additional device by asserting a predefined grant signal on said first grant output line.

Claim 46

Apparatus according to claim 40, wherein said central arbiter further includes circuitry which, while said additional device has control of said resource, deasserts said predefined grant signal on said first grant output line in response to a preemption request from said first device.

Claim 47

Arbitration apparatus for use with a shared resource, a host device and an additional device, said host device requiring control of said resource with at least low and high levels of necessity at different times, said arbitration apparatus comprising a central arbiter having a device request signal line and a device grant signal line both coupled to said additional device, said central arbiter further comprising circuitry which: asserts a device grant signal on said device grant signal line in response to said central arbiter detecting said device request signal line at a first predetermined logic level while said host device does not require control of said resource; if said host device does require control of said resource when said central arbiter first detects said device request signal line at said first predetermined logic level, asserts said device grant signal in response to said host device no longer requiring control of said resource; if said host device does require control of said resource when said central arbiter first detects said device request signal line at said first predetermined logic level, asserts said device grant signal in response to said central arbiter thereafter first detecting said same device request signal line at a second predetermined logic level while said host device's requirement for control of said resource has said low level of necessity; and if said host device does require control of said resource when said central arbiter first detects said device request signal line at said first predetermined logic level, and further requires said resource with said high level of necessity when said central arbiter thereafter first detects said same device request signal line at said second predetermined logic level, asserts said device grant signal in response to said host no longer requiring said resource with said high level of necessity.

Claim 48

Arbitration apparatus for use with a shared resource, a host device and an additional device, said host device requiring control of said resource with at least low and high levels of necessity at different times, said arbitration apparatus comprising a central arbiter having a device request signal line and a device grant signal line both coupled to said additional device, said central arbiter further comprising circuitry which: asserts a device grant signal on said device grant signal line in response to said central arbiter detecting said device request signal line at a first predetermined logic level while said host device does not require control of said resource; if said host device does require control of said resource when said central arbiter first detects said device request signal line at said first predetermined logic level, asserts said device grant signal in response to said host device no longer requiring control of said resource; if said host device does require control of said resource when said central arbiter first detects said device request signal line at said first predetermined logic level, asserts said device grant signal in response to said central arbiter thereafter first detecting said same device request signal line at a second predetermined logic level while said host device's requirement for control of said resource has said low level of necessity; and if said host device does require control of said resource when said central arbiter first detects said device request signal line at said first predetermined logic level, and further requires said resource with said high level of necessity when said central arbiter thereafter first detects said same device request signal line at said second predetermined logic level, asserts said device grant signal in response to said host no longer requiring said resource with said high level of necessity.

Claim 49

Apparatus according to claim 42, wherein said central arbiter further has first and second request inputs both received from said host, wherein said central arbiter determines by sampling both said first and second inputs deasserted, that said host device does not require control of said resource, wherein said central arbiter determines by sampling said first input asserted and said second input deasserted, that said host device requires control of said resource with said low level of necessity; and wherein said central arbiter determines by sampling at least said second input asserted, that said host device requires control of said resource with said high level of necessity.

Claim 50

Apparatus according to claim 42, wherein said second predefined logic level is opposite of said first predefined logic level.

Claim 51

Arbitration apparatus for use with a requesting device, a shared resource and a central arbiter, comprising a device request output signal line coupled to said central arbiter, and further comprising device arbitration circuitry which: in response to a low priority request received by said device arbitration circuitry from said requesting device, asserts a first predefined event on said device request output signal line to said central arbiter; and which in response to a high priority request received by said device arbitration circuitry from said requesting device, asserts a second predefined event on said same device request output signal line, said second predefined event being distinguishable from said first predefined event, and neither of said first and second predefined events being qualified by any other signal output by said device arbitration circuitry.

Claim 52

Arbitration apparatus for use with a requesting device, a shared resource and a central arbiter, comprising a device request output signal line coupled to said central arbiter, and further comprising device arbitration circuitry which: in response to a low priority request received by said device arbitration circuitry from said requesting device, asserts a first predefined event on said device request output signal line to said central arbiter; and which in response to a high priority request received by said device arbitration circuitry from said requesting device, asserts a second predefined event on said same device request output signal line, said second predefined event being distinguishable from said first predefined event, and neither of said first and second predefined events being qualified by any other signal output by said device arbitration circuitry.

Claim 53

Apparatus according to claim 45, wherein said device arbitration circuitry asserts said second predefined event only after asserting said first predefined event.

Claim 54

Apparatus according to claim 45, wherein said first predefined event comprises bringing a signal on said device request output signal line to a first predefined logic level.

Claim 55

Apparatus according to claim 47, wherein said second predefined event comprises bringing said signal on said device request output signal line to a second predefined logic level opposite of said first predefined logic level, after having brought said signal on said device request output signal line to said first predefined logic level to assert said first predefined event.

Claim 56

Apparatus according to claim 45, wherein said shared resource comprises a shared memory and said requesting device comprises a FIFO memory buffering data from said shared memory to a video output, and wherein said device arbitration circuitry further comprises local circuitry which: asserts said low priority request to said device arbitration circuitry in response to said FIFO memory emptying below a predefined high water mark; and which asserts said high priority request to said device arbitration circuitry in response to said FIFO memory emptying below a predefined low water mark.

Claim 57

Apparatus according to claim 49, wherein said requesting device further comprises a graphics engine, and wherein said local circuitry asserts said low priority request to said device arbitration circuitry also in response to a request from said graphics engine for control of said resource.

Claim 58

Arbitration apparatus for use with a shared memory, a FIFO memory buffering data to a video output, and a central arbiter, comprising a device request output signal line coupled to said central arbiter, and further comprising device arbitration circuitry which: in response to said FIFO memory emptying below a predefined high water mark, asserts a first predefined state on said device request output signal line to said central arbiter; and which in response to said FIFO memory emptying below a predefined low water mark, asserts a second predefined state on said same device request output signal line to said central arbiter, wherein said device arbitration circuitry maintains said first predefined state on said device request output signal line once asserted, at least until the earlier to occur of (a) said FIFO memory empties below said predefined low water mark, and (b) said device arbitration circuitry receives an indication granting access to said shared memory.

Claim 59

Arbitration apparatus for use with a shared memory, a FIFO memory buffering data to a video output, and a central arbiter, comprising a device request output signal line coupled to said central arbiter, and further comprising device arbitration circuitry which: in response to said FIFO memory emptying below a predefined high water mark, asserts a first predefined state on said device request output signal line to said central arbiter; and which in response to said FIFO memory emptying below a predefined low water mark, asserts a second predefined state on said same device request output signal line to said central arbiter, wherein said device arbitration circuitry maintains said first predefined state on said device request output signal line once asserted, at least until the earlier to occur of (a) said FIFO memory empties below said predefined low water mark, and (b) said device arbitration circuitry receives an indication granting access to said shared memory.

Claim 60

Apparatus according to claim 51, for use further with a host device, and further comprising said central arbiter, said host device requiring control of said memory with low and high levels of necessity at different times, said central arbiter having a device grant output signal line coupled to said device arbitration circuitry and further having circuitry which: asserts a device grant signal on said device grant signal line in response to detection of said first predefined state by said central arbiter while said host device does not require control of said shared memory; if said host device does require control of said shared memory when said central arbiter detects said first predefined state, asserts said device grant signal in response to said host device no longer requiring control of said shared memory; if said host device does require control of said shared memory when said central arbiter detects said first predefined state, asserts said device grant signal in response to said second predefined state being detected by said central arbiter while said host device's requirement for control of said shared memory has said low level of necessity; and if said host device requires said shared memory with said high level of necessity when said central arbiter detects said second predefined state, asserts said device grant signal in response to said host no longer requiring said shared memory with said high level of necessity.

Claim 61

Apparatus according to claim 51, wherein said first predefined state comprises a second predefined logic level on said device request output signal line.

Claim 62

Apparatus according to claim 53, wherein said second predefined state comprises a second predefined logic level on said device request output signal line, said second predefined logic level being opposite of said first predefined logic level.

Claim 63

Apparatus according to claim 54, for use further with a host device, and further comprising said central arbiter, said host device requiring control of said memory with low and high levels of necessity at different times, said central arbiter having a device grant output signal line coupled to said device arbitration circuitry and further having circuitry which: asserts a device grant signal on said device grant signal line in response to said central arbiter detecting said first predefined state while said host device does not require control of said shared memory; if said host device does require control of said shared memory when said central arbiter detects said first predefined state, asserts said device grant signal in response to said host device no longer requiring control of said shared memory; if said host device does require control of said shared memory when said central arbiter detects said first predefined state, asserts said device grant signal in response to said central arbiter detecting said second predefined state while said host device's requirement for control of said shared memory has said low level of necessity; and if said host device requires said shared memory with said high level of necessity when said central arbiter detects said second predefined state, asserts said device grant signal in response to said host no longer requiring said shared memory with said high level of necessity.

Claim 64

An arbiter for arbitrating control of a shared resource by a plurality of devices including a subject device, said arbiter performing an arbitration with said subject device at a first priority level in response to a first type of request received from said subject device, and performing an arbitration with said subject device at a second priority level different from said first priority level in response to a second type of request received from said subject device, said arbiter comprising: arbitration circuitry; at least one respective device grant signal line output from said arbitration circuitry for each of said devices; at least one respective device request signal line input to said arbitration circuitry for each of said devices other than said subject device; and exactly one device request signal line input to said arbitration circuitry for said subject device.

Claim 65

An arbiter for arbitrating control of a shared resource by a plurality of devices including a subject device, said arbiter performing an arbitration with said subject device at a first priority level in response to a first type of request received from said subject device, and performing an arbitration with said subject device at a second priority level different from said first priority level in response to a second type of request received from said subject device, said arbiter comprising: arbitration circuitry; at least one respective device grant signal line output from said arbitration circuitry for each of said devices; at least one respective device request signal line input to said arbitration circuitry for each of said devices other than said subject device; and exactly one device request signal line input to said arbitration circuitry for said subject device.

Claim 66

An arbiter according to claim 56, wherein said shared resource is a memory, said subject device comprises a video controller, and an additional one of said devices comprises a host processor.

Claim 67

An arbiter according to claim 56, wherein said arbiter comprises exactly one respective device grant signal line output from said arbitration circuitry for each of said devices; and exactly one respective device request signal line input to said arbitration circuitry for each of said devices.

Claim 68

An arbiter according to claim 56, wherein said arbitration circuitry includes determining circuitry which detects a request of said first type received from said subject device by detecting a first predefined event received by said arbitration circuitry on said exactly one device request signal line, and detects a request of said second type received from said subject device by detecting a second predefined event received by said arbitration circuitry on said exactly one device request signal line, said second predefined event being distinguishable by said determining circuitry from said first predefined event.

Claim 71

A circuit according to claim 60, wherein said shared resource is a memory, said subject device comprises a video controller, and an additional one of said devices comprises a host processor.

Claim 72

A circuit according to claim 60, wherein said device arbitration circuit has exactly one device grant signal line input.

Claim 73

An arbiter according to claim 60, wherein said arbitration circuitry includes circuitry which, in order to arbitrate at said first priority level on behalf of said subject device, drives a first predefined event onto said exactly one device request line output, and in order to arbitrate at said second priority level on behalf of said subject device, drives a second predefined event onto said exactly one device request line output, said second predefined event being distinguishable from said first predefined event.

Claim 74

Apparatus for arbitrating control of a shared resource by a plurality of devices including a subject device, comprising: a device arbitration circuit for arbitrating at selectably a first or a second priority level on behalf of said subject device for control of said shared resource; a central arbitration circuit arbitrating control of said shared resource; at least one respective device grant signal line coupled from said central arbitration circuit to each of said devices; at least one respective device request signal line coupled from each of said devices other than said subject device, to said central arbitration circuit; and exactly one device request signal coupled from said subject device to said central arbitration circuit.

Claim 75

Apparatus for arbitrating control of a shared resource by a plurality of devices including a subject device, comprising: a device arbitration circuit for arbitrating at selectably a first or a second priority level on behalf of said subject device for control of said shared resource; a central arbitration circuit arbitrating control of said shared resource; at least one respective device grant signal line coupled from said central arbitration circuit to each of said devices; at least one respective device request signal line coupled from each of said devices other than said subject device, to said central arbitration circuit; and exactly one device request signal coupled from said subject device to said central arbitration circuit.

Claim 76

Apparatus according to claim 64, comprising exactly one respective device grant signal line coupled from said central arbitration circuit to each of said devices; and exactly one respective device request signal line coupled from each of said devices to said central arbitration circuit.

Claim 77

An arbiter according to claim 64, wherein said device arbitration circuit includes circuitry which, in order to arbitrate at said first priority level on behalf of said subject device, drives a first predefined event onto said exactly one device request line output, and in order to arbitrate at said second priority level on behalf of said subject device, drives a second predefined event onto said exactly one device request line output, said second predefined event being distinguishable from said first predefined event, and wherein said central arbitration circuit performs an arbitration with said subject device at said first priority level in response to receipt by said central arbitration circuit of said first predefined event on said exactly one device request signal line, and performs an arbitration with said subject device at said second priority level in response to receipt by said central arbitration circuit of said second predefined event on said exactly one device request signal line.

Claim 78

An arbiter according to claim 56, wherein said arbitration circuitry is formed on at least one integrated circuit chip, and wherein said exactly one device request signal line input crosses a boundary of said at least one integrated circuit chip.

Claim 79

A circuit according to claim 60, wherein said arbitration circuit is formed on at least one integrated circuit chip, and wherein said exactly one device request line output crosses a boundary of said at least one integrated circuit chip.

Claim 80

Apparatus according to claim 64, wherein said exactly one device request signal line crosses at least one integrated circuit chip boundary.