Please enable JavaScript.

Coggle requires JavaScript to display documents.

COA - Coggle Diagram

- - - - The result of the operation may replace the previous
        binary information of a register or may be transferred to another register
      - Examples
        
        count
        
        clear
        
        load
        
        shift
      - The operations executed on data stored in registers are called microoperations
      - A microoperation is an elementary operation performed on the information stored in one or more registers
      - Categories
        
        Shift
        
        Logic
        
        Arithmetic
        
        ALU
        
        Register Transfer
    - - Bit Representation
        
        The numbering of bits in a 16-bit register can be marked on top of the box
        
        Bits 8 through 15 are assigned the symbol H (for high byte)
        
        The individual bits can be distinguished
        
        Bits 0 through 7 are assigned the symbol L (for low byte)
        
        The symbol PC (0–7) or PC (L) refers to the low-order byte and PC(8–15) or PC(H ) to the high-order byte
      - Computer registers are designated by capital letters (sometimes followed by numerals) to denote the function of the register
      - The most common way to represent a register is by a rectangular box with the name of the register inside
      - The individual flip-flops in an n-bit register are num-
        bered in sequence from 0 through n — 1, starting from 0 in the rightmost position and increasing the numbers toward the left
    - - Replacement Operator ←
        
        R2 ← R1
        
        denotes a transfer of the content of register R1 into register R2. It designates a replacement of the content of R 2 by the content of R1. By definition, the content of the source register R1 does not change after the transfer
        
        A statement that specifies a register transfer implies that circuits are available from the outputs of the source register to the inputs of the destination register and that the destination register has a parallel load capability
        
        BUS
        
        BUS ← C
        
        R1 ← BUS
      - Control Function
        
        The control condition is terminated with a colon
        
        transfer to occurs under predetermined control condition P
        
        P : R2 ← R1
        
        It symbolizes the requirement that the transfer operation be executed by the hardware only if P = 1
      - Comma
        
        Separates two microoperations
        
        T : R2 ← R1, R1 ← R2
    - - Memory Representation
        
        Examples
        
        Write
        
        Write: M [AR] ← R1
        
        Assume that the input data are in register R1 and the address is in AR
        
        Read
        
        The data are transferred to another register, called the data register, symbolized by DR
        
        Consider a memory unit that receives the address from a register, called the address register, symbolized by AR
        
        Read: DR ← M [AR]
        
        A memory word will be symbolized by the letter M
        
        This will be done by enclosing the address in square brackets following the letter M
        
        The particular memory word among the many available is selected by the memory address during the transfer
        
        It is necessary to specify the address of M when writing memory transfer operations
      - Operations
        
        Read
        
        The transfer of information from a memory word to the outside environment is called a read operation
        
        Write
        
        The transfer of new information to be stored into the memory is
        called a write operation
  - - - Three-State Bus Buffers
        
        The third state is a high-impedance state
        
        Control Input
        
        1
        
        Behave like a normal buffer
        
        0
        
        Because of this feature, a large number of three-state gate outputs can be connected with wires to form a common bus line without endangering loading effects
        
        Output is disabled with high impedance state
        
        A bus system can be constructed with three-state gates instead of multiplexers
        
        A three-state gate is a digital circuit that exhibits three states
        
        Two of the states are signals equivalent to logic 1 and 0 as in a conventional gate
        
        The high-impedance state behaves like an open circuit, which means that the output is disconnected and does not have a logic significance
        
        Most commonly used in the design of a bus system is the buffer gate
      - Multiplexers
        
        The transfer of information from a bus into one of many destination registers can be accomplished by connecting the bus lines to the inputs of all destination registers and activating the load control of the particular destination register selected
        
        A bus system will multiplex k registers of n bits each to pro-
        duce an n-line common bus. The number of multiplexers needed to construct the bus is equal to n, the number of bits in each register. The size of each multiplexer must be k x 1 since it multiplexes k data lines
  - - - Examples
        
        Write
        
        Write: M [AR] ← R1
        
        Assume that the input data are in register R1 and the address is in AR
        
        Read
        
        The data are transferred to another register, called the data register, symbolized by DR
        
        Consider a memory unit that receives the address from a register, called the address register, symbolized by AR
        
        Read: DR ← M [AR]
      - A memory word will be symbolized by the letter M
      - This will be done by enclosing the address in square brackets following the letter M
      - The particular memory word among the many available is selected by the memory address during the transfer
      - It is necessary to specify the address of M when writing memory transfer operations
    - - Read
        
        The transfer of information from a memory word to the outside environment is called a read operation
      - Write
        
        The transfer of new information to be stored into the memory is
        called a write operation
  - - - It facilitates the transfer of data between the processor and the main memory at the speed which matches to the speed of the processor
      - Cache Mapping
        
        Techniques
        
        K-way Set Associative Mapping
        
        Physical Address
        
        Tag
        
        Block Offset
        
        Line
        
        Need of Replacement Algorithm
        
        set associative mapping requires a replacement algorithm
        
        Set associative mapping is a combination of direct mapping and fully associative mapping
        
        It uses fully associative mapping within each set
        
        The set of the cache to which a
        particular block of the main
        memory can map is given by
        
        Cache set number = ( Main Memory Block Address ) Modulo (Number of sets in Cache)
        
        Cache lines are grouped into sets where each set contains k number of lines
        
        A particular block of main memory can map to only one particular set of the cache
        
        Within that set, the memory block can map any cache line that is freely available
        
        Implementation
        
        Caches operate in parallel
        
        Cache Index selects a “set” from the cache
        
        Tags in a set are compared in parallel
        
        Hit Time
        
        Example 1
        
        Time to decode line bits to select set is ignored
        
        Comparing input tag with tag of each block in set happens in parallel
        
        There is some logic which converts the valid bit for a block to a control signal for the MUX to select the corresponding input which takes 0 time
        
        The actual MUX happens and we read the correct data block
        
        This can be similar to DRAM access logic where each line generates a corresponding value on the select line
        
        Number of sets = Total Size of Cache / k
        
        Self
        
        We may have to assume all blocks are mapped to the same set between two accesses to the same block for the worst case scenario to avoid page fault
        
        We may have to assume each blocks is mapped to a different set between two accesses to the same block for the best case scenario to avoid page fault
        
        Number of unique pages in a sequence of accesses is the guaranteed minimum number of page faults
        
        Minimum miss ratio = Number of unique pages / Total number of accesses
        
        If number of unique pages between two access to the same page map to the same set and the unique number of the pages is less than the associativity of the set, then there will no new page faults apart from the first access page faults
        
        Fully Associative Mapping
        
        All the lines of cache are freely available.
        
        This makes fully associative mapping more flexible than direct mapping.
        
        any block of main memory can map to any line of the cache
        
        Physical Address
        
        Block Number/Tag
        
        Block Offset
        
        Need of Replacement Algorithm
        
        Replacement algorithm suggests the block to be replaced if all the cache lines are occupied
        
        Replacement algorithm like FCFS Algorithm, LRU Algorithm etc is employed
        
        A replacement algorithm is required
        
        Had all the cache lines been occupied, then one of the existing blocks will have to be replaced
        
        A block of main memory can map to any line of the cache that is freely available at that moment
        
        Direct Mapping
        
        Physical Address
        
        Block/Line Offset
        
        Short cut
        
        4 more items...
        
        Tag
        
        Cache stores the tag of the address loaded
        
        The address requested by CPU is compared by converting it into tag and cache line and looking for the tag in the corresponding cache line.
        
        Line
        
        Tag + Line = Block
        
        Need of Replacement
        Algorithm
        
        There is no need of any replacement algorithm
        
        Thus, the new incoming block will always replace the existing block (if any) in that particular line.
        
        This is because a main memory block can map only to a particular line of the cache
        
        The line number of cache to which a
        particular block can map is given by
        
        Cache line number = ( Main Memory Block Address ) Modulo (Number of lines in Cache)
        
        A particular block of main memory can map only to a particular line of the cache
        
        Implementation
        
        Implementation 1
        
        Comparator
        
        2 more items...
        
        Multiplexer
        
        4 more items...
        
        Implementation 2
        
        Tag Decoder
        
        1 more item...
        
        Comparator
        
        1 more item...
        
        Hit Latency
        
        Formula 1
        
        Hit latency = Multiplexer latency + Comparator latency
        
        Formula 2
        
        Hit latency = Comparator latency
        
        This formula either assumes decoder with 0 latency or mux with 0 latency
        
        Cache mapping defines how a block from the main memory is mapped to the cache memory in case of a cache miss.
        
        Cache Size Considerations
        
        A smaller cache block incurs a lower cache miss penalty.
        
        A smaller cache tag ensures a lower cache hit time.
        
        The larger the block size, better will be the spatial locality.
        
        In set associative cache, block size does not affect cache tag anyhow
        
        In fully associative cache, on decreasing block size, cache tag is increased and vice versa.
        
        In direct mapped cache, block size does not affect the cache tag anyhow
        
        The tag bits depend only on the total cache size
        
        On increasing block size, the word offset size increases and the block index size decreases, but the sum remains constant
        
        In main memory region from 0 to (cachesize-1) has tag 0, next unit of cache size has tag 1, so the block size does not affect tag index
        
        Important points :red_flag:
        
        During cache mapping, block of main memory is simply copied to the cache and the block is not actually brought from the main memory.
        
        Cache memory is divided into partitions having same size as that of blocks called as lines.
        
        Main memory is divided into equal size partitions called as blocks or frames.
      - The main advantage of cache memory is its very fast speed
      - Multilevel Cache Organization
        
        This helps to achieve better performance in terms of speed
        
        The smallest size cache memory is placed closest to the CPU
        
        A multilevel cache organization is an organization where cache memories of different sizes are organized at multiple levels to increase the processing speed to a greater extent
        
        The smaller the size of cache, the faster its speed
      - Cache Operation
        
        If the required word is not
        found in the CPU registers
        
        If the required word is not found in
        the cache memory: CACHE MISS
        
        If the page containing the required word
        is not found in the main memory
        
        The required word is delivered to the CPU
        
        A page fault occurs
        
        The page containing the required word is mapped from the secondary memory to the main memory
        
        The page is mapped from the main memory to the cache memory
        
        Page Table is used to determine whether the required page is present in the main memory or not
        
        When the required word is not found in the cache memory, it is searched in the main memory
        
        If the required word is found in the cache memory, the word is delivered to the CPU: CACHE HIT
        
        The required word is searched in the cache memory
        
        Tag directory of the cache memory is used to search whether the required word is present in the cache memory or not
        
        If the required word is found in the CPU registers, it is read from there.
        
        Whenever CPU requires any word of memory, it is first searched in the CPU registers.
      - Cache memory lies on the path between the CPU and the main memory
      - Execution of Program
        
        This allows CPU to access the most probable portion at a faster speed.
        
        The portion of the program that is mostly probably going to be executed in the near future is kept in the cache memory.
        
        Whenever any program has to be executed, it is first loaded in the main memory.
      - Cache memory is a Random Access Memory
      - Data is transferred in the form of words between the cache memory and the CPU.
      - The fast speed of the cache memory makes it extremely useful
      - It is used for bridging the speed mismatch between the fastest CPU and the main memory
      - It does not let the CPU performance suffer due to the slower speed of the main memory.
      - It can be accessed by the CPU at much faster speed than main memory
      - Data is transferred in the form of blocks or pages between the cache memory and the main memory
    - - Simultaneous Access Memory Organization
        
        Whenever CPU requires any word, it starts searching for it in all the levels simultaneously.
        
        Average Cost
        
        S1 = Size of level L1
        
        { C1 x S1 + C2 x S2 } / { S1 + S2 }
        
        Ci = Cost per byte of level Li
        
        All the levels of memory are directly connected to the CPU.
        
        Average Access Time
        
        Ti = Access time of level Li
        
        Hi = Hit rate of level Li
        
        H1 x T1 + (1 – H1) x H2 x T2
      - Hierarchical Access Memory Organization
        
        Average Cost
        
        S1 = Size of level L1
        
        { C1 x S1 + C2 x S2 } / { S1 + S2 }
        
        Ci = Cost per byte of level Li
        
        Whenever CPU requires any word
        
        It first searches for the word in level-1
        
        If the required word is not found in level-1, it searches for the word in level-2
        
        If the required word is not found in level-2, it searches for the word in level-3 and so on.
        
        Average Access Time
        
        2 Level
        
        T1 + M1.T2
        
        3 Level
        
        T1 + M1.T2 + M2.T3
        
        I+D Cache
        
        Calculate access time for I and D cache independently
        
        Use the ratio of I and D cache access to calculate the average access time
        
        Level-2 is directly connected to level-1
        
        Level-1 is directly connected to the CPU
        
        Level-3 is directly connected to level-2 and so on
        
        Problems
        
        Percentage of read and writes are given
        
        Virtual memory access time maybe given
        
        Average access time(R+W) may have to be calculated
    - - Levels
        
        Level 1
        
        At level-1, Cache Memory is present
        
        It is expensive and therefore smaller in size (in MB).
        
        It stores the segments of program that are frequently accessed by the processor.
        
        Cache memory is implemented using static RAM.
        
        Level 2
        
        It is less expensive than cache memory and therefore larger in size (in few GB).
        
        It can communicate directly with the CPU and with auxiliary memory devices through an I/O processor.
        
        At level-2, main memory is present
        
        RAM
        
        DRAM
        
        Word Line
        
        Bit-Line
        
        DRAM cells are usually organized into a square matrix, with separate decoders for the rows and columns
        
        Read
        
        7 more items...
        
        Refresh
        
        Write
        
        8 more items...
        
        3 more items...
        
        Problems
        
        3 more items...
        
        RAM Chip Organization
        
        5 more items...
        
        SRAM
        
        Constructed using flip-flops
        
        As long as power is applied it is able to retain its data
        
        No need for refresh
        
        Faster than DRAM
        
        Used in cache memory
        
        Less data density
        
        More expensive than DRAM
        
        Uses 6 transistors for storing 1 bit
        
        Use for creating small memories
        
        Problems
        
        Common Lines
        
        Lines for chip select
        
        Number of chips needed
        
        Level 3
        
        Magnetic Disk
        
        Performance
        
        Components that contribute
        to the service time are-
        
        Seek Time
        
        4 more items...
        
        Data transfer rate
        
        3 more items...
        
        Rotational latency
        
        3 more items...
        
        Queuing delay
        
        1 more item...
        
        Controller overhead
        
        2 more items...
        
        The time taken by the disk to complete an I/O request is called as disk service time or disk access time
        
        Architecture
        
        These tracks are further divided into sectors which are the smallest divisions in the disk.
        
        Disk Arm
        
        Each platter has 2 surfaces- top and bottom and both the surfaces are used to store the data
        
        Each surface has its own read / write head
        
        The rotation causes the required sector of the track to come under the head
        
        Head has to reach at a particular track and then wait for the rotation of the platter
        
        It is used to read from and write to the disk.
        
        A cylinder is formed by combining the tracks at a given radius of a disk pack.
        
        Each platter consists of concentric circles called as tracks
        
        The entire disk is divided into platters
        
        Storage Density
        
        Innermost track has maximum storage density.
        
        Storage density decreases as we move from one track to another track away from the center.
        
        This is because each track has different storage density.
        
        Outermost track has minimum storage density.
        
        All the tracks of a disk have the same storage capacity.
        
        Important Formulas
        
        Average Seek Time
        
        Average seek time
        = 1 / 3 x Time taken for one full stroke
        
        Average Disk Access Time
        
        Average disk access time
        = Average seek time + Average rotational delay + Transfer time + Controller overhead + Queuing delay
        
        Disk Access Time
        
        Disk access time
        = Seek time + Rotational delay + Transfer time + Controller overhead + Queuing delay
        
        Magnetic disk is a storage device that is used to write, rewrite and access data.
        
        It uses a magnetization process.
        
        At level-3, secondary storage devices like Magnetic Disk are present.
        
        They are used as back up storage.
        
        They are cheaper than main memory and therefore much larger in size (in few TB).
        
        Level 0
        
        Registers are implemented using Flip-Flops.
        
        They are most expensive and therefore smallest in size (in KB).
        
        At level-0, registers are present which are contained inside the CPU
        
        Since they are present inside the CPU, they have least access time.
        
        Level 4
        
        They are cheapest and largest in size (1-20 TB).
        
        They are used to store removable files.
        
        At level-4, tertiary storage devices like magnetic tape are present.
      - Goals
        
        To obtain the highest possible average access speed
        
        To minimize the total cost of the entire memory system
      - Memory hierarchy is the hierarchy of memory and storage devices found in a computer system.
      - It ranges from the slowest but high capacity auxiliary memory to the fastest but low capacity cache memory.
    - - Register Indirect Addressing Mode
        
        The address field of the instruction refers to a CPU register that contains the effective address of the operand.
        
        Only one reference to memory is required to fetch the operand.
        
        Examples
        
        ADD R1, (R2)
        
        Load R1, @R2
        
        Indicated with [[Rn]]
      - Indirect Addressing Mode
        
        The address field of the instruction specifies the address of memory location that contains the effective address of the operand.
        
        Two references to memory are required to fetch the operand.
        
        Examples
        
        Load R1, @1000
        
        ADD R1, (1000)
        
        Indicated with [[Add]]
        
        Used to implement pointers
      - Direct Addressing Mode
        
        The address field of the instruction contains the effective address of the operand.
        
        It is also called as absolute addressing mode.
        
        Only one reference to memory is required to fetch the operand.
        
        Examples
        
        ADD R2, 3
        
        Load R1, 1000
        
        Indicated with [add]
      - Register Direct Addressing Mode
        
        No reference to memory is required to fetch the operand.
        
        The address field of the instruction refers to a CPU register that contains the operand.
        
        The operand is contained in a register set.
      - Implied / Implicit Addressing Mode
        
        The definition of the instruction itself specify the operands implicitly.
        
        It is also called as implicit addressing mode.
      - Immediate Addressing Mode
        
        The operand is specified in the instruction explicitly.
        
        Instead of address field, an operand field is present that contains the operand.
        
        Examples
        
        Load R1, 1000
        
        ADD R2, 3
        
        Immediate addressing mode can be used to specify constants; thus, it cannot be used to specify the destination operand of an instruction
      - Displacement Addressing
        
        Indexed Addressing Mode
        
        Effective address of the operand is obtained by adding the content of index register with the address part of the instruction.
        
        Used to implement array access
        
        Base Register Addressing Mode
        
        Examples
        
        Load R1, 100(R2) is interpreted as R1 ← [100 + [R2]]
        
        Effective address of the operand is obtained by adding the content of base register with the address part of the instruction.
        
        Used for program relocation
        
        Relative Addressing Mode
        
        Effective address of the operand is obtained by adding the content of program counter with the address part of the instruction.
      - Auto-Decrement Addressing Mode
        
        Then, the operand value is fetched.
        
        First, the instruction register RAUTO value is decremented by step size ‘d’.
        
        Examples
        
        ADD R1, -(R2) is interpreted as R2 ← [R2] – d followed by R1 ← [R1] + [[R2]]
        
        Load R1, -(R2) is interpreted as R2 ← [R2] – d followed by R1 ← [[R2]]
        
        Similar to auto increment but with decrement
      - Auto-Increment Addressing Mode
        
        After accessing the operand, the content of the register is automatically incremented by step size ‘d’.
        
        Only one reference to memory is required to fetch the operand.
        
        Step size ‘d’ depends on the size of operand accessed.
        
        Examples
        
        ADD R1, (R2)+ is interpreted as R1 ← [R1] + [[R2]] followed by R2 ← [R2] + d
        
        Load R1, (R2)+ is interpreted as R1 ← [[R2]] followed by R2 ← [R2] + d
        
        This addressing mode is a special case of Register Indirect Addressing Mode where-
        Effective Address of the Operand = Content of Register
      - Stack Addressing Mode
        
        The operand is contained at the top of the stack.
  - - - Pipelined Execution
        
        4 Stage Pipeline
        
        Instruction fetch (IF)
        
        Instruction Execute (IE)
        
        Instruction decode (ID)
        
        Write back (WB)
        
        Perfomance Metrics
        
        Calculating Cycle Time
        
        There are two cases possible-
        
        All the stages do not offer same delay
        
        Cycle time = Maximum delay offered by any stage including the delay due to its register
        
        max { stage delay + buffer delay) }
        
        All the stages offer same delay
        
        Cycle time = Delay offered by one stage including the delay due to its register
        
        stage delay + buffer delay
        
        There is a global clock that synchronizes the working of all the stages.
        
        Frequency Of Clock
        
        Frequency of the clock (f) = 1 / Cycle time
        
        Frequency of the clock is set such that all the stages are synchronized.
        
        At the beginning of each clock cycle, each stage reads the data from its register and process it.
        
        Cycle time is the value of one clock cycle
        
        Pipelining yields a reduction in the average execution time per instruction
        
        Calculating Pipelined Execution Time
        
        So, number of clock cycles taken by each remaining instruction = 1 clock cycle
        
        Multiple instructions execute parallely.
        
        Time taken to execute first instruction + Time taken to execute remaining instructions
        
        (k + n – 1) clock cycles
        
        Number of clock cycles taken by the first instruction = k clock cycles, where k is the number of stages in the pipeline
        
        After first instruction has completely executed, one instruction comes out per clock cycle.
        
        In other words, the aim of pipelining is to maintain CPI ≅ 1.
        
        High efficiency of pipelined
        processor is achieved when-
        
        There are no register and memory conflicts.
        
        There are no conditional branch instructions.
        
        There are no interrupts.
        
        All the stages are of equal duration.
        
        Speed Up
        
        Speed Up (S) = Non-Pipelined execution time / Pipelined execution time
        
        Practically, total number of instructions never tend to infinity.
        
        Therefore, speed up is always less than number of stages in pipeline.
        
        k / { 1 + (k – 1)/n }
        
        n x k clock cycles / (k + n – 1) clock cycles
        
        For very large number of instructions, n→∞. Thus, speed up = k.
        
        It gives an idea of “how much faster” the pipelined execution is as compared to non-pipelined execution.
        
        Example
        
        Find stage with most delay and add pipeline overhead and use it as processing time for each stage
        
        Find total time for n instructions for pipeline case
        
        Non-pipeline latency will be sum of delay for each stage
        
        Speedup from pipelining = Average instruction time unpipelined / Average instruction time pipelined
        
        Pipeline latency due to intermediate register will be added to the duration of the single clock cycle to calculate the average pipelined instruction processing time,
        
        Average non-pipelined Instruction time will be product of cycle time and number of stages in the pipeline or the sum of the stage latency if they are different
        
        Stall
        
        Speedup = Pipeline depth / 1 + Pipeline stall cycles per instruction
        
        In case only one instruction has to be executed, then-
        
        Thus, time taken to execute one instruction in non-pipelined architecture is less.
        
        Non-pipelined execution gives better performance than pipelined execution.
        
        This is because delays are introduced due to registers in pipelined architecture.
        
        One complete instruction is executed per clock cycle i.e. CPI = 1.
        
        Efficiency
        
        Efficiency = Speed Up / Number of stages in Pipelined Architecture
        
        Therefore speed up is always less than number of stages in pipelined architecture.
        
        The aim of pipelined architecture is to execute one complete instruction in one clock cycle
        
        Ideally, a pipelined architecture executes one complete instruction per clock cycle (CPI=1).
        
        Calculating Non-Pipelined Execution Time-
        
        Total number of instructions x Time taken to execute one instruction
        
        The maximum speed up that can be achieved is always equal to the number of stages
        
        Experiments show that 5 stage pipelined processor gives the best performance.
        
        Speed up = Number of stages in pipelined architecture
        
        Throughput
        
        Throughput is defined as number of instructions executed per unit time.
        
        Throughput = Number of instructions executed / Total time taken
        
        This is achieved when efficiency becomes 100%.
        
        Practically, efficiency is always less than 100%.
        
        Practically, it is not possible to achieve CPI ≅ 1 due to delays that get introduced due to registers.
        
        Architecture
        
        The number of functional units may vary from processor to processor.
        
        The hardware of the CPU is split up into several functional units.
        
        There is a global clock that synchronizes the working of all the stages.
        
        These functional units are called as stages of the pipeline.
        
        Each stage then processes the data and feeds its output to the register of the next stage.
        
        At the beginning of each clock cycle, each stage takes the input from its register.
        
        Each functional unit performs a dedicated task.
        
        Control unit manages all the stages using control signals.
        
        There is a register associated with each stage that holds the data.
        
        Phase Diagram
        
        This style of executing the instructions is highly efficient.
        
        A pipelined processor does not wait until the previous instruction has executed completely.
        
        Rather, it fetches the next instruction and begins its execution.
        
        Multiple instructions are executed parallely.
        
        Pipelining increases the CPU instruction throughput - the number of instructions completed per unit of time
        
        It does not reduce the execution time of an individual instruction, in fact, it usually slightly increases the execution time of each instruction due to overhead in the pipeline control
        
        ILP
        
        Pipelining exploits the potential parallelism among instructions
        
        This parallelism is called instruction-level parallelism (ILP)
        
        Methods
        
        Increasing the depth of the pipeline to overlap more instructions
        
        Multiple Dispatch
        
        Replicate the internal components of the computer so
        that it can launch multiple instructions in every pipeline stage
      - Non-Pipelined Execution
        
        A new instruction executes only after the previous instruction has executed completely.
        
        This style of executing the instructions is highly inefficient.
        
        All the instructions of a program are executed sequentially one after the other.
    - - Hazards
        
        Types
        
        Data Hazards
        
        Types
        
        WAW(OD)
        
        Output Dependency
        
        WAW hazards occur only in pipelines that write in more than one stage, or allow an instruction to proceed even when a previous instruction is stalled
        
        Example
        
        3 more items...
        
        RAW(TD)
        
        Examples
        
        2 more items...
        
        True Dependency
        
        Solution
        
        2 more items...
        
        WAR(AD)
        
        Analysis
        
        1 more item...
        
        Anti-Dependency
        
        WAR hazards may occur in a pipeline with a write stage preceding a read
        stage
        
        Example
        
        3 more items...
        
        Data hazards arise due to the unavailabality of an operand
        
        Dependency
        
        True Dependent
        
        Inst2 is (true) data dependent on Inst1, if Inst1 writes its output in a register Reg (or memory location) that Inst2 reads as its input
        
        Anti Dependent
        
        Inst2 is antidependent on Inst1, if Inst1 reads data from a register Reg(or memory location) which is subsequently overwritten by Inst2
        
        Output Dependent
        
        Inst2 is output dependent on Inst1 if both write in the same register Reg(or memory location) and Inst2 writes its output after Inst1
        
        Control Dependent
        
        Inst2 is control dependent on Inst1, if Inst1 must complete before a decision can be made whether or not to execute Inst2
        
        Structural Hazards
        
        A structural hazard occurs when two (or more) instructions that are already in pipeline need the same resource
        
        The result is that instruction must be executed in series rather than parallel for a portion of pipeline
        
        Structural hazards are sometime referred to as resource hazards
        
        Control Hazards
        
        Control hazards arise from branch, jump, and other control flow
        change instructions
        
        Branches take effect at the end of the mem stage
        
        15-20% instructions are branches
        
        Solution
        
        Determine branch taken/not taken sooner
        
        Determine branch target address earlier
        
        All instructions which change the PC lead to control hazard
        
        Stalls
        
        If branch decision is taken nth stage, then there is a stall of n-1 cycles
        
        Conditional and Unconditional branch instructions have different stalls.
        
        Conditional branch may result in branch being taken or not taken. This will affect stall.
        
        Unconditional branches have less stall
        
        Stall happens due to the draining of the instructions that are part of the branch not taken path due to the branch being taken
        
        Unconditional branch can be detected after instruction decode
        
        CPI Calculation with Stall
        
        Version 2
        
        7 more items...
        
        Version 1
        
        1 more item...
        
        Average Instruction Execution Time = Average CPI * Cycle Duration
      - Types
        
        Arithmetic Pipeline
        
        Instruction Pipeline
    - - EX
        
        Arithmetic operations, or calculate effective address for memory instructions, branch condition and branch target address calculated for branch instructions
      - MEM
        
        Load reads, store writes with address calculated in previous stage. Other instructions do not use this stage.
      - ID
        
        Instruction is decoded in the control unit to decide what has to be done, the source registers are read from the register file
      - WB
        
        Write data back to register file, not applicable to branch instructions
      - IF
        
        Instruction is fetched from memory based on PC address, and PC is incremented so that it points to the next instruction
