Method for accessing a memory unit in which sequences of notes are stored, corresponding memory unit and corresponding program

• US 20040047357A1
• Filed: 03/31/2003
• Published: 03/11/2004
• Est. Priority Date: 09/29/2000
• Status: Active Grant

• Current Assignee: Siemens It Solutions and Services GmbH (Atos SE)
• Original Assignee: Siemens AG
• Inventors: Rabaioli, Giovanni
• Granted Patent: US 7,130,857 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method employs a bit sequence having a plurality of successive bits is stored in a write mode in a memory unit for a data value of a datum. The bit positions are each allocated to a data set which contains a data field for storing the datum. This measure enables logic operations to be carried out very rapidly.

Claims

1. Method for accessing a memory unit (16),

in which a bit sequence (25, 25a) consisting of a plurality of successive bits (74), each of which has one of two bit values, is stored in a write mode of a memory unit (16) for a data value (102) of a datum, or in which at least a part of the bit sequence (25, 25a) is read in a read mode,

in which each of some of the bit positions (74) or all of the bit positions (74) is allocated to a data set (30 to 34) containing a data field for storing the datum,

in which the one bit value in the bit sequence (25, 25a) notes that the data set (30 to 34) allocated to the bit position with this bit value contains the data value in the data field for storing the datum,

and in which the other bit value in the bit sequence (25, 25a) notes that the data set (30 to 34) allocated to the bit position (74) with this bit value does not contain the data value in the data field for storing the datum.

2. Method according to claim 1,

characterized in that

the bit sequence (25, 25a) contains more bit positions than are contained in a data word of a processor accessing the memory unit (16);

the bit sequence (25, 25a) preferably contains several thousand, several hundred thousand or several million bit positions, to which are allocated several thousand, several hundred thousand or several million data sets (30 to 34).

3. Method according to claim 1 or 2,

characterized in that

a processor (12) links two bit sequences according to a logic operation, preferably according to the OR function or the AND function,

whereby bit positions (82) belonging to the same data set are linked,

and whereby preferably as many bit positions are processed simultaneously as there are in one data word of the processor.

4. Method according to one of the preceding claims,

characterized in that

two bit sequences are linked simultaneously by at least two processors according to a logic operation, or

a bit sequence is processed according to a logic operation, preferably according to the NOT operation, by at least two processors.

5. Method according to one of the preceding claims,

characterized in that

the bit sequence (25, 25a) is compressed using a compression method, preferably by replacing successive data words in which just one bit value occurs by in each case at least one number value (W1a) that indicates the number of words replaced,

whereby in each case a further number value preferably indicates the number of succeeding uncompressed data words (W2a, W3a).

6. Method according to one of the preceding claims,

characterized in that

the bit position (74) in the bit sequence (25, 25a) designates the number of the allocated data set (30 to 34);

in that this number is noted in the data set (30 to 34);

or

the memory address of the allocated data set (30 to 34) can be calculated from this number preferably using a method that is the same for the data sets.

7. Method according to one of the preceding claims,

characterized in that

the bit sequence (25, 25a) is stored in several memory areas (B1 to B3) that are preferably of the same size;

a sequence of references with references (P1 to Pn) to the memory areas (B1 to B3) defines the order in which the bit sequence (25, 25a) is stored in the memory areas (B1 to B3).

8. Method according to claim 7,

characterized in that

the utilization of the memory areas (B1 to B3) is monitored,

the utilization of other memory areas is also changed in the event of measures to incorporate a new memory area or to release a memory area.

9. Method according to claim 8,

characterized in that

when incorporating a new memory area (B2a) to store a part of the bit sequence (25, 25a), a part (II) of the bit sequence (25, 25a), preferably a part (II) for which more than one third of the memory area (B2) is required, is moved into the new memory area (B2a) from another memory area (B2)

a reference (P2a) to the new memory area (B2a) is inserted into the sequence of references (P1 to Pn) or appended to the sequence of references.

10. Method according to claim 8,

characterized in that

a check is made as to whether less than one third of a memory area (B3) is utilized by the part (IIa) of the bit sequence (25, 25a) stored in it;

a check is made as to whether the memory area (B2, B4) entered before and/or after this memory area (B3) in the sequence of references has sufficient space to accommodate the part (IIa) of the bit sequence (25, 25a);

the part (IIa) of the bit sequence (25, 25a) is transferred if there is sufficient space available and the reference (P3) to the memory area (B3) now freed up is removed from the sequence of references.

12. Memory unit according to claim 11,

characterized in that

the memory unit (16) contains memory cells with data that are required to execute the method according to one of claims 1 to 10.

13. Program having an instruction sequence, the execution of which by a processor (12) executes a method according to one of claims 1 to 10.

11. Memory unit (16)

having memory cells in which a datum of a bit sequence (25, 25a) consisting of a plurality of successive bits (74), each of which has one of two bit values, is stored for a data word (102), and having memory cells for storing a plurality of data sets (30 to 34), each of which is allocated to a bit position (74) of the bit sequence (25, 25a) and contains a data field for storing the datum,

whereby the one bit value in the bit sequence (25, 25a) notes that the data set (30 to 34) allocated to the bit position with this bit value contains the data value in the data field for storing the datum,

and whereby the other bit value in the bit sequence (25, 25a) notes that the data set (30 to 34) allocated to the bit position (74) with this bit value does not contain the data value in the data field for storing the datum.