JPH02501604A - associative memory system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention] associative memory system The invention relates to an associative memory system.The invention also relates to an active memory circuit and an associative memory system. or an associative memory system comprising one or more active memory circuits. .

Data in a record format where each record contains multiple attributes or multiple pieces of information In a computer system containing a large number of If records with specific attributes are to be accessed based on The process of searching for records to output requires a considerable amount of calculation time. cormorant.

This problem is even more accentuated when records are stored on external storage devices such as disks. Ru.

One way to alleviate this problem is to access records based on their attributes or content. It is important to store it in the form that is possible. This type of memory system is an associative memory system. One way to accomplish this is to convert the record file to bitmatsu, known as a system. It is coded to form a matrix, and searches are performed based on it. records that satisfy a particular proposition are found.

A bitmap matrix is a bitmap matrix where each row represents a particular record and each column represents a bitmap. It has an arrangement of bits known as depending on the form of encoding used Each bit within a row typically represents a predetermined attribute of the respective record. the If the bit is 1, the record has an attribute, and if the bit is O, the record has an attribute. Therefore, each bitmap has no information about which records have specific attributes. Provide an indication of which ones do not have.

For complex propositions such as which records have a particular combination of attributes, A logical operation or series of logical operations on the selected bitmap corresponding to the proposition. A bitmap that performs calculations to provide an indication of which records satisfy a proposition. It is resolved by generating a tsup.

One object of the present invention is that it can be used with a host computer and is relatively inexpensive and comparatively Associative memory system that can search records at high speed, especially speed As for the search is accomplished by the host computer without a memory system The purpose of the present invention is to provide an associative memory system with speeds that will be faster than ever before.

Another object of the present invention is to perform logical operations on bitmap matrices. An object of the present invention is to provide an active memory circuit capable of

Yet another object of the invention is to provide an associative memory comprising one or more active memory circuits. It is to provide a memory system.

According to the present invention, a host memory for storing a plurality of records and a host processor buffer are provided. is an associative memory system for connection with a host computer that has a So, the memory system is: A bitmap matrix representing records stored in the host computer. , and in use, connects the host processor bus index memory means addressable by a host computer; The bitmap stored in the means is accessed and the bitmap corresponding to the bitmap is accessed. In use, the host processor bus is connected to the host processor bus. an index processor means controlled by a computer and the index memory hand; the memory means and the processor means; A memory system bus employed for the passage of bitmaps to and from the An associative memory system is provided comprising: an associative memory system;

Preferably, the index memory means includes a plurality of index memories, and the index memory means includes a plurality of index memories. Each of the index memories includes: an array of memory cells; a shift register with a parallel input/output bus connected to the array; Serial input port and serial output port at opposite ends of the shift register and the parallel power/output bus connects selected rows of data in the array. and a shift register that is capable of accessing the memory system bus. Connect the 8 serial input and output ports of the 8 index memory to the index processor. connected in parallel to the processor means; The selected rows of the data accessed at the same time are at least one bitmap form.

According to the present invention, the bitmap is arranged in rows and columns and stores at least a part of the bitmap. an array of memory cells suitable for storing at least a portion of a bitmap; with a suitable shift register; a logic unit connected between the array and the shift register; The array, shift register and logic unit are comprised of integrated circuits; The logical unit can copy selected columns of the array. performs the selected logical operation between the contents of the shift register and the selected column of the array. and the result of the operation is stored in the shift register. A dynamic memory circuit is provided.

According to the invention, the above-defined active memories include one or more of the above-defined active memories. A content addressable memory is also provided.

Preferred embodiments of the invention are described, by way of example only, with reference to the following accompanying figures: Figure 1 shows the array of records and the bits corresponding to the propositions given for the array of records. Figure 2 is a diagram of a bitmap that corresponds to a compound proposition; is a diagram of a plurality of bitmaps representing records corresponding to component propositions of a number; Figure 3 contains a superimposed code index for an array of records. Figure 4 is a diagram of a bitmap matrix representing pool attributes; Figure 5 is a diagram of a bit containing logical operations on binary coded attributes. Fig. 6 is a diagram of searching a bitmap matrix; An illustration of the greater/less than classification performed on the algorithm that accomplishes the classification. is a diagram containing a list of programs; Figure 7 shows how the minimum value of the bitmap matrix is found. 2 is a diagram containing a list of algorithms for determining the minimum value; FIG. 8 is a block diagram of a memory system according to the present invention attached to a host computer. It is a diagram; FIG. 9 is a diagram showing the arrangement of memory in the system of FIG. 8; FIG. 10 is a diagram further illustrating the arrangement of memory within the system of FIG. 8; Figure 11 represents the bitmap operations that the system of Figure 8 can perform. It is a diagram; Figure 12 is a memo and re-chip diagram for the system in Figure 8; Figure 13 is a diagram of the system in Figure 8. Figure 14 is a diagram of the memory unit of the system; Figure 14 is an index of the system of Figure 8; Here is a diagram of the processor: FIG. 15 is a diagram of the data flow of the system of FIG. 8; FIG. 16 is a diagram of the data flow of the system of FIG. This is a block diagram of an active memory circuit: 17 is a more detailed block diagram of the circuit of FIG. 16; FIG. 18 is a more detailed block diagram of the circuit of FIG. is a circuit diagram of a shift register cell and a logic cell of the circuit; Figure 19 shows the architecture of an index memory system that uses the active memory shown in Figure 16. Figure 20 is a diagram of the superimposed codeword calculation unit. It is a diagram of Figure 21 is a diagram of a unit for determining and storing the address of the corresponding record. can be; Figure 22 is a diagram of the compression/expansion unit; Figure 23 is a diagram of the special table reference unit. Figure 24 is a diagram of multiple cascaded active memories; ; Figure 25 is a diagram of the memory system of Figure 8 that employs the active memory circuit of Figure 16. be.

