Friday 2 November 2012

Memory Organization - Main Memory


Memory Organisation
·        Memory is made up of lots of storage locations.
·        Each location can hold a word.
·         A word is the term given to the number of bits that can be processed by the computer in a single operation.
·        So the correct data can be found in main memory, each storage location has its own unique address. Hence, the data wouldn’t be sent to the incorrect destination. This concept is called addressability.

Memory Hierarchy

Main Memory
·        Main memory is a memory unit that communicates directly to the CPU of the computer.
·        It is a combination device of both RAM (random access memory) and ROM (read only memory).
·        Main memory is a part of Central Processing Unit(CPU).


Characteristic of Memory
·         Capacity, representing the global volume of information (in bits) that the memory can store
·         Access time, corresponding to the time interval between the read/write request and the availability of the data
·         Cycle time, representing the minimum time interval between two successive accesses
·         Throughput, which defines the volume of information exchanged per unit of time, expressed in bits per second
·         Non-volatility, which characterises the ability of a memory to store data when it is not being supplied with electricity

Types of Main Memories
·        Main Memory are classified into two basic types:
i.                   Random Access Memory (RAM)
ii.                 Read Only Memory (ROM)

What is RAM?
·        Random Access Memory (RAM) is a type of main memory which store the data temporarily when a program is running.
·        RAM can be called as primary memory/primary storage/main storage/internal memory/core memory/core storage/internal storage
·        It is sometimes called semiconductor memory because storage cells are made out of semi-conducting material.
·        It takes the form of integrated circuits.
·        Hold the data and instructions temporarily when the CPU is processing.
·        Examples of what is stored in RAM:
§  the operating system
§  applications
§  the graphical user interface (GUI)
What is ROM?
·        ROM is a type of main memory ROM is computer memory which retains its data, even when the computer is switched off.
·        ROM can be called as auxiliary memory/physical memory/external memory
·        Hold data necessary for starting up the computer permanently, whose contents cannot be changed by the user.


Difference between RAM and ROM

Types of RAM
There are two types of RAM:
i.                   Dynamic RAM (DRAM)
·        Analog device
·        Volatile in nature but they need  regenerator to retain the data as long as they receive the power.
·        DRAM chips contain a transistor that acts as a gate to a capacitor which purpose is to store the bits as charge in it
·        The charge on the capacitor indicates a ‘1’ bit and no charge indicates a ‘0’ bit. The charge on the capacitor leaks away after a few milliseconds. Therefore, a dynamic RAM has to be refreshed periodically after every two milliseconds.
·        DRAM uses its contents in a very short time even though the power supply is on.
·        Consumes less power and has higher packing density. It is cheaper than the static RAM.
·        DRAM’s be recommended for large sized memories.(i.e. main memory)

DRAM Structure

i.                   Static RAM (S-RAM)
·        Digital device
·        Bits store as flip-flops(on/off switches)
·        Volatile in nature but they need no regenerator to retain the data as long as they receive the power.
·        Consumes more power and is more expensive.
·        The structure of SRAM chips are more complicated and hence require more space.
·        Static RAM’s are faster than the dynamic RAM’s .Static RAM’s have an access time of approximately 85 to 90ns while the dynamic RAM’s may take 150 to 200ns to provide information.
·        SRAM’s are recommended for medium sized memories.(i.e. cache memory)

SRAM structure


Differences between DRAM and SRAM

Types of ROM
There are five types of ROM:
i.                    Programmable Read Only Memory (PROM):
·        A PROM program is used to record information in the PROM chip.
·        The information once programmed into the PROM chip is permanent and cannot be changed or erased.
·        The process of entering the information into the PROM chip is known as “burning the PROM.”
·        It is need special equipment to program.
·        The storing in ROMs will be very expensive when only a small number is required. Thus, PROMs provide a faster and less expensive approach for storing.

ii.            Masked Read Only Memory (MROM)
·        The masking and metallisation process permanently records the information.(ROM bits)
·        It is not easy to perform this process as a large infrastructure is required, and therefore, it is usually the manufacturers who perform this process.

         iii.          Erasable Programmable Read Only Memory (EPROM)

·        An erasable PROM.
·        It can be reprogrammed using an EPROM programmer.
·        It is only one transistor per bit.
·        The contents can be erased by expose it to high intensity ultraviolet light with a wavelength of 2537A (angstrom) for 30 minutes (approximately).
·        The process of changing the contents is not convenient, as the chip has to be removed from the board for exposure to the ultra-violet light source.
·        If the user wants to erase the contents of a single memory,the entire memory contents have to be erased.
The EPROM chip is cheap, reliable and widely available

