# Optimizer

unknown
python
2 years ago
24 kB
6
Indexable
Never
```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):

dim_x = data['x']
dim_y = data['y']
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):
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):
vtype=GRB.CONTINUOUS, lb=0, name='interference[%d][%d]' % (flow_id, flow_id_other))
for switch_id in range(num_switches):
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))
# 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)
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]]:

# 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])]:
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:
for port_id in active_output_port_ids[switch_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:
for port_id in active_output_port_ids[switch_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
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)
# TOP LEFT
elif is_top_left_switch(dim_y, switch_id):
#print("Switch ID %d is top left" % switch_id)
# TOP RIGHT
elif is_top_right_switch(dim_y, switch_id):
#print("Switch ID %d is top right" % switch_id)
# BOTTOM LEFT
elif is_bottom_left_switch(dim_y, switch_id):
#print("Switch ID %d is bottom left" % switch_id)
# BOTTOM RIGHT
elif is_bottom_right_switch(dim_y, switch_id):
#
# BOTTOM ROW
elif is_bottom_border_switch(dim_y, switch_id):
#print("Switch ID %d is bottom row" % switch_id)
# TOP ROW
elif is_top_border_switch(dim_y, switch_id):
#print("Switch ID %d is top row" % switch_id)
# LEFT ROW
elif is_left_border_switch(dim_y, switch_id):
#print("Switch ID %d is left row" % switch_id)
# RIGHT ROW
elif is_right_border_switch(dim_y, switch_id):
#print("Switch ID %d is right row" % switch_id)

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
#   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
else:
# port overlap is true if two flows pass the same port
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):
[
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):
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):
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
name="preempted[%d][%d]" % (flow_id, flow_id_other))
else:
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):
vtype=GRB.BINARY, name='coupling[%d][%d][%d]' % (flow_id, flow_id_intermediate, flow_id_other))
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):
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):
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):
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')```