File 2 shown in Figure 1 is stored in the memory built into the computer system. or stored on a secondary storage device such as a disk, comprising a number of records 4. Ru. When indexing or searching file 2, a set of records 4 is It is necessary to decide whether it matches the property or proposition. For example, each record 4 is of a vehicle. Information about the vehicle registration such as color, vehicle owner, state where the vehicle was registered, and date of registration. Contains information about As shown in Figure 1, the proposition is which vehicle is red and N , S, W, state, and whether it was registered on or after January 1, 1985, from Fal 2. It is a matter of making decisions. The set of records corresponding to such a proposition is shown in Figure 1. It can be determined from the bitmap 6 as shown in FIG. Bitmap 6 is record 4 This is a bit array with one bit per piece. Bit corresponding to specific record 4 is '1 if record 4 satisfies or corresponds to the proposition, and if it does not correspond to the proposition, then It becomes 0. Thus, bitmap 6 is a compressed set of records that satisfy the proposition. In the illustrated example, a table of 4096 records or File 2 requires 4096 bits or 512 bytes for bitmap 6. do.

Figure 1 represents the complex proposition consisting of: Bitmap 6 or Record 4 corresponds to a single proposition that is a component of a compound proposition as shown in Figure 2. A simple logical operation on bitmaps 8, 10, and 12 representing records Therefore, it can be calculated. Following the previous example, each proposition is Records where the vehicle is red, records registered in N, S, W, states, registrations. Three bitmaps showing records whose recording date is after January 1, 19858 ．． 10 and 12 can be decomposed into three propositions to determine.

Perform an AND operation on the three bitmaps 8.1 (l and 12) as shown in Figure 2. A bitmap 6 representing records corresponding to the compound proposition is then obtained. Each bit Once the topmaps are kept in memory, the elementary bitmaps 8, 10 and 12 are Assuming that the bitmap 6 has already been obtained, the final bitmap 6 can be calculated immediately.

To fully benefit from a fast bitmap processor, you need more than that. Compute bitmaps of elementary propositions by logical operations on elementary bitmaps. It must be possible to calculate One way to accomplish this is to ial-Match Retrieval via Plethod of S upperimposed　Codes”　Robe-rts　C,S, (197 9) Proceedings of IEEE Vol. 67, Na12. p using the superimposed code indexing method described in p. It is to use it. This method will be described schematically with reference to FIG. record 4 The array is in the superimposed code index as bit matrix 14. It is expressed in

To determine which record 4 has a red vehicle according to the previous example: , a predetermined proposition code 2o is generated. Code 20 is to satisfy the proposition is used to determine the final bitmap 22 representing the records corresponding to the proposition. A logical AND operation must be performed on columns 16 and 18 of the map. It shows that Each column of matrix 14 can be thought of as a bitmap. Bitmap 22 is obtained by accomplishing the logical operation shown by Problem 2o. It will be done.

The advantages of superimposed code indexes are: 1. The index is compressed, for example, for 4096 records. The index occupies only 64 bytes of memory.

If the Z index is expressed in column format as shown in Figure 3, any particular Only a portion of the indicators are processed for the proposition.

The power of the superimposed code index is that the attributes of the record of interest are It is increased by using methods such as those expressed in the form.

However, the disadvantages of superimposed code are as follows: 1. Since all ordering information is lost, the greater or less proposition cannot be reached. Although not done, they are often used to encode ranges like discrete attributes. Therefore, it is approximated.

2. Since there is a (usually small) Wi rate at which a wrong choice occurs, The bitmap created by Contains. The main problem with this is that the record analogy corresponding to the non-equality proposition Superimposed for the purpose of finding unregistered vehicles in N, S, W, etc. This means that the code cannot be used.

However, there are other ways to process indicators. A record's pool attribute is For example, if the attribute indicates that the vehicle owner paid the registration fee. If you paid or not, a true or false answer is simply required. As shown in Figure 4 The record pool attribute is for array 26 of record 28, and the attribute is can be determined by simply examining the bitmap 24 with a single bit representing I can do it. Bitmap 24 provides an immediate indication of whether the attribute is true. genus The bitmap 30 for a proposition whose gender is false is map 3 as shown in FIG. Calculated by taking the logical inversion of 0.

This leads to a process that yields the complete equality proposition, as shown in Figure 5. Ru. Attributes consisting of, for example, the state of registration, are encoded in binary numbers and a table 32 of the attributes is a collection of pool properties, and a complete equality proposition is a series of true and false pool propositions. and can be placed. Non-equality propositions can be handled in a similar manner.

As shown in FIG. , 36 and 38, and the state of registration is N, S, W. The bitmap 39 shown is determined.

However, the drawback of the above approach is that the attributes have a small number of bits (i.e. 5 or less), use a superinput to compute the set of records corresponding to the proposition. The problem is that it requires more time than the paused code attribute. but However, it is partially useful for attributes with a very small number of possible values. be.

As shown in Figure 6, the proposition involving determining the order of records is It can be calculated using An algorithm that determines whether the value is greater than or less than the boundary value. The algorithm is detailed in Figure 6 in PASCAL format, where the labels L, G and B[i] represent a bitmap column or kXf bit matrix, and k is the number of records in table 40 and n is the number of encoded records in table 40. It is the number of bits of the record. W is test word 42, greater than or less than proposition represents the basic code. This algorithm is Sorting of the records in table 40 with respect to code 42 is accomplished. The algorithm is an L map 44 representing records known to be less than test word 42; From a G-map representing records known to be greater than test word 42. It has two working bitmaps. The first bit is different from the test word. (compare from most significant bit to least significant bit) to the corresponding bit in the test word. A given word or coded record is tested if the bit is greater than Greater than word 42. The bit can only take the value O or 1, so the word first in a different bit test word if the code is greater than the test word. That bit of an O coded record or word should be 1. Te If a bit in the stword is O, then that bit is the bit under consideration. The set of coded words determined to be greater than the test word when A set of coded words or records that is 1 in the set.

