Optimizer
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...