iv.         Electrically Erasable Programmable Read Only Memory (EEPROM)
·         An electrically erasable PROM.
·        Using electrical signals can alter the information and that is why the chip need not be removed from the board.
·        EEPROM chip has over the EPROM is that even single memory can be altered, i.e., the entire memory need not be erased and reprogrammed unless required.
·        Changing the contents does not require additional equipment.
·        The change in the contents of the EEPROM chip is made in milliseconds, which is much less than the erasing time for EPROM.
·        It is less dense than EPROM.



v.                  Non-Volatile RAM
·        Combination device of a static RAM and EEPROM.
·        It operates as normal RAM but in case the power supply fails, the entire contents of the RAM are stored in EEPROM.
·        The data from EEPROM is transferred back to the RAM when the power supply is restored.
References

Written by,
TAN SIN YEE
B031210297









Memory Organization - Auxinary Memory


Auxiliary Memory
The main memory construction is costly. Therefore, it has to be limited in size. The main memory is used to store only those instructions and data which are to be used immediately. However, a computer has to store a large amount of information. The bulk of information is stored in the auxiliary memory. This is also called backing storage or secondary storage. They include hard disk, floppy disks, CD-ROM, USB flash drives, etc.
When the electricity supply to the computer is off, all data stored in the primary storage is destroyed. On the other hand, this is not true for secondary storage. The data stored in secondary storage can be stored for the desired time.
The most common auxiliary memory devices used in computer systems are magnetic disks and tapes. Other components used, but not as frequently, are magnetic drums, magnetic bubble memory, and optical disks. To understand fully the physical mechanism of auxiliary memory devices one must have knowledge of magnetic, electronics, and electromechanical systems. 

Although the physical properties of these storage devices can be quite complex, their logical properties can be characterized and compared by a few parameters. The important characteristics of any device are its access mode, access time, transfer rate, capacity, and cost.
The average time required to reach a storage location in memory and obtain its contents is called the access time. In electromechanical devices with moving parts such as disks and tapes, the access time consists of  a seek time required to position the read-write head to location and a transfer time required to transfer data to or from the device. Because the seek time is usually much longer than the transfer time, auxiliary storage is organized in records or blocks. A record is a specified number of characters or words. Reading or writing is always done on entire records. The transfer rate is the number of characters or words that the device can transfer per second, after it has been positioned at the beginning of the record.
Magnetic drums and disks are quite similar in operation. Both consist of high-speed rotating surfaces coated with a magnetic recording medium. The rotating surface of the drum is a cylinder and that of the disk, a round flat plate. The recording surface rotates at uniform speed and is not started or stopped during access operations. Bits are recorded as magnetic spots on the surface as it passes a stationary mechanism called a write head. Stored bits are detected by a change in magnetic field produced by a recorded spot on the surface as it passes through a read head. The amount of surface available for recording in a disk is greater than in a drum of equal physical size. Therefore, more information can be stored on a disk than on a drum of comparable size. For this reason, disks have replaced drums in more recent computers.

Magnetic Disks
A magnetic disk is a circular plate constructed of metal or plastic coated with magnetized material. Often both sides of the disk are used and several disks may be stacked on one spindle with read/write heads available on each surface. All disks rotate together at high speed and are not stopped or started for access purposes. Bits are stored in the magnetized surface in spots along concentric circles called tracks. The tracks are commonly divided into sections called sectors. In most systems, the minimum quantity of information which can be transferred in a sector. The subdivision of one disk surface into tracks and sectors in shown in Figure 12.5.
Some units use a single read/write head for each disk surface. In this type of unit, the track address bits are used by a mechanical assembly to move the head into the specified track position before reading or writing. In other disk systems, separate read/write heads are provided for each track in each surface. The address bits can then select a particular track electronically through a decoder circuit. This type of unit is more expensive and is found only in very large computer systems.
Permanent timing tracks are used in disks to synchronize the bits and recognize the sectors. A disk system is addressed by address bits that specify the disk number, the disk surface, the sector number and the track within the sector. After the read/write heads are positioned in the specified track, the system has to wait until the rotating disk reaches the specified sector under the read/write head. Information transfer is very fast once the beginning of a sector has been reached. Disks may have multiple heads and simultaneous transfer of bits from several tracks at the same time.  

