Granted Patent B1

US 7,016,996 · App. 10/123,553 · Granted Mar 21, 2006

Abstract

Claims (85)

1. A method to detect a timeout condition for a data item within the process, the method including:

maintaining a current time as a first N-bit binary number (A);

recording an event time of an occurrence of an event pertaining to the data item within the process, and storing the event time as a second N-bit binary number (B);

configuring a predetermined time limit expressed as a non-negative integer K, where K is less than N and K is a logarithm base 2 of the predetermined time limit; and

detecting a timeout condition pertaining to the data item when a difference between the current time and the event time exceeds the predetermined time limit,

wherein the detection of the timeout condition is performed as a single-stage operation.

2. The method of claim 1 wherein the single-stage operation is a single O (log 2 n) computation.

3. The method of claim 1 wherein the single-stage operation is performed as a single combinatorial operation.

4. The method of claim 1 wherein, if N>=1 and K=0, the timeout condition is detected if a positive Boolean value results from a first computation (A#B).

5. The method of claim 1 wherein, if N>=2 and K=1, the timeout condition is detected if a positive Boolean value z results from a second computation:

Where:

A=a n-1 a n-2 a n-3 . . . a i . . . a 2 a 1 a 0 .

B=b n-1 b n-2 b n-3 . . . b i . . . b 2 b 1 b 0 ; and

z←((a n-1 {circumflex over (+)}b n-1 ){circumflex over (+)}(α n-2 ·b n-2 ))

|((a n-2 {circumflex over (+)}b n-2 ){circumflex over (+)}(α n-3 ·b n-3 ))

((a n-3 {circumflex over (+)}b n-3 ){circumflex over (+)}({overscore (α)} n-4 ·b n-4 ))

:

|((a i {circumflex over (+)}b i ){circumflex over (+)}({overscore (α)} i-1 ·b i-1 ))

:

|((a 3 {circumflex over (+)}b 3 ){circumflex over (+)}({overscore (α)} 2 ·b 2 ))

|((a 2 {circumflex over (+)}b 2 ){circumflex over (+)}({overscore (α)}·b 1 ))

|((a 1 {circumflex over (+)}b 1 ){circumflex over (+)}({overscore (α)} 0 ·b 0 )).

6. The method of claim 1 wherein, if N>=3 and K=N−1, the timeout condition is detected if a positive Boolean value z results from a third computation:

Where:

A=a n-1 a n-2 a n-3 . . . a i . . . . a 2 a 1 a 0 .

B=b n-1 b n-2 b n-3 . . . b i . . . b 2 b 1 b 0 ; and

z←(a n-1 {circumflex over (+)}b n-1 ){circumflex over (+)}(A[n−2 . . . 0]<B[n−2 . . . 0]).

7. The method of claim 1 wherein, if N>=4 and N−2>=K>=1, the timeout condition is detected if a positive Boolean value z results from a fourth computation:

Where:

A=a n-1 a n-2 a n-3 . . . a i . . . a 2 a 1 a 0 .

B=b n-1 b n-2 b n-3 . . . b i . . . b 2 b 1 b 0 , and

z←(((A[n−1 . . . k]−B[n−1 . . . k]) modulo 2 n-k )≧2)

|((A[n−1 . . . k]≠B[n−1 . . . k]){circumflex over (+)}(A[k−1 . . . 0])).

8. The method of claim 1 wherein the data item comprises a resource request, the process comprises an arbitration process between competing requests.

9. The method of claim 8 wherein the event comprises an arrival of the resource request at an interconnect device, and the event time comprises an interconnect device arrival time of the arrival of the resource request at the interconnect device.

10. The method of claim 9 wherein the event comprises an arrival of the resource request at a resource allocator of an arbiter for the interconnect device, and the event time comprises an allocator arrival time of the arrival of the resource request at the resource allocator.

11. The method of claim 8 wherein the event comprises an arrival of the resource request at the head of a queue within the arbitration process, and the event time comprises a head-of-queue arrival time.

12. A system to detect a timeout condition for a data item within the process, the system including:

a memory to store a current time as a first N-bit binary number (A) and to store an event time as a second N-bit binary number (B), the event time being of the time of an occurrence of an event pertaining to the data item within the process, and

a detector to detect a timeout condition pertaining to the data item when a difference between the current time and the event time exceeds a predetermined time limit,

wherein the predetermined time limit is expressed as a non-negative integer K, where K is less than N and K is a logarithm base 2 of the predetermined time limit, and wherein the detection of the timeout condition is performed as a single-stage operation.

13. The system of claim 12 wherein the single-stage operation is a single O (log 2 n) computation.

14. The system of claim 12 wherein the detect the comprises combination logic, and wherein the single-stage operation is performed as a single combinatorial operation.

15. The system of claim 12 wherein, if N>=1 and K=0, the timeout condition is detected if a positive Boolean value results from a first computation (A≠B).

16. The system of claim 12 wherein, if N>=2 and K=1, the timeout condition is detected if a positive Boolean value results from a second computation:

Where:

A=a n-1 a n-2 a n-3 . . . a i . . . a 2 a 1 a 0 .

B=b n-1 b n-2 b n-3 . . . b i . . . b 2 b 1 b 0 ; and

z←(a n-1 {circumflex over (+)}b n-1 ){circumflex over (+)}({overscore (α)} n-2 ·b n-2 ))

