Associative methodology for diagnosing personal maturity Authors: E. V. Kalyaeva, T. V. ProkofievaInstruction. Your attention is invited to a number of words. Think about what associations each of these words evokes, write them down. 35 characteristics are offered that reveal the concept

"Everyday" memory and long-term memory Consider two more questions related to the topic "Memory". So far, the focus has been on standard laboratory methods that are often used in the study of memory at any age. The last two

8. Associative psychology In the process of the formation of psychology, the associative approach to perception began to prevail. Associative psychology is one of the main trends in the psychology of the 17th–19th centuries. The main explanatory principle of mental life was the concept

The storage device, as a rule, contains many identical storage elements that form a storage array (SM). The array is divided into individual cells; each of them is designed to store a binary code, the number of bits in which is determined by the width of the memory sample (in particular, it can be one, half, or several machine words). The way memory is organized depends on the methods of placing and searching for information in the storage array. On this basis, address, associative and stack (store) memory are distinguished.

address memory. In memory with an address organization, the placement and search of information in the SM is based on the use of the storage address of the word (number, command, etc.), the address is the number of the SM cell in which this word is located.

When writing (or reading) a word to the SM, the command initiating this operation must indicate the address (cell number) at which the recording (reading) is performed.

The typical address memory structure shown in fig. 4.2 contains a storage array of N n-bit cells and its hardware frame, including the address register RgA, having k(k> log 2 N) bits, information register RGI, address fetch block BAS, readout amplifier unit BUS, block of bit amplifiers-formers of recording signals BUZ and memory management BUP.

Fig.4.2.Structure of address memory.

By address code RgA BAV generates signals in the corresponding memory cell that allow reading or writing a word in the cell.

The memory access cycle is initiated by the arrival of BUP from outside the signal Appeal. The general part of the circulation cycle includes the reception in RgA with address bus USA addresses of appeal and reception in BUP and decoding of the control signal Operation, indicating the type of requested operation (read or write).

Next when reading BAS decrypts the address, sends read signals to the cell specified by the address ZM, in this case, the code of the word written in the cell is read by the readout amplifiers BUS and transferred to RGI. Then in memory with destructive reading (when reading, all storage elements of the cell are set to the zero state). information is regenerated in the cell by writing to it from RGI read word. The read operation is completed by issuing a word from RGI to the output information bus SHIout.

When writing, in addition to performing the above general part of the access cycle, the word being written is received from the input information bus SHIVx in RGI. The record itself consists of two operations: clearing the cell (reset to 0) and the record itself. For this BAS first selects and clears the cell specified by the address in RgA. Clearing is performed by the word read signals in the cell, but the read amplifiers and from BUS in RGI information is not received. Then to the chosen BAS cell is written word from RGI.

Control block BUP generates the necessary sequences of control signals that initiate the operation of individual memory nodes. Control signal transmission chains are shown by thin lines in fig. 4.2.

associative memory. In this type of memory, the search necessary information produced not by address, but by its content (by association). In this case, the search by an associative attribute (or sequentially by individual digits of this attribute) occurs in parallel in time for all cells of the storage array. In many cases, associative search can significantly simplify and speed up data processing. This is achieved due to the fact that in this type of memory the operation of reading information is combined with the execution of a number of logical operations.

A typical structure of associative memory is shown in fig. 4.3. The storage array contains N(P + 1) -bit cells. The service n-th bit is used to indicate the occupancy of the cell (0 - the cell is free, 1 - the word is written in the cell).

On the input information bus SHIVx to the register of the associative feature RGAP in digits 0-and-1 enters P- bit associative query, and into the mask register RgM - search mask code, with the nth digit RgM set to 0. Associative search is performed only for a set of digits RGAP, which "correspond to 1 in RgM(unmasked digits RgAP). For words in which the digits in the digits matched the unmasked digits RGAP, combinational circuit KS sets 1 to the corresponding bits of the match register RgSv and 0 to the rest of the bits. So the value j-ro discharge in RgSv is defined by the expression

