room for a new one; the obvious thing is to suppress the item that has been there for the longest period of time, but other algorithms slightly cheaper to implement have also been proposed. It is claimed on the basis of simulations that eight associative registers enable the full procedure of three memory cycles to be shortcircuited on 90% of occasions." (Wilkes, 1967, p. 4).

"In the past, associative or content addressable memories of any significant size have been impractical for widespread use. Relatively small associative memories have been built with various technologies, such as multiaperture ferrite cores, cryotrons, and various thin-film techniques. The logical flexibility of microelectronics now makes at least scratchpadsize associative memories practical." (Hudson, 1968, p. 42).

6.116 "By a slave memory I mean one which automatically accumulates to itself words that come from a slower main memory and keeps them available for subsequent use without it being necessary for the penalty of main memory access to be incurred again. Since the slave memory can only be a fraction of the size of the main memory, words cannot be preserved in it indefinitely, and there must be wired into the system an algorithm by which they are progressively overwritten. In favorable circumstances, however, a good proportion of the words will survive long enough to be used on subsequent occasions and a distinct gain of speed results. The actual gain depends on the statistics of the particular situation.

"Slave memories have recently come into prominence as a way of reducing instruction access time in an otherwise conventional computer. A small, very-high-speed memory of, say, 32 words, accumulates instructions as they are taken out of the main memory. Since instructions often occur in small loops a quite appreciable speeding up can be obtained. . .

"A number of base registers could be provided and the fast core memory divided into sections, each serving as a slave to a separate program block in the main memory. Such a provision would, in principle, enable short programs belonging to a number of users to remain in the fast memory while some other user was active, being displaced only when the space they occupied was required for some other purpose." (Wilkes, 1965, pp. 270-271).

6.117 "The B8500 scratchpads are implemented by magnetic thin film techniques developed and organized into linear-select memory arrays . . . To realize the high speed access requirement of 45 nanoseconds, the reading function is nondestructive, eliminating the need for a restoring write cycle when data are to be retained unchanged.

"Insertion of new data into the local memories (writing) can be accomplished within the 100nanosecond clock period of the computer module." (Gluck, 1965, p. 663).

"4 52-bit words can be requested from a memory module and received at a computer module in a

total of 1.0 microsecond, or an average of 250 nanoseconds per word." (Gluck, 1965, p. 662).

"The rationale behind the inclusion of local scratchpad memories in the B8500 computer module encompasses . . . the need for buffering of four-fetches of instructions and data in advance of their use, i.e., lookahead. Also important are its uses as storage for intermediate results, as an economical implementation for registers and counters, and for the extension of the push-down stack." (Gluck, 1965, p. 663).

6.118 "A specific application for a CAM is encountered when assembling or compiling programs where it is common to refer to variables, locations and other items in terms of a symbol. The value or information associated with each symbol must be stored somewhere in memory and a table must be made to relate each symbol to its value. As an example, the symbol ABLKR may be assigned the value 5076. The computer may take this information and store the value 5076 at location 1000 for example. Then the first entry in the symbol table will relate the symbol ABLKR to the location 1000 where the value of ABLKR is stored. As more symbols are defined, this symbol table will grow in length." (Rux, 1967, p. 10).

6.119 "Tied in with scratchpad No. 2 is a small 28-word associative memory (19 bits per word) whose use enhances the utilization of the scratchpad memory by providing content addressing as well as the conventional binary coded word addressing capability." (Gluck, 1965, p. 663).

6.120 "Each cell of the memory receives signals from a set of pattern lines and command lines in parallel, and the commands are executed simultaneously in each cell. One of the commands orders each cell to match its contents against the pattern lines. Each cell in which a match occurs sets its match flip-flop and also generates an signal . . .” (Gaines and Lee, 1965, p. 72).

output

These investigators describe some of the differences between their proposed system and others, in part as follows: "The memory we describe here is a logical and practical outgrowth of the content addressable distributed logic memory of Lee and Paull. However, there are several significant differences: the inclusion of a 'match' flip-flop and a 'control' flip-flop in each cell of the memory, the addition of a 'mark' line to activate many cells simultaneously, and the control of the propagation of the marking signal. As a consequence of these, the memory has some novel capabilities, among which are the ability to simultaneously shift the contents of a large group of cells, thus opening or closing a gap in the memory, and the ability to simultaneously mark strings of interest in separate parts of the memory.

"By properly manipulating the cell states, simple programs for correcting errors involving missing or extraneous letters, multiple mispellings, etc.,

can be devised. Furthermore, by using the marking capabilities of the memory, error correction during retrieval can be accomplished on a selected subset of strings which may be located at widely separated parts of the cell memory." (Gaines and Lee, 1965, p. 75).

