1. Sam Mussmann
  2. tomasulo


tomasulo / tomasulo.py

#!/usr/bin/env python

import collections
import itertools

Instruction = collections.namedtuple('Instruction', ('opcode',
      'write_register', 'read_registers'))
"""This is the instruction tuple.  The first value is the opcode of the instruction, the second the register it will write to (or None), and the third is an iterable of the registers that the instruction will read from.

So the instruction:
    ADD.D F2, F0, F4
Would become:
    Instruction(opcode='ADD.D', write_register='F2', read_registers=('F0', 'F4'))

class _InstructionTracker:
  """Holds onto the state of each instruction.

  Therefore also knows which instruction(s) are next to issue and when the
  instructions are all done executing.
  done = False

  class _Instruction:
    """ Internal representation of an instruction.
    Tracks the state of the instruction and the pending state, and updates it
    for the new cycle.  Also tracks how many unsatisfied dependences this
    instruction currently has (when waiting in the reservation station) and
    which instruction in the stream this is.

    In addition, gives logging capabilities for the instruction to track things
    like RAW dependences and structural hazards/dependences.
    _new_state = None
    cur_state = 'unissued'
    states = set(('unissued', 'IS', 'reservation-station', 'queued-for-EX',
          'EX', 'queued-for-WB', 'WB', 'waiting-for-commit', 'CM'))
    dependence_count = 0

    def __init__(self, instruction, index):
      self.opcode = instruction.opcode
      self.write_register = instruction.write_register
      self.read_registers = instruction.read_registers
      self.index = index
      self.history = list()
      self.messages = set()

    def _set_state(self, state):
      if state not in self.states:
        raise Exception("Tried to set illegal state {0}".format(state))
      self._new_state = state

    def update(self, new_cycle):
      if self. _new_state:
        if self._new_state in set(('IS', 'EX', 'WB', 'CM')):
          self.history.append((self._new_state, new_cycle))
        if self.cur_state == 'EX':
          self.history.append(('EX-end', new_cycle - 1))
        self.cur_state = self._new_state
        self._new_state = None
    def issue(self):

    def wait_in_reservation_station(self):

    def enqueue_for_execute(self):

    def execute(self):

    def enqueue_for_writeback(self):

    def writeback(self):

    def wait_for_commit(self):

    def commit(self):

    def ready_to_commit(self):
      return self.cur_state in ('WB', 'waiting-for-commit')

    def __repr__(self):
      return str(self)

    def __str__(self):
      return ('{0.index}: {0.opcode} {0.write_register} {0.read_registers} state: '
          '{0.cur_state} pending state: {0._new_state} d_c: '

    def final_dict(self):
      def format_msg(msg):
        return '{0} on {1} (from {2})'.format(*msg)

      def get_cycle(state):
        index = map(lambda x: x[0], self.history).index(state)
        if state == 'EX':
          start_cycle = str(self.history[index][1])
          end_cycle = get_cycle('EX-end')
          if start_cycle != end_cycle:
            return '{0!s}-{1}'.format(self.history[index][1], end_cycle)
            return start_cycle
          return str(self.history[index][1])

      reg_iter = itertools.chain((self.write_register,), self.read_registers)
      instruction_text = '{0} {1}'.format(self.opcode, ', '.join(reg_iter))
      return {'index': self.index, 'instruction': instruction_text,
        'IS': get_cycle('IS'), 'EX': get_cycle('EX'),
        'WB': get_cycle('WB'), 'CM': get_cycle('CM'),
        'messages': '; '.join(format_msg(m) for m in self.messages)}

  def __init__(self, instructions):
    self.instructions = [_InstructionTracker._Instruction(instr, i) for
                         i, instr in enumerate(instructions)]

  def issue_next(self, reorder_buffer):
    unissued = filter(lambda i: i.cur_state == "unissued", self.instructions)
    if unissued and not reorder_buffer.is_full():

  def update(self, new_cycle):
    for instruction in self.instructions:
    if self.instructions[-1].cur_state == 'CM':
      self.done = True
    if new_cycle > 1000:
      print "failed to stop"
      self.done = True

class _ReorderBuffer:
  """Mimics a reorder buffer.

    Holds instructions that are add()ed to it, lets you know if it is full, and
    can do a commit.
  def __init__(self, length=1e6):
    self.storage = list()
    self.length = length  # Default arg is basically infinity

  def add(self, instruction):
    if self.is_full():
      raise Exception("Reorder buffer just got too full!! Oops!")

  def is_full(self):
    return len(self.storage) >= self.length

  def commit(self):
    if len(self.storage) == 0:
    head = self.storage[0]
    if head.ready_to_commit():

  def IS_instruction_iterator(self, instruction_tracker):
    return itertools.ifilter(lambda i: i.cur_state == "IS", self.storage)

