Method and apparatus to detect a timeout condition for a data item within a process

• US 7,016,996 B1
• Filed: 04/15/2002
• Issued: 03/21/2006
• Est. Priority Date: 04/15/2002
• Status: Expired due to Fees

• Current Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Original Assignee: Palau Acquisition Corporation
• Inventors: Schober, Richard L.
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Cerullo, Jeremy S.
• Application Number:
  US10/123,553
• Time in Patent Office: 1,436 Days
• Field of Search: None
• US Class Current: 710/113
• CPC Class Codes: G06F 13/362 with centralised access control

Abstract

A method for detecting a timeout condition for a data item (e.g., a request) within the process (e.g., within an arbitration process) includes maintaining a current time as a first N-bit binary number (A). An event time of an occurrence of an event pertaining to the data item within the process is recorded and stored as a second N-bit binary number (B). A predetermined time limit, expressed as a non-negative integer K, is configured. K is less than N and K is a logarithm base 2 of the predetermined time limit. A timeout condition pertaining to the data item is detected when a difference between the current time and the event time exceeds the predetermined time limit. The detection of the timeout condition is performed utilizing a single-stage operation. This single stage operation may include computing A (current time)−B (event time) modulo 2ⁿ≧2^k.

Claims

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₂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₂ a₁ a₀.

B=b_n-1 b_n-2 b_n-3 . . . b_i . . . b₂ b₁ b₀; 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₃{circumflex over (+)}b₃){circumflex over (+)}({overscore (α

)}₂·

b₂))

|((a₂{circumflex over (+)}b₂){circumflex over (+)}({overscore (α

)}·

b₁))

|((a₁{circumflex over (+)}b₁){circumflex over (+)}({overscore (α

)}₀·

b₀)).

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₂ a₁ a₀.

B=b_n-1 b_n-2 b_n-3 . . . b_i . . . b₂ b₁ b₀; 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₂ a₁ a₀.

B=b_n-1 b_n-2 b_n-3 . . . b_i . . . b₂ b₁ b₀, 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₂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₂ a₁ a₀.

B=b_n-1 b_n-2 b_n-3 . . . b_i . . . b₂ b₁ b₀; 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₃{circumflex over (+)}b₃){circumflex over (+)}({overscore (α

)}₂·

b₂))

|((a₂{circumflex over (+)}b₂){circumflex over (+)}({overscore (α

)}₁·

b₁))

|((a₂{circumflex over (+)}b₂){circumflex over (+)}({overscore (α

)}₀·

b₀)).

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₂ a₁ a₀.

B=b_n-1 b_n-2 b_n-3 . . . b_i . . . b₂ b₁ b₀; 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₂ a₁ a₀.

B=b_n-1 b_n-2 b_n-3 . . . b_i . . . b₂ b₁ b₀; 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.