Similarly, if the test word has a 1 in a particular bit position, then A set of coded words that is smaller than the test word in terms of focus position. is the set of encoded records that have a value of 0 in that bit position.

When test word 42 has a 0 in a particular bit position, the minutes in table 40 An unclassified reference value or coded word is equivalent to a test word 42. either continues to be or is determined to be greater than test word 42. . When test word 42 is 1 in that bit position, an unclassified code coded word remains equal to test word 42 or Either it is determined to be less than 42. Words that have been encoded even once If a word is classified as greater or less than the test word, its classification remains unchanged. minutes Class operations require the operation of several focus maps for each attribute, so the essential It would be economical to encode coarse attributes in a way that protects order information .

For example, a date attribute with a range of one year is encoded as 9 bits.

By adopting an algorithm from the associative memory literature, the It is possible to find the minimum value of an attribute and the position of the record containing the minimum value, as in This is possible using map operations. The algorithms listed in Figure 7 are PASC It is AL type 2, and the labels M and B [i] represent the rows of the bitmap, and W [i] is the smallest or smallest coded word of the bit matrix 48. Indicates one focus. Which record does M bitmap 50 after the algorithm completes? indicates whether the code contains the smallest coded word of the matrix 48, where n is is the number of bits in the coded record of matrix 48. This algorithm The bits of matrix 48 are moved from left to right (most significant bit to least significant bit) one at a time. M bitmap 5 with the smallest word W52 by parsing the bitmap Calculate 0.

At any particular bit position of matrix 48 bitmap 50 is still discarded. Word W52 contains instructions regarding records that have not been previously determined. It will contain the minimum word focus. The record that has not yet been thrown away has that bit. When we have a coded word with value O in bit position, A record with a coded word that is l cannot be minimal, corresponds to a record that has a coded word that is 1 in that bit position The bit in the bitmap 50 that follows is necessarily O. The smallest word is also the Has an O in the bit position. However, records that have not yet been discarded are all 1 in the bit position under consideration, all records are discarded. the smallest word would be l at that bit position.

Step in the algorithm (M AND B[i]) = M is the operation (M ANDB [i]) All bits in the bitmap generated by XORM are O The result is a test for whether or not (“all zero test”), and the reason is that they If all 0, the M bit map 50 is unchanged and does not need to be calculated. It is.

Since this step takes up a significant portion of the computation time, the active memory circuit shown below By using the all-zero output from and reducing it, the algorithm becomes more It is fast and makes the algorithm practical.

As described previously, it is possible to achieve various propositions on bitmap indexes. It is Noh. The index is preferably the superimport codeword. The table contains a small number of values, propositions with possible non-equality propositions, and information about the propositions. This is the addition of the complete binary code of the attributes that require the order of . of memory space For economy, all fully binary attributes are encoded with a small number of bits.

An associative memory method that allows the above-mentioned operations to be accomplished on a bitmap matrix. A memory system 62 is shown connected to a host computer 60 in FIG. . The host computer 60 includes a central processing unit 64, memory 66, and multiple disk drives. Equipped with a mass storage device 68 such as a storage device, and an input/output port 0 for external equipment This is a commercially available computer system. A host processor bus 72 is also provided. data between units 64, 66, 68 and 70 of host computer 60. data transfer.

The associative memory system 62 includes an index memory unit 74 and an index processor. Connect the processor 76 and index memory unit 74 to the index processor 76. memory that enables data transfer between continuous memory unit 74 and processor 76; It is equipped with a resystem bus 78.

The index memory circuit 74 and index processor 76 are connected to a host processor bus. 72. The index processor 76 communicates with the index memory 74. It sends and receives data to the host computer via the host processor bus 72. Data operations are accomplished in response to instructions received from 60.

The host computer 60 accesses the index memory via the host processor bus 72. Data from unit 74 can be accessed and provided to computer 60. The index memory unit 74 has standard random access of 16-bit words. Looks like memory. Memory unit 74 is accessed by host computer 60. memory content through memory system bus 78 without memory contention even while being accessed. Data is accessed from index memory unit 74 by index processor 76. be accessed. This means that memory system 62 is autonomous with respect to host computer 60. This is because it includes a bus 78 that operates regularly.

Index memory unit 74 stores records stored within host computer 60. used to store bitmap matrices, which are coded representations of It will be done. Index processor 76 is stored within index memory unit 74. It is designed to accomplish bitmap operations on matrices. memory system The 62 prototype has been assembled and is equipped with an attached index machine (AIM). It is known as The remaining description of the memory system 62 is the line length 409 Capable of storing and calculating bit matrices with 6 bits and a column length of 256 bits. It would be of interest to implement an AIM that includes a capable index memory unit 74.

Memory system 62 stores and operates on pin matrices of any practical size. It is understood that it can be used for

The memory system 62 serially stores the bits of the bit matrix for one record. bit-serial to access al and access all records in parallel It is a word parallel associative memory system.

The index memory unit 74 is arranged on a vertical printed circuit board as shown in FIG. 32 index memories arranged in 4 groups to fit on the board 82 It is equipped with 80. The memory 80 is also arranged in two banks, each with two banks. 16 memories that can store 56 x 4096 bit matrices It is equipped with 80. The 4096 bit string or bitmap is shown in Figure 10. 25 of the 16 index memories 80 are placed in corresponding locations in the memory 80 so that It is stored in a six bit portion 82.

Index processor 76 extracts two data from matrix 88 as shown in FIG. 4096 bit strings or bitmaps 84 and 86 are accessed and columns 84 and 8 are accessed. Perform the selected bitmap operation on 6 and write the resulting column or bitmap 90 is employed to return to matrix 88. Currently, AIM does not have this function. can be achieved within one 16 microsecond cycle. This is the host computer If all bits of bitmap 90 are zero for computer 60, for the address of the record associated with the bit that is otherwise 1 in column 90. including providing information on

