basics of computers

Topics : 

Topics Instruction Execution CPU organization Parallel Instruction Execution Microprocessor chips & Buses, Example of a typical Microprocessor Memory : Main memory, Secondary memory, Types & Organization Input/ Output : Common types of I/O devices, Controllers.

Instruction Execution : 

Instruction Execution The CPU executes each instruction in a series of small steps. The steps are as follows: Fetch the next instruction from memory into the instruction register. Change the program counter to point the following instruction. Determine the type of instruction just fetched. If the instruction uses a word in memory, determine where it is. Fetch the word, if needed, into a CPU register. Execute the instruction. Go to step 1 to begin executing the following instruction.

Slide 3: 

This sequence of steps is frequently referred to as the fetch-decode-execute cycle. It is the central to the operation of all computers. A program that fetches, examines, and executes the instructions of another program is called interpreter.

CPU Organization : 

CPU Organization

Slide 5: 

The fig. shows the internal organization of part of a typical Von Neumann CPU. This part is called the data path and consist of the registers, the ALU, and several buses connecting the pieces. The registers feed into two ALU input registers, labeled A and B. These register hold the ALU input while the ALU is computing. The ALU itself performs addition , subtraction and other simple operations on its inputs. And get a result in the O/P register. This O/P register can be stored back into a register, or can be written into memory.

Slide 6: 

The most instructions can be divided into one of two categories: register - memory register – register Register – memory instructions allow memory word to be fetched into registers, where they can be used as ALU inputs in sub sequent instructions. - Another types of register – memory instructions allows registers to be stored back into memory. A typical register – register instructions fetches two operands from the registers, brings them to the ALU input register, performs some operations on them( e.g. addition, subtraction) and stores the result back in one of the register.

Slide 7: 

The process of running two operands through the ALU and storing the result is called the data path cycle and is the heart of the most CPU. The faster data path cycle is, the faster the machine runs.

Multiprocessor : 

Multiprocessor Multi processor is a system with more than one CPU sharing a common memory like a group of people in a room sharing a common whiteboard. Since each CPU can read or write any part of memory, they must co-ordinate to avoid getting in each other’s way. Various implementation schemes are possible. The simplest one is to have a single bus with multiple CPUs and one memory all plugged into it. A diagram of such single bus-based multiprocessors is shown in the following figure.

With a large numbers of fast processors constantly trying to access memory over the same bus, conflict will result.To eliminate this conflict and improve performance, one design was developed. : 

With a large numbers of fast processors constantly trying to access memory over the same bus, conflict will result.To eliminate this conflict and improve performance, one design was developed.

Slide 10: 

In this design, each processor has some local memory of its own, not accessible to others. This memory can be used for program code and those data items that need not be shared. Access to this private memory does not use the main bus, greatly reducing bus traffic.

Multicomputers : 

Multicomputers Multiprocessors with a small number of processors (≤ 64) are relatively easy to build, large once are surprisingly difficult to construct. The difficulty is in connecting all the processors to the memory. To solve this problem, many designers have build system consisting of large number of interconnected computers, each having its own private memory, but no common memory. The CPUs in a multicomputer communicate by sending each other messages, something like e-mail, but much faster. For large systems, having every computer connected to every other computer is impractical. So topology are used to connect them. As a result messages from one computer to another often must pass through one or more intermediate computers or switches to get from source to destination.

Instruction-Level Parallelism : 

Instruction-Level Parallelism Parallelism comes in two general forms: Instruction-level parallelism Processor-level parallelism In the Instruction-level parallelism, parallelism is exploited within individual instructions to get more instruction/sec out of the machine. In the processor-level parallelism, multiple CPUs work together on the same problem.

Instruction-Level Parallelism : 

Instruction-Level Parallelism There are two types of Instruction-level parallelism: Pipelining Superscalar Architectures

1. Pipelining : 

1. Pipelining It has been known for the years that the actual fetching of instructions from memory is a major blockage in instruction execution speed. To solve these problem, these instructions were stored in a set of register called prefetch buffer. This way when instruction was needed, it could be usually taken from the prefetch buffer rather than waiting for a memory read to complete. Prefetching divides instruction execution up into two part: fetching and actual execution. The concept of a pipeline carries this strategy much further. Instead of dividing instruction execution into only two parts, it is often divided into many parts, each handled by a dedicated work.

Slide 15: 

Fig: A five stage pipeline

Slide 16: 

Stage 1 fetches the instruction from memory and place it in a buffer until it is needed. Stage 2 decodes the instruction, determining its type and what operands it needs. Stage 3 locates and fetches the operands, either from register or from memory. Stage 4 actually does the work of carrying out instruction, typically by running the operands through the data path . Finally stage 5 writes the result back to the proper register.

Slide 17: 

Fig: The stage of each stage as a function of time. Nine cycles are illustrated.

The state of each stage as a function of time. : 

