Sub-pages:
Data Dependencies

     Two members of the ARSe instruction set, load and store (the “memops”), have a two-cycle clock latency, which makes it necessary for some type of independent instruction to immediately follow them to prevent a stall.  Our goal is to locate suitable independent instructions from further along in the code and insert them after the loads/stores to allow for more streamlined execution.  However, this becomes tricky when you consider the ARSe set’s many data dependencies.  This site section covers all the details of data dependencies, initially documented in our Milestone 3 Report.  Here is a list of each instruction, with those that are directly dependent on it listed underneath: (x is a don’t care unless otherwise noted)

load sink, M1

  • store sink, x
  • store x, M1
  • load sink, x
  • unop sink, x, x    *   unop x, sink, x
  • binop sink, x, x   *   binop x, sink, x  *  binop x, x, sink

store source, M1

  • load source, x
  • load x, M1
  • store x, M1
  • unop source, x, x
  • binop source, x, x
  • jump (when the store is not also the latent instruction we are seeking a follower for)

unop sink, source, x (where the x to the left is an immediate)

  • store sink, x
  • unop x, sink, x  *  unop source, x , x   *   unop sink, x, x
  • binop x, sink, x   *   binop x, x, sink  *  binop source, x, x   *   binop sink, x, x
  • load source, x
  • load sink, x

binop sink, source1, source2

  • store sink, x
  • load source1, x  *  load source2, x  *  load sink, x
  • binop x, sink, x   *   binop x, x, sink  *  binop source1, x, x  *  binop source2, x, x  *
    binop sink, x, x
  • unop x, sink, x  *  unop source1, x, x   *   unop source2, x, x  *  unop sink, x, x

In addition to the above, in our processor, we will always mark anything we find following a jump destination instruction as dependent on it, since we don’t want to change a jump destination’s position.  It would be impossible for us to then go back and change the jump offset if we did move the destination. Also, any time (jump offset + distance it would have to move up to fill latent spot) is greater than the maximum jump offset (5 bits) we would mark it as being dependent, or unmovable. If the movement of an instruction under a jump (causing it to move down) would overflow the offset in the negative sense, everything under the jump is marked as dependent.  The main reason that jumps are so mobile in this instruction set is that register values are never guaranteed after a jump has occurred.

We have broken down the exact logic of our dependency checker, allowing us to create an EQN file describing the logic that we then converted to a PLA.  Select the link of interest from below: