Better schedule, including plotting

• plot_schedule method that plots the schedule
• forward_slack and backward_slack
• Execution times supported
• Slightly different graph_id that more often do not change the previous
• scipy is now a dependency for drawing splines

Close #35 (closed)

b_asic/schema.py

@@ -3,11 +3,18 @@
 Contains the schema class for scheduling operations in an SFG.
 """
 
-from typing import Dict, List, Optional
+from collections import defaultdict
+from typing import Dict, List, Optional, Tuple
+import matplotlib.pyplot as plt
+from matplotlib.ticker import MaxNLocator
+import numpy as np
+from scipy import interpolate
+import sys
+import io
 
 from b_asic.signal_flow_graph import SFG
 from b_asic.graph_component import GraphID
-from b_asic.operation import Operation
+from b_asic.special_operations import Delay, Output
 
 
 class Schema:
@@ -24,7 +31,7 @@ class Schema:
         """Construct a Schema from an SFG."""
         self._sfg = sfg
         self._start_times = dict()
-        self._laps = dict()
+        self._laps = defaultdict(lambda: 0)
         self._cyclic = cyclic
         self._resolution = resolution
 
@@ -34,12 +41,7 @@ class Schema:
             raise NotImplementedError(
                 f"No algorithm with name: {scheduling_alg} defined.")
 
-        max_end_time = 0
-        for op_id, op_start_time in self._start_times.items():
-            op = self._sfg.find_by_id(op_id)
-            for outport in op.outputs:
-                max_end_time = max(
-                    max_end_time, op_start_time + outport.latency_offset)
+        max_end_time = self._get_max_end_time()
 
         if not self._cyclic:
             if schedule_time is None:
@@ -55,15 +57,153 @@ class Schema:
         assert op_id in self._start_times, "No operation with the specified op_id in this schema."
         return self._start_times[op_id]
 
+    def _get_max_end_time(self) -> int:
+        max_end_time = 0
+        for op_id, op_start_time in self._start_times.items():
+            op = self._sfg.find_by_id(op_id)
+            for outport in op.outputs:
+                max_end_time = max(
+                    max_end_time, op_start_time + outport.latency_offset)
+        return max_end_time
+
     def forward_slack(self, op_id: GraphID) -> int:
-        raise NotImplementedError
+        assert op_id in self._start_times, "No operation with the specified op_id in this schema."
+        slack = sys.maxsize
+        output_slacks = self._forward_slacks(op_id)
+        # Make more pythonic
+        for signal_slacks in output_slacks.values():
+            for signal_slack in signal_slacks.values():
+                slack = min(slack, signal_slack)
+        return slack
+
+    def _forward_slacks(self, op_id: GraphID) -> Dict["OutputPort", Dict["Signal", int]]:
+        ret = dict()
+        start_time = self._start_times[op_id]
+        op = self._sfg.find_by_id(op_id)
+        for output_port in op.outputs:
+            output_slacks = dict()
+            available_time = start_time + output_port.latency_offset
+
+            for signal in output_port.signals:
+                usage_time = (signal.destination.latency_offset +
+                             self._start_times[signal.destination.operation.graph_id] +
+                             self._schedule_time*self._laps[signal.graph_id])
+                output_slacks[signal] = usage_time - available_time
+            ret[output_port] = output_slacks
+        return ret
 
     def backward_slack(self, op_id: GraphID) -> int:
-        raise NotImplementedError
+        assert op_id in self._start_times, "No operation with the specified op_id in this schema."
+        slack = sys.maxsize
+        input_slacks = self._backward_slacks(op_id)
+        # Make more pythonic
+        for signal_slacks in input_slacks.values():
+            for signal_slack in signal_slacks.values():
+                slack = min(slack, signal_slack)
+        return slack
+
+    def _backward_slacks(self, op_id: GraphID) -> Dict["OutputPort", Dict["Signal", int]]:
+        ret = dict()
+        start_time = self._start_times[op_id]
+        op = self._sfg.find_by_id(op_id)
+        for input_port in op.inputs:
+            input_slacks = dict()
+            usage_time = start_time + input_port.latency_offset
+
+            for signal in input_port.signals:
+                available_time = (signal.source.latency_offset +
+                             self._start_times[signal.source.operation.graph_id] -
+                             self._schedule_time*self._laps[signal.graph_id])
+                input_slacks[signal] = usage_time - available_time
+            ret[input_port] = input_slacks
+        return ret
+
+
+    def slacks(self, op_id: GraphID) -> Tuple[int, int]:
+        assert op_id in self._start_times, "No operation with the specified op_id in this schema."
+        return (self.backward_slack(op_id), self.forward_slack(op_id))
 
     def print_slacks(self) -> None:
         raise NotImplementedError
 
+    def set_schedule_time(self, time: int) -> "Schema":
+        assert self._get_max_end_time() < time, "New schedule time to short."
+        self._schedule_time = time
+        return self
+
+    @property
+    def schedule_time(self) -> int:
+        return self._schedule_time
+
+    def increase_time_resolution(self, factor: int) -> "Schema":
+        raise NotImplementedError
+
+    def decrease_time_resolution(self, factor: int) -> "Schema":
+        raise NotImplementedError
+
+    def move_operation(self, op_id: GraphID, time: int) -> "Schema":
+        assert op_id in self._start_times, "No operation with the specified op_id in this schema."
+
+        (backward_slack, forward_slack) = self.slacks(op_id)
+        if time < 0:
+            if -time > backward_slack:
+                raise ValueError
+        else:
+            if time > forward_slack:
+                raise ValueError
+
+        tmp_start = self._start_times[op_id] + time
+        new_start = tmp_start % self._schedule_time
+
+        # Update input laps
+        input_slacks = self._backward_slacks(op_id)
+        for in_port, signal_slacks in input_slacks.items():
+            tmp_usage = tmp_start + in_port.latency_offset
+            new_usage = tmp_usage % self._schedule_time
+            for signal, signal_slack in signal_slacks.items():
+                new_slack = signal_slack + time
+                old_laps = self._laps[signal.graph_id]
+                tmp_prev_available = tmp_usage - new_slack
+                prev_available = tmp_prev_available % self._schedule_time
+                laps = new_slack // self._schedule_time
+                if new_usage < prev_available:
+                    laps += 1
+                print([signal_slack, new_slack, old_laps, laps, new_usage, prev_available, tmp_usage, tmp_prev_available])
+                self._laps[signal.graph_id] = laps
+
+        # Update output laps
+        output_slacks = self._forward_slacks(op_id)
+        for out_port, signal_slacks in output_slacks.items():
+            tmp_available = tmp_start + out_port.latency_offset
+            new_available = tmp_available % self._schedule_time
+            for signal, signal_slack in signal_slacks.items():
+                new_slack = signal_slack - time
+                tmp_next_usage = tmp_available + new_slack
+                next_usage = tmp_next_usage % self._schedule_time
+                laps = new_slack // self._schedule_time
+                if next_usage < new_available:
+                    laps += 1
+                if new_available == 0 and new_slack > 0:
+                    laps += 1
+                self._laps[signal.graph_id] = laps
+
+
+        # Set new start time
+        self._start_times[op_id] = new_start
+        return self
+
+    def _remove_delays(self) -> None:
+        delay_list = self._sfg.find_by_type_name(Delay.type_name())
+        while delay_list:
+            delay_op = delay_list[0]
+            delay_input_id = delay_op.input(0).signals[0].graph_id
+            delay_output_ids = [sig.graph_id for sig in delay_op.output(0).signals]
+            self._sfg = self._sfg.remove_operation(delay_op.graph_id)
+            for output_id in delay_output_ids:
+                self._laps[output_id] += 1 + self._laps[delay_input_id]
+            del self._laps[delay_input_id]
+            delay_list = self._sfg.find_by_type_name(Delay.type_name())
+
     def _schedule_asap(self) -> None:
         pl = self._sfg.get_precedence_list()
 
@@ -71,11 +211,19 @@ class Schema:
             print("Empty signal flow graph cannot be scheduled.")
             return
 
-        non_schedulable_ops = set((outp.operation.graph_id for outp in pl[0]))
+        non_schedulable_ops = set()
+        for outport in pl[0]:
+            op = outport.operation
+            if op.type_name()  not in [Delay.type_name()]:
+                if op.graph_id not in self._start_times:
+                    # Set start time of all operations in the first iter to 0
+                    self._start_times[op.graph_id] = 0
+            else:
+                non_schedulable_ops.add(op.graph_id)
 
         for outport in pl[1]:
             op = outport.operation
-            if op not in self._start_times:
+            if op.graph_id not in self._start_times:
                 # Set start time of all operations in the first iter to 0
                 self._start_times[op.graph_id] = 0
 
@@ -86,7 +234,6 @@ class Schema:
                     # Schedule the operation if it doesn't have a start time yet.
                     op_start_time = 0
                     for inport in op.inputs:
-                        print(inport.operation.graph_id)
                         assert len(
                             inport.signals) == 1, "Error in scheduling, dangling input port detected."
                         assert inport.signals[0].source is not None, "Error in scheduling, signal with no source detected."
@@ -110,3 +257,106 @@ class Schema:
                             op_start_time, op_start_time_from_in)
 
                     self._start_times[op.graph_id] = op_start_time
+        for output in self._sfg.find_by_type_name(Output.type_name()):
+            source_port = output.inputs[0].signals[0].source
+            if source_port.operation.graph_id in non_schedulable_ops:
+                self._start_times[output.graph_id] = 0
+            else:
+                self._start_times[output.graph_id] = self._start_times[source_port.operation.graph_id] + source_port.latency_offset
+        self._remove_delays()
+
+    def _plot_schedule(self):
+        def _draw_arrow2(start, end):
+            if end[0] < start[0]: # Wrap around
+                plt.plot([start[0], self._schedule_time], [start[1], start[1]])
+                plt.plot([0, end[0]], [end[1], end[1]])
+            elif end[0] == start[0]:
+                plt.plot([start[0], start[0] + 0.2, start[0] + 0.2, start[0] - 0.2, start[0] - 0.2, start[0]],
+                         [start[1], start[1], (start[1] + end[1])/2, (start[1] + end[1])/2, end[1], end[1]])
+            else:
+                plt.plot([start[0], (start[0] + end[0])/2, (start[0] + end[0])/2, end[0]],
+                         [start[1], start[1], end[1], end[1]])
+
+        def _draw_spline(x, y):
+            l = len(x)
+            t = np.linspace(0, 1, l-2, endpoint=True)
+            t = np.append([0, 0, 0], t)
+            t = np.append(t, [1, 1, 1])
+            tck = [t, [x, y], 3]
+            u3 = np.linspace(0, 1, 50, endpoint=True)
+            out = interpolate.splev(u3, tck)
+            plt.plot(out[0], out[1], color='black')
+
+        def _draw_arrow(start, end, name="", laps=0):
+            if end[0] < start[0] or laps > 0: # Wrap around
+                plt.plot([start[0], self._schedule_time + 0.2], [start[1], start[1]], color='black')
+                plt.plot([-0.2, end[0]], [end[1], end[1]], color='black')
+                plt.text(self._schedule_time + 0.2, start[1], name, verticalalignment='center')
+                plt.text(-0.2, end[1], "{}: {}".format(name, laps), verticalalignment='center', horizontalalignment='right')
+
+            elif end[0] == start[0]:
+                _draw_spline([start[0], start[0] + 0.2, start[0] + 0.2, start[0] - 0.2, start[0] - 0.2, start[0]],
+                             [start[1], start[1], (start[1] + end[1])/2, (start[1] + end[1])/2, end[1], end[1]])
+            else:
+                _draw_spline([start[0], (start[0] + end[0])/2, (start[0] + end[0])/2, end[0]],
+                             [start[1], start[1], end[1], end[1]])
+
+        def _draw_offset_arrow(start, end, start_offset, end_offset, name="", laps=0):
+            _draw_arrow([start[0] + start_offset[0], start[1] + start_offset[1]],
+                        [end[0] + end_offset[0], end[1] + end_offset[1]], name=name, laps=laps)
+
+        ypos = 0.5
+        ytickpositions = []
+        yticklabels = []
+        plt.grid(zorder=0.5)
+        ypositions = dict()
+        for op_id, op_start_time in self._start_times.items():
+            op = self._sfg.find_by_id(op_id)
+            latency_coords, execution_time_coords = op.get_plot_coordinates()
+            _x, _y = zip(*latency_coords)
+            x = np.array(_x)
+            y = np.array(_y)
+            plt.fill(x + op_start_time, y + ypos)
+            _x, _y = zip(*execution_time_coords)
+            x = np.array(_x)
+            y = np.array(_y)
+            plt.plot(x + op_start_time, y + ypos, color='black', linewidth=3, alpha=0.5)
+            ytickpositions.append(ypos + 0.5)
+            yticklabels.append(self._sfg.find_by_id(op_id).name)
+            ypositions[op_id] = ypos
+            ypos += 1.5
+
+        for op_id, op_start_time in self._start_times.items():
+            op = self._sfg.find_by_id(op_id)
+            _, out_coords = op.get_io_coordinates()
+            source_ypos = ypositions[op_id]
+            for output_port in op.outputs:
+                for output_signal in output_port.signals:
+                    dest_op = output_signal.destination.operation
+                    dest_start_time = self._start_times[dest_op.graph_id]
+                    dest_ypos = ypositions[dest_op.graph_id]
+                    dest_in_coords, _ = output_signal.destination.operation.get_io_coordinates()
+                    _draw_offset_arrow(out_coords[output_port.index],
+                                       dest_in_coords[output_signal.destination.index],
+                                       [op_start_time, source_ypos],
+                                       [dest_start_time, dest_ypos], name=op_id,
+                                       laps=self._laps[output_signal.graph_id])
+
+        plt.yticks(ytickpositions, yticklabels)
+        plt.axis([-1, self._schedule_time+1, 0, ypos])
+        plt.gca().xaxis.set_major_locator(MaxNLocator(integer=True))
+        plt.plot([0, 0], [0, ypos], linestyle='--', color='black')
+        plt.plot([self._schedule_time, self._schedule_time], [0, ypos], linestyle='--', color='black')
+
+    def plot_schedule(self) -> None:
+        plt.figure()
+        self._plot_schedule()
+        plt.show()
+
+    def _repr_svg_(self):
+        plt.figure()
+        self._plot_schedule()
+        f = io.StringIO()
+        plt.savefig(f, format='svg')
+
+        return f.getvalue()