The index memory 80 is a TMS 4161EV4 video as shown in FIG. It is equipped with a memory chip, which is a 64-bit dynamic RAM array. 92 and 256 bit shift registers 94. Memory array 92 is It is connected to shift register 94 via parallel 256-bit bus 96.

TMS 9141 chip 80 basically accesses any selected row of array 92. This is a standard RAM with a shift register 94 that can be accessed. . The rows of array 92 are 4096 bit strings or 256 bit portions of a bitmap. It is equipped with 82.

Address line 98 accesses a particular 256-bit row within array 92. By making the TR/QE input Karaifuka line 100 Birr, the data is shifted to the row. The data is transferred to and from the register 94. The direction of transfer is the read/write line 102 ruled by. Performs a transfer between shift register 94 and a selected row of array 92 In order to do this, a transfer request is issued by the index processor 76 and a row is selected. be done. At this stage, any access request from the host computer 60 It is necessary to synchronize the transfer request from the processor 76, and this This is accomplished by a three-part arbitraryization circuit (not shown) within memory unit 74.

At other times, index processor 76 receives access from host computer 60. To operate the contents of a shift register 94 without making an access request to a customer.

The shift register 94 has a serial output port 104 at one end as shown in FIG. and a serial input port 106 at the other end, which is a shift register. 94 to clock line 108 and shift register 94 Data is outputted at one end via output port 104 and transferred to shift register 94. Data is input via input port 106 at the other end.

The index memory unit 74 has two banks 110 and 110 as shown in FIG. and 112, each of which has 16 index memories 80 as previously mentioned. Equipped with: When a bitmap operation is performed, one operand is a bank 110 and other operands are selected from bank 112. operand are selected by host computer 60 and stored in each bank 110 and 112. A predetermined row is activated in each of the arrays 92 within each bank 110 and 112. The contents of the accessed and predetermined rows are transferred to shift registers 94 of banks 110 and 112. be transferred. The shift registers 94 of banks 110 and 112 are thereby both Both include bitmaps. The shift register 94 in the first bank 110 All of the real output ports 104 are connected to the first bank output bus 114 in parallel. The memory system bus 78 is connected to the memory system bus 78 via the memory system bus 78 . Similarly, the second bank 11 All of the serial output ports 104 of shift registers 94 in It is connected to memory system bus 78 via second bank output bus 116 .

Bitmap stored in registers 94 in two banks 110 and 112 Operands for operations are synchronized in registers 94 using clock line 108. output to index processor 76 via buses 114 and 116 by be done. Bits of the bitmap in registers 94 in two banks 110 and 112 The bits in each part 82 are output serially, as shown in Figure 10. 16 bits are used for index processing along each bank output bus 114 and 116. They are output simultaneously to processor 76 as 16-bit words. index pro Processor 76 receives 16-bit data input via bank output buses 114 and 116. Performs the selected bitmap operation on the code and memorizes the resulting 16-bit word. along system bus 78 back to 16-bit bank input bus 118. bus 78 contains at least three 16-bit data paths.

Bank input bus 118 connects 94,016 registers in banks 110 and 112. It is connected in parallel to real input port 06. Therefore, 16 bits When the code is output via bank output buses 114 and 116, the resulting 16-bit The keywords are written at opposite ends of shift registers 94 in banks 110 and 112. be remembered. At the end of the selected bitmap operation, the resulting bitmap is Shift register 94 of bank 110 and shift register 9 of second bank 112 4. The index processor 76 then indexes the resulting bitmap. host computer 6 in array 92 of one bank 110 or second bank 112; Transfer to a predetermined line selected by 0.

Index processor 76 connects to host processor bus 7 via bidirectional bus 122. 2, including a host interface port 120 connected to the host interface port 120.

Processor 76 also connects to host interfaces via bidirectional buses 126 and 128, respectively. Serial interface port 120 and memory system bus 78 includes a function unit 124.

Serial function unit 124 connects host interface port 120 input to unit 124 via system bus 78. Performs a bitmap operation on a 16-bit word. It is also the result of 16 bits Compare the word with the test word and see if all bits of the resulting word are 0. Determine the offset location or address of the bit that is 1 in the resulting word. Contains circuitry for recording slocations. Serial function unit nit 124 is 256 cycles when triggered on the host interface port can be configured to perform two 16-bit words each cycle. perform a bitmap operation on a word, the resulting word and outputting the result word on bus 78.

Host interface port 120 includes a control unit and is connected to a host computer. Receive orders from 60. respond to commands received from host computer 60 Therefore, the board 120 performs calculation and index processing of the serial function unit 124. Controls data transfer within and between the Smemory Stores 74.

Data flow between index memory unit 74 and index processor 76 This is shown in Figure 15, but not all data paths are shown. Two 16-bit words are processed by processor 76 to perform the map operation. Accessed from banks 110 and 112, each word is accessed simultaneously by the serial function input to the application unit 124. The two words are connected to gates 130 and 1, respectively. 32 and gates according to the states of mask registers 134 and ]36, respectively. masked inside. Gates 130 and 132 are inputs to pool logic unit 138. It performs the selected logical operation on the word and the 16 bits of the operation outputs the result to shift logic unit [40 and -match logic unit 142]. pool The logic unit 138 is AND, AND NOT, OR, ORNOT, NO Performing many logical operations such as T, XOR, XORNOT ORC0PY Can be done. Copy is achieved by setting one operand to zero and performing an OR operation. will be accomplished. The operations to be executed are based on instructions received from the host computer 60. selected by control unit 144 in host interface port 120. It will be done.

