Optimizer

 avatar
unknown
python
3 years ago
24 kB
9
Indexable
from typing import List, Any
import gurobipy as gp
from gurobipy import GRB
import json
from gurobipy.gurobipy import Model
import re

# Assuming that switches are counted starting from 0
# 6 = (0,0), 7 = (1,0), 8 = (2,0)
# 3 = (0,0), 4 = (1,0), 5 = (2,0)
# 0 = (0,0), 1 = (1,0), 2 = (2,0)

# Input: N 0, E 1, S 2, W 3
# Output: N 4, E 5, S 6, W 7

IN_NORTH = 0
IN_EAST = 1
IN_SOUTH = 2
IN_WEST = 3

OUT_NORTH = 4
OUT_EAST = 5
OUT_SOUTH = 6
OUT_WEST = 7


def route_to_string(routes):
    port_mapping = {
        0: 'IN_NORTH', 1: 'IN_EAST', 2: 'IN_SOUTH', 3: 'IN_WEST',
        4: 'OUT_NORTH', 5: 'OUT_EAST', 6: 'OUT_SOUTH', 7: 'OUT_WEST'}
    for route in routes:
        direction = "<-" if route[1] < 4 else "->"
        print("[%d]%s %s" % (route[0], direction, port_mapping[route[1]]))


def coord_x(dim: int, switch_id: int):
    return switch_id % dim


def coord_y(dim: int, switch_id: int):
    return int(switch_id / dim)


def is_inner_switch(dim, switch_id):
    if (0 < coord_x(dim, switch_id) < dim-1) \
            and (0 < coord_y(dim, switch_id) < dim-1):
        return True
    return False


def is_top_right_switch(dim, switch_id):
    if coord_x(dim, switch_id) == dim-1 and coord_y(dim, switch_id) == dim-1:
        return True
    return False


def is_top_left_switch(dim, switch_id):
    if coord_x(dim, switch_id) == 0 and coord_y(dim, switch_id) == dim-1:
        return True
    return False


def is_bottom_left_switch(dim, switch_id):
    if coord_x(dim, switch_id) == 0 and coord_y(dim, switch_id) == 0:
        return True
    return False


def is_bottom_right_switch(dim, switch_id):
    if coord_x(dim, switch_id) == dim-1 and coord_y(dim, switch_id) == 0:
        return True
    return False


def is_top_border_switch(dim, switch_id):
    if coord_x(dim, switch_id) in range(1, dim) and coord_y(dim, switch_id) == dim-1:
        return True
    return False


def is_bottom_border_switch(dim, switch_id):
    if coord_x(dim, switch_id) in range(1, dim) and coord_y(dim, switch_id) == 0:
        return True
    return False


def is_left_border_switch(dim, switch_id):
    if coord_x(dim, switch_id) in range(1, dim) and coord_y(dim, switch_id) == 0:
        return True
    return False


def is_right_border_switch(dim, switch_id):
    if coord_x(dim, switch_id) == dim-1 and coord_y(dim, switch_id) in range(1, dim):
        return True
    return False