- - - - Bus request(BR) and Bus grant (BG) signals are used by the
        DMA controller to request the CPU to relinquish control of the buses and get the control of system buses
      - One common method CPU may be placed in an idle state extensively used in microprocessors is to disable the buses through special control signals
      - Bus Request
        
        The bus request (BR) input is used by the DMA controller to request the CPU to relinquish control of the buses
        
        When this input is active, the CPU terminates the execution of the current instruction and places the address bus, the data bus, and the read and write lines into a high-impedance state
        
        The high-impedance state behaves like an open circuit, which means that the output is disconnected and does not have a logic
        significance
      - Bus Grant
        
        The CPU activates the bus grant (BG) output to inform the external DMA that the buses are in the high-impedance state
        
        The DMA that originated the bus request can now take control of the buses to conduct memory transfers without processor intervention
        
        When the DMA terminates the transfer, it disables the bus request line
        
        The CPU disables the bus grant, takes control of the buses, and returns to its normal operation
      - The DMA controller uses hold request (HOLD) and hold acknowledge (HOLDA) signals to ask the CPU to stop driving the address, data and control buses so that the DMA controller can drive them to carry out a transfer
      - Sequence
        
        Each time the peripheral is ready to transfer a byte it asserts its DMA request(DRQ) line to the DMA controller
        
        The DMA controller asserts the CPU’s hold request(HRQ) pin
        
        When the CPU control circuitry is able to suspend execution (at the end of an instruction or by inserting wait states in T2) it asserts the hold acknowledge (HOLDA) signal to the
        DMA controller and floats (“tri-states”) the address, data and control bus signals
        
        The DMA controller then puts the memory address on the address bus, asserts either MEMR* plus IOW* or MEMW* plus IOR* on the control bus and asserts the appropriate DMA acknowledge line to the peripheral
        
        The peripheral responds to the DMA acknowledge signal by reading or writing it’s data to the data bus
        
        At the same time the memory responds to the
        MEMR*/MEMW* control signal which causes
        the data to be read/written directly from/to memory
        
        At the end of the bus cycle the DMA controller
        then negates hold request line and the CPU can
        continue to execute until the next DMA request
    - - An address register
      - A control register
      - A word counter register
    - - Burst or block transfer mode
        
        In this mode, the entire block of data is transferred once the
        DMA controller is granted access to the system bus by the CPU
        
        The bytes of data in the block are transferred before releasing control of the system buses back to the CPU
        
        The only disadvantage of this mode is that it renders the CPU inactive for some long periods of time
        
        Burst mode has low overhead and can handle the highest peak data rates, but the CPU can get locked out of memory for intervals that are as long as the longest block to be transferred
        
        If the transfer is longer than the shortest interrupt interval, such as the real time clock tick interval, interrupts can get lost
        
        Burst mode DMA is more effective when relatively short time
        durations are needed to transfer the data block
        
        The disadvantage is that a burst mode DMA device “hogs” the bus, thus preventing any other device from accessing memory during the burst
        
        If the burst lasts too long, it may prevent the CPU from servicing certain time critical events, such as the real time clock interval (clock tick)
        
        The data within a burst comes in too quickly to allow the arbitration handshaking required for the DMA controller to acquire and release the data between each data element
        
        Steps
        
        Bus grant request time.
        
        Transfer the entire block of data at transfer rate of device because the device is usually slow than the speed at which the data can be transferred to CPU.
        
        Release the control of the bus back to CPU
        
        Total time taken to transfer the N bytes =
        Bus grant request time + (N) * (memory transfer rate) + Bus release control time.
        
        X µsec = data transfer time or preparation time (words/block)
        Y µsec =memory cycle time or cycle time or transfer time (words/block)
        % CPU idle (Blocked)=(Y/X+Y)*100
        % CPU Busy=(X/X+Y)*100
      - Cycle stealing mode
        
        In this mode, the DMA controller obtains access to the system buses like burst mode; but after one word of data transfer, the control of the system bus is released back to the CPU via
        BG
        
        It is then continually requested again via BR, transferring one byte of data per request, until the entire block of data has been transferred
        
        This mode is suitable for the systems in which the CPU cannot
        be disabled for the considerable length of time as in burst transfer modes such as for controllers monitoring the data in real time
        
        The advantage is that CPU is not idled for as long as in burst mode, but the data block is not transferred as quickly
        
        It is also called Interleaved DMA as it allows other memory transfers to be interleaved with the DMA
        
        Single cycle DMA is better suited to transferring data over longer
        periods of time, where there is enough time to acquire and release the bus for every word transferred
        
        In this case, the CPU and other devices can still access the memory, at a reduced bandwidth. As a result, the CPU may be a bit slower because it will sometimes have to wait for a DMA cycle to complete, but it is not entirely shut out when a DMA transfer is in progress
        
        When a single cycle DMA transfer occurs, more time is used in acquiring and transferring control of the memory to and from the DMA controller since it happens so much more frequently
        
        This “overhead” frequently reduces the overall available memory bandwidth, especially when it is performed sequentially with the data transfers
        
        Some systems overlap the memory bus arbitration handshaking with the memory data transfers so that the arbitration does not slow down the data transfers
        
        Steps
        
        Buffer the byte into the buffer
        
        Inform the CPU that the device has 1 byte to transfer (i.e. bus grant request)
        
        Transfer the byte (at system bus speed)
        
        Release the control of the bus back to CPU.
        
        For 1 byte of transfer of data, time taken by using cycle stealing mode (T) = time required for bus grant + 1 bus cycle to transfer data + time required to release the bus
      - Transparent mode
        
        It is the slowest yet more efficient data transfer mode in terms of overall system performance
        
        The DMA controller transfers data only when the CPU is busy in performing operations that do not use the system buses
        
        So, the CPU never stops executing its programs but the biggest disadvantage is complex hardware circuitry that needs to determine when the CPU is not using the system buses
      - Interleaved mode
        
        Interleaved DMA is a more complex type of DMA operation
        
        The DMA controller takes over the system bus when the
        microprocessor is not using it
        
        With Interleaved DMA, each data transfer includes 1 byte per instruction cycle
        
        An alternate half cycle i.e. half cycle DMA + half cycle processor
        
        The microprocessor doesn't use the bus when it performs internal operations, such as decoding an instruction or ALU operations
        
        The DMA controller takes advantage of those times in order to transfer data
    - - Two Step
        
        DMA controllers can transfer data in a two-step process by reading a value from one port or address in one bus cycle and writing that value to another port or address in a second bus cycle
      - Single Step
        
        It is also possible for the DMA controller to carry out read and write operations simultaneously. In this case the data is
        transferred directly between the I/O device and memory in the same bus cycle
    - - Let D be the size of data which is transferred at a time
      - Let R be the arrival data rate
      - Time take to to receive D amount of data = D/R
      - Let T be the time to transfer D amount of data
      - CPU will be busy for D/R amount of time
      - CPU will be idle for T amount of time
      - CPU Idle % = (T/(T+D/R))*100
      - CPU busy % = ((D/R)/(T+D/R))*100
      - Example Scenarios
        
        Magnetic Disk
        
        Radius/Diameter, data density, RPM
        
        Perimeter = 2*PI*R = PI*D
        
        Data = Perimeter * Data Density
        
        Data Rate = Data / RPM
        
        Network Data
    - - DMA data count register determines the maximum amount of data we can transfer at one go
      - DMA count = Total Transfer Size / DMA Data Count register size