RgSv(j) =

where RGAP[i], RgM[i] and ZM - values ​​of the i-th digit, respectively RGAP, RGM and j-th cell ZM.

Combination scheme for generating the result of an associative call FS forms from a word formed in RgSv, signals  0 ,  1 ,  2 corresponding to the absence of words in ZM, satisfying the associative feature, the presence of one or more than one such word. For this FS implements the following boolean functions:

 0 =

 1 = РгСв

 2 =  0  1

Content Shaping RgSv and signals  0 ,  1 ,  2 by content RGAP, RGM and ZM is called an association control operation. This operation is an integral part of the read and write operations, although it also has an independent meaning.

When reading, the association is first controlled by an associative feature in RGAP. Then at  0 = 1 reading is canceled due to the lack of the required information, when  1 = 1 it is read in RGI found word, with  2 = 1 in RGI the word is read from the cell with the smallest number among the cells marked 1 in RgSt. From RGI the read word is issued on SHIout.

Rice. 4.3. Structure of associative memory

When writing, a free cell is first searched. To do this, an association control operation is performed when RgAP= 111. ..10 and RgM== 00... 01. In this case, free cells are marked 1 in RgSt. For recording, a free cell with the smallest number is selected. It contains the word received from SHIVx in RGI.

Rice. 4.4. stack memory

With the help of the association control operation, it is possible, without reading words from memory, to determine by the content RgSv, how many words in memory that satisfy an associative attribute, for example, to implement queries like how many students in a group have an excellent mark in a given discipline. When appropriate combinational circuits are used, quite complex logical operations can be performed in associative memory, such as searching for a larger (smaller) number, searching for words enclosed within certain boundaries, searching for the maximum (minimum) number, etc.

Note that associative memory requires storage elements that can be read without destroying the information recorded in them. This is due to the fact that in the associative search, reading is performed over the entire SM for all unmasked bits and there is no place to store information temporarily destroyed by reading.

stack memory, as well as associative, is unaddressed. AT stack memory(Fig. 4.4) cells form a one-dimensional array in which neighboring cells are connected to each other by bit chains of word transmission. A new word is written to the top cell (cell 0), while all previously recorded words (including the word that was in cell 0) are shifted down to adjacent cells with numbers larger by 1. Reading is possible only from the upper (zero) memory cell, while if reading with deletion is performed, all other words in the memory are shifted upwards to neighboring cells with higher numbers. In this memory, the order in which words are read follows the rule: last entered - served first. In a number of devices of the type under consideration, the operation of simply reading a word from the zero cell (without deleting it and shifting the word in memory) is also provided. Sometimes stack memory is provided with a stack counter chst, showing the number of memorized words. Signal MFST = 0 matches empty, stack, MFST = N - 1 - full stack.

Often stack memory is organized using address memory. Stack memory is widely used when processing nested data structures.

The following paragraphs of the chapter describe the various types of memory with address organization. Associative memory is used in the equipment for dynamic memory allocation, as well as for building a cache memory.

Associative memory

Associative memory(AP) or Associative storage device(CAM) is a special kind of machine memory used in very fast search applications. Also known as content-addressable memory, associative storage device, content-addressable memory or associative array, although the latter term is more commonly used in programming to refer to a data structure. (Hannum et al., 2004)

Hardware Associative Array

Unlike conventional machine memory (random access memory, or RAM), in which the user specifies a memory address and RAM returns the data word stored at that address, the AP is designed so that the user specifies the data word and the AP looks for it throughout memory. to find out if it's stored anywhere in it. If a data word is found, the UA returns a list of one or more storage addresses where the word was found (and, on some architectures, also returns the data word itself, or other related pieces of data). Thus, the AP is a hardware implementation of what in terms of programming would be called an associative array.

Industry standard content addressable memory