A track in a given sector near the circumference is longer than a track near the center of the disk. If bits are recorded with equal density, some tracks will contain more recorded bits than others. To make all the records in a sector of equal length, some disks use a variable recording density with higher density on tracks near the center than on tracks near the circumference. This equalizes the number of bits on all tracks of a given sector.
Disks that are permanently attached to the unit assembly and cannot be removed by the occasional user are called hard disks. A disk drive with removable disks is called a floppy disk. The disks used with a floppy disk drive are small removable disks made of plastic coated with magnetic recording material. There are 2 sizes commonly used, with diameters of 5.25 and 3.5 inches. The 3.5-inch disks are smaller and can store more data than can the 5.25-inch disks. Floppy disks are extensively used in personal computers as a medium for distributing software to computer users.

Magnetic Tape
          A magnetic tape transport consists of the electrical, mechanical, and electronic components to provide the parts and control mechanism for a magnetic-tape unit. The tape itself is a strip of plastic coated with a magnetic recording medium. Bits are recorded as magnetic spots on the tape along several tracks. Usually, 7 or 9 bits are recorded simultaneously to form a character together with a parity bit. Read/write heads are mounted one in each track so that data can be recorded and read as a sequence of characters.
          Magnetic tape units can be stopped, started to move forward or in reverse, or can be rewound. However, they cannot be started or stopped fast enough between individual characters. For this reason, information is recorded in blocks referred to as records. Gaps of unrecorded tape are inserted between records where the tape can be stopped. The tape starts moving while in a gap and attains its constant speed by the time it reaches the next record. Each record on tape has an identification bit pattern at the beginning and end. By reading the bit pattern at the beginning, the tape control identifies the record number. By reading the bit pattern at the end of the record, the control recognizes the beginning of a gap. A tape unit is addressed by specifying the record number and the number of characters in the record. Records may be of fixed or variable length.

What is auxiliary memory give an example of auxiliary memory?

The major difference between main memory and auxiliary memory is that main memory is directly accessed by CPU but the auxiliary memory is not accessed by the CPU directly. For this the data is first transferred to main memory from auxiliary memory and then from main memory the data is transferred to the CPU for further processing.


Distinguish between primary memory and auxiliary memory?

The main memory is the central storage unit of the computer system. It is relatively large and fast memory used to store the programs and data during the computer operation. Main memory communicates directly with the CPU. Main memory includes RAM and ROMs.

Devices that provide backup storage are known as auxiliary memory. Auxiliary memory is relatively slow in comparison to the main memory. Auxiliary memory includes flash memory, magnetic disks and floppy. Main memory is located inside the CPU but auxiliary memory is located out the CPU.


Why is auxiliary memory required?

Auxiliary memory is required so that set of instruction given first stored in temporary memory which can be edited & then can be stored


What is the Difference between secondary memory and auxiliary memory?

Secondary memory is actually the permanent memory/the backing storage of the computer. It is of two types :
- sequential access
- direct access
Auxiliary memory is the computer's internal/temporary memory. It is also of two types:
- random access memory (RAM)
- read only memory (ROM)
The difference between secondary memory and auxiliary memory is that:-
both are same i.e. both perform the same operations.


Written by,
GOH HOOI KUAN
B031210043

Memory Organization - Associative Memory

Associative memory

What is associative memory in computer organization and architecture?
·        Is also known as
o   content addressable memory(CAM) or
o   associative storage or
o   associative array 
·        is a hardware search engines, a special type of computer memory used in certain very high searching applications
·        are composed of conventional semiconductor memory (usually SRAM) with added comparison circuitry that enable a search operation to complete in a single clock cycle.
·        is a special type of memory that is optimized for performing searches through data, as opposed to providing a simple direct access to the data based on an address.
·        The two most common search-intensive tasks that use CAMs are
o   packet forwarding and
o   packet classification in Internet routers.
·        A data-storage device in which a location is identified by its informational content rather than by names, addresses, or relative positions, and from which the data may be taken
·        Is a content-addressable structure that allows
o   maps a set of input patterns to a set of output patterns stored in memory. the process of transferring of data from main memory to cache is referred as mapping function, 
o   the recall of data based on the degree of similarity between the input patterns stored in memory.
·        There are 2 types of associative memory
o   Auto-associative
o   Hetero-associative
·        Auto-associative memory takes back(retrieves) a previously stored pattern that most closely resembles the current pattern.
·        Hetero-associative memory, the retrieved pattern is in general, different from the input pattern not only in content but possibly also in type and format.
·        Neutral networks are used to implement these associative memory models called NAM (Neutral associative memory).

Notes
ü Static random-access memory (SRAM) is a type of semiconductor memory that uses bistable latching circuitry to store each bit.
ü SRAM exhibits data remanence, but is still volatile in the conventional sense that data is eventually lost when the memory is not powered.

