Method and access means for determining the storage address of a data value in a memory device

• US 6,415,279 B1
• Filed: 03/11/1999
• Issued: 07/02/2002
• Est. Priority Date: 03/12/1998
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Kling, Lars-Örjan, Gard, Bengt Erik Ingemar, Johnsson, Sten Edvard
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Mofiz, Apu M
• Application Number:
  US09/265,952
• Time in Patent Office: 1,209 Days
• Field of Search: 707/2, 707/3, 707/7, 365/49, 704/222, 716/3, 716/20, 708/7, 708/503, 708/709
• US Class Current: 711/3
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method and an access mechanism for determining the storage address of a predetermined data value (D₁, D₂, D₃) in a memory device is disclosed. The data values are stored in an increasing order sequentially in a column direction according to a binary tree data structure. A new subtree root node (B(L(X)), B(R(X)), A=1 is calculated from the previous leaf node address (LN) when the data value to be searched is not located in the previous subtree. Since a new subtree root node (X₁) is always calculated from a previous leaf node address and the comparison result between the searched and read out value, the number of row address changes can be kept to a minimum whilst a high speed for the subtree searching is maintained. The search method and the access means is memory efficient since no pointers are used and fast, since the address of a next memory location to be investigated can always be calculated from the previous address and the last comparison result.

Claims

1. A method for determining the storage address (A(X), B(X)) of a predetermined data value (D), in a memory device (DRAM), the data values (D) being stored at predetermined storage addresses (A(X), B(X)) according to a binary tree data structure of nodes, branches, subtrees and leafs, comprising the following steps:

a) reading out a data value (D) at a predetermined current search address (A(X), B(X)) from the memory device;

b) comparing said read out data value (D) with the data value (I) to be searched to determine whether said read out data value (D) is greater or smaller than said data value (I) to be searched; and

c) determining a complete next search address (A′

, B′

) to be searched for the data value on the basis of the comparison result (C) and said current address (A(X), B(X));

wherein

d) said steps a)-c) are recursively carried out until said read out data value (D) matches said data value (I) to be searched within a predetermined tolerance (Δ

D).

2. A method according to claim 1, wherein

the data values are stored in a binary tree data structure having a predetermined number of levels (K), wherein in said step c) said next address is determined on the basis of said comparison result (C), said current search address and also said predetermined number (K) of levels, after having performed a number of comparisons in said step b) equal to said predetermined number (K) of levels.

3. A method according to claim 1, wherein

the data values (D) are in a range of a lowest data value and a highest data value, wherein a center data value corresponding to the center value of said range is stored at a predetermined root address (A(0), B(0);

“

root”

), wherein, when step a) is carried out for the first time, said root address is used as said current address.

4. A method according to claim 1, wherein

said data values are stored in said memory device in a matrix arrangement of rows and columns, wherein each data value (D) is assigned a row address (A) and a column address (B).

5. A method according to claim 1, wherein

said data values are stored in said memory device in a matrix arrangement of rows and columns, wherein each data value (D) is assigned a row address (A) and a column address (B);

and

when said comparison result (C) in step b) indicates that the read out data value is smaller than said data value to be searched (“

branch left”

), said next address in step c) is calculated by the following equation (1);

6. A method according to claim 5, wherein

said data value stored at said next address is half the data value stored at the current address.

7. A method according to claim 1, wherein

said data values are stored in said memory device in a matrix arrangement of rows and columns, wherein each data value (D) is assigned a row address (A) and a column address (B);

and

when said comparison result in step b) indicates that the read out data value is greater than said data value to be searched (“

branch right”

), said next address in step c) is calculated by the following equation (2);

8. A method according to claim 7, wherein

said data value stored at said next address is 1.5 times the data value stored at the current address.

9. A method according to claim 1, wherein

the data values are stored in a binary tree data structure having a predetermined number of levels (K), wherein in said step c) said next address is determined on the basis of said comparison result (C), said current search address and also said predetermined number (K) of levels, after having performed a number of comparisons in said step b) equal to said predetermined number (K) of levels;

said data values are stored in said memory device in a matrix arrangement of rows and columns, wherein each data value (D) is assigned a row address (A) and a column address (B); and

when said comparison result in step b) indicates that said read out data value is smaller than said data value to be searched (“

leaf left”

), said next address in step c) is calculated by the following equation (3);

10. A method according to claim 9, wherein

said data value stored at said next address is half the data value stored at the current address.

11. A method according to claim 1, wherein

the data values are stored in a binary tree data structure having a predetermined number of levels (K), wherein in said step c) said next address is determined on the basis of said comparison result (C), said current search address and also said predetermined number (K) of levels, after having performed a number of comparisons in said step b) equal to said predetermined number (K) of levels;

said data values are stored in said memory device in a matrix arrangement of rows and columns, wherein each data value (D) is assigned a row address (A) and a column address (B); and

when said comparison result in step b) indicates that the read out data value is greater than said data value to be searched (“

leaf right”

), said next address in step c) is calculated by the following equation (4);

12. A method according to claim 11, wherein

said data value stored at said next address is 1.5 times the data value stored at the current address.

13. A method according to claim 1, wherein

after said step d) information stored in association with said matching data value is read out from the memory location having said current address.

14. A method according to claim 1, wherein

the memory device is one of a DRAM or a cache memory.

15. An accedes means for a memory device for determining the storage address (A(X), B(X)) of a predetermined data value (D) in a memory device (DRAM), the data values (D) being stored at predetermined storage addresses (A(X), B(X)) according to a binary tree data structure of nodes, branches, subtrees and leafs, comprising:

a) a reading out means (R) for reading out a data value at a predetermined current search address (A(X), B(X)) of said memory device;