The zero matching logical unit 142 is one of the results output by the pool logical unit 38. The 6-bit word is stored in the test word register 148 as a 16-bit test word. If the resulting word compared with the test word matches the test word, the control unit 144 Offset or address of matching result word in FIFO hit register 150 Memorize location. Test words to achieve all zero test Register 138 is loaded with a word in which all bits are zero. shift The logic unit stores the 16-bit words of the result while they are stored in the zero-match logic unit. The resulting words are compared at 142 and stored in a bank in index memory unit 74. The output signals are output to networks 110 and 112. The control unit 134 has a zero match logic unit 14. 2 and the shift logic unit as well as other elements of the memory system 62 and control the host controller. It receives instructions from computer 62 and stores them in instruction register 152.

The instruction register 152 is connected to the register 134 in the serial function unit 120. ．． 136, 148 and 150, but the register 152 usually forms a part of the control unit) 144.

An active memory circuit or chip 150 as shown in FIG. It is designed to perform bitmap operations on map matrices. circuit 150 is a memory section 152 capable of storing an array of bits, preferably both Shift register 154, logic unit or circuit 156, and bits under operation A zero o'clock storage area or section 158 is provided for temporarily storing the tomato map.

Chip 150 in use includes an array of bits stored within memory portion 152. Contains. An array of bits represents a bitmap matrix, the size of the array is Although not critical, 256 x 256 bits is preferred. chips expressed in bits Data held within 150 is handled differently than in regular memory.

A bit matrix containing part of the index into a table of records is used , directly mapped onto the array of memory section 152. row 1 in array 60 for a single record (256 bits is usually sufficient for complex records) ) is maintained. Any column 162 of the array is 7. Stores a bitmap of a table or matrix of the type described with reference to Figure 7. hold

Shift register 154 on chip 150 is similar to the memory used in the previously mentioned AIM. It is similar to the shift register 94 to Moribanks 110 and 112.

Chip 150 stores selected columns from the bit array stored in memory portion 152. Copying onto shift register 154 as in banks 110 and 112 Can be done. The contents of the shift register are transferred to the selected column and the previous shift register 154. It is also possible to replace it with the result of a logical operation performed on the contents of .

Data is transferred by shift-in and shift-out lines 164 and 166, respectively. Shifts in and out of register 154 are performed. Chip 150 is the row/column selection input line 168 and the data input to the memory section 152 in consecutive rows. There is also an input/output line 170 for data input/output. Chip or circuit 1 50 and the selection of memory elements in memory sections 152 and 158. A plurality of control lines 172 are also provided for selection. shift register 154 An output signal that goes low whenever the bits of the column stored in the column are not all zeros. A zero output line 174 is also provided. All zero line 174 is minimal can be practically performed using the following algorithm. Command line 172 is In particular, shift register 154, logic unit 156, memory section 152 and temporary storage A signal for controlling input/output operations of the bitmap from the storage section 158 is input.

The input on line 172 is the bit map previously described for chip or circuit 150. commands to accomplish the following functions to accomplish the index operation:

(i) AND of the contents of the shift register 154 and the selected bitmap 162 and stores the result in the shift register 154.

(ii) OR the contents of the shift register 154 and the selected bitmap. The result is placed in shift register 154.

(ij) XO between the contents of the shift register 154 and the selected bitmap 162 R is taken and input to the shift register 154.

(iv) Copy the selected bitmap 162 to the shift register 154.

(V) Transfer the contents of the shift register 154 to the selected column 162 of the memory section 152. beep.

(vi) The contents of the shift register 154 are inverted.

(F) Shift up the contents of the shift register 154 by 1 bit.

(vii) Shift down the contents of shift register 154 by 1 bit.

Shift registers at once for many purposes including greater/less than sorting operations Some additional columns or bitmaps that cannot be stored in It is convenient to have a temporary storage section 158 that is The column is The same applies to the columns of the bit array stored in the memory section 152. The circuit 150 is All the bitmap logic operations described earlier are accomplished on the semiconductor chip substrate. It is possible to Upon processing the proposition, the final bitmap corresponds to the proposition. It becomes possible to examine records in order to identify them. This consideration has shifted out. This is accomplished by external circuitry accessing the bitmap through line 166. . Since the index for a table or file is stored on multiple chips 150, , and since only a few records will correspond to the proposition, the final bit matsu Most of the bits in the shift register 154 that stores the Dew. Therefore, all zero line 174 is the code stored within chip 150. Provides an indication of whether the record corresponding to the index should be examined further. Ru. If the all zero output 174 is at a high level, the record related to that chip 150 is As for the codes, they are discarded as not corresponding to the proposition. Therefore, If there is an all-zero output line 174, there is a low level on the all-zero output line 174. To determine the record corresponding to the proposition only for chips with a signal of Extract the final bitmap stored in each shift register 154 It is sufficient to consider all chips 150 for a given file. No need to search.

The index stored on the chip 150 is transferred from an external storage device onto the chip 150. must be read and updated. Chip 150 has an index column. format, but accesses rows in the memory section 152 for external storage and updating. It is useful to be able to access a selected row within a bit array. The serial input/output port 170 shifts bits directly from/to This is achieved by inputting data realistically. The speed of this operation is 1 or 2 Shift-in/shift-out operation at 25 MHz or higher It's slow. Line input/output functionality is also available using standard single-bit access ports. This can be achieved in earnest.