Example: Associative Memory
The figure below shows a memory containing names of several people.
If the given memory is content-addressable, then  using the erroneous(wrong) string “Crhistine Cullen” as key is sufficient to retrieve the correct name “Christine Cullen. ”
So this type of memory is robust and fault-tolerant, because this type of memory exhibits some form of error-correction capability.

Where is Associative memory used?
·        We are only using this associative memory in memory allocation format  and it is widely used in database management systems etc...

Advantages of Associative Memory        
·        This is suitable for parallel searches. It is also used where search time needs to be short
·        Associative memory is often used to speed up databases, in neural networks and in the page tables used by the virtual memory of modern computers.
·        CAM-design challenge is to reduce power consumption associated with the large amount of parallel active circuitry, without sacrificing speed or memory density
·        considerably facilitates the programming and solution of informational-logical problems and accelerates by hundreds (thousands) of times the speed of retrieval, analysis, classification, and processing of data.

Disadvantages of Associative Memory
·        It is expensive than RAM, as each cell must have storage capability and logical circuits for matching its content with external argument

Overview of Associative memory

Associative memory Vs Random access memory (RAM)
·        In RAM, the user supplies a memory address and the RAM returns the data word stored at that address
·        In associative memory,  the user supplies a data word and the associative memory searches its entire memory to see if that data word is stored anywhere in it.
·        If the data word is found, the associative memory returns a list of one or more storage addresses where the word was found
·        hardware of associative memory allows operations to occur in a single-clock cycle, as opposed to the much greater time required for an algorithmic based search through traditional RAM.
·        is a special type of memory that is optimized for performing searches through data, as opposed to providing a simple direct access to the data based on an address as in RAM.


Relationships between RAM and Associative memory



Associative Memory in Routers
·        A simple network with three routers.
·        The use of associative memories in high-end routers reduces the lookup time by allowing a search to be performed in a single operation.
·        The search is based on the destination address, rather than the physical memory address.
·        Access methods for this memory have been standardized into an interface interoperability agreement by the Network Processing Forum.


The application of address lookup in Internet routers
·        Internet routers forward data packets from an incoming port using an address lookup function 
·        The address lookup function examines the packet's destination address and chooses an output port associated with that address.
·        The router's list of destination addresses and their corresponding output ports is called the routing table.
·        An example of a simplified routing table is displayed in Table 1.

·        All four entries in the table 1 are 5-bit words, with the don't care bit, X, matching both a 0 and a 1 in that position.
·        Because of the X bits, the first three entries in Table 1 represent a range of input addresses, i.e. the entry on Line 1 indicates that all addresses in the range of 101002—101112 are forwarded to port A.
·        The router searches for the destination address of each incoming packet in the address lookup table to find the appropriate output port.
·        For example, if the router receives a packet with the incoming address 01101, the address lookup matches both Line 2 and Line 3 in the table.
·         Line 2 is selected since it has the most defined bits, indicating it is the most direct route to the destination.
·        This lookup style is called longest-prefix matching and is required to implement the most recent Internet Protocol (IP) networking standard.
·        The CAM contains the routing table from Table 1 to illustrate how a CAM implements address lookup.
There are two basic forms of Associative Memory(CAM):
o   Binary
Binary CAMs support storage and searching of binary bits, zero or one (0,1). 
o   Ternary.
o   Ternary CAMs support storing of zero, one, or don't care bit (0,1,X).
o   Ternary CAMs are presently the dominant CAM since longest-prefix routing is the Internet standard.
o   Figure 1 shows a block diagram of a simplified 4 x 5 bit ternary CAM with a NOR-based architecture.

o   The CAM core cells are arranged into four horizontal words, each five bits long.
o   Core cells contain both storage and comparison circuitry.
o   The search lines run vertically in the figure and broadcast the search data to the CAM cells.
o   The matchlines run horizontally across the array and indicate whether the search data matches the row's word.
o   An activated matchline indicates a match and a deactivated matchline indicates a non-match, called amismatch in the CAM literature.
o   The matchlines are inputs to an encoder that generates the address corresponding to the match location.
o   A CAM search operation begins with precharging all matchlines high, putting them all temporarily in the match state.
o   Next, the search line drivers broadcast the search data, 01101 in the figure, onto the search lines.
o   Then each CAM core cell compares its stored bit against the bit on its corresponding search lines.
o   Cells with matching data do not affect the matchline but cells with a mismatch pull down the matchline.
o    Cells storing an X operate as if a match has occurred. The aggregate result is that matchlines are pulled down for any word that has at least one mismatch.
o   All other matchlines remain activated (precharged high). In the figure, the two middle matchlines remain activated, indicating a match, while the other matchlines discharge to ground, indicating a mismatch.
o   Last, the encoder generates the search address location of the matching data. In the example, the encoder selects numerically the smallest numbered matchline of the two activated matchlines, generating the match address 01.