b) a comparison means (MC) for comparing said read out data value (D) with said data value (I) to be searched to determine whether said read out data value (D) is greater or smaller than said data value (I) to be searched; and

c) determining means (SEQ, SMB, SMA, RB, RA) for determining a complete next search address (A, B) to be searched for the data value on the basis of the comparison result (C) and said current search address (A(X), B(X));

wherein

d) said reading out means, said comparison means and said determining means carry out recursively said reading out, said comparing and said determining until said read out data value (D) matches (M) said data value (I) to be searched within a predetermined tolerance.

16. An access means according to claim 15, wherein

the data values are stored in the memory device (DRAM) in a matrix arrangement of rows and columns, wherein each data value (D) is assigned a row address (A) and a column address (B).

17. An access means according to claim 16, wherein

the data values in the memory device are stored in a binary tree data structure having a predetermined number of levels (K), wherein said state machine (SEQ) comprises a counter (CNT) which counts the number of comparisons (C) performed by said comparison means (MC).

18. An access means according to claim 16, wherein said determining means comprises:

a first and second register (RB;

RA) for holding a next column and row address (B′

, A′

);

a first and second calculation circuit (SMB, SMA) for computing the next column and row addresses (A′

, B′

) to be searched depending on the comparison result (C), the current address (B, A) and a control signal (S); and

a state machine (SEQ) for determining a search state (STATE_t) during the searching through the binary tree data structure and for determining said control signal (S) on the basis of the comparison result (C).

19. An access means according to claim 18, wherein

said state machine (SEQ) calculates said control signal (S) on the basis of the following equations (8):

20. An access means according to claim 18, wherein

said comparison result (C) is calculated by said comparison means (MC) according to the following equation (5):

21. An access means according to claim 20, wherein

said first calculation circuit (SMB) calculates the next column address (B′

) according to the following equation (6);

22. An access means according to claim 20, wherein

said second calculation circuit (SMA) calculates the next row address (A′

) according to the following equation (7);

23. An access means according to claim 15, wherein

said reading out means (R) reads out information stored in said memory means (DRAM) in association with said matching data value.

24. An access means according to claim 15, wherein

said memory device is one of a DRAM or a cache memory.

25. A method for determining the row/column addresses (B(X), A(X)) of a given data value (I) in a memory device (DRAM), in the memory positions of which data values (D) are stored in accordance with a binary tree data structure of nodes (X), branches, subtrees and leaves comprising a predetermined number K of planes in each subtree, in which

the nodes (X) and leaves (LN) correspond to the memory position;

each branch constitutes a relation of a memory position to another memory position in which the next smaller or next larger data value is stored; and

the memory positions of a respective row correspond to the nodes of a subtree;

in which the data values (D) are in a range between a lowest data value and a highest data value and a middle data value which corresponds to the mid value of the range, and is stored at a predetermined root-row/column address (B(0), A(0)), which corresponds to a root node of the binary tree data structure;

comprising of the following steps;

a) reading out a data value (D) at a present row/column address (B(X), A(X)) from the memory device, in which, when step a) has been carried out for the first time, the root-row/column address is used as the present address;

b) comparing the read out data value (D) with the data value (I) to be sought, to determine whether the read out data value (D) is greater or smaller than the data value (I) to be sought;

c) determining a complete next row/column address (B(L(X)), B(RRX));

A(L(X)), which is to be sought in accordance with the data value on the basis of the comparison result (C) of the present row/column address (B(X), A(X)), the predetermined number of planes K in each subtree and the number of comparisons carried out in step b);

in which

d) the steps a) to c) are carried out recursively, until the read out data value (D) is identical with the data value (I) to be sought within a predetermined tolerance (D);

in which

c1) when the comparison result (C) shows in step b) that the read out data value is greater (“

lefthand branch”

) or smaller (“

righthand branch”

) than the data value (I) to be sought and the number of comparisons, which were carried out in step b), is not equal to a multiple of the number K of planes in a subtree, the next column row address is computed in step c) by the following equation (1) or by equation (2);

26. A method in accordance with claim 25, wherein

after step d) information which is stored in connection with the identical data value is read out from the memory position with the present address.

27. A method in accordance with claim 25, wherein

the memory device is a DRAM or a cache memory.

28. An access means for a memory device for carrying out the method in accordance with claim 25, comprising:

a) a read out device (R) to read out a data value at the preset present column/row address B(X), A(X) of the memory device;

b) a comparative device (MC) to compare the read out data value (D) with the data value (I) to be sought, to find a comparison result, which shows whether the read out data value (D) is larger or smaller than the data value (I) to be sought; and

c) a determination device (SEQ, SMB, SMA, RB, RA) to determine the complete next row/column address (A, B), which is to be sought in accordance with the data value, in which

c1) the determination device comprises;

a first and second register (RB;

RA) to hold the next row/column address (B′

, A′

);

a first and second computation circuit (SMB, SMA) to compute the next column/row address (B′

, A′

) which is to be sought, depending on the comparison result (C), the present address (B, A) and a control signal (S); and

a state machine (SEQ) to determine a search state (STATE_t) during the search of the binary tree data structure and to determine the control signal on the basis of the comparison result (C), in which the state machine (SEQ) has a counter (CNT) which counts the number of comparisons carried out by the comparison device (MC);

b1) wherein the comparsion result (C) is computed by the comparison device (MC) as in the following equation (5);

29. An access means in accordance with claim 28, wherein

the read out device (R) reads out information which is stored in the memory device (DRAM) in connection with the identical data value.

30. An access means in accordance with claim 28, characterized in that

the memory device is a DRAM or a cache memory.

31. An access means in accordance with claim 30, characterized in that

the memory device has a row address part and a column address part and the column address part is used to select one entry of the sequential data entries within a specific cache line and the line address part is used to select a specific cache line.