def optimize(file):
    with open(file, "r") as read_file:
        data = json.load(read_file)

    dim_x = data['x']
    dim_y = data['y']
    deadlines = data['deadlines']
    periods = data['periods']
    source_switches = data['source']
    destination_switches = data['destination']
    active_input_port_ids = [data["input"][key] for key in sorted(data["input"].keys())]
    active_output_port_ids = [data["output"][key] for key in sorted(data["output"].keys())]
    # higher value implies higher priority
    priorities = data['priorities']
    num_flits = data['num_flits']
    # auxiliary variables
    num_flows = len(periods)
    num_switches = dim_x*dim_y
    num_ports = 8

    try:
        m = gp.Model('SP2-Routing-Optimizations')  # type: Model
        # priorities
        isHP = [[[] for x in range(num_flows)] for x in range(num_flows)]
        # passes[i][r][l] = 1 if flow i passes port l of router r -- and 0 otherwise : BINARY
        passes = [[[[] for x in range(num_ports)] for x in range(num_switches)] for x in range(num_flows)]
        # overlaps[i][j] = 1 if flow i and flow j share at least one link
        overlaps = [[[] for x in range(num_flows)] for x in range(num_flows)]
        # interference[i][j] = amount of interfernece of flow j to flow i
        interference = [[[] for x in range(num_flows)] for x in range(num_flows)]
        # preempted[i][j] = flow i is preempted by flow j, i.e., min(overlaps[i][j], isHP[i][j]): BINARY
        preempted = [[[] for x in range(num_flows)] for x in range(num_flows)]  # type: List[List[Any]]
        # not_preempted[i][j] = 1-preempted[i][j]
        not_preempted = [[[] for x in range(num_flows)] for x in range(num_flows)]  # type: List[List[Any]]
        # suspends[i][j] = flow j has ss behaviour wrt. flow i : BINARY
        suspended = [[[] for x in range(num_flows)] for x in range(num_flows)]
        # suspension_time[i] = flow i can expose suspension of at most that value
        suspension_time = [[] for x in range(num_flows)]
        # wcrt[i] = worst-case response-time of flow i
        wcrt = []
        # worst-case traversal time C[i] traversal time of flow i in hops
        wctt = []
        # port_overlap (overlapping ports)
        port_overlap = [[[[[] for x in range(num_ports)] for x in range(num_switches)] for x in range(num_flows)] for x
                        in range(num_flows)]
        # port_overlap (overlapping ports)
        port_overlap_switch = [[[[] for x in range(num_switches)] for x in range(num_flows)] for x in range(num_flows)]
        # coupling[i][k][j] = flow i and flow j are coupled by flow k in the following way:
        # coupling[i][k][j] == 1 if preempted[i][j] == 1 AND preempted[j][k] == 1 AND (1-preempted[i][k])
        coupling = [[[[] for x in range(num_flows)] for x in range(num_flows)] for x in range(num_flows)]

        for flow_id in range(num_flows):
            wcrt.append(m.addVar(vtype=GRB.CONTINUOUS, lb=0, name='wcrt %d' % flow_id))
            wctt.append(m.addVar(vtype=GRB.CONTINUOUS, lb=0, name='wctt %d' % flow_id))
            for switch_id in range(num_switches):
                for port_id in range(num_ports):
                    passes[flow_id][switch_id][port_id] = m.addVar(vtype=GRB.BINARY, name='passes %d %d %d' %
                                                                                          (flow_id, switch_id, port_id))
                    for flow_id_other in range(num_flows):
                        port_overlap[flow_id][flow_id_other][switch_id][port_id] = m.addVar(
                            vtype=GRB.BINARY, name='port_overlap[%d][%d][%d][%d]' % (flow_id, flow_id_other, switch_id, port_id))

        for flow_id in range(num_flows):
            for flow_id_other in range(num_flows):
                interference[flow_id][flow_id_other] = m.addVar(
                    vtype=GRB.CONTINUOUS, lb=0, name='interference[%d][%d]' % (flow_id, flow_id_other))
                for switch_id in range(num_switches):
                    port_overlap_switch[flow_id][flow_id_other][switch_id] = m.addVar(
                        vtype=GRB.BINARY, name='port_overlap_switch[%d][%d][%d]' % (flow_id, flow_id_other, switch_id))
            # create variables that depend on another flow
            for flow_id_other in range(num_flows):
                # 1 if flow 'flow_id' has higher-priority thant flow 'flow_id_other'
                isHP[flow_id][flow_id_other] = m.addVar(vtype=GRB.BINARY, name='isHP[%d][%d]' % (flow_id, flow_id_other))
                # true if flow i overlaps (shares at least one link) with flow j
                overlaps[flow_id][flow_id_other] = m.addVar(vtype=GRB.BINARY, name='overlaps[%d][%d]' % (flow_id, flow_id_other))
                preempted[flow_id][flow_id_other] = m.addVar(vtype=GRB.BINARY, name='preempted[%d][%d]' % (flow_id, flow_id_other))
                not_preempted[flow_id][flow_id_other] = m.addVar(vtype=GRB.BINARY, name='not_preempted[%d][%d]' % (flow_id, flow_id_other))
                suspended[flow_id][flow_id_other] = m.addVar(vtype=GRB.BINARY, name='suspended[%d][%d]' % (flow_id, flow_id_other))
                m.addConstr(not_preempted[flow_id][flow_id_other] == 1-preempted[flow_id][flow_id_other])
                # required auxiliary variable for AND constraints
                if priorities[flow_id] > priorities[flow_id_other]:
                    m.addConstr(isHP[flow_id][flow_id_other] == 1, name="isHP[%d][%d]" % (flow_id, flow_id_other))
                else:
                    m.addConstr(isHP[flow_id][flow_id_other] == 0, name="isHP[%d][%d]" % (flow_id, flow_id_other))
        # suspension_time, i.e., maximum suspension time of flow i, i.e., S_i = R_i-C_i
        for flow_id in range(num_flows):
            suspension_time[flow_id] = m.addVar(vtype=GRB.CONTINUOUS, name='suspension_time[%d]' % flow_id)
            m.addConstr(suspension_time[flow_id] == wcrt[flow_id] - wctt[flow_id])
            for switch_id in range(num_switches):
                for port_id in [x for x in range(num_ports) if x not in active_input_port_ids[switch_id] + active_output_port_ids[switch_id]]:
                    m.addConstr(passes[flow_id][switch_id][port_id] == 0, name="inactive ports")

            # port overlap pre processing here =>
            # port_overlap[flow_id][flow_id_other][switch_id][port_id] == 0 for all unusable ports
            for flow_id in range(num_flows):
                for flow_id_other in range(num_flows):
                    for switch_id in range(num_switches):
                            for port_id in [x for x in range(num_ports) if x not in (active_input_port_ids[switch_id] +
                                            active_output_port_ids[switch_id])]:
                                m.addConstr(port_overlap[flow_id][flow_id_other][switch_id][port_id] == 0,
                                            name="inactive ports")

        # assumption is that the input model already implies only
        # active ports, i.e., no west ports in bottom left switches
        for flow_id in range(num_flows):
            for switch_id in range(num_switches):
                # if switch 'switch_id' is the source of flow i then assure that
                # the flow leaves once and never rejoins
                if source_switches[flow_id] == switch_id:
                    m.addConstr(1 == gp.quicksum(passes[flow_id][switch_id][port_id]
                                                 for port_id in active_output_port_ids[switch_id]))
                    m.addConstr(0 == gp.quicksum(passes[flow_id][switch_id][port_id]
                                                 for port_id in active_input_port_ids[switch_id]))
                # if switch 'switch_id' is the destination of flow i then assure that
                # the flow enters once and never leaves
                elif destination_switches[flow_id] == switch_id:
                    m.addConstr(0 == gp.quicksum(passes[flow_id][switch_id][port_id]
                                                 for port_id in active_output_port_ids[switch_id]))
                    m.addConstr(1 == gp.quicksum(passes[flow_id][switch_id][port_id]
                                                 for port_id in active_input_port_ids[switch_id]))
                else:
                    # intermediate switch constraints: if a flow enters a switch then the flow needs
                    # to leave that switch
                    m.addConstr(
                        gp.quicksum(passes[flow_id][switch_id][port_id]
                                    for port_id in active_output_port_ids[switch_id])
                        == gp.quicksum(passes[flow_id][switch_id][port_id]
                                       for port_id in active_input_port_ids[switch_id]))

        # connect the ports ???
        # directions to ports with dim_x dim_y
        # if flow i uses R k  port
        # Assuming that switches are counted starting from 0
        # 6 = (0,0), 7 = (1,0), 8 = (2,0)
        # 3 = (0,0), 4 = (1,0), 5 = (2,0)
        # 0 = (0,0), 1 = (1,0), 2 = (2,0)
        # OUT_EAST passes[i][k][OUT_EAST] == passes[i][k+1][IN_WEST]
        # OUT_NORTH passes[i][k][OUT_NORTH] == passes[i][k+dim_x][IN_SOUTH]
        # OUT_SOUTH passes[i][k][OUT_SOUTH] == passes[i][k-dim_x][IN_NORTH]
        # OUT_WEST passes[i][k][OUT_WEST] == passes[i][k-1][IN_EAST]
        for flow_id in range(num_flows):
            for switch_id in range(num_switches):
                print(switch_id)
                # has all four portsNORTH
                if is_inner_switch(dim_y, switch_id):
                    #print("Switch ID %d is inner" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == passes[flow_id][switch_id+dim_y][IN_SOUTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id+1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == passes[flow_id][switch_id-dim_y][IN_NORTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == passes[flow_id][switch_id-1][IN_EAST])
                # TOP LEFT
                elif is_top_left_switch(dim_y, switch_id):
                    #print("Switch ID %d is top left" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id+1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == passes[flow_id][switch_id-dim_y][IN_NORTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == 0)
                # TOP RIGHT
                elif is_top_right_switch(dim_y, switch_id):
                    #print("Switch ID %d is top right" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == passes[flow_id][switch_id - dim_y][IN_NORTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == passes[flow_id][switch_id - 1][IN_EAST])
                # BOTTOM LEFT
                elif is_bottom_left_switch(dim_y, switch_id):
                    #print("Switch ID %d is bottom left" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == passes[flow_id][switch_id + dim_y][IN_SOUTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id + 1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == 0)
                # BOTTOM RIGHT
                elif is_bottom_right_switch(dim_y, switch_id):
                    #
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == passes[flow_id][switch_id + dim_y][IN_SOUTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == passes[flow_id][switch_id - 1][IN_EAST])
                # BOTTOM ROW
                elif is_bottom_border_switch(dim_y, switch_id):
                    #print("Switch ID %d is bottom row" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == passes[flow_id][switch_id + dim_y][IN_SOUTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id + 1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == passes[flow_id][switch_id - 1][IN_EAST])
                # TOP ROW
                elif is_top_border_switch(dim_y, switch_id):
                    #print("Switch ID %d is top row" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == 0)
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id + 1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == passes[flow_id][switch_id - dim_y][IN_NORTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == passes[flow_id][switch_id - 1][IN_EAST])
                # LEFT ROW
                elif is_left_border_switch(dim_y, switch_id):
                    #print("Switch ID %d is left row" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == passes[flow_id][switch_id + dim_y][IN_SOUTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id + 1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == passes[flow_id][switch_id - dim_y][IN_NORTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == 0)
                # RIGHT ROW
                elif is_right_border_switch(dim_y, switch_id):
                    #print("Switch ID %d is right row" % switch_id)
                    m.addConstr(passes[flow_id][switch_id][OUT_NORTH] == passes[flow_id][switch_id + dim_y][IN_SOUTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_EAST] == passes[flow_id][switch_id + 1][IN_WEST])
                    m.addConstr(passes[flow_id][switch_id][OUT_SOUTH] == passes[flow_id][switch_id - dim_y][IN_NORTH])
                    m.addConstr(passes[flow_id][switch_id][OUT_WEST] == 0)

        for flow_id in range(num_flows):
            max_route_length = abs(
                coord_x(dim_x, source_switches[flow_id])-coord_x(dim_x, destination_switches[flow_id]))+abs(
                coord_y(dim_y, source_switches[flow_id])-coord_y(dim_y, destination_switches[flow_id]))

            #max_used_ports = 2*max_route_length
            #m.addConstr(max_used_ports >= gp.quicksum(
             #   gp.quicksum(
              #      passes[flow_id][switch_id][port_id] for port_id in
               #     (active_input_port_ids[switch_id] + active_output_port_ids[switch_id]))
                #for switch_id in range(num_switches)), name="minimal route constraints")

        # OVERLAPS constraints
        for flow_id in range(num_flows):
            for flow_id_other in range(num_flows):
                for switch_id in range(num_switches):
                    for port_id in active_input_port_ids[switch_id] + active_output_port_ids[switch_id]:
                        if flow_id_other == flow_id:
                            # each flow overlaps with itself
                            m.addConstr(port_overlap[flow_id][flow_id_other][switch_id][port_id] == 1)
                        else:
                            # port overlap is true if two flows pass the same port
                            m.addGenConstrAnd(
                                port_overlap[flow_id][flow_id_other][switch_id][port_id],
                                [
                                    passes[flow_id][switch_id][port_id], passes[flow_id_other][switch_id][port_id]
                                ], name="overlap")

        for flow_id in range(num_flows):
            for flow_id_other in range(num_flows):
                for switch_id in range(num_switches):
                    m.addGenConstrOr(port_overlap_switch[flow_id][flow_id_other][switch_id],
                                      [
                                          port_overlap[flow_id][flow_id_other][switch_id][port_id] for port_id in range(num_ports)
                                      ], name="")

        for flow_id in range(num_flows):
            for flow_id_other in range(num_flows):
                m.addGenConstrOr(
                    overlaps[flow_id][flow_id_other],
                    [
                        port_overlap_switch[flow_id][flow_id_other][switch_id] for switch_id in range(num_switches)
                    ], name="overlap constraint")

        # worst-case traversal time constraints in SP2 are given by num_flits + (num_links-1)
        # = number of used switches and constraints
        for flow_id in range(num_flows):
            m.addConstr(wctt[flow_id] == num_flits[flow_id]+-1+0.5*(gp.quicksum(
                passes[flow_id][switch_id][port_id] for switch_id in range(num_switches) for port_id in range(num_ports))))
            # preemption constraints
            for flow_id_other in range(num_flows):
                if flow_id == flow_id_other:
                    # a flow does not preempt itself
                    m.addConstr(preempted[flow_id][flow_id_other] == 0,
                                name="preempted[%d][%d]" % (flow_id, flow_id_other))
                else:
                    m.addGenConstrAnd(
                        preempted[flow_id][flow_id_other],
                        [
                            overlaps[flow_id][flow_id_other], isHP[flow_id_other][flow_id]
                        ],
                        name="preempted[%d][%d]" % (flow_id, flow_id_other))

        for flow_id in range(num_flows):
            for flow_id_intermediate in range(num_flows):
                for flow_id_other in range(num_flows):
                    coupling[flow_id][flow_id_intermediate][flow_id_other] = m.addVar(
                        vtype=GRB.BINARY, name='coupling[%d][%d][%d]' % (flow_id, flow_id_intermediate, flow_id_other))
                    m.addGenConstrAnd(
                        coupling[flow_id][flow_id_intermediate][flow_id_other],
                        [
                            preempted[flow_id][flow_id_other],
                            preempted[flow_id_other][flow_id_intermediate],
                            not_preempted[flow_id][flow_id_intermediate]
                        ], name="coupling constraint")

        for flow_id in range(num_flows):
            for flow_id_other in range(num_flows):
                m.addGenConstrOr(
                    suspended[flow_id][flow_id_other],
                    [
                        coupling[flow_id][k][flow_id_other] for k in range(num_flows)
                    ], name="suspended[%d][%d]" % (flow_id, flow_id_other))

        # Ui t + Ci + Ui * suspension_time
        # Ui(Rk+(Ri-Ci)) + Ci
        # consider flow k in interference analysis of flow i if
        # contribution

        for flow_id in range(num_flows):
            for flow_id_other in range(num_flows):
                m.addConstr(
                    interference[flow_id][flow_id_other] == (wctt[flow_id_other]/periods[flow_id_other]) *
                    (wcrt[flow_id]+wcrt[flow_id_other]-wctt[flow_id_other]) + wctt[flow_id_other])

        for flow_id in range(num_flows):
            m.addConstr(wcrt[flow_id] <= deadlines[flow_id])
            m.addConstr(
                wcrt[flow_id] == wctt[flow_id]+gp.quicksum(
                    preempted[flow_id][flow_id_other] * interference[flow_id][flow_id_other]
                    for flow_id_other in range(num_flows)), name="WCRT constraint")
        # optimization settings
        m.setObjective(1.0, GRB.MAXIMIZE)
        m.setParam("NonConvex", 2)
        m.optimize()

        if m.status == GRB.OPTIMAL:
            final_routes = [[] for x in range(num_flows)]
            routes = [var for var in m.getVars() if var.varName.find('passes') != -1 and var.x != 0]
            wctts = [var for var in m.getVars() if var.varName.find('wctt') != -1 and var.x != 0]
            wcrts = [var for var in m.getVars() if var.varName.find('wcrt') != -1 and var.x != 0]

            for i, wctt in enumerate(wctts):
                wctts[i] = wctt.x

            for i, wcrt in enumerate(wcrts):
                wcrts[i] = wcrt.x

            for route in routes:
                parsed = route.varName.split(' ')
                flow_id = int(parsed[1])
                switch_id = int(parsed[2])
                port_id = int(parsed[3])
                final_routes[flow_id].append((switch_id, port_id))

            for flow_id in range(num_flows):
                print("Flow ID %d [%d -> %d]" % (flow_id, source_switches[flow_id], destination_switches[flow_id]))
                route_to_string(final_routes[flow_id])

    except gp.GurobiError as e:
        print(e)

    except AttributeError as e:
        print(e)


optimize('experiment_2_file.json')
Editor is loading...