Associative Mapping
·        Because no bit field in the address specifies a line number the cache size is not determined by the address size
·        Associative-mapped memory is also called “content-addressable memory.”
·        Items are found not by their address but by their content
o   Used extensively in routers and other network devices
o    Corresponds to associative arrays in Perl and other languages
·        Primary disadvantage is the cost of circuitry

Associative Mapping
·        Parking lot analogy: there are more permits than spaces
·         Any student can park in any space
·        Makes full use of parking lot
o   With direct mapping many spaces may be unfilled
·        Note that associative mapping allows flexibility in choice of replacement blocks when cache is full

Associative Mapping Summary
·        Address length = (s + w) bits where w = log2(block size)
·        Number of addressable units = 2s+w words or bytes
·        Block size = line size = 2w words or bytes
·        Number of blocks in main memory = 2s+ w/2w = 2s
·        Number of lines in cache = undetermined
·        Size of tag = s bits
                                                                                        
Set Associative Mapping
·         A compromise that provides strengths of both direct and associative approaches
·        Cache is divided into a number of sets of lines
·        Each set contains a fixed number of lines
·        A given block maps to any line in a given set determined by that block’s address
— e.g. Block B can be in any line of set i
·        e.g. 2 lines per set
— 2-way associative mapping
— A given block can be in one of 2 lines in only one set

Set Associative Mapping
·        m = v * k
Where m = number of lines in cache, v = number of sets and k = lines/set
Lines in cache = sets * lines per set
·        i = j modulo v
Where I = set number and j = main memory block number
Set number = block number % number of sets
·        This is referred to as a “k-way” set associative mapping
·        Block Bi can be mapped only into lines of set j.

Set Associative Mapping: Parking Analogy
·        If we have 10,000 parking spaces we can divide them into 1000 sets of 10 spaces each
·        Still use middle digits of id to find your parking place set: xxx PPP yyy
·        You have a choice of any place in your set
·        Our parking lots actually work like this, but the sets are fairly large: Fac/Staff; Commuter; Resident; Visitor


Set Associative Mapping Example
·        Assume 13 bit set number
·        Block number in main memory is modulo 213 (0010 0000 0000 0000 = 2000h
·        000000, 002000, 004000, … map to same set

Set Associative Mapping Address Structure
·        Cache control logic sees address as three fields: tag, set and word
·        Use set field to determine cache set to look in
·        Compare tag field to see if we have a hit
·        e.g
— Address Tag Data Set number
— 1FF 7FFC 1FF 12345678 1FFF
— 001 7FFC 001 11223344 1FFF
·        Tags are much smaller than fully associative memories and comparators for simultaneous lookup are much less expensive

Set Associative Mapping Summary

·        For a k-way set associative cache with v sets (each set contains k lines):
Address length = (t+d+w) bits where w = log2(block size) and d= log2(v)
Number of addressable units = 2t+d+w words or bytes
Size of tag = t bits
Block size = line size = 2w words or bytes
Number of blocks in main memory = 2t+d
Number of lines in set = k
Number of sets = v = 2d
Number of lines in cache = kv = k * 2d
·        Tag (t bits) Set (d bits) Word
·        (w bits)

The operation of an associative memory
·        is based on the representation of all information in the form of a sequence of zones according to properties and characteristic attributes.
·        In this case the retrieval of information is reduced to the determination of the zone according to the preset attributes by means of scanning and comparison of those attributes with the attributes that are stored in the associative memory.
·        There are 2 basic methods of realizing the associative memory.
o   The first is the construction of a memory with storage cells that have the capability of performing simultaneously the functions of storage, nondestructive reading, and comparison.
Notes :
ü Such a method of realizing an associative memory is called network parallel-associative—that is, the required sets of attributes are preserved in all the memory cells, and the information that possesses a given set of attributes is searched for simultaneously and independently over the entire storage capacity.
·        The second method of realizing an associative memory is the programmed organization (modeling) of the memory.
o   It consists of the establishment of associative connections between the information contained in the memory by means of ordered arrangement of the information in the form of sequential chains or groups (lists) connected by linkage addresses whose codes are stored in the same memory cells.
o   This procedure is the more suitable for practical realization in dealing with large volumes of information because it provides for the use of conventional accumulators with address reference.

References
http://www.myreaders.info/04_Associative_Memory.pdf


Written by
LAI WAI KUEN
B031210027