6.121 This Sylvania development involves the use of automatically preprocessed plastic sheets to affect the performance and logic behavior of a solenoid-transformer array.

"The interrogation, which may consist of a number of descriptors, each containing many bits. of information, causes an appropriate group of solenoids to be driven . . . The solenoids interact simultaneously with all enclosed loops on all the data planes, resulting in a simultaneous voltage on the output of each data plane that is the crosscorrelation between the driven input solenoids and each individual data plane. The output of each plane is connected to its own detector-driver which tests the output in comparison with all the other data plane outputs to find that output containing the best correlation. Alternatively, the detectordriver can be set to test for some pre-determined threshold." (Pick and Brick, 1963, p. 245).

Brick and Pick (1964) describe "the application of the solenoid array principle to the problem of word recognition, code recognition, and (in a limited sense), associative memory. The proposed device, based entirely on existing experience with a large character recognition cross correlator, is capable of recognizing one of 24,000 individual English words up to 16 letters long. The simultaneous correlation and selection is made in less than 3 μsec. The selection can be made either on a perfect-match or a best-match basis." (Brick and Pick, 1964, p. 57).

"This form of semipermanent memory offers many advantages to computer and memory users. Among these are: a) ease of contents preparation, involving automated punching of inexpensive standardized cards; b) reliability, as a result of few electrical connections, loose mechanical tolerances, and passive components; c) low cost, since the cards are not magnetic and need only a continuous conducting path; and d) high speed, with estimated cycle time below 1 μsec." (Pick et al., 1964, p. 35).

6.122 "A number of associative memory stacks of 120 resistor cards have been constructed, each stack storing 7200 bits, with each card storing one word of 60 bits length." (Lewin et al., 1965, p. 432).

"This paper describes a fixed memory consisting of one or more stacks of paper or plastic cards, each of which contains an interconnected array of printed or silk-screened film resistors. Each card is compatible with conventional key punches, and information is inserted by the punching of a pattern of holes, each of which breaks an appropriate electrical connection. All punched cards

in a stack are cheaply and reliably interconnected using a new batch interconnection technique which resembles an injection molding process, using molten low-temperature solder. The circuit which results is a resistor matrix where the information stored is in the form of a connection pattern. The matrix may be operated as a content-addressable or associative memory, so that the entire array can be searched in parallel, and any word or words stored answering a given description can be retrieved in microseconds." (Lewin et al., 1965, p. 428).

6.123 "The study by Dugan was restricted to considering an existing computer environment and the Goodyear Associative Processor (GAP), a 2048-word associative memory with related logic and instructions. A benchmark problem was studied in which the data base exceeded the size of GAP and was stored on disc. The disc-stored data required transfers to the associative processor or the conventional core for further operations. The study concluded that the effectiveness of a small associative processor, such as GAP, for formatted file problems depended upon the interface of the associative processor with the computer system, the logic of the associative processor, and the load/unload characteristics of the memory associated with the problem. The authors showed that embedding the associative processor within the core memory provided the best system. It also provided a facility for performing arithmetic operations on data, which is ordinarily difficult for an associative processor. The study did not show any major advantages in using a system with associative processor similar to GAP over one without an associative processor.

an

"Gall utilized the same computer environment as Dugan but investigated a dictionary lookup phase of an automatic abstracting problem. He concludes that incorporating associative memories that do not have the capacity to store the entire data base requires excessive data transfer and cannot compete with conventional systems that employ a pseudorandom mapping of a word onto a storage location and, therefore, can locate a word by content. Randomized addressing is another software simulation of but one of the facilities provided by an associative processor, namely, the so-called 'exact-match' 'function." (Minker and Sable, 1967, pp. 130-131).

6.124 The Librascope Associative Parallel Processor was developed for use in the extraction of pattern properties and for automatic classification patterns. It is noted in particular that "the parallel search function of associative memories requires that comparison logic be provided at each memory word cell. The APP, by moderate additions to this logic, allows the contents of many cells, selected on the basis of their initial content, to be modified simultaneously through a 'multiwrite' operation." (Fuller and Bird, 1965, p. 108).

...

