Abstract:
An associative bubble memory apparatus utilizing a plurality of registers therein to provide a high total memory capacity and to provide data retrieval or correlation based upon content rather than the address of the data of interest.

Description:
STATEMENT OF GOVERNMENT INTEREST 
     The invention described herein may be manufactured and used by or for the Government for governmental purposes without the payment of any royalty thereon. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention relates broadly to magnetic bubble domains, and in particular to an associative bubble memory apparatus. 
     In the present state of the art computer memories, information is stored in one of two magnetic states on a magnetic material. The unique characteristics of magnetic materials enable them (1) to hold one of two magnetic states (direction of magnetization) in the absence of power (nonvolatility), (2) to be quickly alterable between states with a small amount of input power, (3) to be readable at high speeds by means resulting in a system-compatible electric current flow, and (4) to store large amounts of information by providing extremely high geometric densities of magnetization. These characteristics have caused magnetic memory devices to supersede most prior attempts at memory design, and such devices will continue to be useful for a long time into the future. Electrostatic storage in cathode ray tubes and mercury delay lines has been made obsolete by magnetic cores and drums. 
     Magnetic core memories may be classified as discrete stationary medium memories. Each core is capable of storing only one bit. A &#34;zero&#34; is represented by magnetizing the doughnut-shaped core so that the flux direction is, say, clockwise, while a &#34;one&#34; is represented by the opposite direction of magnetization. The core is set by a current flowing in a wire through the center of the core. A rectangular grid of wires, with a core surrounding each wire crossing, is called a plane. Selective setting of cores is accomplished by passing half currents (half the amount required for switching) through the grid wires. Only those cores will be set where the half currents coincide and thus exceed the switching threshold of the cores. A stack of planes is a memory array. For a word length of 16 bits, an array of 16 planes, each holding 1024 cores, would be called a 1024 word, coincident current, word addressable memory. 
     The speed of core memories is limited by the switching time of the cores, the length of the wires in the arrays, and the pulse length and frequency of the drive and recovery time of the read or sense amplifiers. 
     SUMMARY 
     The present invention utilizes magnetic bubble domains to provide an associative memory apparatus wherein access to the memory data is achieved through the content rather than the address of the data being retrieved. This enables the rapid searching of the memory for a given bit-pattern to determine its presence, and to report its location or locations where it is stored if it is present. The associative memory apparatus includes an arithmetic logic unit to perform such functions as the AND function on all words in the memory with respect to a given key word which is applied as an input to the memory apparatus. The arithmetic logic unit may also be utilized to perform the OR functions and the binary ADD. The associative memory apparatus also has the capability to read and write data into random location in the memory in the same manner as a conventional memory. 
     It is one object of the present invention, therefore, to provide a new and improved associative bubble memory apparatus. 
     It is another object of the invention to provide an improved associative bubble memory apparatus that allows access to memory data by content rather than by the address of the data in the memory. 
     It is still another object of the invention to provide an improved assocative bubble memory apparatus having the capability of performing logical operations on an array of memory words. 
     It is yet another object of the invention to provide an improved associative bubble memory apparatus which may be utilized to read and write data words into random locations. 
     These and other advantages, objects and features of the invention will become more apparent from the following description taken in conjunction with the illustrative embodiment in the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of the associative bubble memory apparatus in accordance with the present invention, 
     FIG. 2 is a block diagram of the current-controlled switch decoders for the associative bubble memory apparatus, 
     FIG. 3 is a schematic diagram of the associative bubble memory apparatus chip with 128 512-bit registers, 
     FIG. 4 is a block diagram of the arithmetic logic unit for the associative bubble memory apparatus, and 
     FIG. 5 is a block diagram of the correlator unit for the associative bubble memory apparatus. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention is an associative memory chip apparatus which permits access to memory via the content rather than the address of the data being retrieved. This is equivalent to searching a memory for a given bit pattern to determine if it is present; and if it is present, to report the locations where it is stored. The present invention includes the capability of the simultaneous performance of logical operations on an array of memory words. For example, the present apparatus can perform the AND function on all words in the memory with respect to the chip. In addition to the AND function, the apparatus can perform the function OR and the binary ADD. 
     The present associative bubble memory apparatus which utilizes associative processing to perform logic operations, may also operate similar to a conventional self-contained chip for reading and writing, with 256 registers containing 512 bits each for a total memory capacity of 128 K bits. The bubble size in the present apparatus is 0.5 μm. 
     Referring now to FIG. 1, there is shown an associative memory register apparatus containing logic circuits and a pair of address decoders for each register. The associative bubble memory apparatus is comprised of a plurality of chips containing 256 register units (one complete unit of which is shown in FIG. 1), each of which having read-write addressing requiring eight current and eight control lines for operation. The current lines are designated L 1  through L 8 . The control lines are designated L G , L A , L R , L O , L P , L R , L S , and L T . The other symbols which are used are shown in Table I. 
     TABLE I 
     G = generator 
     A = annihilator 
     = Disjoint Crossover 
     = Exclusive Merge 
     = Transient Bubble Switch 
     The symbol for the current-controlled annihilator is defined in FIG. 1. The sixteen current lines are common to all 256 registers on the chip. 
     The only input is a single generator 10 in each register, controlled by line L G . Since this line is common to all registers, the generated bubbles are destroyed by the bubble eater 12 at H in all registers except the one selected by the address lines. Bubble output is accomplished with detectors 14, 16 that are connected to each register in daisy-chain fashion by paths L and M. For faster access, there are two detectors per chip as shown in the schematic chip layout in FIG. 3. Each detector serves 128 registers. Bond pad placement to allow easy multiple-chip serial interconnection is also shown in FIG. 3. 
     The control of the associative memory chip which is described in terms of bubble streams is shown in Table 11 below. 
     
                                           TABLE II__________________________________________________________________________                                       Return  Selected             Paths Not                             ALU       to  Register or  Selected Paths                       Selected                             Outputs   StorageOperation  All Registers         G     B  A A  H  F  C    E    K__________________________________________________________________________         Data toWRITE  Selected         Be Written               G  D D  O  O  O    C    G  All but         Data toWRITE  Selected         Be Written               D  O O  G  D  O    O    DREAD   Selected         O     O  D D  O  O  D    D    DREAD All but Selected         O     O  O O  O  D  O    O    DCOMPARE  ALL    Input Key               G  D D  O  O  G Plus D                                  D    DADD    All    Data to               G  D D  O  O  O    G Plus D                                       G Plus D         Be AddedAND    ALL    Data to         Be ANDed               G  D D  O  O  O    G · D                                       G · D         Data toOR     All    Be ORed               G  D D  O  O  O    G + D                                       G + DCirculate  All    O     O  O O  O  D  O    O    D__________________________________________________________________________ 
    
     The path symbols are as given in FIG. 1. The functions to be performed are listed on the left-hand side of the table, and the required paths which are followed by the generate stream G and the data stream D are shown on the right-hand side. It may be noted that the chip is capable of performing destructive logical operations on arbitrary fields of its register contents in addition to the READ, WRITE, and COMPARE functions. This extra logical capability is available because the logic products were easily available in the arithmetic logic unit, 18. 
     Turning now to FIG. 2, there is shown the current-controlled switch decoders for associative memory apparatus. The switch arrangment for register number 45 10  = 00101101 2  is shown. Eight lines with bipolar drivers are required for selecting a given register. Eight current-controlled address lines are needed for register selection on the chip. Each line passes through two current-controlled bubble switches. The two decode circuits are required for each register as shown in FIG. 1. Two types of bipolar current switches are employed, designated by the labels &#34;0&#34; and &#34;1&#34;. Type 0 switches do not switch bubbles from their path when current is flowing in the normal direction as indicated by arrows. Type 1 switches divert bubbles with normal current flow. The switch actions are reversed when the current is flowing in the reverse direction. Each register in the memory has a unique set of switch types so that register selection can be accomplished. The combination 00101101 2  is shown as an example in FIG. 2 to indicate the required switch set for register number 45 10 . The subscript is used to indicate the number base: 2 for binary, 10 for decimal. 
     There is shown in FIG. 4 a schematic diagram of the arithmetic logic unit for the associative processor portion of the associative bubble memory apparatus. The arithmetic logic unit is controlled by the four conductors shown with normal current flow indicated. 
     The operational states are listed in Table III along with the necessary directional current controls for implementing those states. With all currents in the normal direction, the arithmetic logic unit operates as a full adder. 
     The correlator circuit is shown in FIG. 5. Operation of the correlation is explained by a simple example. Three five-bit fields containing the numbers +7 10 , -7 10 , and +5 10  are compared with the search key of +5 10 . The two&#39;s complement of the search key (11011 2 ) is written into all registers simultaneously via control lead L G . The input word is then added to each field and the sum transmitted to the correlator circuit via path C. The correlator circuit is then controlled by two wires to perform the following sequence: first, the sign bit is stripped off and sent to M for output. Second, the carry bit is annihilated because it is not necessary to the process. Third, the presence or absence of bubbles in the sum is tested and the result is sent through output 1. 
     
                       TABLE III______________________________________  Conductors      OutputsOperation    L.sub.R           L.sub.R  L.sub.O                         L.sub.P                              C      E______________________________________                                     O Plus BWRITE    N      N        N    N    O      = BREAD     R      R        N    N    A Plus O                                     A Plus O                              = A    = ACOMPARE  R      R        N    N    A Plus B                                     AADD      N      N        N    N    O      A Plus BAND      N      N        R    N    O      ABOR       N      N        N    R    O      A + BCirculate    X      X        X    X    O      O______________________________________ N = normal current flow, R = reversed current flow, X = either current flow. Note that L.sub.R and L.sub.R &#39; may be driven in parallel by the same electronic drive circuit. 
    
     The truth table for decoding the correlator outputs is given below. 
     
         ______________________________________M          L            Result______________________________________0          0            Key &lt; Field0          L            Key = Field1          0            Key &gt; Field1          1            Undefined______________________________________ 
    
     The correlator outputs from each register are placed on the same path for transmission and serial detection as seen in FIG. 1. 
     A summary of the functional elements in the associative memory is given in Table IV. The density of these elements using 0.5 μm bubbles should allow realization on a 100 × 100 mil 2  active chip area. A 128 K bit organization with 128 registers of 1024 bits each may be required, depending on the width-to-length ratio of the logic blocks. 
     In summary, a 128 K bit associative memory chip is disclosed using 0.5 μm bubble technology and functional logic elements. The applications of such a device are centered in the data processing areas of (1) file manipulation, (2) hardware-aided compiler programs, and (3) real-time surveillance and control. The third application includes the specific areas of air-traffic control (e.g., the STARAN computer) and surveillance satellite processing. 
     
                                           TABLE IV__________________________________________________________________________                  Number in                          Total NumberElement   Description  Each Register                          on Chip__________________________________________________________________________Switch    Current Controlled                  24      6144     Permalloy (transient logic)                  8       2048     Current Controlled                  2       512Generator Permalloy    2       512     Current Controlled                  2       512Annihilator     Permalloy    12      3072Merge     Permalloy    25      6400Crossover Permalloy    25      512Memory Locations     Permalloy    512     128   KControl Lines     Conductor    8       8Address Lines     Conductor    8       8Detector  Permalloy    0       2Bond Pads              0       36__________________________________________________________________________ 
    
     The surveillance satellite application satisfies the need for on-board signal processing for deriving true targets from the raw data generated by a focal plane sensor array. The processor would perform scan-to-scan correlation for tracking and X-coincidence correlation for noise rejection, thus reducing the net volume of data to be sent via the limited bandwidth telemetry. The attractive system characteristics offered by the magnetic bubble associative processor include radiation-hardness, low power, low volume, and low weight. 
     Although the invention has been described with reference to a particular embodiment, it will be understood to those skilled in the art that the invention is capable of a variety of alternative embodiments within the spirit and scope of the appended claims.