- - - - Von-Neumann Architecture
        
        Aspects
        
        Memory that stores data and instructions
        
        External mass storage
        
        A control unit that contains an instruction register and program counter
        
        Input and output mechanisms
        
        A processing unit that contains an arithmetic logic unit and processor registers
        
        Limitations
        
        von Neumann bottleneck
        
        An instruction fetch and a data operation cannot occur at the same time because they share a common bus. This is referred to as the von Neumann bottleneck and often limits the performance of the system.
        
        Once one instruction is executed at a time
        
        IAS machine
        
        IAS machine was the first electronic computer to be built at the Institute for Advanced Study (IAS) in Princeton, New Jersey
        
        It is sometimes called the von Neumann machine, since the paper describing its design was edited by John von Neumann, a mathematics professor at both Princeton University and IAS.
      - General Purpose System
      - Parallel Processing :
      - Harvard architecture
        
        The Harvard architecture is a computer architecture with separate storage and signal pathways for instructions and data
        
        Modified Harvard architecture
        
        Instruction and data memories occupy different address spaces
        
        Instruction and data memories have separate hardware pathways to the central processing unit (CPU)
        
        Instruction and data memories may be accessed in different ways
        
        Examples
        
        Separate dCache and iCache makes it possible to fetch instructions and data in parallel
        
        It has to do with which functional units of the CPU primarily access that cache. Since the ALU and FPU access the data cache which the decoder and scheduler access the instruction cache, and often pipelining allows the instruction processor and the execution unit to work simultaneously, using a single cache would cause contention between these two components. By separating them we lose some flexibility and gain the ability for these two major components of the processor to fetch data from cache simultaneously.
  - - - Control Unit
        
        Functions
        
        Fetches code for instructions
        
        Controls how data moves in the system
        
        Handles all processor control signals
        
        It directs all input and output flow
        
        Types
        
        Hardwired
        
        Generates the control signals needed for the processor using logic circuits
        
        Faster than micro-programmed
        
        Difficult to modify
        
        Costlier
        
        Cannot handle complex instructions
        
        Limited number of instructions
        
        Used in RISC
        
        Microprogrammed Control Unit
        
        Generates the control signals with help of micro instructions stored in control memory
        
        Slower than hard-wired
        
        Easy to modify
        
        Less costlier
        
        Can handle complex instructions
        
        Can handle many instructions
        
        Used in CISC
        
        Types
        
        Horizontal Micro Programmed
        
        Control signals are represented in decoded binary format i.e. 1bit/CS
        
        Supports longer control word
        
        Allows higher degree of parallelism
        
        No additional hardware needed
        
        Faster than vertical MC
        
        Less flexible than vertical MC
        
        Uses horizontal MicroInstruction where every bit in the control field attaches to a control line
        
        Uses less ROM encoding than Vertical MC
        
        Minimum Bits Needed
        
        2 more items...
        
        Vertical Microprogrammed
        
        Control signals are represented in encoded binary format
        
        Supports shorter control word
        
        Allows low degree of parallelism, 0 or 1
        
        Additional hardware in the form of decoders needed to generate control signals
        
        Slower than horizontal MC
        
        More flexible than horizontal MC
        
        Uses vertical MicroInstruction where a code is used for each action to be performed and the decoder translates this code into individual control signals
        
        Uses more ROM encoding than Horizontal MC
        
        Minimum Bits Needed
        
        3 more items...
        
        Micro Program Counter
        
        Also Called Control Address Register
        
        Size
        
        Size depends on the number of instructions and the number of cycles per instruction
        
        We can think that the micro-program contains the micro code for each instruction. Each instruction executes in multiple cycles and for each cycle we need a micro code
        
        Size = Number of instructions X Cycles per Instruction
        
        It is also termed as the decode unit since it decodes the instruction
        
        Receives status signals from the ALU
      - Arithmetic and Logic Unit
        
        Handles all the calculations the CPU may need
      - Registers
        
        Memory Address Register
        
        Memory Data Register
        
        Program Counter
        
        Jump Instruction
        
        Conditional/Unconditional Jump
        
        Interrupt
        
        Current Instruction Register
        
        Accumulator
        
        Instruction Buffer Register
        
        Input Register
        
        Output Register
        
        Temporary Register
      - Instructions
        
        Operation Code
        
        Expanding Opcode Technique
        
        Explanation
        
        Having a single instruction length is simpler and makes decoding easier, but is less efficient
        
        Algorithm
        
        Start with opcodes with largest number of addresses
        
        The last value of the opcode + 1 will be the prefix of the next set of opcodes
        
        Opcode is part of the MSB
        
        If address size if k bits, for m address fields, the opcode size will be n-m*k
        
        For m-1 address fields, the opcode size is n-(m-1)k with the prefix being the last value of n-(m-1)k-bit, m address opcode + 1
        
        This means the actual number of m address opcodes should be less than 2^(n-mk)
        
        This logic can be applied recursively with the prefix of the previous opcode and the last value of the current op code + 1 will be the prefix of the next opcode
        
        Opcode Formats
        
        1-Address Opcode
        
        2-Address Opcode
        
        0-Address Opcode
        
        3-Address Opcode
        
        Address Field
        
        Mode Field
        
        Types
        
        Direct AM
        
        Indirect AM
        
        Types
        
        Memory Reference Instruction
        
        0xxx-6xxx
        8xxx-Exxx
        
        Register Reference Instruction
        
        7xxxx
        
        I/O Instruction
        
        Fxxxx
        
        Classification
        
        0-Address
        
        Stack Organization
        
        Length of instruction is short as they do not have address field
        
        Size of program increases
        
        Execution of instructions is fast because operand data are stored in consecutive memory locations.
        
        1-Address
        
        Single Accumulator Organization
        
        2-Address
        
        Format
        
        Opcode
        
        Destination Address
        
        Source Address
        
        Mode
        
        3-Address
        
        Format
        
        Opcode
        
        Destination Address
        
        Source Address
        
        Mode
        
        Source Address
        
        Problems
        
        Types
        
        Number of registers is given
        
        Number of instructions is given
        
        Instructions format is given
        
        Find the size of n instructions
        
        Round up the size when converting to bytes
        
        Types
        
        Arithmetic Instructions
        
        String Manipulation Instructions
        
        Data Transfer Instructions
        
        Logic Instructions
        
        Control Transfer Instructions
        
        Loop Control Instructions
      - Organization
        
        Single Accumulator Organization
        
        General Register Organization
        
        Stack Organization
      - Interrupt
        
        When data are ready an I/O device can interrupt CPU
        
        After completing the current instruction at hand the CPU attends to the I/O device
        
        The CPU enters into a subroutine known as interrupt service subroutine (ISS) to transfer data from the device
        
        Each CPU has interrupt lines through which I/O device can be connected to the CPU
        
        Slow I/O devices are connected through interrupt lines
        
        When data transfer is over the CPU returns to the program it was executing
        
        An interrupt caused by an external signal applied to an interrupt input line of a CPU is known as hardware/external interrupt
        
        Enable/Disable
        
        Enabling of Interrupts
        
        When interrupts are to be used they are enabled (made effective) using instruction EI (it is an 8085 instruction) in the main program
        
        Disabling of Interrupts
        
        When the microprocessor is performing certain important task it may be desired to prevent the occurrence of interrupts during that period
        
        This is achieved using DI instruction. The use of DI instruction in the program prevents occurrence of all the interrupts
        
        Masking
        
        In certain situations it may be desired that some of the several interrupts should not occur while microprocessor is performing some important task
        
        This is done by masking technique
        
        Certain interrupts can be masked off (made ineffective) by software technique
        
        The interrupt that can be masked off is called maskable interrupt
        
        Types
        
        Software Interrupts
        
        This is known as software interrupt
        
        A special instruction is included in the program for this type of interrupt
        
        Return from Exception
        
        Transitions from kernel to user mode are performed explicitly by the operating system, generally at the end of an interrupt handler or kernel call, using a privileged RFE (return from exception) instruction
        
        Note the difference in terminology as exception here means software interrupt
        
        The normal program execution of a microprocessor can be interrupted by a special instruction in the program
        
        It can be used by the programmer to initiate an interrupt procedure at any desired point in the program. This instruction provides means for switching from a CPU user mode to the supervisor mode
        
        Software interrupt is a special call instruction that behaves like
        an interrupt rather than a subroutine call
        
        A software interrupt is initiated by executing an instruction
        
        Exception/Traps/Internal Interrupts
        
        The internal events, which cause the processor to go out of its normal processing sequence, are called exceptions
        
        Exceptions handle internal abnormal or unusual conditions, which prevent further processing
        
        Examples
        
        Register overflow
        
        Attempt to divide by zero
        
        An invalid operation code
        
        Stack overflow
        
        Protection violation
        
        If the program is rerun, the internal interrupts will occur in the same place each time
        
        External/Hardware
        
        External interrupts come from
        
        Timing device
        
        Elapsed time of an event
        
        Timeout interrupt may result from a program that is in an
        endless loop and thus exceeded its time allocation
        
        Circuit monitoring
        the power supply
        
        Power failure
        
        Power failure interrupt may have as its service routine a program that transfers the complete state of the CPU into a nondestructive memory in the few milliseconds before power ceases
        
        Input–output (I/O) devices
        
        I/O device requesting transfer of data, I/O device finished transfer of data
        
        Any other external source
        
        External interrupts depend on external conditions that are independent of the program being executed at the time
        
        Properties
        
        External and internal interrupts are initiated from signals that occur in the hardware of the CPU
        
        A software interrupt is initiated by executing an
        instruction
        
        Internal interrupts are synchronous with the program while external interrupts are asynchronous
        
        Interrupt Handling
        
        The hardware procedure for processing an interrupt is very similar to the execution of a subroutine call instruction
        
        The state of the CPU is pushed into a memory stack and the beginning address of the service routine is transferred
        to the program counter
        
        The beginning address of the service routine is determined by the hardware rather than the address field of an instruction
        
        Some computers assign a memory location for
        each possible interrupt
        
        The service routine must then determine what caused the interrupt and proceed to service it
        
        Some computers assign one memory location where interrupts are always transferred
        
        The hardware interrupt provides its own address that directs the CPU to the desired service routine
        
        The CPU does not respond to an interrupt until the end of an instruction execution
        
        Just before going to the next fetch phase, control checks for any
        interrupt signals
        
        CPU State Handling
        
        CPU State
        
        The content of the program counter
        
        The content of all processor registers
        
        The content of certain status conditions
        
        PSW
        
        The PSW is stored in a separate hardware register and contains the status information that characterizes the state of the CPU
        
        The collection of all status bit conditions in the CPU is sometimes called a program status word or PSW
        
        Includes
        
        The status bits from the last ALU operation
        
        It specifies the interrupts that are allowed to occur
        
        Whether the CPU is operating in a supervisor or user mode
        
        Saving Registers
        
        Some computers store only the program counter when responding to an interrupt
        
        The service program must then include instructions to store status and register content before these resources are used
        
        Only a few computers store both program counter and all status and register content in response to an interrupt
        
        Most computers just store the program counter and the PSW
        
        In some cases, there exist two sets of processor registers within the computer, one for each CPU mode. In this way, when the program switches from the user to the supervisor mode (or vice versa) in response to an interrupt, it is not necessary to store the contents of processor registers as each mode uses its own
        set of registers
        
        Priority
        
        A priority interrupt is a system that establishes a priority over the various sources to determine which condition is to be serviced first when two or more requests arrive simultaneously
        
        The system may also determine which conditions are permitted to interrupt the computer while another interrupt is being serviced
        
        Higher-priority interrupt levels are assigned to requests which,
        if delayed or interrupted, could have serious consequences
        
        Software-Polling
        
        Establishing the priority of simultaneous interrupts can be done by software or hardware
        
        A polling procedure is used to identify the highest-priority
        source by software means
        
        In this method there is one common branch address for all interrupts
        
        The program that takes care of interrupts begins at the branch address and polls the interrupt sources in sequence
        
        The order in which they are tested determines the priority of each interrupt
        
        The highest priority source is tested first, and if its interrupt signal is on, control branches to a service routine for this source
        
        Otherwise, the next-lower-priority source is tested, and so on
        
        Thus the initial service routine for all interrupts consists of a program that tests the interrupt sources in sequence and branches to one of many possible service routines
        
        The particular service routine reached belongs to the highest-priority device among all devices that interrupted the computer
        
        The disadvantage of the software method is that if there are many
        interrupts, the time required to poll them can exceed the time available to service the I/O device
        
        In this situation a hardware priority-interrupt unit can be used to speed up the operation
        
        When two devices interrupt the computer at the same time, the computer services the device, with the higher priority first
        
        Devices with highspeed transfers such as magnetic disks are given high priority, and slow devices such as keyboards receive low priority
        
        Hardware
        
        A hardware priority-interrupt unit functions as an overall manager in an interrupt system environment
        
        It accepts interrupt requests from many sources, determines which of the incoming requests has the highest priority, and issues an interrupt request to the computer based on this determination
        
        To speed up the operation, each interrupt source has its own interrupt vector to access its own service routine directly
        
        Thus no polling is required because all the decisions are established by the hardware priority-interrupt unit
        
        The hardware priority function can be established by either a serial or a parallel connection of interrupt lines
        
        Serial Connection
        
        The daisy-chaining method of establishing priority consists of a serial connection of all devices that request an interrupt.
        
        The device with the highest priority is placed in the first position, followed by lower-priority devices up to the device with the lowest priority, which is placed last in the chain
        
        The interrupt request line is common to all devices and forms a wired logic connection
        
        If any device has its interrupt signal in the low-level state, the interrupt line goes to the low-level state and enables the interrupt input in the CPU
        
        When no interrupts arc pending, the interrupt line stays in the high-level state and no interrupts are recognized by the CPU
        
        This is equivalent to a negative logic OR operation
        
        The CPU responds to an interrupt request by enabling the interrupt acknowledge line
        
        This signal is received by device 1 at its PI (priority in) input
        
        The acknowledge signal passes on to the next device through the PO (priority out) output only if device 1 is not requesting an interrupt
        
        If device 1 has a pending interrupt, it blocks the acknowledge signal from the next device by placing a 0 in the PO output
        
        It then proceeds to insert its own interrupt vector address (VAD) into the data bus for the CPU to use during the interrupt cycle
        
        Parallel
        
        The parallel priority interrupt method uses a register whose bits are set separately by the interrupt signal from each device
        
        Priority is established according to the position of the bits in the register
        
        In addition to the interrupt register, the circuit may include a mask register whose purpose is to control the status of each interrupt request
        
        The mask register can be programmed to disable lower-priority interrupts while a higher-priority device is being serviced
        
        It can also provide a facility that allows a high-priority device to interrupt the CPU while a lower-priority device is being serviced
        
        The priority logic consists of an interrupt register whose individual bits are set by external conditions and cleared by program instructions
        
        Another output from the encoder sets an interrupt status flip-flop IST when an interrupt that is not masked occurs
        
        The interrupt enable flip-flop IEN can be set or cleared by the program to provide an overall control over the interrupt system
        
        The outputs of IST ANDed with IEN provide a common
        interrupt signal for the CPU
        
        The interrupt acknowledge INTACK signal from
        the CPU enables the bus buffers in the output register and a vector address VAD is placed into the data bus
        
        Priority Encoder
        
        The priority encoder is a circuit that implements the priority function
        
        The logic of the priority encoder is such that if two or more inputs arrive at the same time, the input having the highest priority will take precedence
        
        Interrupt Cycle
        
        The interrupt enable flip-flop IEN can be set or cleared by program instructions
        
        When IEN is cleared, the interrupt request coming from
        IST is neglected by the CPU
        
        The program-controlled IEN bit allows the programmer
        to choose whether to use the interrupt facility
        
        If an instruction to clear IEN has been inserted in the program, it means that the user does not want his program to be interrupted
        
        An instruction to set IEN indicates that the interrupt facility will be used while the current program is running
        
        Most computers include internal hardware that clears IEN to 0 every time an interrupt is acknowledged by the processor
        
        At the end of each instruction cycle the CPU checks IEN and the interrupt signal from IST
        
        If either is equal to 0, control continues with the next
        instruction
        
        If both IEN and IST are equal to 1, the CPU goes to an interrupt
        cycle
        
        Interrupt cycle ops
        
        6 more items...
        
        Software Routines
        
        A priority interrupt system is a combination of hardware and software techniques
        
        The computer must have software routines for servicing the interrupt requests and for controlling the interrupt hardware registers
        
        Initial/Final Operations
        
        Initial
        
        2 more items...
        
        Final
        
        1 more item...
      - RISC/CISC
        
        RISC
        
        Reduce the cycles per instruction at the cost of the number of instructions per program
        
        Simpler instructions, hence simple instruction decoding.
        
        Instruction size under one word.
        
        Instructions take single clock cycle to get executed.
        
        More number of general purpose register
        
        Simple Addressing Modes
        
        Uses only Hardwired control unit
        
        Fixed sized instructions
        
        Can perform only Register to Register Arithmetic operations
        
        Requires more number of registers
        
        Code size is large
        
        CISC
        
        The CISC approach attempts to minimize the number of instructions per program but at the cost of increase in number of cycles per instruction
        
        Complex instruction, hence complex instruction decoding.
        
        Instruction are larger than one word size
        
        Instruction may take more than single clock cycle to get executed
        
        Less number of general purpose register as operation get performed in memory itself
        
        Complex Addressing Modes
        
        Uses both hardwired and micro programmed control unit
        
        Variable sized instructions
        
        Can perform REG to REG or REG to MEM or MEM to MEM
        
        Requires less number of registers
        
        Code size is small
        
        Instruction take more than one clock cycle
        
        Instruction are larger than size of one word
    - - Types
        
        Address Bus
        
        Control Bus
        
        Data Bus
      - Common Bus System
        
        Multiplixer
        
        Multiplex output of different registers to BUS
        
        Number of Mux = Width of bus
        
        Number of inputs of Mux = number of registers
      - Three State Bus Buffers
        
        A bus system can be constructed with three-state gates instead of multiplexers
        
        A three-state gate is a digital circuit that exhibits three states
        
        Two of the states are signals equivalent to logic 1 and 0 as in a conventional gate, with the third being a high impedance state
        
        The high-impedance state behaves like an open circuit, which means that the output is disconnected and does not have
        a logic significance
    - - Functional or atomic operations of a processor
      - These are low level instructions used to implement complex machine instructions
      - They perform operations on data stored in one ore more registers
      - They transfer data between registers or between external buses of the CPU
      - Each instruction cycle is made up of smaller units
      - Types
        
        Register transfer microoperations transfer binary information from one register to another
        
        Arithmetic microoperations perform arithmetic operation on numeric data stored in registers
        
        Logic microoperations perform bit manipulation operations on nonnumeric data stored in registers
        
        Shift microoperations perform shift operations on data stored in
        registers
