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