Active memory circuit 150 performs matrix address decoding as shown in more detail in FIG. A memory comprising a number of 1-bit storage elements 182 addressable by a memory card 184. A rear array 180 is provided. An array 186 of 1-bit storage elements 182 is also provided. A temporary storage section 158 is formed. Array 186 is a temporary bint map address. accessed via the response decoder 188. Decoders 184 and 188 select arrays 182 and 186 based on row/column and address inputs 190 To do so. These inputs 190 are part of the previously described control personnel 172 and row/column A selection input 168 is formed. Each of the 1-bit memory elements 182 has a bin output M1 92 and the inversion of the bit output 194 are supplied. Data is part of control human power 172 Inputs received from memory control unit 196 which receive inputs 197 to form 192 and 194 of the selected element 182, respectively. It is brought out. Bidirectional shift register 154 is a master-slave flip-flop. It has 198 arrays. The contents of flip-flop 198 are flip-flop Each shift/invert unit 10 is also capable of inverting the contents of the 0 to shift up or down. Logical unit 1102 The contents and notes of shift register 154 as previously described by flip-flop 198 are arranged to perform selected logical operations with columns of rear array 180. shift /Inversion unit 1100 and logic unit 1102 are command decoder 1104 Each shift inversion unit 1100 or each logic Units 102 function simultaneously and in the same manner. Therefore, logic, shifts and antithesis The conversion operation is performed on the string of bits forming the bitmap. command deco The reader 1104 is connected via a command line 1106 that forms part of the control line 172. output signals to units 1100 and 1102 in response to inputs received by . Shift register 154 is bidirectional, so data can be shifted in and out respectively. Shift-out top line 1108 or shift-in/shift-out bottom line 1110 through the top of register 154 or the bottom of register 154 using Shifted in and out for 4. All zero output 174 has multiple inputs A NOR operation on the contents of flip-flop 198 is performed within NOR gate 1112. It is obtained by doing.

When the auxiliary memory circuit 150 is constructed on a single semiconductor chip, the shift/inversion Each of the units 1100 and each of the flip-flops 198 are shown in FIG. A single shift register cell 1150 is formed as shown in FIG. shift register cell 1150 is master-slave flip-flop 1152 and most of them are command A plurality of MOS FET) transistor 1154.

Look-through control line 1156 is connected through input Sin of flip-flop 1152. to enable data input and output, and the invert control line 1158 is set high. The contents of shift register 1152 are inverted. All zero line 1160 Low level whenever the output 51162 of flip-flop 1152 is high level be made into When the downshift control line 1164 is high, the higher level The contents of the flip-flop of the register cell 1150 are the contents of the flip-flop of the flip-flop 115. 2 is passed to the input Sin 1164. Similarly, the shift up control line Flip-flop of lower shift register cell 1150 when at high level is passed to input 1164 of flip-flop 1152.

As shown in FIG. 10, the cell 1170 of the logic unit 1102 is 72. AND gate 1174 and XOR gate) 1176, these output The contents of the flip-flop register 1152 appearing on line 1166 and line M 117B to accomplish a logical operation with the contents of the selected memory cell 182 appearing on Ru. To achieve the XOR function, the XOR gates 1176 each have a flip-flop. A line that is the inverse of the contents of the drop 1152 and the selected memory cell 182. Requires input from 1180 and 1182. OR system according to selected operation The control line 1184, A N D 1tlJ control line 1186 or XOR118B is high level. When the bell is reached, a logical operation is performed and the result of the selected operation is sent to the flip-flop 11. 52 input 1164 only. High and low voltage lines 1190 and 119 2 is for the OR gate 1172 and the AWD gate 1174 as shown in FIG. It is set in.

When the line M>S 1194 goes high, the selected memory cell 182 is input through line 1178 to input 1164 of flip-flop 1152. It will be done. Similarly, when the SUM line 1196 goes high, the flip-flop The contents of input 1152 are output to the selected memory cell 182 through input 1162. be done.

Memory cells 182 have their contents shifted into and out of shift register 154. decoders 184 and 188 to perform logical operations on them. is selected in the column coming from array 180 or array 186.

The main application of active memory circuits is related to associative memory, which was mentioned earlier. indexes and more specialized reference tables for retrieval of information such as in AIM The purpose is to provide bulls.

A subsystem 1200 with active memory designed as a coprocessor is 9, it is connected to the host system via the host system bus 1202. Ru. An active memory comprising multiple active memory chips or circuits 150 can be and control logic 1206 into memory system 1200. specific Control of active memory to implement functionality is incorporated within the logic subsystem 1204. This is done by a special logic unit 1208 that is created. host system bus 1 Access to 202, data transfer, and overall control are provided by the instruction decode/interpretation unit. ) 1210.

For general indexing, logical unit 208 is described with reference to Figures 1-7. Achieve the desired behavior. Superimposed encoding is the most complex of these operations. It's rough. Figure 20 accepts a chopped constant as input and a codeword (register). in the memory subsystem 1200) and the corresponding record in the memory subsystem 1200. A superimposed codeword forming either or both bitmaps of 12 represents a code calculation unit 1220. This unit) used in 1220 The random numbers generated are calculated using a linear sequential circuit.

Indexing means that the result of an operation is a bit map of the corresponding record in memory system 1200. It's Tsupu. The host application primarily uses the bitmap calls rather than the bitmap itself. We are interested in the location of the corresponding record. Figure 21 shows all zeros. circuit 150, that is, a circuit that outputs a low level signal on the all-zero output line. multiple active notes for extracting corresponding bitmaps from the shift registers of Holds a recircuit or chip 150 and corresponds to one bit in the corresponding bitmap. Store the address in the FIFO storage unit) 1232. It represents. Preferably, by pipelined processes, the host Obtain an address as soon as it is generated.

Unit 1232 automatically calculates the next addresses and transfers them to FIFO unit 1. 232. FIFO before the entire corresponding bitmap is scanned. When the unit 1232 is full, the host requests or orders the unit 1232. The process is paused until the subject is removed or the address is retrieved from the FIFO 1232.

The corresponding bitmap is stored in the bit register 1231 and the control is selected/controlled. This is done by unit 1233.

In highly dynamic applications, as previously described with reference to FIG. Inserting or deleting entire indexes using line input/output lines 170 is frequently required. Also, it is possible to process a large number of entire pieces of data at once within a given validity period. Garbage disposal may also be required. One way to achieve such behavior is to The method is to use a compression/expansion unit 1234 as shown in FIG.

