Computer Organization Study Guide PDF

11/6/24, 7:56 PM Untitled notebook - NotebookLM Here is a study guide based on the provided source document, "CO-88-123.pdf": UNIT III Micro-Programmed Control Control Memory A random access memory (RAM) cons...

11/6/24, 7:56 PM Untitled notebook - NotebookLM Here is a study guide based on the provided source document, "CO-88-123.pdf": UNIT III Micro-Programmed Control Control Memory A random access memory (RAM) consisting of addressable storage registers Primarily used in mini and mainframe computers as temporary storage for data Access to control memory data is faster than main memory, speeding up CPU operation Addresses divided into task mode and executive (interrupt) mode Addressing words is done via address select logic for each of the up to five register groups Registers can be accessed directly by the CPU logic during programmed CPU operations Data routing circuits interconnect the registers Registers include: Accumulators Indexes Monitor clock status indicating registers Interrupt data registers Microprogramming Basics Control signals generated by hardware are hardwired In a bus-oriented system, control signals are groups of bits The control unit initiates a series of sequential steps of micro operations Control variables are represented by a control word made of 1s and 0s A microprogrammed control unit stores binary control variables in memory A microprogram is a sequence of microinstructions Read-only memory can be used for control memory Dynamic microprogramming uses writable control memory and allows microprograms to be loaded Computers with microprogrammed control units have main memory and control memory Microinstructions specify internal control signals for register micro operations Micro operations generated by microinstructions: Fetch instructions from main memory Evaluate the effective address Execute the operation Return control to the fetch phase Control Memory Address Register (CAR) specifies the address of the microinstruction Control Data Register (CDR) holds the microinstruction read from memory The microinstruction's control word specifies micro operations for the data processor The next microinstruction's location may not be sequential Bits in the current microinstruction can control the next microinstruction's address External input conditions can also influence the next address The next address generator circuit (sequencer) computes the next address while micro operations are being executed Sequencer functions: Incrementing the CAR by one Loading an address from control memory into the CAR Transferring an external address Loading an initial address to start control operations A clock is applied to the CAR The ROM uses the address value as input and outputs the control word Advantages of microprogrammed control: No hardware or wiring changes needed once the configuration is established Different control sequences can be established by specifying different sets of microinstructions for control memory Addressing Sequencing A routine is a collection of microinstructions that implement a machine instruction The MCU determines the first microinstruction's address based on the machine instruction's opcode Upon power-up, the CAR holds the address of the first microinstruction The MCU can execute microinstructions sequentially and branch to other microinstructions https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 1/7 11/6/24, 7:56 PM Untitled notebook - NotebookLM Sequential retrieval is done by incrementing the CAR Branching requires determining the desired CW address and loading it into the CAR Components: Control Address Register (CAR) Control memory (CM): Holds CWs Opcode: Opcode field from the machine instruction Mapping logic: Maps opcode into microinstruction address Branch logic: Determines how the next CAR value is determined Multiplexors: Implement the choice of branch logic for the next CAR value Incrementer: Generates CAR + 1 as a possible next CAR value SBR: Holds the return address for subroutine-call branch operations Conditional branches are needed in microprograms to execute sequences only when certain conditions exist Subroutine branches at the microprogram level help shorten routines and save memory Mapping opcodes to microinstruction addresses is simplified by determining a "required" length for machine instruction routines, rounding it up to the next power of 2 (k), and locating the first instruction of each routine at multiples of N (the required length) [13, 14] The multiplexor bank, made of N 4x1 muxes (N = number of bits in a CW's address), is used to choose between the possible ways of generating CAR values Branch logic determines which "next address" value is passed to the CAR Computer Arithmetic Addition and SubtractionEight different conditions can occur when adding or subtracting signed numbers, depending on the signs and the operation performed Addition/Subtraction Algorithm: If signs of A and B are identical, add magnitudes and attach the sign of A to the result If signs are different: Compare magnitudes and subtract the smaller number from the larger number If A > B, the result has the same sign as A If A < B, the result has the complement of the sign of A If A = B, subtract B from A and make the result positive Hardware Implementation: Two registers (A and B) store magnitudes Two flip-flops (As and Bs) store signs Register A and As act as an accumulator for results Subtraction is performed by adding A to the 2's complement of B Output carry is transferred to flip-flop E Overflow is stored in flip-flop A ⊕ F When m = 0, E's output is transferred to the adder with an input carry of '0', resulting in A + B (addition) When m = 1, B's content is complemented and transferred to the adder with an input carry of '1', resulting in A + B' + 1 = A - B (subtraction) Hardware Algorithm: As and Bs are compared by an exclusive-OR gate Output = 0: Signs are identical Output = 1: Signs are different Addition: Identical signs dictate adding magnitudes Subtraction: Different signs dictate adding magnitudes Magnitudes are added with micro operation EA Two magnitudes are subtracted if signs are different for addition or identical for subtraction Magnitudes are subtracted with micro operation EA = B, and the number in A is the correct result E = 0 indicates A < B, so the 2's complement of A is taken MultiplicationHardware Implementation and Algorithm: Multiplication of fixed-point binary numbers in signed magnitude representation is done by successive shift and ADD operations Steps: Examine successive bits of the multiplier (least significant bit first) If the multiplier bit is 1, copy the multiplicand If the multiplier bit is 0, copy 0s Shift numbers copied down in successive lines one position to the left https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 2/7 11/6/24, 7:56 PM Untitled notebook - NotebookLM Add all the numbers to get the product In digital computers: An adder sums two binary numbers at a time The partial product is accumulated in a register The partial product is shifted right instead of shifting the multiplicand left Hardware: Multiplier stored in Q register Multiplicand stored in B register A register stores the partial product Sequence counter (SC) set to the number of bits in the multiplier A and B are summed to form the partial product Both are shifted right using "Shr EAQ" Flip-flops As, Bs, and Qs store the signs of A, B, and Q, respectively A binary '0' is inserted into flip-flop E during the right shift Booth Algorithm: Used for multiplying binary integers in signed 2's complement form Based on the principle that: Strings of 0s in the multiplier only require shifting Strings of 1s from bit weight 2k to 2m can be treated as 2k+1 - 2m (e.g., +14 = 001110 = 23 + 22 + 21 = 16 - 2 = 14) Product obtained by shifting the binary multiplication left and subtracting the multiplier shifted left once Rules: Subtract multiplicand from the partial product if the first least significant bit is 1 in a string of 1s in the multiplier Add multiplicand to the partial product if the first least significant bit is 0 (and there was a previous 1) in a string of 0s in the multiplier Partial product remains unchanged if the multiplier bit is identical to the previous multiplier bit Applicable to both positive and negative numbers in signed 2's complement form Array Multiplier: Uses a combinational circuit to calculate the product in one micro operation, unlike the sequential process of the multiplication algorithm Example: Multiplicand bits: b1 and b0 Multiplier bits: a1 and a0 Partial product: c3c2c1c0 Multiplication of a0 and a1 produces a binary 1 if both bits are 1, otherwise a binary 0 (equivalent to an AND operation) Implemented using AND gates Division AlgorithmDivision of fixed-point signed numbers is done by successive compare, shift, and subtraction operations In digital computers, the dividend or partial remainder is shifted left instead of shifting the divisor right Subtraction is achieved by adding A to the 2's complement of B The end carry provides information about the relative magnitudes of the numbers Hardware Implementation: Divisor stored in register B Double-length dividend stored in registers A and Q Dividend is shifted left, and the divisor is subtracted by adding its 2's complement If E = 1 (A ≥ B), a quotient bit 1 is inserted into Qn, and the partial remainder is shifted left If E = 0 (A < B), Qn remains 0, B is added to restore the partial remainder in A, the partial remainder is shifted left, and the process continues E, A, and Q are shifted left with 0 inserted into Qn, and the previous value of E is lost Restoring Method: The partial remainder is restored by adding the divisor to the negative result Other Methods: Comparison Method: A and B are compared before subtraction; B is subtracted from A only if A ≥ B Non-Restoring Method: If A - B is negative, the negative difference is shifted left and then B is added, resulting in 2(A - B) + B = 2A - B Divide Overflow (Dividend Overflow): Occurs when: The quotient has more bits than the register's capacity https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 3/7 11/6/24, 7:56 PM Untitled notebook - NotebookLM The value of the most significant half of the dividend is greater than or equal to the divisor The dividend is divided by 0 Can cause errors or halt the operation (divide stop) Arithmetic Operations on Floating-Point NumbersRules for the single-precision IEEE standard format Add/Subtract Rule: Unpack sign, exponent, and fraction fields; handle special operands (zero, infinity, NaN) Right-shift the significand of the number with the smaller exponent by a certain number of bits Set the result exponent (er) to the maximum of e1 and e2 Add the significands if the instruction is FA and s1 = s2 or if it's FS and s1 ≠ s2; otherwise, subtract them Count the leading zeros (z); a carry can make z = -1; shift the result significand left by z bits or right by 1 bit if z = -1 Round the significand and adjust z if rounding overflow (carry-out of the leftmost digit) occurs Adjust the exponent by er = er - z, check for overflow/underflow, and pack the result sign, biased exponent, and fraction bits into the result word Multiplication and division are simpler than addition and subtraction as they don't require significand alignment BCD Adder: A 4-bit binary adder that adds two 4-bit BCD words, producing a BCD-format 4-bit output and a carry if the sum exceeds 9 [36, 37] UNIT IV The Memory SystemBasic ConceptsAddressing Scheme determines the maximum main memory size Word-Addressable: Each memory word has a distinct address Byte-Addressable: Each byte has a distinct address CPU-Main Memory Connection: Data transfer happens via MAR (Memory Address Register) and MDR (Memory Data Register) Memory Cycle: 'n' bits of data are transferred between MM and CPU Processor Bus: Address Bus: k address lines Data Bus: n data lines Control Bus: Read, Write, MFC (Memory Function Completed), byte specifiers, etc. Read Operation: CPU loads address into MAR, sets READ to 1, MM loads data into MDR, sets MFC to 1 Write Operation: CPU loads MAR and MDR, sets WRITE to 1, MM loads data into the appropriate location, sets MFC to 1 [41, 42] Memory Access Time: Time between the initiation and completion of a memory operation Memory Cycle Time: Minimum time between two successive memory operations Random Access Memory (RAM): Any location can be accessed for read/write in a fixed time, independent of the address Cache Memory: Small, fast memory between CPU and main memory to hold active program segments and data Locality of Reference helps CPU find data in cache (cache hit) most of the time Cache misses require accessing main memory Improves system performance cost-effectively Memory Interleaving: Divides memory into modules, placing successive words in different modules Allows parallel access to modules for consecutive addresses, increasing the average fetch rate Virtual Memory: CPU-generated address is the virtual/logical address Memory Management Unit (MMU) maps logical addresses to physical addresses Mapping can change during execution Logical address space can be larger than physical memory Active portions of the logical address space are mapped to physical memory, the rest to bulk storage https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 4/7 11/6/24, 7:56 PM Untitled notebook - NotebookLM If data is not in MM, MMU transfers a block from bulk storage to MM, replacing an inactive block Creates the illusion of a large memory with a smaller, cheaper MM if transfers are infrequent Internal Organization of Semiconductor Memory Chips: Organized as an array of cells, each storing one bit A row of cells forms a memory word Word Line: Connects cells in a row and is driven by the address decoder Bit Lines: Connect cells in a column to a sense/write circuit Sense/Write circuits are connected to the data input/output lines Read Operation: Sense/Write circuits read data from selected cells and transmit it to output lines Write Operation: Sense/Write circuits receive and store input data in selected cells Example: 16 x 8 organization (16 words of 8 bits each) with 14 external connections [50, 51] Example: 1k x 1 organization with 10-bit address divided into row and column addresses Types: Bipolar: Faster access time Higher power consumption Lower bit density MOS: Slower access time Lower power consumption Higher bit density A Typical Memory Cell: Two-transistor inverters forming a flip-flop Connected to one word line and two bit lines Bit lines at ~1.6V, word line at ~2.5V, isolating the cell due to reverse-biased diodes Read Operation: Word line voltage reduced to ~0.3V, forward-biasing a diode and allowing current flow from b or b' based on the cell state Write Operation: With word line at 0.3V, applying positive voltage (~3V) to b' or b forces the cell to 1 or 0 state, respectively MOS Memory Cell: Commonly used in main memory Flip-flop structure with transistors T1 and T2 Active pull-up to VCC via T3 and T4 T5 and T6 act as switches controlled by the word line Read Operation: Selected cell's T5 or T6 is closed, and current flow through b or b' is sensed to set the output bit line Write Operation: Positive voltage applied to the appropriate bit line of the selected cell to store 0 or 1 [56, 57] Static Memories: Maintain information as long as power is supplied Dynamic Memories: Require power and periodic refresh to maintain data High bit density and low power consumption Dynamic Memory: Information stored as charge on a capacitor Data read correctly only if read before the charge drops below a threshold Read Operation: Bit line in high-impedance state, transistor turned on, sense circuit checks charge on the capacitor and refreshes it [59, 60] Typical Organization: Square array of cells with row and column addresses from the 16-bit address Row and column addresses multiplexed on 8 pins Access: Row address applied first, loaded into row address latch by RAS (Row Address Strobe), then column address applied and loaded by CAS (Column Address Strobe) Read: Output of the selected circuit transferred to data output DO Write: Data on DI line overwrites the selected cell Applying a row address reads and refreshes all cells in that row Refresh Circuit: Ensures data maintenance by periodically addressing each row Pseudostatic: Dynamic memory chips with built-in refresh, appearing as static memories Block Transfers: After loading the row address, successive locations accessed by loading only column addresses, useful for regular access patterns https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 5/7 11/6/24, 7:56 PM Untitled notebook - NotebookLM RAID (Redundant Array of Independent Disks): Stores data redundantly on multiple hard disks Improves performance by allowing overlapped I/O operations Increases fault tolerance by increasing MTBF (Mean Time Between Failures) Appears as a single logical hard disk to the OS Uses disk mirroring or disk striping (partitioning storage space into units) Stripe Size: Small stripes for single-user systems with large records (e.g., 512 bytes) for fast access Large stripes for multi-user systems to hold typical/maximum record size for overlapped disk I/O Standard RAID Levels: RAID 0: Striping, no redundancy, best performance, no fault tolerance RAID 1: Disk mirroring, data duplication, improved read performance, write performance same as single disk RAID 2: Striping with dedicated disks for ECC (Error Checking and Correcting) information, no advantage over RAID 3, obsolete RAID 3: Striping with one drive for parity information, uses ECC for error detection, data recovery via XOR calculation, best for single-user systems with long records [67, 68] RAID 4: Large stripes, overlapped I/O for reads, all writes update the parity drive, no advantage over RAID 5 RAID 5: Block-level striping with distributed parity, functions even with one drive failure, allows read/write operations to span multiple drives, good performance, requires at least three disks (five recommended), poor choice for write-intensive systems due to parity write overhead, slow rebuild time after failure [69, 70] RAID 6: Similar to RAID 5 but with a second parity scheme, tolerates two simultaneous disk failures, higher cost per GB, slower write performance than RAID 5 [70, 71] Direct Memory Access (DMA): Transfers data from RAM to another part of the computer without CPU processing Saves processing time for data that doesn't require CPU processing or can be processed by other devices Devices using DMA are assigned to DMA channels Examples: Sound cards accessing RAM data for processing DMA-enabled video cards accessing system memory for graphics processing Ultra DMA hard drives for faster data transfer Programmed Input/Output (PIO): Alternative to DMA, where all data transfer goes through the CPU Ultra DMA: Newer protocol for ATA/IDE interface, burst data transfer rate up to 33 Mbps DMA Transfer Types: Memory to Memory Transfer: Moves data from one memory address to another using DMA channels 0 and 1, data transferred via temporary register in the DMA controller [74, 75] Auto Initialize: After a block transfer, the current address and word count registers are automatically restored from base registers, enabling another DMA service without CPU intervention [76, 77] DMA Controller: Manages DMA data transfers Receives location, destination, and data amount from the microprocessor Transfers data while the microprocessor handles other tasks Doesn't arbitrate for bus control; the I/O device (DMA slave) does Takes control of the bus when granted by the central arbitration control point DMA vs. Interrupts vs. Polling: DMA: Works in the background without CPU intervention, speeds up data transfer and CPU speed, suitable for large files Interrupts: Require CPU time, request CPU usage via interrupts, used for immediate tasks [79, 80] Polling: CPU actively monitors the process, adjustable to device needs, suitable for devices that don't need quick response [80, 81] https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 6/7 11/6/24, 7:56 PM Untitled notebook - NotebookLM UNIT V MultiprocessorsCharacteristics: Interconnection of two or more CPUs, memory, and I/O equipment MIMD (Multiple Instruction, Multiple Data) category Controlled by a single operating system coordinating processor activities via shared memory or inter-processor messages [82, 83] Advantages: Increased reliability due to processor redundancy Increased throughput due to parallel job execution Types: Tightly Coupled/Shared Memory Processors: Information shared through common memory, each processor may also have local memory Loosely Coupled/Distributed Memory Multiprocessors: Each processor has private memory, information shared via interconnection switching or message passing [84, 85] Key characteristic: Ability to share main memory and I/O devices through interconnection structures Inter-Processor Arbitration: Buses facilitate information transfer between components Memory Bus: Connects CPUs and memory I/O Bus: Connects I/O devices System Bus: Connects major components (CPUs, I/Os, memory) Processors request component access via the system bus Bus Contention: Resolved through arbitration by a bus controller [87, 88] Inter-Processor Communication and Synchronization: Shared Memory Systems: Messages written to a common memory area Synchronization needed to manage shared resources like I/O Critical Sections: Resources needing protection from simultaneous access Assumptions: Mutual Exclusion: Only one processor can be in a critical section at a time Termination: Critical section execution completes in a finite time Fair Scheduling: A process requesting entry to the critical section will eventually enter in a finite time Semaphore: Binary value indicating if a processor is in the critical section Cache Coherence: Each processor in a shared memory multiprocessor has its own private cache Multiple copies of the cache can lead to data inconsistency (cache coherence problem) Cache updates by one processor need to be communicated to others to maintain consistency Ensuring data consistency is crucial for system correctness Please let me know if you need clarification on any of these points. If you have more specific questions or areas you want to explore further, feel free to ask! https://notebooklm.google.com/notebook/2798616f-209c-4421-a2e7-3e15014294bc?_gl=1*14m0vwb*_ga*MTE2NTM4MjQyNy4xNzMwMjgyMDk… 7/7