- - - - Devices with highspeed transfers such as magnetic disks are given high priority, and slow devices such as keyboards receive low priority
      - Higher-priority interrupt levels are assigned to requests which,
        if delayed or interrupted, could have serious consequences
    - - The daisy-chaining method of establishing priority consists of a serial connection of all devices that request an interrupt
      - The device with the highest priority is placed in the first position, followed by lower-priority devices up to the device with the lowest priority, which is placed last in the chain
      - The interrupt request line is common to all devices and forms a wired logic connection
      - If any device has its interrupt signal in the low-level state, the interrupt line goes to the low-level state and enables the interrupt input in the CPU
      - When no interrupts are pending, the interrupt line stays in the high-level state and no interrupts are recognized by the CPU
      - Priority In/Out
        
        Priority Out
        
        The acknowledge signal(PI) passes on to the next device through
        the PO (priority out) output only if the is not requesting an interrupt
        
        If device 1 has a pending interrupt, it blocks the acknowledge signal from the next device by placing a 0 in the PO output
        
        Priority In
        
        This signal is received by device 1 at its PI(Priority In)
        
        The CPU responds to an interrupt request by enabling
        the interrupt acknowledge line
      - It then proceeds to insert its own interrupt vector address (VAD) into the data bus for the CPU to use during the interrupt cycle
      - Example
    - - Interrupt Register
        
        Priority is established according to the position of the bits in the register
        
        The parallel priority interrupt method uses a register whose bits are set separately by the interrupt signal from each device
        
        It consists of an interrupt register whose individual bits are set by
        external conditions and cleared by program instructions
      - Mask Register
        
        The mask register can be programmed to disable lower-priority interrupts while a higher-priority device is being serviced
        
        In addition to the interrupt register, the circuit may include a mask register whose purpose is to control the status of each interrupt request
        
        It can also provide a facility that allows a high-priority device to interrupt the CPU while a lower-priority device is being serviced
        
        By means of program instructions, it is possible to set or reset any bit in the mask register
      - Priority Encoder
        
        In this way an interrupt is recognized only if its corresponding mask bit is by the program
        
        The priority encoder generates the vector address, which is transferred to the CPU
        
        Each interrupt bit and its corresponding mask bit are applied to an AND gate to produce the four inputs to a priority encoder
      - Signals
        
        IST
        
        Another output from the encoder sets an interrupt status flip-flop IST when an interrupt that is not masked occurs
        
        IEN
        
        The interrupt enable flip-flop IEN can be set or cleared by the program to provide an overall control over the interrupt system
        
        The outputs of IST ANDed with IEN provide a common interrupt signal for the CPU
        
        INTACK
        
        The interrupt acknowledge INTACK signal from the CPU enables the bus buffers in the output register and a vector address VAD is placed into the data bus
      - Example
      - Interrupt Cycle
        
        At the end of each instruction cycle the CPU checks IEN and the interrupt signal from IST
        
        If either is equal to 0, control continues with the next
        instruction
        
        If both IEN and IST are equal to 1, the CPU goes to an interrupt
        cycle
        
        Interrupt Cycle Operations
        
        SP ← SP - 1 Decrement stack pointer
        
        M [SP] ← PC Push PC into stack
        
        INTACK ← 1 Enable interrupt acknowledge
        
        PC ← VAD Transfer vector address to PC
        
        IEN ← 0 Disable further interrupts
        
        Go to fetch next instruction
      - ISR Final Opertaions
        
        Initial Operations
        
        Clear lower-level mask register bits
        
        Clear interrupt status bit IST
        
        Save contents of processor registers
        
        Set interrupt enable bit IEN
        
        Proceed with service routine
        
        Final Operations
        
        Clear interrupt enable bit IEN
        
        Restore contents of processor registers
        
        Clear the bit in the interrupt register belonging to the source that has been serviced
        
        Set lower-level priority bits in the mask register
        
        Restore return address into PC and set IEN
  - - - The top half does what needs to be done immediately
    - - A bottom half is used to process data, letting the top half to deal with new incoming interrupts
      - Interrupts are enabled when a bottom half runs