Unit 1234 is an active memory circuit or chip 15 under control of the bitmap. Compress or expand the row at index stored in 0. In compressed mode, the bit The map has a 1 in each row position of the index to be removed. Yu The unit further copies each row to its row buffer 1236. The unit 234 is Keep a count of the number of lines to be removed and store it in the contents of line buffer 1236. Used to determine which lines to copy. Expansion works in the opposite way. bit pine The row with the highest copy activity has a 1 in each position where a row should be inserted. Performed from address to lowest. Zeros are inserted into empty lines. bit pine If one bit is set in the row, one row is inserted or deleted. compression / expansion unit) 1234 is controlled by the selection/control unit 1235 and is a control bit Map storage 1237 contains bits that indicate which rows will be compressed or expanded. memorize the map.

A plurality of active memory circuits or chips 150 provide virtual memory support, data flow control, and Computer node switching and tracking of objects in CAD systems It can be used in many applications for fast table lookups, such as retention. this is A very simple application of the active memory circuit 150, even if the equivalence test Since only one person is required and only one person is expected, the elaboration of Figure 19 no special architecture is required. Figure 23 shows integrated active memory chip 1 50 shows a preferred embodiment of a special table lookup unit 1236 having 50 . The host provides a test word for storage in test word register 1239. The supply unit 1239 inputs instructions regarding the test word address in the table. The unit 1238 includes a control unit H241. Ru.

Active memory chip 150 preferably includes additional memory provided by zero time storage array 186. It has a square array 180 of memory elements 182 with additional columns. array 1 Since the view of 80 from the row is different from the view from the column, the storage requirements for bits are different. It is clear from important applications of circuit 150 that the arrangement of elements 182 need not be symmetrical. That's it. The index for a file of 100,000 records is often 128 Compatible with bits. Table references only require 32 pins per row, but many There are several rows. Therefore it is 32 of the cascadable units 1250. Preferably, active memory circuit 150 is designed as a bit square.

As shown in Figure 24, a high-density chip has many of these cascadable units. It has a cut 1250.

In the table reference application, the table portion is within each unit 1250. Elementary operations are accomplished in all units 1250 simultaneously. one For general indexing applications, a logical row may consist of several units or rows in the row direction. It extends across the chip 1250. The final bitmap contains everything in one column. It is formed into pieces using the operation of selecting all the elements, and finally the process of combining them. There is a The combinatorial process transfers the contents of the selected shift register to that row's It is convenient to be able to copy to the shift register of the leftmost unit 1250 The simplest logical combination of shift registers is to cascade the 0 columns that are This is a very demanding request.

The most easily recognizable application of active memory circuit 150 is the associative memory method previously described. This is an application in the Mori system 62.

An associative memory system employing an active memory circuit 150 as shown in FIG. The system 62 has 16 video memories 80 forming an index memory unit 74. , 16 active memory circuits 150 forming an index processor 76. ing. Index processor 76 performs the following operations for controlling active memory circuit 150. A control unit such as host interface port 120 previously described (not shown) ) is also included. A bitmap or column with a size of 4096 bits is 1 Bitmap storage facility on active memory circuit 150 via 6-bit bus 1500 will be forwarded to. Bits for bitmap stored in active memory circuit 150 The map operation is executed and the result of the operation is imported via the 16-bit data bus 1502. The data is returned to the index memory unit 74. The architecture shown in Figure 25 is Achieves complex bitmap operations much faster than the memory system 62 in Figure 8. do. The architecture in Figure 25 uses a large amount of bitmap memory with the same amount of memory. It is also possible to store the risk at the serial input port of register 94. memory unit without the need to recover previous data output by data input Data can be shifted out from register 94 within 74. data transfer The bus required for data transfer only needs to be 16 bits in size, so the memory system shown in Figure 8 16-bit word instead of three 16-bit word transfers as in Only the transfer of the data needs to be monitored. Architecture 25 index process The processor 76 executes bitmap operations in cycles of 1 microsecond or less. is possible.

Engraving (no changes to the content) Algorithm: L:=0・62:O・ for i:=1 to n d.

caseW[1lof O, :G:=G or not L and 8 [i]; 1: L:=L o r　notG　and　not　8[;]end・ −−−−Rabbit−−−−−−−−−− r-1----------- Engraving (no changes to the content) Engraving (no changes to the content) How to write procedural amendments> Yoshi, Commissioner of the Patent Office 1) Takeshi Moon 1.Display of the incident PCT/AU87100284 2. Name of the invention associative memory system 3. Person who makes corrections Relationship to the incident: Patent applicant Address: 8-10-5 Toranomon-chome, Minato-ku, Tokyo 105, Date of amendment order November 7, 1999 (shipment date) 6. Subject of correction (1) Inventor's address, patent “Applicant representative” column (2) Power of attorney (3) Translation of the specification (4) Translation of the scope of claims (5) Translation of drawings 7. Contents of correction +1) +2) As per attached sheet (3) Engraving of the translation of the specification (No change in content) (4) Engraving of the translation of the scope of claims (No change in content) (5) Engraving of drawing translation (no change in content) 8. List of attached documents (1) Amended Article 184-5 of the Patent Act One document pursuant to the provisions of paragraph 1 (2) Power of attorney and its translation (two copies each) (3) Translation of the written specification: 1 copy (4) Translation of the written claims: 1 (5) Translation of the painted drawing: 1 copy international search report -1-,-,l-+,,,,-,,,,----,,PCT/AU 87100 284 is a flash πL fu Σ廚π? City = l court 9th K] de Pgo σlzαM APPLIC ATICN　hl:1. I’CT AIJ 8700284tE 42009 35 DE 2849944 FR2408868GB 2009469A,% lEX To “WE Fu-kun=R Fusu-CM) J, 5EAROI REPCRT 　GJ chutai χα kan c record, Ni γJ Hi TTGI history, Ni Tehe〇　O7(a) 284 ( CCNI) Hair p) O54412313cA 116B376 EP 69764 WO8202615DE 3232675a (658329JP 5E10 39341 t’s 4476528EX) OF ANNEK