((an n-2 {circumflex over (+)}b n-2 ){circumflex over (+)}({overscore (α)} n-3 ·b n-3 ))

((a n' {circumflex over (+)}b n-3 ){circumflex over (+)}({overscore (α)} n-4 ·b n-4 ))

:

|((a i {circumflex over (+)}b i ){circumflex over (+)}({overscore (α)} i-1  b i-1 ))

:

|(a 3 {circumflex over (+)}b 3 ){circumflex over (+)}({overscore (α)} 2 ·b 2 ))

|((a 2 {circumflex over (+)}b 2 ){circumflex over (+)}({overscore (α)} 1 ·b 1 ))

|((a 2 {circumflex over (+)}b 2 ){circumflex over (+)}({overscore (α)} 0 ·b 0 )).

17. The system of claim 12 wherein, if N>=3 and K=N−1, the timeout condition is detected if a positive Boolean value results from a third computation:

Where:

A=a n-1 a n-2 a n-3 . . . a i . . . a 2 a 1 a 0 .

B=b n-1 b n-2 b n-3 . . . b i . . . b 2 b 1 b 0 ; and

z←(a n-1 {circumflex over (+)}b n-1 ){circumflex over (+)}(A [n−2 . . . 0]<B[n−2 . . . 0]).

18. The system of claim 12 wherein, if N>=4 and N-2>=K>=1, the timeout condition is detected if a positive Boolean value results from a fourth computation:

Where:

A=a n-1 a n-2 a n-3 . . . a i . . . a 2 a 1 a 0 .

B=b n-1 b n-2 b n-3 . . . b i . . . b 2 b 1 b 0 ; and

z←(((A[n−1 . . . k]−B[n−1 . . . k]) modulo 2 n-k )≧2)

|((A[n−1 . . . k]≠B[n−1 . . . k]){circumflex over (+)}(A[k−1 . . . 0]<B[k−1 . . . 0])).

19. The system of claim 12 wherein the data item comprises a resource request, the process comprises an arbitration process between competing requests, and the memory and detector are associated with an arbiter that performs the arbitration process.

20. The system of claim 19 wherein the event comprises an arrival of the resource request at an interconnect device, and the event time comprises an interconnect device arrival time of the arrival of the resource request at the interconnect device.

21. The system of claim 20 wherein the event comprises an arrival of the resource request at a resource allocator of an arbiter for the interconnect device, and the event time comprises an allocator arrival time of the arrival of the resource request at the resource allocator.

22. The system of claim 19 wherein the event comprises an arrival of the resource request at the head of a queue within the arbitration process, and the event time comprises a head-of-queue arrival time.

23. Apparatus to detect a timeout condition for a data item within the process, the system including:

first means for storing a current time as a first N-bit binary number (A) and for storing an event time as a second N-bit binary number (B), the event time being of the time of an occurrence of an event pertaining to the data item within the process, and

second means for detecting a timeout condition pertaining to the data item when a difference between the current time and the event time exceeds a predetermined time limit,

wherein the predetermined time limit is expressed as a non-negative integer K, where K is less than N and K is a logarithm base 2 of the predetermined time limit, and wherein the detection of the timeout condition is performed as a single-stage operation.

24. A machine-readable medium storing a description of a circuit, said circuit comprising:

a memory to store a current time as a first N-bit binary number (A) and to store an event time as a second N-bit binary number (B), the event time being of the time of an occurrence of an event pertaining to the data item within the process, and

a detector to detect a timeout condition pertaining to the data item when a difference between the current time and the event time exceeds a predetermined time limit,

wherein the predetermined time limit is expressed as a non-negative integer K, where K is less than N and K is a logarithm base 2 of the predetermined time limit, and wherein the detection of the timeout condition is performed as a single-stage operation.

25. The machine-readable medium of claim 24 wherein the description comprises a behavioral level description of the circuit.

26. The machine-readable medium of claim 25 wherein the behavioral level description is compatible with a VHDL format.

27. The machine-readable medium of claim 25 wherein the behavioral level description is compatible with a Verilog format.

28. The machine-readable medium of claim 24 wherein the description comprises a register transfer level netlist.

29. The machine-readable medium of claim 24 wherein the description comprises a transistor level netlist.

Assignments (14)