Swanson comments as follows: "Fuller, Bird, and Worthy recently described two machines: an associative parallel processor programmed to abstract properties from visual and other patterns and classify the patterns from the properties; and an associative file processor for rapid parallel search of large complex data bases." (1967, p. 38). 6.125 "The ASP machine organization. [has as its dominant element] the context-addressed memory . . . [which] stores both ASP data and programs, and . . . provides the capability to identify, in parallel, unknown items (and link labels) by specifying the context of relations in which the unknowns appear . . . . [It] consists of a square array of identical storage cells which are interconnected both globally and locally. Each cell contains both memory and logic circuitry. The memory circuitry stores either an item, link label, or a relation, plus tag bits. The main purpose of the logic circuitry is to perform the comparison operations which are required to implement global searches of the array and local inter-cell communication." (Savitt et al., 1967, p. 95). See also note 5.47.

6.126 "In the earliest associative memories all bits of all the words of the memory were simultaneously compared with a search word; this is called word-parallel search. For such word-parallel search, the memory has to be of the nondestructivereadout (NDRO) type." (Chu, 1965, p. 600).

"Instead of word-parallel search, bit-parallel search has been developed because of its simpler design and because word-parallel search is of less importance in more complex searches. Bit-parallel search (or bit-sequential search) searches one corresponding bit of all words at one time. For a word of 64 bits, a maximum of 64 bit-parallel searches is made in succession; thus, bit-parallel search pays a price in speed . . . [but] the price is a limited one. In a bit-parallel-search associative memory, nondestructive readout property of memory elements is not necessarily required. This paper describes the organization of a destructivereadout associative memory which can be implemented by a special, very high-speed, magneticcore memory using conventional technology." (Chu, 1965, p. 600).

"Because parallel-search logic is implemented for only one long-word, implementation of several varieties of search logic is practical. In addition to a bit-comparison logic, other logical operations (such as NAND, NOR, AND, OR) can be implemented relatively simply and less expensively.' (Chu, 1965, p. 600).

"For these operations [bit count and bit count and store], each bit of the memory short-word may represent an attribute (a property or a characteristic), and the count of attributes is a useful argument for searching closeness in attributes." (Chu, 1965, p. 605).

6.127 "Circulating memories offer an enormous

savings in quantities of logic necessary for a CAM since one set of comparison logic can be used to compare the key register with many memory locations. The comparison logic need only monitor the memory's contents as it passes through the circulating system. . . .

"The principle disadvantage of a circulating CAM is speed. At least one circulation time of the memory is required to interrogate the entire memory. In the case of a magnetic drum system, this time would be measured in milliseconds which is much too slow for many applications. However, with the use of glass delay lines, information can be stored at very high rates, 20 MHZ and higher, and short circulation times can store large amounts of data. For example, a 100 microsecond delay line at 20 MHZ can store 2,000 bits of information. Thus 32 delay lines could store 2,000 words of 32 bits each and this memory could be searched in 100 μsec." (Rux, 1967, p. 2).

6.128 "A goal in designing and interfacing the associative mapping device into the System/360, Model 40, was to introduce no time degradation in the critical main memory address path. We have accomplished this goal by designing the hardware to perform this address translation function in 220 ns. This interrogate time through the associative memory is approximately 50 ns and the remaining time is spent in wire delay and conventional logic, such as the encode circuit which was designed using the 30-ns IBM SLT family. . .

"The technology used to implement the associative mapping device is the IBM SLT technology. Four special circuits were designed for the associative memory array. They are the associative memory cell used for storing one bit of information, the bit driver, the word driver, and the common sense amplifier used for sensing a mismatch signal in the word direction or a binary ‘one' signal in the bit direction." (Lindquist, et al., 1966, p. 1777).

"The mapping device which provides the dynamic storage allocation function in the time-shared system is a 64-word, 16 bit per word, associative memory." (Lindquist et al., 1966, p. 1776).

... The Univac 128-word by 36 bit-per-word, 600-nsec scratch pad memory." (Pugh et al., 1967, p. 169).

"The memory . . utilizes a plated-wire (Rod) memory device operating in a 512-word 36 bit per word memory system. The DRO mode is employed and operation at a 100-nanosecond read-write cycle time is achieved." (Kaufman et al., 1966, p. 293).

"The memory is word-organized with a capacity of 64 words each 24 bits long. Cycle time is approximately 250 nanoseconds. Such memories are suitable for use as 'scratchpads' operating within the central processor or input-output control systems of a computer." (Bialer et al., 1965, p. 109).

"All of the memory circuits - approximately 180 chips-plus 1,536 bits of thin-film magnetic storage and the thin-film interconnection wiring are on a

glass substrate measuring 3 by 4-1/2 by 1/10 inches. The circuits occupy about half the substrate area. The extremely small physical size of the memory, the shorter signal paths, the elimination of redundant connections, which packaged circuits would have required, all contribute to an improvement in system speed.

