EXAM'.pdf

What is a Computer? ● Computers are machines that perform calculations: ○ Machines can be ■ Mechanical ■ Electronic ■ A combination of both mechanical and electronic ○ Programmable, in general ■ Automatically carry out a sequence of operations under control of a stored program ○ High to low programm...

What is a Computer? ● Computers are machines that perform calculations: ○ Machines can be ■ Mechanical ■ Electronic ■ A combination of both mechanical and electronic ○ Programmable, in general ■ Automatically carry out a sequence of operations under control of a stored program ○ High to low programmability (discuss in detailed later) ○ Not limited to desktop / personal computers! ● Computers are ubiquitous! ● Computers means calculating 1 Computing Process - The User’s Point of View The Input-Process-Output Model (IPO model) Data Storage Input Computing Process Output 21 Computing Process - The User’s Point of View Basic process has three steps: ● Read input data ● Process data ● Write output data Computing process ● Computer program that is being sequentially executed by a computer Data storage ● Store data ● Retrieve data 3 Examples of Computing Process A census of Hong Kong collected a lot of data about its citizens. The process converts the raw census data into more informative statistics such as mean family size and income. An online bookstore receives a purchase order from a customer. A process handles the purchase order by storing the current order and uses previous orders to make recommendation of other books for the customer. 4 Programming versus Coding Programming ● Process of creating a program that follows certain standards and performing a certain task Include ● ● ● ● ● Coding ● Subset of programming ● Translating human readable language (pseudo code) to machine readable language Planning Designing Testing Develoyment Maintenance 5 Programmability ● Degree of how a system can be programmed ● Low programmability ○ Some flexibility in adjusting the computing process ○ Vacuum robots, vehicle navigation systems ● High programmability ○ Re-purposed to serve a larger range of processes ○ Modern desktop computers, smartphones and tablets 6 From Low to High Programmability ● ● ● ● A toaster with a time knob A washing machine with programs for various types of clothing A DVD recorder supporting various recording modes A programmable calculator supporting programmed sequences of calculation steps ● An Excel spreadsheet supporting functions and macros ● A modern general purpose computer system We aim high 7 Programmable enabled processes data The process is driven by a program data The process is composed of instructions 8 Be a useful computing process MUST include input and output for interacting with the outside world Example of input: Example of input: 9 Major components of a programmable computer ● Arithmetic and Logic Unit (ALU) ○ For instruction execution ● Memory system ○ For data and program storage ● Input device ○ For data input (including program) into the programmable computer ● Output device ○ For data output from the programmable computer 10 Arithmetic and Logic Unit (ALU) ● Functional unit for instruction execution ○ ALU accepts data and instructions ○ ALU produces data output which is a result of instruction execution ● Fundamental building block of computing circuits (e.g. CPU, GPU) 11 Arithmetic and Logic Unit (ALU) Instruction (Addition, subtraction, etc.) Input data Input status Input data Output status Clock Output data 12 Arithmetic and Logic Unit (ALU) ● Most ALU has two data input ports ○ Input data to be operated on, called operands ● ALU operation is controlled by the instruction port ○ The instruction operated on the data presented at the input ports ○ The code presented at instruction port mapped to a particular instruction ● ALU operation timing is controlled by the clock port ○ A clock signal is provided to control when operations take place 13 Memory ● Functions of memory ○ Retrieve data (Read) ○ Store data (Write) ○ Overwrite a previously stored data (Overwrite) 14 Memory 15 Memory ● ● ● ● Duplex data channel Read/write line Clock line Data operations involve a data unit ○ The size of data unit varies: bit, byte ● Address to identify each data unit in memory ○ Numbered 0 onwards ○ Number of addresses determine the size of memory system ○ Address specifies which data unit for the current operation 16 Lecture 4. Basic Programmable Computer Design From ALU to CPU 17 First design of programmable computer 18 Connection between Memory and ALU A data bus connects all the registers Data from ACC to MDR to memory Data from memory to MDR to ACC MAR connected to ACC Address of memory operations controlled by ALU operations MAR connected to IR Address of memory operations determined by instructions 19 Instructions for interacting with memory Recall the five instructions ● Instructions for arithmetic operation in the ALU ○ ○ ○ Addition Subtraction Negation ● Instructions for memory operations ○ ○ Allowing data loaded from the memory (Load) Allowing results to be stored back to the memory (Store) 20 Instructions for interacting with memory The load and store instructions have an operand ● Operand = parameter ● The operand specifies the memory address for the load/store ● The operand takes up the last 16 bits of the representation to save space Instruction 32-bit binary representation (Special Name: Operation code (Opcode) ) Addition 0000 0000 0000 0001 0000 0000 0000 0000 Subtraction 0000 0000 0000 0010 0000 0000 0000 0000 Negation 0000 0000 0000 0011 0000 0000 0000 0000 Load 0000 0000 0000 0100 <16-bit memory address operand> Store 0000 0000 0000 0101 <16-bit memory address operand> 21 Executing a load instruction 1. Opcode + Operand stored in IR 2.Controller confirms the opcode as load instruction 3. Controller signals ● IR to send operand to MAR ● R/W line to Read mode 4.Memory system carries out the operation of reading a data from the address 5. The data is sent to MDR 6.Controller signals MDR to move the data to the ACC 22 Von Neumann Architecture ● Specify the storage of program and data in the Memory System ● Flexible to re-programme ○ ○ ○ ○ Readily accessible by electronic signals Stored indefinitely in memory Programs modify themselves in operation ■ Programs code is simply data in memory cells Stored programs allow the likes of compilers and interpreters possible ■ Purpose of these programs is to write programs 23 Von Neumann Architecture ● Program code is stored in memory ● Systems bus supports data movement from memory to IR ● Controller moves an instruction to IR by ○ ○ ○ Controller sends the address (containing the next instruction) to MAR Memory system retrieves the data of the address. The data is sent to the MDR Controller moves the instruction from MDR to IR 24 Lecture 5. Case Study: Little Man’s Computer Part 1 1 Major features of the LMC ● Three-digit decimal representation ● The registers hold 3-digit positive decimal ● The ALU supports addition and subtraction ○ ○ Overflows are not reported Carry is discarded ● ALU sends two types of status to ACC ○ ○ Zero Positive ● Memory system has 100 addresses, from 00 to 99 ○ Each address stores a 3-digit positive decimal LMC - analogy of a programmable computer LMC Programmable computer Calculator ALU Little man Controller Mailboxes Memory Instruction location counter Program counter In-basket Input controller with buffer Out-basket Output controller More about the features of LMC ● Little man is hidden inside a room ○ ○ User can communicate with the little man by placing a 3-digit data in the in-basket It is up to little man to read at a particular time ■ He may leave a 3-digit data in the out-basket ● 100 mailboxes with address from 00 to 99 ● Calculator perform simple arithmetic and stores data temporarily ○ Display is 3-digit data ● Location counter is a hand counter for ○ Keeping track of work with 2-digit number (from 00 to 99) ● External instruction could be applied to reset the counter Mnemonics Mnemonics Code Remarks LDA 5XX Load from mailbox to calculator STO 3XX Store in mailbox from calculator ADD 1XX Add from mailbox to calculator SUB 2XX Subtract from calculator the mailbox value INP 901 Input OUT 902 Output HLT 000 Coffee break of halt BRA 6XX Branch unconditionally BRZ 7XX Branch if zero BRP 8XX Branch if positive or zero DAT A location for data storage Benefits of Von Neumann Architecture ● Simpler computer design ○ Single memory system for data and program instructions ● Self-modifying instruction ○ ○ ○ ○ Allow programmer to write instructions that modify instructions during execution Programmer can create other instructions during execution Reduce program size Improve programmability Hazards of Von Neumann Architecture ● No indicator to signify whether it is an instruction or data ● Only programmer has knowledge and can take care the LMC ● A fetched instruction is assumed to be valid ○ ○ If invalid (e.g. 903), cause a system exception A data (e.g. 512) coincides with a valid instruction ■ The LMC cannot tell one from another ● Constants in LMC programs can also be instructions ○ It can be used as the stem of a self-modifying instruction Lecture 5. Case Study: Little Man’s Computer Part 2 1 2 Register transfer language Register transfer language (Example 1) ● Fetch of an instruction ● Put the instruction into the IR PC -> MAR Send instruction address to MAR M[MAR] -> MDR Read the current instruction MDR -> IR Copy the instruction to the IR PC + 1 -> PC Point to the next instruction Register transfer language (Example 2) ● Execute an instruction of ADD A, ACC ● Add data of memory address A to ACC ● Store the result of addition in ACC PC -> MAR Send instruction address to MAR M[MAR] -> MDR Read the current instruction MDR -> IR Copy the instruction to the IR PC + 1 -> PC Point to the next instruction IR[address field] -> MAR Send the operand address A to MAR M[MAR] -> MDR Read the operand from memory MDR + ACC -> ACC Perform the addition and put it the ACC Register transfer language (Example 3) ● Write down the RTL for an instruction ADD R0, 4. The instruction adds the content of Memory Address 4 to R0. PC -> MAR Send instruction address to MAR M[MAR] -> MDR Read the current instruction MDR -> IR Copy the instruction to the IR PC + 1 -> PC Point to the next instruction IR[address field] -> MAR Send the operand address A to MAR M[4] -> MDR Read the operand from memory #4 MDR + R0 -> R0 Perform the addition and put it the R0 Register transfer language (Exercise) Given the LMC program 00 INP // 901 Input the data 01 STO 10 // 310 Store to location 10 02 INP // 901 Input the data 03 STO 11 // 311 Store to location 11 04 ADD 10 // 110 Add with location 10 05 OUT // 902 Output 06 BRA 00 // 600 Branch to 00 07 HLT // 000 End of Program 10 DAT 000 // Data 11 DAT 000 // Data Assume PC is 03. What are the steps in executing the instruction STO 11 using RTL? Register transfer language (Exercise 1) Assume PC is 03. What are the steps in executing the instruction STO 11 using RTL? PC -> MAR M[MAR] -> MDR MDR -> IR IR[Address] -> MAR A -> MDR MDR -> M[MAR] PC + 1 -> PC Register transfer language (Exercise 2) Refer to the LMC program Exercise What are the steps in executing the instruction BRA 00 using RTL? PC -> MAR M[MAR] -> MDR MDR -> IR IR[Address] -> PC Register transfer language (Exercise 3) Refer to the LMC program Exercise The LMC is executing the instruction BRA 00 at address 06. Write down the content of MAR, MDR, IR, and PC after the execution. MAR = 06 MDR = 600 IR = 600 PC = 00 3 Performance analysis of LMC Number of execution cycles Mnemonics Execution cycles Memory operation LDA 7 2 STO 7 2 ADD 7 2 SUB 7 2 INP 5 1 OUT 5 1 HLT 3 1 BRA 4 1 BRZ 4 1 BRP 4 1 ● Each data movement between registers takes one cycle ● Each memory system operation takes one cycle ● Each input and output operation takes one cycle LMC Performance Analysis ● Number of execution cycles of each LMC instruction ○ Calculate speed of LMC program execution ● Running time of a program ○ ○ Total number of instructions executed Composition of the instructions ● If the instructions take fewer cycles to execute, program execution can be faster Execution speed of LMC program Question: You have written an LMC program. In one execution of the program, you counted the number of instruction executed: there are 300 LDA or STO instructions, 120 ADD or SUB instructions, 20 BRA, BRZ, or BRP instructions, and 5 INP or OUT instructions. If the CPU clock rate is 100 MHz, calculate the time taken to execute the program. Answer: The total number of cycles is calculated from the summation of number of cycles for each instruction. # of Cycles = 300x7 cycles + 120x7 cycles + 20x4 cycles + 5x5 cycles = 3045 cycles The clock rate is 100 MHz, which means 100 M cycles per second The time taken to execute the program is 3045/100M = 0.00003045 seconds Execution speed of LMC program Question: Both Anders and Betsy have written an LMC program to find out the square of a number. Anders’ program execution has involved 40 instruction, including 15 ADD/SUB, 20 LDA/STO, 3 BRA/BRZ/BRP, and 2 INP/OUT. Betsy’s program execution has involved 42 instruction, including 14 ADD/SUB, 18 LDA/STO, 8 BRA/BRZ/BRP, and 2 INP/OUT. Answer: The total number of cycles is calculated from the summation of number of cycles for each instruction. # of Cycles of Anders’ program = 15x7 cycles + 20x7 cycles + 3x4 cycles + 2x5 cycles = 267 cycles # of Cycles of Betsy’s program = 14x7 cycles + 18x7 cycles + 8x4 cycles + 2x5 cycles = 266 cycles The clock rate is 100 MHz, which means 100 M cycles per second. Betsy’s program ran faster, even if the total number of instructions is more. Lecture 6. Technologies of Computer Components Part 1 46 Characteristics of Buses ● System bus is only one of the many buses in a computer system ● A bus consists of many lines, for the following purposes: ○ ○ ○ ○ Data ■ Data line is binary encoded. It carries one bit of data at a time Addressing ■ Address line is binary encoded. It carries one bit of data at at time Control ■ Control line is binary encoded. Data on control line is a signal ■ E.g. Controller sends a signal to PC Power ■ Computer system supplies stable voltage 47 Parallel bus ● More than 1 data lines or data channels sending data at the same time ● Transfer more than 1 bit at a time ● Problem of clock skew ○ Signals of different data lines arrive at different time ● Problem of crosstalk ○ Signals between data lines may interfere with each other 48 Serial bus ● Single data channel (sending 1 bit at a time) ● Most common form of buses ○ Short and long(er) distance ● Can outperform parallel bus ○ Running at a significantly fast clock rate ● Cheaper in price 49 Lecture 6. Technologies of Computer Components Part 2 50 Classes of memory system Volatility CPU accessibility Mutability Access restriction Volatile Non-volatile Volatile memory requires electric power to keep the stored value Non-volatile memory can retain its value without electric power Primary Secondary Directly accessible by the CPU CPU access through indirect means of data transfer Mutable Immutable R/W allowed Read only Random access Sequential access Any of the addressable unit can be accessed Memory must be retrieved in an order 51 Memory hierarchy of a desktop computer Processor Registers Cache memory Primary memory Main memory I/O cache & buffer Secondary memory Hard disk CDROM USB disk Tape-drive 52 Static RAM (SRAM) ● Uses digital electronic circuitry to store data (such as flip-flops) ● Very fast but more expensive, larger in size (each flip-flop is made up of 6-8 transistors) ● Used for small amount of high speed memory ○ Registers in the CPU Flip-flop 53 Dynamic RAM ● Store data as charge on a capacitor ○ ○ Arranged in an array of cells Provide the storage of multiple bits of data ● The capacitors tend to lose their charge quickly ○ ○ Periodic refresh cycle (in milliseconds) to prevent data lost A memory subsystem to support this refreshing ● DRAM is less expensive, requiring less power, smaller in size 54 Static RAM & Dynamic RAM Static RAM Dynamic RAM Does not need refreshing Need constant refreshing SRAM uses normal high speed CMOS technology. (flip-flops) DRAM uses capacitors for storing bits in the form of charge. Faster, but more expensive Slower than SRAM because of refreshing time Used as registers in CPU or Cache memory Used in main memory Technologies include: Synchronous SRAM, Asynchronous SRAM Technologies include: EDO RAM, VRAM, DDR-RAM Synchronous DRAM 55 Synchronous and Asynchronous I/O 56 I/O Operation Handling ● Synchronous I/O characteristics: ○ ○ ○ Wait instruction idles the CPU until the next interrupt Wait loop (contention for memory access) No simultaneous I/O processing ● Asynchronous I/O characteristics: ○ ○ ○ System call ■ Request sent to the OS to allow user to wait for I/O completion Device-status table contains entry for each I/O device ■ Indicating its type, address, and state. Operating system indexes into I/O device table to determine device status and to modify table entry to include interrupt 57 Lecture 6. Technologies of Computer Components Part 3 1 Operations of Magnetic Disks ● Seek ○ ○ Starting the mechanics if disk is resting Moving the read-write arm to place the read-write head over the desired track ● Rotation ○ Wait until the rotation to place the head over the desired sector 59 Read/Write Performance ● Overhead of read/write data operation ○ ○ ○ ○ Seek time: The time taken for the moving arm to move over the desired track Rotational Delay: The time taken for the desired sector to be rotated under the read/write head Controller time: The time taken for the I/O controller to process an I/O request Queuing time or queuing delay: A hard disk can serve one request each time. Other requests must wait and queue for the service for the hard disk. 60 Example Fujitsu Hard Disk MHT2160BT Model MHV2160BT Storage capacity (formatted) 160.0 GB Bytes/sector 512 Seek time Track to track 1.5 ms typ. Average Read: 12 ms typ. Write: 14 ms typ. Maximum 22 ms typ. Rotational speed 4,200 RPM Data transfer to/from host 150 MB/s Interface SATA Buffer size 8 MB 61 Example ● Calculate the time taken in a read/write operation. ○ ○ ○ Assume that the size of one sector is 512 bytes Assume that the controller time is 0.1ms ■ the disk is free of queue and it is available The time taken to transfer 512 bytes can be worked out as the following: ■ Average disk access is the sum of average seek time, average rotational latency, transfer time, and controller time. 62 Example ● ● ● ● ● Average seek time = 12 ms Average rotational latency = 50% * (1 / 4200 RPM * 60) = 7.1 ms Transfer time for a sector = 512 bytes / 150 MB/s = 0.003 ms Controller overhead = 0.1 ms Overall average disk access = 12ms + 7.1ms + 0.003ms + 0.1ms = 19.2ms 63 Lecture 8. Instruction Set Architecture and Addressing Modes Part 1 6 4 Addressing modes in E-LMC instructions E-LMC supports the following addressing modes ● ● ● ● ● ● Immediate addressing mode Direct addressing mode Indirect addressing mode Register addressing mode Register index relative addressing mode Register indirect addressing mode ○ Two operands: one is a base address and another operand is register RN containing an offset value. The sum specifies the address at which the data is found 65 Addressing modes in mnemonic form Addressing mode Syntax Examples Immediate #Data LDA #20 Direct Address LDA 20 Indirect (Address) LDA (20) Register RN LDA R4 Register index relative RN + Address LDA R4 + 20 Register indirect (RN) LDA (R4) 66 Lecture 8. Instruction Set Architecture and Addressing Modes Part 2 6 7