Please enable JavaScript.

Coggle requires JavaScript to display documents.

Computer Systems, Questions - Coggle Diagram

- - - - One bit full adder
        
        1 output for the sum
        
        1 output for the carryOuts
        
        2 inputs for the operands
        
        1 input for carryIn (from previous addition if we are chaining one bit adders)
        
        carryOut = bcarryIn + acarryIn + a*b
        
        sum = a-b-carryIn + -ab-carryIn + -a-bcarryIn + abcarryIn
        
        The sum bit only represents the state of the current bit after addition
      - Half adder: this adder doesn't have a carryIn input
      - To add larger numbers we need to chain one bit adders together into something called a ripple carry adder.
      - To do subtraction we can invert all the bits with a multiplexer and set the first carryIn bit to one to turn the number negative. Then we can add them as normal to perform the subtraction.
  - - - Memories
      - Latches
        
        D Latch/ D flip flop
      - Register files
      - The output from a memory element depends on the inputs and the value already stored in the memory element
      - All memory elements store state
      - Clocked memory elements have a clock signal input
      - Flip Flops
        
        Flip flops are often made from latches
      - What is the difference between a latch and a flip flop. A flip flop changes on a clock edge, a latch changes on inputs and a clock assertion.
    - - Direct mapping: each memory location is mapped to one block on the cache
      - Handling a cache miss
        
        Set PC back one instruction PC = PC -4
        
        Request main memory read and wait
        
        Write memory into cache
        
        Restart original instruction, this time the data will be found in the cache
      - To keep cache and memory consistent after writes:
        
        Write through scheme: writes write into both the cache and main memory every single time. Slow
        
        Write back scheme writes to the cache, only writes to main memory when the block is replaced in the cache. Faster but stores need two cycles now (to check for cache hit then to write to memory if the block was already modified by previous write)
        
        A write buffer allows us to store data waiting to be written to memory to speed up operations. If this is full the processor will have to write all the data back into main memory.
      - Parts of the cache block: Index V Tag Data
      - Locality
        
        Temporal: recent instructions are likely to be accessed again
        
        Spatial: instructions close to the current instruction are likely to be referenced again.
      - The TlB is a specialised cache which stores common virtual - physical memory addresses to prevent costly lookups in the page table.
    - - smaller faster memory is located closer to the processor, larger slower memory is located further away.
    - - To speed up processing times, main memory can act as a cache for secondary storage.
        
        Page is the equivalent of a cache block
        
        Page fault is the equivalent of a cache miss. This has very high time cost so it should be avoided.
      - Virtual memory allows us to run programs (or virtual machines) on the same physical memory without sharing the same physical memory. We need to prevent memory sharing for security and memory safety issues.
      - Programs run on virtual memory reference virtual memory addresses rather than physical ones.
      - It is up to the page table to convert virtual memory addresses to physical ones.
      - Virtual memory allows programs to exceed size of main memory? How?
      - Page Table: a table consisting of a mapping of virtual memory addresses to physical ones in real memory.
        
        Least Recently Used replacement scheme: The least frequently used pages in the page table will be replaced by other pages and written to the swap space instead. The processor uses a heuristic involving the swap bit
        
        The page table allows virtual memory to dynamically grow. It can grow in different directions to allow for memory for the heap and the stack
      - When RAM runs out, we may need to make use of swap space. This is secondary storage that acts like memory for us. The need to use this should be avoided as it is very slow.
      - Uses a write back scheme as writing to the disk is extremely slow (relatively)
      - OS ensures programs can't access each others page tables
      - There is a supervisor mode bit to indicate what kind of process it is, so what kind of privileges it should have
      - Virtual Machines
        
        You need to virtualise the instruction set for each virtual machine
        
        Each virtual machine will have their own virtual memory and own page tables. Only the host OS will actually interact with real addresses.
      - It is called thrashing when you have to access secondary memory to get the data. This is very slow
      - If two processes want to communicate they can get special permission from the OS to share some same memory
  - - - a decoder to select the correct read or write port
      - registers (which are built from d flip flops)
  - - - Cycle 1. Instruction fetch and PC increment
      - Cycle 2. Reading sources from the register file
      - Cycle 3 Performing an ALU computation
      - Cycle 4 Reading or writing (data) memory
      - Cycle 5 Storing data back to the register file
- - - - Canonical Form
        
        Sum of Products(minTerms)/ Disjunctive normal form
        
        Product of sums(maxTerms)/ Conjunctive normal form
        
        Both of these have a gate level of 2
        
        How to obtain these from a truth table?
  - - - An encoder is the inverse function to a decoder
      - Since the different combinations of inputs produce 2^n binary numbers it is common to label the output whatever binary number the inputs produce
    - - Consists of:
        
        Decoder: That generates n outputs one for each input to the multiplexer (so the decoder itself requires log2(n) inputs). This is to allow the multiplexer to select the input line to output.
        
        First layer of AND gates: One for each input, to combine with the selector lines from the decoder to allows us to select the input line to output.
        
        One large or gate to allow us to combine the outputs of all these AND gates back into a single wire.
    - - Allows us to produce gate level implementations of any logic function in the sum of product form.
      - First it has AND gates to form the products
      - Then it combines these using OR gates to form the sums
      - PLA's are efficient as they don't need gates for inputs which never produce truth values. Each product only needs one output gate e.g. if the same product is produced multiple times it can use the same gates
  - - - Next state finds the next state given the current state and inputs
      - Output produces a set of outputs from the current state and the inputs