class _FunctionalUnits:
  class FunctionalUnit:
    current_instruction = None
    end_cycle = None

    def __init__(self, duration, name):
      self.duration = duration
      self.name = name
      self.queue = list()

    def __repr__(self):
      return str(self)

    def __str__(self):
      return '{0.name}: {0.current_instruction} ends at {0.end_cycle} -- duration {0.duration} queuelen {1}'.format(self, len(self.queue))

    def start_instruction(self, current_cycle):
      self.queue.sort(key=lambda i: i.index)
      if self.queue:
        self.current_instruction = self.queue.pop(0)
        self.end_cycle = current_cycle + self.duration

    def busy(self, cycle):
      return self.end_cycle and cycle < self.end_cycle

    def update(self, instruction_tracker, cdb, current_cycle):
      if current_cycle == self.end_cycle:
      if not self.busy(current_cycle):
      for instruction in self.queue:
        instruction.messages.add(('SD', self.name, self.current_instruction.index))

    def enqueue(self, instruction):

  def __init__(self):
    int_fu = _FunctionalUnits.FunctionalUnit(1, 'int')
    fp_add_fu = _FunctionalUnits.FunctionalUnit(5, 'fp_add')
    fp_mul_fu = _FunctionalUnits.FunctionalUnit(8, 'fp_mul')
    fp_div_fu = _FunctionalUnits.FunctionalUnit(15, 'fp_div')
    self.opcode_map = collections.defaultdict(lambda: int_fu)
    self.opcode_map.update({'ADD.D': fp_add_fu, 'MUL.D': fp_mul_fu,
        'DIV.D': fp_div_fu})
    self.fu_list = [int_fu, fp_add_fu, fp_mul_fu, fp_div_fu]

  def enqueue(self, instruction):

  def update(self, instruction_tracker, cdb, current_cycle):
    for fu in self.fu_list:
      fu.update(instruction_tracker, cdb, current_cycle)

  def __repr__(self):
    return str(self)

  def __str__(self):
    return '\n'.join(str(fu) for fu in self.fu_list)

def run(input_instructions):
  """This is the primary computation point of this module.

    It takes a list of Instructions, and generates the output structure.

    Each instruction should be a tomasulo.Instruction.
  cycle = 0
  instruction_tracker = _InstructionTracker(input_instructions)
  reorder_buffer = _ReorderBuffer()
  register_file = collections.defaultdict(lambda: None)
  reservation_station = collections.defaultdict(list)
  cdb = list()
  functional_units = _FunctionalUnits()

  while not instruction_tracker.done:
    # Set up next instruction to issue next time

    # Deal with instructions currently in issue stage
    for instruction in reorder_buffer.IS_instruction_iterator(instruction_tracker):
      has_dependence = False
      for register in instruction.read_registers:
        if register_file[register] is not None:
          has_dependence = True
          instruction.dependence_count += 1
          instruction.messages.add(('RAW', register, register_file[register]))
      if not has_dependence:
      register_file[instruction.write_register] = instruction.index

    # Deal with EX stage
    functional_units.update(instruction_tracker, cdb, cycle)

    # Deal with WB stage
    if cdb:
      cdb.sort(key=lambda x: x.index)
      for instruction in cdb[1:]:
        instruction.messages.add(('SD', 'CDB', cdb[0].index))
      instruction = cdb.pop(0)
      waiting_instructions = [instruction_tracker.instructions[i] for i in
      for instr in waiting_instructions:
        instr.dependence_count -= 1
        if instr.dependence_count == 0:
      del reservation_station[instruction.index] 
    # Deal with CM stage

    cycle += 1

# This is debug stuff to dump the state of various hardware pieces.  I'm
# leaving it here should you need it to debug stuff.
#  for instruction in reorder_buffer.storage:
#    print instruction
#  print("reservation_station_state",
#    ['{0!s}: {1}'.format(k, ', '.join(map(lambda x: str(x), v))) for k, v in
#    reservation_station.iteritems() if v])
#  print("reg_file_state:", ['{0}: {1!s}'.format(k, v) for k, v in register_file.iteritems() if v is not None])
#  print functional_units

# Print final state:
  format_str = '{index: >2} {instruction: >19}{IS: >5}{EX: >9}{WB: >5}{CM: >5}  {messages}'
  print format_str.format(index='', instruction='Instruction', IS='IS',
      EX='EX', WB='WB', CM='CM', messages='Messages')
  print 80 * '-'
  for instruction in instruction_tracker.instructions:
    print format_str.format(**instruction.final_dict())