The definition of the main interface for the UA and other Network Search Elements (NSE) was specified in an Interoperability Agreement called the Look-Aside Interface ( LA-1 and LA-1B) which was developed by the Network Processing Forum, which was later merged into the Optical Internetworking Forum (OIF). Numerous devices have been manufactured by Integrated Device Technology, Cypress Semiconductor, IBM, Netlogic Micro Systems, and others under these LA agreements. On December 11, 2007, the OIF issued the Serial Lookaside Interface Convention (Serial Lookaside, SLA).

Implementation on semiconductors

Because the AP is designed to search all of memory in one operation, this is much faster than searching RAM in virtually all search applications. However, there is a downside to the higher cost of AP. Unlike the RAM chip, which has simple stores, each individual bit of memory in a fully parallel AP must have its own comparison circuit attached to detect a match between the stored bit and the input bit. In addition, the outputs of the comparisons from each cell in the data word must be combined to yield the full comparison result of the data word. The additional circuitry increases the physical size of the AP chip, which adds to the manufacturing cost. The extra circuitry also increases power dissipation, since all comparison circuits are active on every clock cycle. As a consequence, AM is used only in specialized applications where search speed cannot be achieved using other less expensive methods.

Alternative implementations

In order to achieve a different balance between speed, memory size, and cost, some implementations emulate AP functions by using standard search tree or hashing algorithms implemented in hardware, also using hardware tricks such as replication and pipelining to speed up efficient operation. These designs are often used in routers.

Ternary Associative Memory

Binary AA is the simplest type of associative memory that uses data lookup words composed entirely of 1s and 0s. In ternary AA, a third value is added to compare "X" or "don't care" for one or more bits in the stored data word, thus adding more search flexibility. For example, in a ternary UA, the word "10XX0" could be stored, which would match any of the four search words "10000", "10010", "10100", or "10110". Adding flexibility to the search comes at the expense of increasing the cost of the binary AT, since the internal memory cell must now encode three possible states instead of two. This additional state is usually implemented by adding an "importance" ("important"/"not important") mask bit to each memory location.

Holographic associative memory provides a mathematical model for integrated don't care bit associative memory using a complex-valued representation.

Application examples

Content-addressable memory is often used in computer network devices. For example, when a network switch receives a data frame on one of its ports, it updates an internal table with the origin of the frame's MAC address and the port on which it was received. It then looks up the destination MAC address in a table to determine which port the frame should be sent to, and sends it to that port. Table MAC addresses usually implemented on a binary AP, so the destination port can be found very quickly, reducing the switch's latency.

Ternary APs are often used in those network routers where each address has two parts: (1) the network address, which can change in size depending on the subnet configuration, and (2) the host address, which occupies the remaining bits. Each subnet has a netmask that specifies which bits are the network address and which bits are the host address. Routing is done by checking against the routing table maintained by the router. It contains all known destination network addresses, their associated netmask, and information needed by packets routed to that destination. A router implemented without a UA compares the destination address of the packet to be split with each entry in the routing table, doing a logical AND with the netmask and comparing the results with the net address. If they are equal, the corresponding direction information is used to send the packet. The use of a ternary UA for the routing table makes the lookup process very efficient. Addresses are stored using the don't care bit in the host address part, so looking up the destination address in the UA immediately retrieves the correct entry in the routing table; both operations - applying the mask and comparing - are performed by the hardware of the AP.

Other AP applications include

• Cache Managers CPU and associative translation buffers (TLBs)

Bibliography

• Kohonen T. Associative storage devices. M.: Mir, 1982. - 384 p.

In English

• Anargyros Krikelis, Charles C. Weems (editors) (1997) Associative Processing and Processors, IEEE Computer Science Press. ISBN 0-8186-7661-2

• Hannum et al. (2004) System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state. U.S. Patent 6,823,434.

Links

Wikimedia Foundation. 2010 .

See what "Associative Memory" is in other dictionaries:

In computer science, unaddressed memory, in which information is searched for by its content (associative feature). See also: Computer memory software Finam Financial Dictionary ... Financial vocabulary