"The 64-word memory has a cycle time of about 250 nanoseconds . . . Plans are to build a 256-word memory that is equally fast and expectations are that eventually 50-nanosecond memories can be built with similar design and fabrication methods [i.e., ultrasonic face-down bonding for interconnection of integrated circuit chips with thin-films].” (Bialer et al., 1965, pp. 102-103).

6.129 "The sonic film memory represents a novel approach to the storage of digital information. Thin magnetic films and scanning strain waves are combined to realize a memory in which information is stored serially. The remanent property of magnetic films is used for nonvolatile storage. The effect of strain waves on magnetic films is used to obtain serial accessing. This effect is also used to derive a nondestructive read signal for interrogation." (Weinstein et al., 1966, p. 333).

6.130 "The new [tunnel diode] memory system contains 64 words of 48 bits each, and test results from a partially-populated cross-sectional model indicate a complete READ/RESTORE or a CLEAR/ WRITE cycle time of less than 25 nanoseconds." (Crawford et al., 1965, p. 627).

6.131 "The basic cell employs a thick magnetic film as the high-speed sensing element to sense the information which is stored as a pattern of magnets on a card. Since the magnet card is separate from the array, the latter can be permanently laminated or sealed and the information can be changed very simply and reliably. The advantages of this system stem from a combination of several important features, namely card changeability, high speed, wide mechanical and electrical tolerances, and a linear drive-sense relationship which results in a wide range of operating levels.

"Circuit costs can be minimized by using low-level drivers, giving an additional increase in speed with only a minor increase in sense circuitry . . . For a memory containing four arrays of 256 words and 288 bits per word, an access and cycle time of 19 and 45 ns respectively was achieved. . ." (Matick et al., 1966, p. 341.)

6.132 These investigators suggest further that "the number of bits of storage can be increased in several ways. A modular approach can be used by connecting 64 × 8 memories in parallel or the memory boards can be redesigned to accept the larger number of bits. The modular approach is particularly applicable to the distribution of small memories of various sizes throughout a large computer. It is possible to construct a 64 × 32 memory using either of the above approaches with a cycle time of approximately 20 nanoseconds." (Catt et al., 1966, p. 330).

6.133 "It has been demonstrated that 1000-bit NiFe film DRO memories with cycle times of 60 nsec and access times of about 30 nsec can be built using existing components. Experience with this model indicates that the design can be extended to allow a significant increase of capacity in a memory having this same cycle time and access time; however, it is felt that to achieve a marked increase in speed will require radical departures from the conventional circuit and array techniques that were employed in the model described here.' (Anacker et al., 1966, p. 50).

“IBM has developed a bipolar monolithic IC buffer memory for use on the 360/85 that is faster than any they have previously introduced. Access time to the entire contents of the 2K by 72-bit memory is 40 nsec. The buffer memory is constructed of half-inch square building blocks composed of two silicon chips and their leads and insulation. Each of the chips measures less than an eighth of a square inch and contains 664 components (transistors, diodes, and resistors). Each chip provides 64 distinct but interconnected storage cells. The components involved are SO minute that 53,000 can fit into a one square inch

area.

"The significance of the microminiaturization is of course little related to 'how many of what fit where.' What IBM gains from this construction is a circuit speed- demonstrated on some experimental chips-that is as fast as 750 picoseconds (trillionths of a second).

"The speed of the buffer memory (which at one time was to be called a 'cache', but that term has apparently been dropped) is not down to the 750 pisec figure, but a 7 nsec/chip read and a 12 nsec/chip write speed isn't bad." (Datamation 15, No. 4, 193 (Apr. 1969).)

6.134 "Electronic Memories, Inc., demonstrated its NANOMEMORY 650 . . . capacity of 16,384 words of up to 84 bits, and an access time of 300 nsec." (Commun. ACM 9, No. 6, 468 (June 1966).)

6.135 "The ICM-40, a one μ sec cycle time, 500 nsec access time, core memory, available with capacities from 4K × 6 bits to 16K × 84 bits has been announced by Computer Control Company, Inc." (Commun. ACM 9, 316 (1966).)