The state of each stage as a function of time. Fig shows how the pipeline operates as a function of time. During clock cycle 1, stage S1 is working on instruction 1, fetching it from memory. During cycle 2, stage S2 decodes instruction 1, while stage S1 fetches instruction 2. During cycle 3, stage S3 fetches the operands for instruction 1, stage S2 decodes instruction 2, and stage S1 fetches the third instruction. During cycle 4, stage S4 executes instruction 1, S3 fetches the operands for instruction 2, S2 writes the result of instruction1 back, while the other stages work on the following instructions. `

Superscalar Architectures : 

Superscalar Architectures If one pipeline is good, then surely two pipelines are better. Be fig. shows dual pipeline CPU.

Slide 20: 

Here a single instruction fetch unit fetches pairs of instructions together and puts each one into its own pipeline, complete with its own ALU for parallel operation. To be able to run in parallel, the two instructions must not conflict over resource usage. (Here register), and neither must depend on the result of the other. As with a single pipeline, either the compiler must guarantee this situation to hold or conflicts are detected and eliminated during execution using extra hardware. i.e the hardware does not check and gives incorrect results if the instructions are not compatible

Slide 21: 

The basic idea is to have just a single pipeline but give it multiple functional units, as shown in below figure. Fig: A Superscalar processor with five functional units.

Slide 22: 

For example, the Pentium II has a structure similar to this figure. The term superscalar architecture was coined for this approach in 1987. Its roots, however. Go back more than 30 years to the CDC 6600 computer. The 6600 fetched an instruction every 100 nsec and passed it off to one of 10 functional units for parallel execution while the CPU went off to get the next instruction.

Slide 23: 

The basic idea of a superscalar processor is that the S3 stage can issue instruction considerably faster than the S4 stage is able to execute them. If the S3 stage issued an instruction every 10 nsec and all the functional units could do their work in 10 nsec. In reality, most of functional units in stage 4 takes appreciably longer than one clock cycle to execute, certainly the ones that access memory or do floating-point arithmetic. As can be seen from the figure, it is possible to have multiple ALUs in stage S4.

Processor-Level Parallelism : 

Processor-Level Parallelism Instruction – level parallelism helps a little, but pipelining and superscalar operation rarely win more than a factor of five or ten. To get gains of 50, 100, or more, the only way is to design computers with multiple CPUs. There are two types of Processor-level parallelism: Array Processor Vector Processor

Array Processor : 

Array Processor An array processor consists of a large number of identical processors that perform the same sequence of instructions on different sets of data. The world’s first array processor was the University of Illinois ILLIAC IV computers, illustrated in below figure.

Slide 26: 

The original plan was to build a machine consisting of four quadrant having an 8 X 8 square grid of processor/memory elements. A single control unit per quadrant broadcast instructions, which were carried out in lockstep by all the processors, each one using its own data from its own memory. Due to a cost overrun by a factor of four, only one quadrant was ever built, but it did achieve a performance of 50 megaflops (million floating-point operations per second).

Vector Processor : 

Vector Processor A vector processor is like an array processor. It is very efficient at executing a sequence of operations on pairs of data elements. But unlike the array processor, all of the addition operation are performed in a single , heavily-pipelined adder.

Slide 28: 

Both array processor and vector processors works on arrays of data. Both executes single instruction that, e.g. add the elements together pair wise for two vectors. But while the array processor does it by having as many adders as elements in the vector. The vector processor has the concept of a vector register, which consists of a set of conventional register that can be loaded from memory in a single instruction, which actually loads them from memory serially. Then a vector addition instruction performs the pairwise addition of elements of two such vectors by feeding them to a pipelined adder from the two vector register.

Slide 29: 

The result from the adder is another vector, which can either be stored into a vector register, or used directly as an operand for another vector operations. Disadvantage of array processor: Array processor can perform some data operations more efficiently than vector computers. But they required much more hardware .

Types of common INPUT/OUTPUT devices and controllers : 

Types of common INPUT/OUTPUT devices and controllers A computer system has three major components : the CPU, the memories (primary and secondary), and the I/O (Input/output) devices. Input devices allow us to enter raw data into a computer. The computer processes the data and then produces outputs that we can understand using an output device. Input devices can be manual or automatic. The processing is mainly handled by the Central Processing Unit (CPU).

Input Devices : 

Input Devices Keyboard : It is a primary device. A computer keyboard is a peripheral modeled on the typewriter keyboard. Keyboards are designed for the input of text and characters, and also to control the operation of the computer. Physically, computer keyboards are an arrangement of rectangular or near-rectangular buttons, or "keys". The number of keys on a keyboard generally varies from the standard 101 keys and 104-key Windows keyboards, to as many as 130 keys, with many programmable keys. There are also compact variants that have fewer than 90 keys.

Slide 33: 

A "dome-switch" keyboard is commonly used variation of the membrane-type keyboard.

Slide 34: 

Mouse: Mouse is small device to point to a particular place on the screen and select in order to perform one or more operations. It is used to select menu command, size windows, and start programs etc. Most of the mouse has basic three buttons called left, right and dragger. Left click is used to select a file. Double click is used to open any file. Right click is used to set commands. Drag and drops allows you to select and move data from one location to another.

Slide 36: 

Joystick : Joystick is a vertical stick which moves the graphics cursor in the direction the stick is moved. It typically has a button on the top that is used to select the option pointed by the cursor. It is used in video games and controlling robots.

Slide 37: 

Scanner : Scanner is an input device used to direct data entry from the source document into the computer system. It converts the documents image into the digital form so that it can be fed into the computer. Capturing the information like this reduce the possibility of errors typically occurred during large data entry.

Slide 38: 

Light Pen: It is a pen shape device used to select any object to the screen. Its functionally is quite same as a mouse but use a light pen to move the pointer and select any object on the screen by pointing to the object .

Slide 39: 

Touch screen : It allows the user to operate/make selection by simply touching the display screen either by a finger, or with a stylus, rather than typing on a keyboard or pointing with a mouse. Common example is bank ATM. The touch screen interface - whereby users navigate a computer system by touching icons or links on the screen itself - is the most simple, and easiest to learn of all PC input devices and is fast becoming the interface of choice for a wide variety of applications,

Output devices : 

Output devices Monitor: The most common output device is the monitor or VDU. Modern monitors, where the case isn’t more than a few centimetres deep, are usually Liquid Crystal Displays (LCD) or Thin Film Transistors (TFT) monitors. Older monitors, where the case is likely to be around 30 cm deep, are Cathode Ray Tube (CRT) monitors. A monitor is the screen on which words, numbers, and graphics can be seem.  The monitor is the most common output device.

Slide 41: 

CRT LCD

Slide 42: 

Printers Laser printers are quite expensive to buy and run but produce a high quality output and are quiet and fast. Ink-jet printers offer black and white or colour printing with reduced levels of quality and speed. Colour ink jet printers are cheaper to buy than colour laser printers. Dot matrix printers are not so common today. They are comparatively noisy and low quality but are cheap to run and are used when carbon copies or duplicates need to be made, such as for wage slips. Also, they are useful in dirty environments such as a garage because they are much sturdier than the other two types of printer.

Slide 43: 

Plotters A plotter can be used to produce high quality, accurate, A3 size or bigger drawings. They are usually used for Computer Aided Design (CAD) and Computer Aided Manufacture (CAM) applications, such as printing out plans for houses or car parts.

THE MAIN MEMORY : 

THE MAIN MEMORY Earlier we saw that the CPU contains the necessary circuitry for data processing and controlling the other components of a computer system. We saw that the CPU does contain several register for storing data and instructions, but these are very small areas, which can hold only few bytes at a time, and are just sufficient to hold only one or two instructions and the corresponding data. If the instruction and data of a program being executed by the CPU, were to reside in secondary storage like a disk, and fetched and loaded one by one into the registers of the CPU as the program execution proceeded, this would lead the CPU being idle most of the time.

Slide 45: 

Because There is a large speed mismatch between the rate at which CPU can process data and the rate at which data can be transferred from the disk to the CPU registers. For example CPU can process data at a rate of about 5 nanosecond/byte, and a disk reader can read data at a speed of around 5 microsecond/byte. This would lead to very slow overall performance, even if the computer system used a very fast CPU. To overcome this problem, there is a need to have a reasonably large storage space, which can hold the instruction and data of the programs, on which CPU is currently working.

Slide 46: 

The time to fetch and load data from this storage space into the CPU registers must also be very small as compared to that for disk storage, to reduce the speed mismatch problem with the CPU speed. Every computer has such type of a storage space, known as primary storage, main memory or simply memory.

Primary or Main Memory : 

Primary or Main Memory The primary memory is the part of a computer where programs and data are stored. It is a temporary storage area, which is built into the computer hardware, and in which instruction and data of a program live, mainly when the program being executed by the CPU. Physically, this memory consist of some chips either on the motherboard, or on a small circuit board attached to the motherboard of a computer system. This built in memory allows the CPU to store and retrieve data very quickly. The rate of fetching data from this memory is typically of the order of 50 nanosecond/byte. Hence the rate of data fetching from the main memory is about 100 times faster than that from a high speed secondary storage like disk.

Storage Evaluation Criteria : 

Storage Evaluation Criteria Any storage unit of a compute system is characterized and evaluated based on the following properties. Storage capacity : It is the amount of data, which can be stored in the storage unit. A large capacity is desire. As compared to secondary storage unit , primary storage unit have less storage capacity. Access time : This is the time required to locate and retrieve stored data from the storage unit, in response to a program instruction. A fast access time is preferred. As compared to secondary storage unit, primary storage units have faster access time.

Slide 49: 

Cost per bit of storage : This refers to the cost of a storage unit for a given storage capacity. Obviously, the lower cost is desirable. As compared to secondary storage units, primary storage units have higher cost per bit of storage. Volatile : If the storage unit can retain the data stored in it, even if when the power or turned off or interrupted, it is called non-volatile storage. On the other hand, if the data stored are lost, when the power is turned off or interrupted is called volatile storage. Obviously a non-volatile storage is desirable. In almost all computer systems, the primary storage units are volatile and secondary storage units are non-volatile.

Slide 50: 

Random access : If the time taken to access a piece of data from the storage unit is independent of the location of the data in the storage unit, it is called a random access storage or random access memory(RAM). Each separate location of a RAM is as easy to access any other location, and takes the same amount time. In almost all computer systems, the primary storage units have random access property, and the secondary storage units have either random access or sequential access property.

Main Memory Organization : 

Main Memory Organization A primary storage or main memory of a computer system is made up of several small storage areas, called locations, or cells. Each of these locations can store a fixed number of bits, called word length of that particular memory. Hence a given memory is divided into N words, where N generally is some power of 2. Each word or location has a built-in and unique number assigned to it. This number is called the address of the location, and is used to identify the location. Each location can hold either a data item or an instruction, and its address remains the same , regardless of its contents.

Slide 52: 

0 1 2 N - 2 N - 1 A D D R E S S O F A M E M O R Y The word of a memory Each word contains the same number of bits = word length Fig: Organization of a main memory having N words

Slide 53: 

The addresses normally start at 0 (Zero) , and the highest address equals the number of the words, which can be stored in memory minus 1. For example, if a memory has 1024 locations, the address ranges between 0 and 1023. Hence , at address 0 (zero) we find a first word, at address 1 a second word, and so on, up to the final word at the largest address.

Why More Bits? : 

Why More Bits? You might have heard about 8-bit computers, 16-bit computers, 32-bit computers, etc. This refers to the word length of the memory of a particular computer, in terms of total number of bits per memory word. The word length is an important architectural factor. Smallest machine have word length of 8, 16, or 32 bits, whereas large machines have word lengths of 64 bits or more. The question that arises is, what is the advantage of having more number of bit per word, instead of having more words of smaller length?

Slide 55: 

For an answer to the previous question, imagine a highway with eight lanes, and a heavy flow of traffic. If it is expanded to sixteen lanes, the flow of traffic speeds up considerably. “8 bits” refers to the number of “lanes” on a microchip. More bits, means a more rapid flow of electronic signals. In other words, a faster computer. Hence what an 8-bit computer takes one minute to d0, a 32-bit computer may do in few seconds.

Fixed and Variable Word-length Memory : 

Fixed and Variable Word-length Memory Fixed-word-length Memory The main memory of some computers is designed to store a fixed number of characters (equals to its word-length in bytes) in each numbered address location. Such computers are said to be word-addressable, and they employ a fixed-word-length memory approach. In these computers, storage space is always allocated in multiples of word-length. Therefore, if a word-addressable computer has a fixed word-length of 4 bytes (4 character), this computer will require one word to store the word “ CAT”.

Slide 57: 

Variable-Word-length Memory In many computers, the main memory is designed in a manner that each numbered address can only store a single character ( A, B, 1 ,2 etc). Computer designed in this manner, are said to be character-addressable, and they employ a variable-word-length memory approach. Hence, in these machines, only 3 bytes will be required to store the word “ CAT”.

Slide 58: 

merits and demerits of Both the fixed and the variable word-length memory systems The fixed-word-length approach is normally used in scientific computers, for gaining speed if calculation. On the other hand, the variable-word-length approach is used in small business computers, for optimizing the use of storage space. For example, let us consider a fix-word-length memory machine with a word size of eight characters. If most of the data words to be stored are less than five characters, more than half of the storage space will remain unused. This will not happen in variable-word-length machines because a character can be placed in every storage cell.

Slide 59: 

Word-addressable computers possess faster calculating capability, because they can add two data in a single operation. For example, if the fixed-word-length is eight characters, two eight digit numbers can be added in a single operation. On the other hand, with a character addressable machine, only one digit in each number is added during a single operation, and eight steps would ne added to add two eight digit numbers. Day-by-day memory becoming cheaper and larger. Most modern computers employ fixed-word-length memory organization.

Main Memory Capacity : 

Main Memory Capacity The main memory capacity of a large computer systems is normally more than that of small systems. This capacity is defined in terms of the number of bytes a computer system can store. Memory capacity of a computer system is normally stated in terms of kilobytes (KB), which is equal to 1024 bytes of storage. Megabytes (MB), which is equal to 1,048,576 bytes of storage. Gigabytes (GB), which is equal to 1,073,741,824 bytes of storage.

Slide 61: 

Notice that 1 KB is about 103 bytes 1 MB is about 106 bytes 1 GB is about 109 bytes

Slide 62: 

Main memories are of two types : RAM (Random access memory) and ROM (read only memory) There is various types of RAMs and ROMs.

RAM (Random Access Memory) : 

RAM (Random Access Memory) The read and write memory (R/W memory) of a computer is called RAM. User can write information into RAM and read information from it. User can enter his /her program and data into RAM. It possesses random access property. In a random access memory and memory location can be accessed in a random manner without going through any other memory location. The access time is same for reading any memory location.

Slide 64: 

RAM is a volatile(Unstable) memory. The information written into it is kept in it as long as the power supply is on. When the power supply goes off (or interrupted) its stored information is lost. The programmer has to reload his/her program and data into RAM when the power supply is resumed. There are two types of RAM. Static RAM Dynamic RAM

Slide 65: 

Static RAM keep stored information only as long as the power supply is on. But dynamic RAM loses its stored information in a very short time even though the power supply is on. Therefore, dynamic RAMs have to be refreshed periodically, generally after every 2 milliseconds. The dynamic RAMs are cheaper and have high density and moderate speed. They consume less power. They are used where large capacity of memory is needed. Static RAMs are costlier and consume more power. They do not need refreshing circuitry. They have higher speed than dynamic RAMs.

ROM (Read Only Memory) : 

ROM (Read Only Memory) ROM stands for “ Read Only Memory”. It is a nonvolatile(Stable) memory, and the information stored in it is not lost even if the power supply goes off. Read-only memory is most commonly used to store system-level programs that we want to have available to the PC at all times. It used for permanent storage of information. It also possesses random access property. ROMs are much cheaper compared to RAMs. The stored information can only be read from ROMs at the time of operation. Information can not be written into a ROM by the user or programmers.

Slide 67: 

ROMs store monitor, assembler, debugging package, function tables such as sine, cosine etc. PROM ( Programmable ROM) PROM is a programmable ROM. Its contents are decided by the user. The user can store permanent programs, data in a PROM. An example of PROM is 74S287.

EPROM (Erasable PROM) : 

EPROM (Erasable PROM) Once information is stored in a ROM chip or a PROM chip, it can not be altered (changed). There is another type of memory chip, called EPROM (Erasable Programmable Read-Only Memory), which overcomes this problem. As the name implies, it is possible to erase information stored in an EPROM chip, and the chip can be reprogrammed to store new information.

Register : 

Register A CPU contains a number of registers to store data temporarily during the execution of a program. The number of register differ from micro processor to micro processor. Some processor contains less register, some more. Registers are of the following types. Accumulator General purpose register

Slide 70: 

Accumulator : The accumulator is a register which holds one of the operands prior to the execution of an instruction, and receive the result of most of the arithmetic and logical operation. So the accumulator is the most frequently used register. Some CPU have a single accumulator and some have several. General purpose register: These registers store data and intermediate results during the execution of a program. They are accessible to users through instruction when users are working in assembly language.

Slide 71: 

Different types of registers Memory Address Register (MAR) : It holds the address of active memory location. Memory Buffer Register (MBR) : It hold the contents of the memory read from, or written in memory. Program Counter Register (PC) : It holds the address of the next instruction to be executed. Accumulator Register (A) : It holds the data to be operated. Instruction Register (IR) : It holds the currents instruction, which is being executed. Input/output Register (I/O) : It is used to communicate with the input/output devices.

Cache Memory : 

Cache Memory We saw that the use of main memory helps in minimizing the disk-processor speed mismatch to a large extent because the rate of data fetching by the CPU from the main memory is about 100 times faster than that from a high-speed secondary memory. However, even with the use of main memory, memory-processor speed mismatch becomes a blockage in the speed with which the CPU can process instruction because there is a 1 to 10 speed mismatch between the processor and the memory. That is, the rate at which data can be fetched from memory is about 10 times slower that the rate at which CPU can process data.

Slide 73: 

Hence , in many situations, the performance of processors gets limited due to the slow speed of main memory. One way to overcome this problem is to insert a small high speed buffer between the processor and the main memory. Such buffer is generally known as cache (read as “cash”). Cache is commonly used to minimize the memory processor speed –mismatch. Cache memory is extremely fast and small memory whose access time is closer to the processing speed of the CPU. Cache act as a high-speed buffer between the CPU and the main memory and is used to temporarily store very active data and instruction during processing.

Slide 74: 

CPU Cache Memory Main Memory Fast Slow Cache Hierarchy Fig. shows the cache is placed between CPU and main memory, The system first copies data needed by the CPU from the main memory into the cache , and then from the cache into a register in the CPU. Storage of result is on the opposite direction. First system copies the results into cache memory. The data is the immediately copies into the main memory. If some application wants some data again now first it check into the cache memory , if data is not into the cache memory after then it check into the main memory.

Cache operation – overview : 

Cache operation – overview CPU requests contents of memory location Check cache for this data If present, get from cache (fast) If not present, read required block from main memory to cache Then deliver from cache to CPU Cache includes tags to identify which block of main memory is in each cache slot

Slide 76: 

We have only applied caches to data transfer. There is, however, no reason why you could not use caches for other purposes—to fetch instructions. It is possible to implement multiple levels of cache memory. Some of these levels will be a part of the microprocessor (they are said to be on-chip), whereas other levels may be external to the chip. To distinguish between these caches, a level notation is used. The higher the level, the farther away the cache is from the CPU. The level 1 (L1) cache is on-chip, whereas the level 2 (L2) cache is external to the microprocessor.

Slide 77: 

CPU Level L1 Cache Main Memory Fastest Slow Level L2 Cache Fast Slow Micro-Processor Fig : Multiple level of cache memory In above FIGURE , the size of the cache increases from left to right, but the speed decreases. In other words, the capacity increases, but it takes longer to move the data in and out.

Caching in a Memory Hierarchy : 

Caching in a Memory Hierarchy 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Larger, slower, cheaper storage device at level k+1 is partitioned into blocks. Level k+1: 4 4 4 10 10 10

General Caching Concepts : 

Request 14 Request 12 General Caching Concepts Program needs object d, which is stored in some block b. Cache hit Program finds b in the cache at level k. E.g., block 14. Cache miss b is not at level k, so level k cache must fetch it from level k+1. E.g., block 12. If level k cache is full, then some current block must be replaced (evicted). Which one is the “victim”? Placement policy: where can the new block go? E.g., b mod 4 Replacement policy: which block should be evicted? E.g., LRU 9 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Level k: Level k+1: 14 14 12 14 4* 4* 12 12 0 1 2 3 Request 12 4* 4* 12

Secondary Storage Devices : 

Secondary Storage Devices The primary storage of a computer system has the following limitations: Limited Capacity: It is often necessary to store many millions, sometimes billions, and even trillions, of bytes of data in a computer. Unfortunately , the storage capacity of the primary storage of today’s computers is not sufficient to store the large volume of data, which needs to be handled by most data processing centers. Volatile: The primary storage is volatile, and the data stored in it is lost, when the electric power is turned off or interrupted. However, computer system need to store data on a permanent basis for several days, several months, or even several years.

Slide 81: 

As a result, additional memory, called auxiliary memory or secondary storage, is used with most computer system. This section of the computer’s memory is non-volatile, and has lower cost per bit stored, but has lower operating speed than the primary storage. This section of the memory is used to store large volume of data on a permanent basis, which can be partially transferred to the primary storage, as and when required for processing.

Memory Hierarchies : 

Memory Hierarchies The traditional solution to storing a great deal of data is a memory hierarchy as show in the next figure. registers on-chip L1 cache (SRAM) main memory (DRAM) local secondary storage (local disks) Larger, slower, and cheaper (per byte) storage devices remote secondary storage (distributed file systems, Web servers) off-chip L2 cache (SRAM) CPU registers hold words retrieved from L1 cache. L0: L1: L2: L3: L4: L5: Smaller, faster, and costlier (per byte) storage devices

Slide 83: 

At the top are the CPU registers, which can be accesses at full CPU speed. Next comes the cache memory, which is currently on the order of 32 KB to a few megabytes. Main memory is the next, with sizes currently ranging from 16 MB for entry-level systems to tens of gigabytes at the high end. After that come magnetic disks, the current work for permanent storage. After that local disks hold files retrieved from disks on remote network servers.

Slide 84: 

As shown in the previous figure, as we move down the hierarchy, three key parameters increase. First, the access time(Speed) gets bigger. CPU register can be accesses in a few nanoseconds. Cache memories take a small multiple of CPU registers. Main memory accesses are typically a few tens of nanoseconds. Now comes a big gap, secondary storage , access time can be measured in seconds. Second, the storage capacity increase as we go downwards. CPU registers are good for 128 bytes, caches for a few megabytes, main memories for tens to thousands of megabytes, secondary storage units for a few gigabytes to tens of gigabytes. Third , the number of bits (cost) increase as we go down to the hierarchy.

Secondary Storage Devices : 

Secondary Storage Devices Magnetic Disk Optical Disk

Magnetic Disk : 

Magnetic Disk Magnetic disk is the most popular storage medium for direct-access secondary storage. Due to their random access capability , magnetic disks are the most popular on-line secondary storage device. A magnetic disk is a thin, circular plate/platter made of metal or plastic, which is usually coated on both sides with a magnetizable recording material, such as iron oxide. Data are recorded on the disk in the form of tiny invisible magnetized and non-magnetized spots on the coated surfaces of the disk. A standard binary code, usually 8-bit EBCDIC, is used for recording data. A magnetic disk can be erased and reused. Old data on a disk are automatically erased as new data are recorded in the same area.

Basic Principles of Operation : 

Basic Principles of Operation Storage Organization: For data recording, the surface of a disk is divided into a number of invisible concentric circles, called tracks. As shown in figure, the tracks are numbered consecutively from outermost to innermost, starting from zero. Each track is further subdivided into sectors. The disk surface is also divided into invisible pie-shaped segments. Hence, if there are eight such pie-shaped segments, each track will be divided into eight parts, and each of these eight portions of a track is called a sector. A sector typically contains 512 bytes. A sector is the smallest unit with which any disk can work.

Slide 89: 

Each sector of a disk is assigned a unique number. Before a disk drive can access a piece of data stored on a disk, it must specify the record’s disk address. Often, multiple disks are stacked and used together to create large capacity disk-storage systems. In this case, a set of magnetic disks is fixed to a central shaft, one below the other, to form a disk pack. The disk pack is sealed and mounted on a disk drive, which consists of a motor to rotate the disk pack about its axis. Normally, the upper surface of the top disk and the lower surface of the bottom disk, are not used in a disk pack, because these surfaces may be easily scratched.

Slide 91: 

Storage Capacity : The storage capacity of a disk is a multiple of the number of recording surfaces, number of tracks per surfaces, number of sectors per track, and number of bytes per sector. Storage capacity of a disk system = (Number of recording surfaces) X (Number of tracks per surface) X (Number of sectors per track) X (Number of bytes per sector)

Slide 92: 

For example, let us assume that a disk pack has 10 disk plates, each having 2655 tracks. Also assume that there are 125 sectors per track, and each sector can store 512 bytes. Since the disk pack has 10 disk plates, it will have 18 recording surfaces excluding the upper surface of the topmost disk, and the lower surface of the bottommost disk. Hence, the capacity of this disk pack will be = (18 X 2655 X 125 X 512) = 3,05,85,60,000 bytes = 3 X 10 9 bytes (approximately) = 3 GB (3 Giga Bytes) As one character can be stored per byte, this disk pack can store 3 billion characters of information.

Slide 93: 

Accessing of Data : Data are recorded on the tracks of a spinning(rotating) disk surface and read from the surface by one or more read/write heads. There are two types of disk systems – moving-head and fixed-head. The moving-head-system consists of one read/write head for each disk surface mounted on an access arm which can be moved in and out. So in this system, each read/write head moves horizontally across the surface of the disk so it is able to access each track individually.

Slide 95: 

Information stored on the tracks which in the fixed-head system, the access arm is non-movable. A large number of read/write heads are distributed over the disk surfaces, one head for each track. As a result, no head movement is required and therefore information is accessed more quickly. The disk pack on some disk storage devices is permanently fixed in position, while on others, the pack can be removed and replaced by another one. So the storage capacity of a removable disk pack system is virtually unlimited because the storage space can be increased without the heavy expense of buying another complete device.

Slide 96: 

Access Time : Disk access time is the interval between the time a computer makes a request for transfer of data from a disk system to the primary storage, and the time this operation is completed. Disk access time depends on the following three parameters. Seek Time : As soon as a read/write command is received by the disk unit, the read/write heads are first position on to the specified track number by moving the access arms in the proper direction. The time required to position the read/write head over the desired track is called the seek time. Latency : Once the heads are positioned on the desired track, the head on the specified surface is activated. Since the disk is continuously rotating, this head should wait for the desired data to come under it. This rotating waiting time i.e. the time required to spin the desired sector under the head is called the latency. Transfer Rate : Transfer rate refers to the rate at which data are read from or written to the disk.

Types of Magnetic Disks : 

Types of Magnetic Disks All magnetic disks are round platters. They come in different sizes, different types of packaging, and can be made of rigid metal or flexible plastic. Based on these differences, there are many different types of magnetic disks available today. All of them may be broadly classified into two types : Floppy Disks Hard Disks Floppy disks are individually packaged in protective envelops or plastic cases, whereas hard disks may be packaged individually.

Floppy Disks : 

Floppy Disks A floppy disks is a round, flat piece of flexible plastic, coated with magnetic oxide. It is encased in a square plastic cover. The plastic cover gives handling protection on the disk surface. It has a special liner, which provides a clean action to remove dust particles, which are harmful for disk surface and read/write head. Floppy disks are so called because they are made of flexible plastic plates, which can bent, not hard plates. They are also known as floppies or diskettes. They were introduced by IBM in 1972.

Slide 99: 

Floppy-disk drive : A floppy disk drive is a device, which is used to read/write data from/to floppy disks. The drive has a spindle, which rotates the disk, and read/write heads, which can move in and out to position the read/write heads on any track of the disk surface. A floppy disk can easily loaded into or unloaded from a floppy –disk drive. The disks are loaded into the disk drive along with a jacket cover, and data are read/write through an aperture in the jacket. Read/write heads of a floppy disks drive make direct contact with the disk surface during the process of reading or writing. Data transfer rate is of the order of 10 to 30 Kilobytes/second. Floppy-disks are very cheap as compared to other secondary storage devices.

Slide 100: 

Two size exist : 5.25 inch and 3.5 inch. Each of these has a Low-Density (LD) and a High-Density (HD) version. The 3.5-inch floppy disk is the most commonly used floppy disk today. They have replaced the older version 5.35-inch ones. The 3.5-inch diskettes come in rigid jacket for protection. The 3.5-inch diskettes store more data and better protection. All 3.5-inch floppy disks are of double-sided type, and record data on both the disk surfaces. However, they come in three different capacities – double density, high density, and very high density. The total disk storage capacity of double-density 3.5-inch disk is 720 KB (approximately), for high-density 3.5-inch disk has 1.4 MB (approximately) and for very high density 3.5-inch disk have 2.88 MB (Approximately).

Slide 101: 

Sliding Metal piece cover User’s Label for identification Write Protect Plastic Cover

Hard Disks : 

Hard Disks Hard disks are the primary on-line secondary storage device for most compute system today. Hard disks are made of rigid metal. The hard disk platters come in many sizes, ranging from 1 to 14-inch diameter. Types of hard disks : Depending on how they are packaged, hard disks are normally categorized into the following three types : Zip/Bernoulli Disks Disk Packs Winchester Disks

Slide 103: 

Zip/Bernoulli Disks In this type, a single hard disk platter is encased in a plastic cartridge. A commonly used zip disk is of 3.5-inch size, having storage capacity of about 100 MB. Its disk drive is called a zip drive. A zip drive may be of portable or fixed type. The fixed type is a part of the computer system, permanently connected to it. The portable type can be carried to a computer system, connected to it for the duration of use, and then can be disconnected. The zip disk can be easily inserted into or removed from a zip drive.

Slide 104: 

Disk Packs A disk pack consist of multiple (two or more) hard disk platters mounted on a single central shaft. Hence, all the disks of a disk pack revolve together at the same speed. The disk drive of a disk pack has a separate read/write head for each disk surface, excluding the upper surface of the topmost disk and the lower surface of the bottom disk. These two surfaces are not used for data recording in a disk pack. When disk pack is not in used, they are stored in plastic cases.

Slide 106: 

Winchester Disks A Winchester disk also consists of multiple hard disk platters mounted on a single central shaft. The main difference between a Winchester disk and a disk pack is that Winchester disk are of fixed type. That is, the hard disk platters and the disk drive are sealed together in a contamination-free container, and can not be separated from each other. And hence, both upper surface and lower surface can be used for data recording. As opposed to disk packs, which have virtually unlimited capacity, Winchester disks have limited capacity. The storage capacity of today’s Winchester disks is usually of the order of a few tens of megabytes to a few gigabytes (10 9 bytes)

Optical Disk : 

Optical Disk As compared to magnetic disk, optical disk is a relatively new secondary storage medium. Optical disk can store extremely large amount of data in a limited space. An optical disk storage system consists of a rotating disk, which is coated with a thin metal. Laser beam technology is used for recording/reading of data on the disk. Due to the use of laser beam technology, optical disks are also known as laser disks or optical laser disks.

Optical Disk continue…Basic Principle of Operation : 

Optical Disk continue…Basic Principle of Operation Storage Organization : Unlike magnetic disks, which have several concentric tracks, an optical disk has one long track, which starts at the outer edge and spirals inward to the center.

Slide 109: 

This spiral track is ideal for recording large blocks of sequential data, such as music. It makes for slower random access time than the concentric track used by the magnetic disks. Like a track on a magnetic disk, the track of an optical disk is split up into sectors, but each sector has the same length, except that whether it is located near the disk’s center or away from the center. This type of data organization allows data to be packed at maximum density over the entire disk.

Slide 110: 

Storage Capacity : The cost-per-bit of storage is very low for optical disks. They come in various sizes, ranging from 12- inch to 4.7 – inch diameter. The most popular one is of 5.25 inch diameter, whose capacity is around 650 Megabytes. This storage capacity is equivalent to about 2,50,000 pages of printed text. As optical disks have a single track, their storage capacity is a multiple of the number of sectors, and number of bytes per sectors. That is, Storage Capacity of an Optical Disk = Number of sectors X Number of bytes per sector.

Slide 111: 

The 5.25-inch optical disks typically have 3,30,000 sectors, each of 2352 bytes. That gives a total capacity of 3,30,000 x 2352 = 776 x 10 6 bytes = 776 Megabytes. Access Mechanism : Optical disks use laser beam technology for recording/reading of data on the disk surface. That is, the read/write head used in magnetic storage is replaced by two laser beam sources. One laser beam is used to write to the recording surface by etching(design) microscopic pits(lower points) on the disk surface. And the another laser beam is used to read data from the light-sensitive recording surface.

Slide 112: 

The laser beam is turned on and off at a varying rate, due to which tiny pits (visible only through a powerful microscope) are burnt into the metal coating of the disk along its tracks. To read the stored data, the less-powerful laser beam is focused on the disk surface. As shown in below figure, this beam is strongly reflected by the coated surface known as land and weakly reflected by the burnt surface known as pits, producing patterns of on and off reflections, which are converted into electronic signals of binary 1s and 0s by a sensor.

Slide 114: 

Assess Time : Optical Disks will be slower (access time will be more) as compared to that from magnetic disks. Optical Disk Drive : An optical disk has to be mounted on an optical disk drive, before it can be used for reading or writing of information. An optical disk drive contains the tray on which the disk is kept, the read/write laser beams assembly, and the motor to rotate the disk. A typical disk drive is shown in the below figure.

Types of Optical Disks : 

Types of Optical Disks All optical disks are round platters. They come in different sizes and capacities. The two most popular types of optical disks in use today are CD-ROM and WORM disks.

CD-ROM : 

CD-ROM CD-ROM stands for Computer Disk-Read-Only Memory. It is a sin-off music CD technology, and works much like the music CDs used in music systems. If you have a soundboard and speakers connected to your computers, you can play music CDs with your computers. The CD-ROM disk is a shiny, silver color metal disk of 5.25 inch diameter. It has a storage capacity of about 650 Megabytes.

WORM Disk : 

WORM Disk WORM stands for write-once, read-many. WORM disks allow the user to create their own CD-ROM disks by using CD-recordable drive, which can be attached to a computer as a regular device. WORM disks look like standard CD-ROM disks. WORM purchased blank and encoded using a CD-R drive. The information recorded on a WORM disk by a CD-R drive can be read by any ordinary CD-ROM drive.