Claims (17)

[Claims] 1. Host memory (66, 68) and host processor for storing multiple records Content addressable memory for coupling to a host computer (60) having a bus (72). A memory system (62), the memory system (62) having: A bitmap map representing records stored in the host computer (60). in use, the host processor bus (7 2) an index connected to and addressable by the host computer (60); memory means (74); accessing the bitmap stored in the memory means (74); In use, the host processor bus (7 2) an index process connected to the host computer (60) and controlled by the host computer (60); sensor means (76); between the index memory means (74) and the index processor means (76); a bit connected to the memory means (74) and the processor means (76); an association comprising a memory system bus (78) employed for the passage of the map; Storage memory system (62). 2. The index memory means (74) includes a plurality of index memories (80). Each of the plurality of index memories (80) includes: an array of memory cells (92); a shift register (94) with a parallel input connected to the array (92); /output bus (96) and serial at opposite ends of said shift register (94). It has a serial input port (106) and a serial output port (104). The array input/output bus (96) provides access to selected rows of data within the array (92). a shift register (94) that can be accessed; The serial input and output port (1) of the index memory (80) 06 and 104) are connected in parallel to said index processor means (76). ; the selected rows of the data accessed at the same time have at least one bitmap; An associative memory system (62) according to claim 1, wherein the associative memory system (62) forms a group. 3. the array (92) is accessed by the host computer (60); while the index processor means (76) is connected to the shift register (94). 3. An associative memory system (62) according to claim 2, wherein the associative memory system (62) has access to a content addressable memory system (62). 4. The index memory (80) has a first or second bank (110 or 112). ), and in achieving a predetermined bitmap operation, the said index A first bitmap processor means (76) extracts a first bitmap from said first bank (110). a second bitmap access from the second bank (112); The second bitmap forms an operand of the operation. The associative memory system (62) as described in Section 6. 5. Before performing the operation, the bitmap forming the operand is It is stored in the shift register (94) of each bank (110, 112) and is used during the operation. In the index processor means (76) each shift register (94) The bits from the real output port (104) are accessed simultaneously and the accessed bits are The bits added form two words from each bank (110, 112) and The shift register of at least one bank (110, 112) A request for outputting the result word of the operation to the serial input port (106) of the computer (94). The associative memory system (62) according to claim 4. 6. The operation takes 16 microseconds if the bitmap has 4096 bits. An associative memory system (62) according to claim 5, which is accomplished by: 7. said index processor means (76): in use said host processor; a host interface port (120) connected to the server (72); interface port (120) and the memory system bus (20). a serial functional unit (124); The interface port (120) is responsive to the host computer (60). to access the first and second bitmaps and apply them to the serial functional unit. accomplishing a predetermined pitmap operation on the first and second bitmaps; An associative memory system according to any one of claims 4 to 6. 8. The serial functional unit (124) connects the memory system bus (78). an input line coupled to the serial output port (104) via the memory system; an output line coupled to said serial input port (106) via a system bus (78); Monitoring of a logical unit (138) with an input and the output of the logical unit (138) as set forth in claim 7, comprising a delay unit (140) that enables associative memory system (62). 9. At least a portion of the bitmap is placed in row (160) and column (162). an array (180) of memory cells (182) suitable for storing; Shift register (154) suitable for storing at least part of the bitmap and; a logic unit connected between the array (180) and the shift register (154); the array (180), the shift register (154) and The logic unit (156) is composed of an integrated circuit, and the shift register (154) is it is possible to copy selected columns (162) of the array (180); The logic unit (156) combines the contents of the shift register (154) and the array (1 80) with the selected column (162) and the result of the operation is an active memory stored in the shift register (154). Circuit (150). 10. The shift register (154) has a column of shift register cells (1150). said logic circuit (156) comprising a column of logic cells (1170), said logic circuit (156) comprising a column of logic cells (1170); The cells (1170) have respective shift registers (1150) and memory cells (182). ) are combined with each line (160) of the active memo according to claim 9. Recircuit. 11. The logic cell (1170) has a corresponding control line (1184, 1186 or is in the shift register cell (1150) when the shift register cell (1188) is enabled. and the selected column (162) of said memory cell (182). The result of the selected logical operation is written to the shift register (1150). The active memory circuit according to range 10. 12. The logical operations are NOT, AHD, OR, XOR, ANDNOT, ORNO. 12. The active memory circuit of claim 11, comprising: T, and XORNOT. 13. Each shift register cell (1150) is a shift register cell (1150). ) in the column of flip-flop (1152) and flip-flop (1152) and a circuit to invert the content and shift the content to another flip-flop (1152). An active memory circuit according to any one of claims 10 to 12. 14. The logic cell (1170) is connected to first and second storage control lines (1196 and and 1194) respectively are enabled. 0) in the selected column (162) of the memory cell (182) and stores the memory cell ( 182) in the selected column (162) in the shift register (1150). Any one of claims 10 to 13 including a circuit that enables An active memory circuit described in . 15. The contents of the pits stored in the shift register (154) are all low level. It further includes a NOR gate (1112) whose output becomes H level when the signal is high. An active memory circuit according to any one of claims 9 to 14. 16. The control lines (1184, 1186, 1888, 1194 and 1196 ) further comprising a command decoder (1104) having an output connected to the The decoder (1104) receives input via the command line (1106). Active memory circuit according to the corresponding claims 11-14. 17. The index processor means (76) is defined in claims 9 to 16. Claim comprising one or more active memories (150) according to any of paragraphs The associative memory system (62) according to any one of items 1 to 3 of the range .