Commits

Sam Mussmann committed 3bffd2d

This now solves HW3 with the correct answers. Still kinda messy though.

  • Participants
  • Parent commits a4931fb

Comments (0)

Files changed (2)

 
 import tomasulo
 
-instructions = [tomasulo.Instruction('L.D', 'F0', ('R1')),
+instructions = [tomasulo.Instruction('L.D', 'F0', ('R1',)),
                 tomasulo.Instruction('ADD.D', 'F2', ('F0', 'F4')),
                 tomasulo.Instruction('MUL.D', 'F4', ('F2', 'F6')),
                 tomasulo.Instruction('ADD.D', 'F6', ('F8', 'F10')),
-                tomasulo.Instruction('DADDI', 'R1', ('R1')),
-                tomasulo.Instruction('L.D', 'F1', ('R2')),
+                tomasulo.Instruction('DADDI', 'R1', ('R1',)),
+                tomasulo.Instruction('L.D', 'F1', ('R2',)),
                 tomasulo.Instruction('MUL.D', 'F1', ('F1', 'F8')),
                 tomasulo.Instruction('ADD.D', 'F6', ('F3', 'F5')),
-                tomasulo.Instruction('DADDI', 'R2', ('R2'))]
+                tomasulo.Instruction('DADDI', 'R2', ('R2',)),
+                tomasulo.Instruction('DADDI', 'R3', ('R3',)),
+                tomasulo.Instruction('DADDI', 'R4', ('R4',)),
+                tomasulo.Instruction('DADDI', 'R5', ('R5',))]
 
-pprint.pprint(tomasulo.run(instructions))
+tomasulo.run(instructions)
 #!/usr/bin/env python
 
 import collections
-import string
+import itertools
 
 Instruction = collections.namedtuple('Instruction', ('opcode',
       'write_register', 'read_registers'))
     Instruction(opcode='ADD.D', write_register='F2', read_registers=('F0', 'F4'))
 """
 
-_AnnotatedInstruction = collections.namedtuple('_AnnotatedInstruction',
-    ('opcode', 'write_register', 'read_registers', 'dependences'))
-""" Like Instruction, but includes dependences, which is a tuple of
-(instruction_number, register) pairs for which this instruction has RAW
-dependences.
-"""
-
 class _InstructionTracker:
-  """Remembers where each instruction is in execution, and ultimately serves as
-    the state of the simulation loop.
+  """Holds onto the state of each instruction as well as the overall state of the loop
   """
   cycle = 0
   done = False
   _next_instruction = 0
+
   class _Instruction:
     """ Internal representation of an instruction."""
-    history = list()
-    messages = set()
     _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, tracker, dependences):
-      self.instr = instruction
-      self.instr_index = index
+    def __init__(self, instruction, index, tracker):
+      self.opcode = instruction.opcode
+      self.write_register = instruction.write_register
+      self.read_registers = instruction.read_registers
+      self.index = index
       self.tracker = tracker
-      self.write_tag = "{0}-{1}".format(self.instr.write_register,
-          self.instr_index)
-      self.dependences = dependences
+      self.history = list()
+      self.messages = set()
 
     def _set_state(self, state):
       if state not in self.states:
       self._new_state = state
 
     def update(self):
-      if _new_state:
-        if _new_state[0] in string.uppercase:
-          history.append((_new_state, self.tracker.cycle))
-        self.cur_state = _new_state
+      if self. _new_state:
+        if self._new_state in set(('IS', 'EX', 'WB', 'CM')):
+          self.history.append((self._new_state, self.tracker.cycle))
+        if self.cur_state == 'EX':
+          self.history.append(('EX-end', self.tracker.cycle - 1))
+        self.cur_state = self._new_state
+        self._new_state = None
         
     def issue(self):
       self._set_state('IS')
     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.opcode} {0.write-register} {0.read_registers} in state {1} '
-          'with pending state {2} dependences {3}'.format(self.instruction,
-            self.cur_state, self._new_state, self.dependences))
+      return ('{0.index}: {0.opcode} {0.write_register} {0.read_registers} state: '
+          '{0.cur_state} pending state: {0._new_state} d_c: '
+          '{0.dependence_count}'.format(self))
+
+    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)
+          else:
+            return start_cycle
+        else:
+          return str(self.history[index][1])
+
+      reg_chain = itertools.chain((self.write_register,), self.read_registers)
+      instruction_text = '{0} {1}'.format(self.opcode, ', '.join(reg_chain))
+      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 = []
+    self.instructions = [_InstructionTracker._Instruction(instr, i, self) for
+                         i, instr in enumerate(instructions)]
 