associative memory- Memory, in which addressing is determined not by the location of the object, but by its content. To find the address, the object is analyzed and its name (according to certain words) matches other addresses. Using associative memory… … Technical Translator's Handbook

associative memory- associative storage device; associative memory A storage device in which the address is determined by the content of the stored information ... Polytechnic terminological explanatory dictionary

associative memory- asociatyvioji atmintis statusas T sritis automatika atitikmenys: angl. associated memory vok. associater Speicher, m; Durchsuchspeicher, m rus. associative memory, f pranc. mémoire associative, f … Automatikos terminų žodynas

ASSOCIATIVE MEMORY- See memory, associative ... Dictionary in psychology

This article should be wikified. Please, format it according to the rules for formatting articles. Human memory is associative, that is, a certain memory can generate a large area associated with it. One item reminds us ... Wikipedia

Ways to organize memory

Functionally, a memory of any type always consists of a storage array that stores information, and auxiliary, very complex blocks that serve to search in the array, write and read (and, if necessary, regenerate).

The storage array (MS) consists of a plurality of identical storage elements (SE). All SEs are organized into cells, each of which is designed to store a unit of information in the form of a binary code, the number of bits of which is determined by the sample width. The way the memory is organized depends on the methods of placing and searching for information in the SM. On this basis, address, associative and stack memory are distinguished.

ADDRESS MEMORY

In memory with an address organization, the placement and search for information in the SM is based on the use of the storage address of the information unit, which we will call further for brevity word. The address is the number of the SM cell in which this word is placed. When writing (reading) a word in the SM, the command initiating this operation must indicate the address (number) of the cell by which it is necessary to write (read).

On fig. 5.2 shows a generalized structure of address memory.

The memory access cycle is initialized by the "Access" signal arriving at the TCU. The general part of the access cycle includes receiving in RgA from the address bus (SHA) the address of the address and receiving in the TCU the control signal "Operation" indicating the type of the requested operation (reading or writing).

Reading. BAW decrypts the address and sends a signal that highlights the 3M cell specified by the address. In the general case, the BAW can also send signals to the allocated memory cell that set up the GE cells for writing or reading. After that, the word written in the cell is read by the BUS amplifiers and transmitted to the RGI. Further, in the memory with destructive reading, information is regenerated by writing a word from the RgI through the BUZ to the same SM cell. The read operation is completed by issuing a word from the RGI to the output information bus SHI out.

Record. In addition to the above general part of the access cycle, the written word is received from the input bus SHI in to RGI. The record itself generally consists of two operations - clearing the cell and the record itself. To do this, the BAS first selects and clears the cell specified by the address in PrA. Clearing the ZM cell (bringing to the initial state) can be done in different ways. In particular, in a memory with destructive readout, clearing can be done by a signal to read a word in a cell when the BUS is blocked (so that information does not enter the RGI). Next, a new word is written to the selected cell.

The need for the operation of clearing the cell before writing, as well as the operation of regenerating information during reading, is determined by the type of SGs used, control methods, features of the electronic structure of the LSI memory, and therefore these operations may be absent in semiconductor memories.

The TCU generates the necessary sequences of control signals that initiate the operation of individual memory nodes. It should be borne in mind that the TCU must be a very complex device (a kind of control controller with its own cache memory), which gives the memory LSI as a whole special consumer properties, such as multiport, pipelined output of information, etc.

ASSOCIATIVE MEMORY

In this type of memory, the search for information occurs not by address, but by its content. In this case, the content of information is usually understood not as the semantic load of the word stored in the memory cell, but as the content of the GE of the memory cell, ᴛ.ᴇ. the bitwise composition of the recorded binary word. In this case, the associative query (attribute) is also binary code with a certain bitwise composition. The search by an associative feature occurs in parallel in time for all SM cells and is an operation of comparing the content of the attribute register bits with the content of the corresponding bits of the memory cells. To organize such a search, all EP SMs are equipped with single-bit processors; therefore, in some cases, this type of memory is considered as a multiprocessor system.

