| import statistics |
| |
| from copy import deepcopy |
| from collections import defaultdict, namedtuple |
| |
| from data_structs import VprSwitch, MuxEdgeTiming, DriverTiming, SinkTiming |
| from utils import yield_muxes, add_named_item |
| |
| # ============================================================================= |
| |
| |
| def linear_regression(xs, ys): |
| """ |
| Computes linear regression coefficients |
| https://en.wikipedia.org/wiki/Simple_linear_regression |
| |
| Returns a and b coefficients of the function f(y) = a * x + b |
| """ |
| x_mean = statistics.mean(xs) |
| y_mean = statistics.mean(ys) |
| |
| num, den = 0.0, 0.0 |
| for x, y in zip(xs, ys): |
| num += (x - x_mean) * (y - y_mean) |
| den += (x - x_mean) * (x - x_mean) |
| |
| a = num / den |
| b = y_mean - a * x_mean |
| |
| return a, b |
| |
| |
| # ============================================================================= |
| |
| |
| def create_vpr_switch(type, tdel, r, c): |
| """ |
| Creates a VPR switch with the given parameters. Autmatically generates |
| its name with these parameters encoded. |
| |
| The VPR switch parameters are: |
| - type: Switch type. See VPR docs for the available types |
| - tdel: Constant propagation delay [s] |
| - r: Internal resistance [ohm] |
| - c: Internal capacitance (active only when the switch is "on") [F] |
| """ |
| |
| # Format the switch name |
| name = ["sw"] |
| name += ["T{:>08.6f}".format(tdel * 1e9)] |
| name += ["R{:>08.6f}".format(r)] |
| name += ["C{:>010.6f}".format(c * 1e12)] |
| |
| # Create the VPR switch |
| switch = VprSwitch( |
| name="_".join(name), |
| type=type, |
| t_del=tdel, |
| r=r, |
| c_in=0.0, |
| c_out=0.0, |
| c_int=c, |
| ) |
| |
| return switch |
| |
| |
| def compute_switchbox_timing_model(switchbox, timing_data): |
| """ |
| Processes switchbox timing data. |
| |
| The timing data is provided in a form of delays for each mux edge (path |
| from its input pin to the output pin). The delay varies with number of |
| active loads of the source. |
| |
| This data is used to compute driver resistances and load capacitances |
| as well as constant propagation delays. |
| |
| The timing model assumes that each output of a mux has a certain resistance |
| and constant propagation time. Then, every load has a capacitance which is |
| connected when it is active. All capacitances are identical. The input |
| timing data does not allow to distinguish between them. Additionally, each |
| load can have a constant propagation delay. |
| |
| For multiplexers that are driver by switchbox inputs, fake drivers are |
| assumed solely for the purpose of the timing model. |
| """ |
| |
| # A helper struct |
| Timing = namedtuple("Timing", "driver_r driver_tdel sink_c sink_tdel") |
| |
| # Delay scaling factor |
| FACTOR = 1.0 |
| |
| # Error threshold (for reporting) in ns |
| ERROR_THRESHOLD = 0.4 * 1e-9 |
| |
| # Build a map of sinks for each driver |
| # For internal drivers key = (stage_id, switch_id, mux_id) |
| # For external drivers key = (stage_id, input_name) |
| sink_map = defaultdict(lambda: []) |
| |
| for connection in switchbox.connections: |
| src = connection.src |
| dst = connection.dst |
| |
| dst_key = (dst.stage_id, dst.switch_id, dst.mux_id, dst.pin_id) |
| src_key = (src.stage_id, src.switch_id, src.mux_id) |
| |
| sink_map[src_key].append(dst_key) |
| |
| for pin in switchbox.inputs.values(): |
| for loc in pin.locs: |
| |
| dst_key = (loc.stage_id, loc.switch_id, loc.mux_id, loc.pin_id) |
| src_key = (loc.stage_id, pin.name) |
| |
| sink_map[src_key].append(dst_key) |
| |
| # Compute timing model for each driver |
| driver_timing = {} |
| for driver, sinks in sink_map.items(): |
| |
| # Collect timing data for each sink edge |
| edge_timings = {} |
| for stage_id, switch_id, mux_id, pin_id in sinks: |
| |
| # Try getting timing data. If not found then probably we are |
| # computing timing for VCC or GND input. |
| try: |
| data = timing_data[stage_id][switch_id][mux_id][pin_id] |
| except KeyError: |
| continue |
| |
| # Sanity check. The number of load counts must be equal to the |
| # number of sinks for the driver. |
| assert len(data) == len(sinks) |
| |
| # Take the worst case (max), convert ns to seconds. |
| data = {n: max(d) * 1e-9 for n, d in data.items()} |
| |
| # Store |
| key = (stage_id, switch_id, mux_id, pin_id) |
| edge_timings[key] = data |
| |
| # No timing data, probably it is a VCC or GND input |
| if not len(edge_timings): |
| continue |
| |
| # Compute linear regression for each sink data |
| coeffs = {} |
| for sink in sinks: |
| xs = sorted(edge_timings[sink].keys()) |
| ys = [edge_timings[sink][x] for x in xs] |
| |
| a, b = linear_regression(xs, ys) |
| |
| # Cannot have a < 0 (decreasing relation). If such thing happens |
| # force the regression line to be flat. |
| if a < 0.0: |
| print( |
| "WARNING: For '{} {}' the delay model slope is negative! (a={:.2e})" |
| .format(switchbox.type, sink, a) |
| ) |
| a = 0.0 |
| |
| # Cannot have any delay higher than the model. Check if all delays |
| # lie below the regression line and if not then shift the line up |
| # accordingly. |
| for x, y in zip(xs, ys): |
| t = a * x + b |
| if y > t: |
| b += y - t |
| |
| coeffs[sink] = (a, b) |
| |
| # Assumed driver resistance [ohm] |
| driver_r = 1.0 |
| |
| # Compute driver's Tdel |
| driver_tdel = min([cfs[1] for cfs in coeffs.values()]) |
| |
| # Compute per-sink Tdel |
| sink_tdel = {s: cfs[1] - driver_tdel for s, cfs in coeffs.items()} |
| |
| # Compute sink capacitance. Since we have multiple edge timings that |
| # should yield the same capacitance, compute one for each timing and |
| # then choose the worst case (max). |
| sink_cs = { |
| s: (cfs[0] / (FACTOR * driver_r) - sink_tdel[s]) |
| for s, cfs in coeffs.items() |
| } |
| sink_c = max(sink_cs.values()) |
| |
| # Sanity check |
| assert sink_c >= 0.0, (switchbox.type, sink, sink_c) |
| |
| # Compute error of the delay model |
| for sink in sinks: |
| |
| # Compute for this sink |
| error = {} |
| for n, true_delay in edge_timings[sink].items(): |
| model_delay = driver_tdel + FACTOR * driver_r * sink_c * n + sink_tdel[ |
| sink] |
| error[n] = true_delay - model_delay |
| |
| max_error = max([abs(e) for e in error.values()]) |
| |
| # Report the error |
| if max_error > ERROR_THRESHOLD: |
| print( |
| "WARNING: Error of the timing model of '{} {}' is too high:" |
| .format(switchbox.type, sink) |
| ) |
| print("--------------------------------------------") |
| print("| # loads | actual | model | error |") |
| print("|---------+----------+----------+----------|") |
| |
| for n in edge_timings[sink].keys(): |
| print( |
| "| {:<8}| {:<9.3f}| {:<9.3f}| {:<9.3f}|".format( |
| n, 1e9 * edge_timings[sink][n], |
| 1e9 * (edge_timings[sink][n] - error[n]), |
| 1e9 * error[n] |
| ) |
| ) |
| |
| print("--------------------------------------------") |
| print("") |
| |
| # Store the data |
| driver_timing[driver] = Timing( |
| driver_r=driver_r, |
| driver_tdel=driver_tdel, |
| sink_tdel={s: d |
| for s, d in sink_tdel.items()}, |
| sink_c=sink_c |
| ) |
| |
| return driver_timing, sink_map |
| |
| |
| def populate_switchbox_timing( |
| switchbox, driver_timing, sink_map, vpr_switches |
| ): |
| """ |
| Populates the switchbox timing model by annotating its muxes with the timing |
| data. Creates new VPR switches with required parameters or uses existing |
| ones if already created. |
| """ |
| |
| # Populate timing data to the switchbox |
| for driver, timing in driver_timing.items(): |
| |
| # Driver VPR switch |
| driver_vpr_switch = create_vpr_switch( |
| type="mux", |
| tdel=timing.driver_tdel, |
| r=timing.driver_r, |
| c=0.0, |
| ) |
| |
| driver_vpr_switch = add_named_item( |
| vpr_switches, driver_vpr_switch, driver_vpr_switch.name |
| ) |
| |
| # Annotate all driver's edges |
| for sink in sink_map[driver]: |
| stage_id, switch_id, mux_id, pin_id = sink |
| |
| # Sink VPR switch |
| sink_vpr_switch = create_vpr_switch( |
| type="mux", |
| tdel=timing.sink_tdel[sink], |
| r=0.0, |
| c=timing.sink_c, |
| ) |
| |
| sink_vpr_switch = add_named_item( |
| vpr_switches, sink_vpr_switch, sink_vpr_switch.name |
| ) |
| |
| # Get the mux |
| stage = switchbox.stages[stage_id] |
| switch = stage.switches[switch_id] |
| mux = switch.muxes[mux_id] |
| |
| assert pin_id not in mux.timing |
| |
| mux.timing[pin_id] = MuxEdgeTiming( |
| driver=DriverTiming( |
| tdel=timing.driver_tdel, |
| r=timing.driver_r, |
| vpr_switch=driver_vpr_switch.name |
| ), |
| sink=SinkTiming( |
| tdel=timing.sink_tdel, |
| c=timing.sink_c, |
| vpr_switch=sink_vpr_switch.name |
| ) |
| ) |
| |
| |
| def copy_switchbox_timing(src_switchbox, dst_switchbox): |
| """ |
| Copies all timing information from the source switchbox to the destination |
| one. |
| """ |
| |
| # Mux timing |
| for dst_stage, dst_switch, dst_mux in yield_muxes(dst_switchbox): |
| |
| src_stage = src_switchbox.stages[dst_stage.id] |
| src_switch = src_stage.switches[dst_switch.id] |
| src_mux = src_switch.muxes[dst_mux.id] |
| |
| dst_mux.timing = deepcopy(src_mux.timing) |
| |
| |
| # ============================================================================= |
| |
| |
| def add_vpr_switches_for_cell(cell_type, cell_timings): |
| """ |
| Creates VPR switches for IOPATH delays read from SDF file(s) for the given |
| cell type. |
| """ |
| |
| # Filter timings for the cell |
| timings = { |
| k: v |
| for k, v in cell_timings.items() |
| if k.startswith(cell_type) |
| } |
| |
| # Add VPR switches |
| vpr_switches = {} |
| for celltype, cell_data in timings.items(): |
| for instance, inst_data in cell_data.items(): |
| |
| # Add IOPATHs |
| for timing, timing_data in inst_data.items(): |
| if timing_data["type"].lower() != "iopath": |
| continue |
| |
| # Get data |
| name = "{}.{}.{}.{}".format( |
| cell_type, instance, timing_data["from_pin"], |
| timing_data["to_pin"] |
| ) |
| tdel = timing_data["delay_paths"]["slow"]["avg"] |
| |
| # Add the switch |
| sw = VprSwitch( |
| name=name, |
| type="mux", |
| t_del=tdel, |
| r=0.0, |
| c_in=0.0, |
| c_out=0.0, |
| c_int=0.0, |
| ) |
| vpr_switches[sw.name] = sw |
| |
| return vpr_switches |