6.136 "International Business Machines Corp. has developed an experimental thin-film computer memory that has a 120-nanosecond cycle time, a 589, 824-bit capacity and fits in a frame 68 by 42 by 7 inches-including the electronic circuits for driving and sensing." (Electronics 39, No. 3, 41 (1966).

6.137 "The memory has a capacity of 8192 words, 72 bits per word, and has a cycle time of 110 nanoseconds and an access time of 67 nanoseconds. The storage devices are miniature ferrite cores, 0.0075 by 0.0123 by 0.0029 inches, and are operated in a two-core-per-bit destructive readout mode. A planar array geometry with cores

resting on a single ground plane is used to control drive line parameters. Device switching speed and bit line recovery are treated as special problems." (Werner et al., 1967, abstract, p. 153).

6.138 "It seems a certainty that plated wire memories will become a very important member in the hierarchy of storage systems to be used in the computers of tomorrow." (McCallister and Chong, 1966, p. 313).

"Both UNIVAC 9200/9300 Systems utilize a new plated-wire memory for internal storage featuring a non-destructive read-out mode and monolithic circuitry." (Commun. ACM 9, 650 (1966).)

6.139 "Capacity of this memory is 4096 68bit words (278, 528 bits, to be exact) and it operates with a cycle time of 200 nanoseconds and an access time of 160 nanoseconds. It is a word-organized, random-access memory. The memory element is composed of a pair of planar thin films coupled together and read out destructively." (Meddaugh and Pearson, 1966, p. 281).

6.140 "The operation of this half-microsecondcycle memory module represents a significant achievement in a program of magnetic thin-film development for computer storage which was begun at these laboratories in 1955. Large numbers of substrates were processed and tested, and memory plane assembly and test are now routine operations.

"Memory frames which contain 20 substrates (15,360 bits) can be assembled without great difficulty

"A shorter memory cycle can be made possible by reducing the total sense delay, and by the elimination of the bit recover pulse. The pulse transformers will be replaced by active solid-state devices. A reduction of 150 nsec-50 nsec from a shorter sense delay and 100 nsec from elimination of the bit recover pulse- make a cycle time of 350 nsec, or 3-Mc operation, possible." (Bittman, 1964, p. 105).

"Fabrication, assembly, and operation of these half-microsecond memories has proven that large numbers of reliable film substrates are producible and that the completed memories can compete in both speed and price with the high-speed 2-1/2 D-type core memories. The future for planar films looks very bright — both larger and faster memories are in the design stage. These memories will combine the economic advantages of batch fabrication with the fast switching properties of thin-films." (Jones and Bittmann, 1967, p. 352).

6.141 "Extensive memory research aimed at implementing the inherent 1-ns switching capabilities of thin magnetic films within a system environment has resulted in a cross-sectional 147000-bit capacity film memory model with a nondestructive-READ-cycle time of 20 ns, an access time of 30 ns, and a WRITE-READ time interval of 65 ns. The shortest time interval between

addressing of two different word lines is 20 ns." Seitzer, 1967, p. 172).

6.142 "A single layer composite magnetic film is operated in a rotational destructive-read-out mode with two access wires. Each bit is composed of two 2 × 6 mil intersections of the word and digit lines with a density of 12,500 bits/in. Magnetic film structures which provide flux closure in the hard, easy, or both directions were considered by rejected when adequate margins were obtained with the single layer. Although the open structure has fabrication advantages, the closed structures remain of interest for future work." (Raffel et al., 1968, pp. 259–260).

"The access time of the memory from change of address to information output from the buffer flip-flops is about 450 nsec. The largest contribution to this delay is the transient on the sense-line due to group-switch voltage transitions. The circuitlimited cycle time for read-write or clear-write is 600 nsec. Recovery from the digit-pulse transient limits the total cycle time to lusec with the digit transient overlapping the group-switch transient. (Raffel et al., 1968, p. 261). made from copper

6.143 "The chains

are

strips which have been plated with a Ni-Fe film and are used to carry word current. The bit/sense signals are carried in wires which pass through the holes in the 'links' of the chain. The memory element thus formed will operate in a rotational switching mode and can be used for a word-organized memory." (Geldermans et al., 1967, abstract, p. 291).

6.144 "It has been shown that high-speed chain memories can be built in very high-density arrays with minimum electromagnetic interactions. The bit/sense wires can be treated as homogeneous transmission lines with relatively high characteristic impedence (100 ) and good signal-to-noise ratios. The word lines are high-impedence strip lines whose inductance is mainly determined by the nonlinear magnetic film. This makes evaluation more difficult, but implies favorable properties for the design of very long lines.

"Based on the analysis of recently plated chains with smaller dimensions and better films, the characteristics of various possible chain memories have been extrapolated. Straightforward design philosophy, using transistor selection can be applied for a 0.3 106-bit NDRO memory, a 106-bit, 100-nsec DRO memory, and a 38×106-bit 500-nsec DRO

memory.

"These performance predictions reflect the merits of a film device with complete flux closure and highquality oriented films as exhibited in the chain device; they appear quite attractive for their size, speed, and circuitry requirements. Chains imply a simple semi-batch process and combine fast rotational switching properties of oriented films with the larger signal capability of cores." (Abbas et al., 1967, p. 311).