Large fully associative memory is a very expensive device, therefore, in order to reduce its cost, the number of single-bit processors is reduced to one per memory cell. In this case, the comparison of the associative query with the contents of the memory cells is carried out sequentially for individual digits, parallel in time for all SM cells.

With very large amounts of memory on certain classes of problems, associative search significantly speeds up data processing and reduces the probability of failure in the computer. At the same time, associative memories with blocks of corresponding combinational circuits make it possible to perform rather complex logical operations: finding the maximum or minimum number in an array, finding words within certain boundaries, sorting an array, etc.

It should be noted that an associative search can also be implemented in a computer with a conventional address memory, sequentially calling the words written in the memory cells to the processor and comparing them with some associative feature (template). At the same time, with large amounts of memory, a lot of time will be spent on this. When using associative memory, it is possible, without reading words from the RAM to the processor, to determine the number of words corresponding to one or another associative query in one call. This allows in large databases to very quickly implement a query like: how many residents of the region did not submit an income declaration, etc.

In some specialized computers, the OP or part of it is built in such a way that it makes it possible to implement both associative and targeted information search.

Simplified structural scheme associative memory, in which all ME SM are equipped with single-bit processors, is shown in fig. 5.3.

Let us first consider the operation called association control. This operation is common to the read and write operations, and also has an independent value.

An n-bit associative request, ᴛ.ᴇ, enters the RGAP via the input information buse. digits from 0 to n-1 are filled. At the same time, the search mask code enters RgM, while the nth bit of RgM is set to 0. Associative search is performed only for the set of RgAP bits that correspond to 1 in RgM (unmasked RgAP bits). It is important to note that for words in which the digits in the digits coincided with the unmasked digits of PrAP, the CS sets 1 in the corresponding digits of PrCv and 0 in the remaining digits.

The combinational scheme for generating the result of the associative inversion of the FS forms at least three signals from the word formed in RgSv:

A 0 - the absence in the SM of words that satisfy the associative attribute;

A 1 - the presence of one such word;

A 2 - the presence of more than one word.

Other operations on the contents of PgSv are also possible, for example, counting the number of units, ᴛ.ᴇ. counting words in memory that satisfy an associative query, etc.

The formation of the contents of RgSv and a 0 , a 1 , a 2 according to the contents of RgAP, RgM, ZM is usually called the association control operation.

Reading. First, the association is controlled on the basis of RgAP.

A 0 = 1 - reading is canceled due to the lack of the required information;

A 1 \u003d 1 - the found word is read into the RGI, after which it is issued to the SHI output;

A 2 \u003d 1 - a word is read that has, for example, the smallest number among the cells marked 1 in RgSv, after which it is issued to the SHI output.

Record. First, a free cell is found (we assume that 0 is written in the busy bit of a free cell). To do this, the association control is performed at PgAP=111...10 and PgM=000...01, ᴛ.ᴇ. The nth digit of RgAP is set to 0, and the nth digit of RgM is set to 1. In this case, the free cell is marked 1 in RgSv. For recording, a free cell is selected, for example, with the smallest number. It contains the word received from SHI in RGI.

It should be noted that this diagram does not show the blocks BUP, BUS, BUS, which are in real devices. At the same time, to build an associative memory, storage elements are required that can be read without destruction.

STACK MEMORY (STORE)

Stack memory, like associative memory, is unaddressed. Stack memory must be organized both in hardware and on a regular array of address memory.

In the case of a hardware implementation, the stack memory cells form a one-dimensional array in which neighboring cells are connected to each other by bit chains of word transmission (Fig. 5.4). In this case, two types of devices (a, b) are possible, the principles of operation of which are different. Let us first consider the structure in Fig. 5.4, ​​a.

The entry of a new word received from SHI in is made to the upper (zero) cell, while all previously recorded words (including the word in cell 0) are shifted down to adjacent cells, the numbers of which are greater by one. Reading is possible only from the upper (zero) memory cell. The main mode is ϶ᴛᴏ reading with deletion. At the same time, all other words in memory are shifted up to adjacent cells with lower numbers. In such a memory, the following rule is implemented: last in, first out. Stacks of this type are called LIFO (Last In - First Out) stacks.