-    # figure out the RAW dependences and initialize the instructions list
-    dependence_state = {}
-    for i, instruction in enumerate(instructions):
-      dependences = list()
-      for register in instruction.read_registers:
-        if register in dependence_state:
-          dependences.append((state[register], register))
-      if instruction.write_register:
-        state[instruction.write_register] = i
-      self.instructions.append(_Instruction(instruction, i, self,
-            tuple(dependences)))
-
-  def issue_next(self, reorder_buffer, issue_stage):
-    if (self.next_instruction < len(self.instructions) and
+  def issue_next(self, reorder_buffer):
+    if (self._next_instruction < len(self.instructions) and
         not reorder_buffer.is_full()):
       reorder_buffer.add(self._next_instruction)
+      instruction = self.instructions[self._next_instruction]
+      instruction.issue()
       self._next_instruction += 1
-      return self._next_instruction - 1
-    else:
-      return None
 
   def update(self):
     self.cycle += 1
-    for instruction in instructions:
+    for instruction in self.instructions:
       instruction.update()
-    if instructions[-1].cur_state == 'CM':
+    if self.instructions[-1].cur_state == 'CM':
+      self.done = True
+    if self.cycle > 1000:
+      print "failed to stop"
       self.done = True
 
 class _ReorderBuffer:
     Holds instructions that are add()ed to it, lets you know if it is full, and
     can do a commit.
   """
-  def __init__(self, instruction_tracker, length=1e6):
+  def __init__(self, length=1e6):
     self.storage = list()
     self.length = length  # Default arg is basically infinity
-    self.instruction_tracker = instruction_tracker
 
   def add(self, instruction_number):
     if self.is_full():
   def is_full(self):
     return len(self.storage) >= self.length
 
-  def commit(self):
+  def commit(self, instruction_tracker):
     if len(self.storage) == 0:
       return
     head = self.storage[0]
-    if self.instruction_tracker.instructions[head].ready_to_commit():
-      self.instruction_tracker.instructions[head].commit()
+    if instruction_tracker.instructions[head].ready_to_commit():
+      instruction_tracker.instructions[head].commit()
       self.storage.pop(0)
 
+  def IS_instruction_iterator(self, instruction_tracker):
+    return itertools.ifilter(lambda i: i.cur_state == "IS",
+        itertools.imap(lambda i: instruction_tracker.instructions[i],
+          self.storage))
+
+  def WB_instruction_iterator(self, instruction_tracker):
+    return itertools.ifilter(lambda i: i.cur_state == "WB",
+        itertools.imap(lambda i: instruction_tracker.instructions[i],
+          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.current_instruction.execute()
+        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 = instruction_tracker.cycle
+      if current_cycle == self.end_cycle:
+        self.current_instruction.enqueue_for_writeback()
+        cdb.append(self.current_instruction)
+        self.start_instruction(current_cycle)
+      if not self.busy(current_cycle):
+        self.start_instruction(current_cycle)
+      for instruction in self.queue:
+        instruction.messages.add(('SD', self.name, self.current_instruction.index))
+
+    def enqueue(self, instruction):
+      self.queue.append(instruction)
+      instruction.enqueue_for_execute()
+
+  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):
+    self.opcode_map[instruction.opcode].enqueue(instruction)
+
+  def update(self, instruction_tracker, cdb):
+    for fu in self.fu_list:
+      fu.update(instruction_tracker, cdb)
+
+  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.
 
 
     Each instruction should be a tomasulo.Instruction.
   """
-  def issue(instruction):
-    instruction.issue
   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:
-    issue_stage
-# Issue next
-
+    # Set up next instruction to issue next time
+    instruction_tracker.issue_next(reorder_buffer)
 
-
-  return instruction_list
+    # 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.wait_in_reservation_station()
+          instruction.dependence_count += 1
+          reservation_station[register_file[register]].append(instruction.index)
+          instruction.messages.add(('RAW', register, register_file[register]))
+      if not has_dependence:
+        functional_units.enqueue(instruction)
+      register_file[instruction.write_register] = instruction.index
+
+    # Deal with EX stage
+    functional_units.update(instruction_tracker, cdb)
+
+    # 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)
+      instruction.writeback()
+      waiting_instructions = [instruction_tracker.instructions[i] for i in
+                              reservation_station[instruction.index]]
+      for instr in waiting_instructions:
+        instr.dependence_count -= 1
+        if instr.dependence_count == 0:
+          functional_units.enqueue(instr)
+      del reservation_station[instruction.index] 
+    # Deal with CM stage
+    reorder_buffer.commit(instruction_tracker)
+
+    instruction_tracker.update()
+
+# 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 (instruction_tracker.instructions[i] for i 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())