In some cases, stack memory devices also provide for the operation of simply reading a word from cell 0 without deleting it and shifting the rest of the words. When using the stack to store the initialization parameters of the controllers of any computer devices, it is usually possible to read the contents of any stack cell without deleting it, ᴛ.ᴇ. reading content not just cell 0.

The first word pushed onto the stack is said to be located on bottom of the stack. The last word sent (in time) to the stack is said to be in top of the stack. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, cell N-1 is the bottom of the stack, and cell 0 is the top.

Typically, the hardware stack is provided with a stack counter, ChSt, showing the total number of words stored in memory (CHSt = 0 - the stack is empty). When the stack is full, it disables further write operations.

The stack principle of memory organization can be implemented not only in devices specially designed for this purpose. Stack organization of data is also possible on conventional address memory with random access (software stack). To organize the LIFO stack in this case, one more memory cell (register) is needed, in which the address of the top of the stack is always stored and which is commonly called stack pointer. Usually, one of the processor's internal registers is used as the stack pointer. In addition, appropriate software is required. The principles of stack organization of data on conventional address memory are illustrated by the diagram in fig. 5.5.

Unlike a hardware stack, data placed on a software stack is not moved when a new number is written or read. Each new word is written to the memory location following in order the one whose address is contained in the stack pointer. After a new word is written, the stack pointer is incremented by one (see Figure 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, it's not the data that moves on the software stack, but the top of the stack. When a word is read from the stack, the process is reversed. The word is read from the location whose address is in the stack pointer, after which the contents of the stack pointer are decremented by one.

If the words newly loaded onto the stack are placed in memory cells with sequentially increasing addresses, the stack is called direct. If the addresses are consecutively decreasing, then - upside down. In most cases, a flipped stack is used, which is due to the peculiarities of the hardware implementation of counters inside the processor.

How convenient is this form of memory organization? Looking ahead, it can be noted that any instruction executed in the processor, in the general case, must contain an operation code (COP), the address of the first and second operands, and the address of the result. To save memory and reduce the execution time of a machine instruction by the processor, it is desirable to reduce the length of the instruction. The limit for this reduction is the length of the unaddressed command, ᴛ.ᴇ. just COP. It is these instructions that are possible with the stack organization of memory, since with the correct arrangement of operands on the stack, it is enough to sequentially extract them and perform the appropriate operations on them.

In addition to the stack memory of the LIFO type discussed above, computers use stack memories of another type that implement the rule: first in - first out. Stacks of this type are called FIFO (First In - First Out) stacks. Such stack memory is widely used for organizing various kinds of queues (commands, data, requests, etc.). The generalized structure of the hardware stack of the FIFO type is shown in fig. 5.4b.

As in the previous case, the stack memory cells form a one-dimensional array in which adjacent cells are connected to each other by bit chains of word transmission. The entry of a new word received from SHI in is carried out in the upper (zero) cell, after which it immediately moves down and is written to the last empty cell. If the stack before writing was empty, the word immediately goes to the cell with the number N-1, ᴛ.ᴇ. to the bottom of the stack. Reading is only possible from the bottom cell numbered N-1 (the bottom of the stack). The main mode is ϶ᴛᴏ reading with deletion. In this case, all subsequent (recorded) words are shifted down to adjacent cells, the numbers of which are one more. When the stack is full, the counter (CHST) prohibits further writes to the stack.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, unlike the LIFO stack, the FIFO stack does not move the bottom, but the top. Words written to the FIFO stack gradually move from the top to the bottom, from where they are read as they are extremely important, and the rate of writing and reading is determined by external control signals and is not related to each other.

Software implementation The FIFO stack is not considered in this section, since it is rarely used in practice.

Ways of memory organization - concept and types. Classification and features of the category "Methods of organizing memory" 2017, 2018.