sct.py 8.97 KiB
import networkx as nx
import scipy as sc
from scipy.optimize import linprog
from etf import etf
#from cylp.cy import CyClpSimplex
from cvxopt import spmatrix, matrix, solvers
def to_float(arr):
return [float(temp) for temp in arr]
def append_val(col, row_count, val, LHS_VAL, LHS_I, LHS_J):
LHS_J.append(row_count)
LHS_I.append(col)
LHS_VAL.append(val)
def small_example():
'''
G = nx.DiGraph()
G.add_node(1, weight=3, favor=-1, parent= 0, id=1)
G.add_node(2, weight=5, favor=-1, parent= 0, id=2)
G.add_node(3, weight=6, favor=-1, parent= 0, id=3)
G.add_node(4, weight=4, favor=-1, parent= 0, id=4)
G.add_node(5, weight=4, favor=-1, parent= 0, id=5)
G.add_node(6, weight=3, favor=-1, parent= 0, id=6)
G.add_node(7, weight=4, favor=-1, parent= 0, id=7)
G.add_edge(1, 3, weight=2, id=1)
G.add_edge(1, 4, weight=3, id=2)
G.add_edge(2, 4, weight=2, id=3)
G.add_edge(2, 5, weight=2, id=4)
G.add_edge(3, 6, weight=3, id=5)
G.add_edge(3, 7, weight=3, id=6)
G.add_edge(4, 6, weight=1, id=7)
G.add_edge(4, 7, weight=3, id=8)
'''
P = nx.DiGraph()
P.add_node(1, id=1, l=-1, s='free', size=0.0)
P.add_node(2, id=2, l=-1, s='free', size=0.0)
P.add_node(3, id=3, l=-1, s='free', size=0.0)
P.add_edge(1, 1, weight=0)
P.add_edge(2, 2, weight=0)
P.add_edge(3, 3, weight=0)
P.add_edge(1, 2, weight=1)
P.add_edge(1, 3, weight=1)
P.add_edge(2, 3, weight=1)
P.add_edge(2, 1, weight=1)
P.add_edge(3, 1, weight=1)
P.add_edge(3, 2, weight=1)
G = nx.DiGraph()
G.add_node(1, weight=6, id=1, memory=1.0, parent=0)
G.add_node(2, weight=7, id=2, memory=1.0, parent=0)
G.add_node(3, weight=9, id=3, memory=1.0, parent=0)
G.add_node(4, weight=8, id=4, memory=1.0, parent=0)
G.add_node(5, weight=10, id=5, memory=1.0, parent=0)
G.add_node(6, weight=6, id=6, memory=1.0, parent=0)
G.add_node(7, weight=6, id=7, memory=1.0, parent=0)
G.add_node(8, weight=10, id=8, memory=1.0, parent=0)
G.add_node(9, weight=6, id=9, memory=1.0, parent=0)
G.add_edge(1, 3, weight=1, id=1)
G.add_edge(1, 4, weight=5, id=2)
G.add_edge(1, 5, weight=2, id=3)
G.add_edge(2, 3, weight=1, id=4)
G.add_edge(2, 4, weight=1, id=5)
G.add_edge(2, 5, weight=1, id=6)
G.add_edge(3, 6, weight=5, id=7)
G.add_edge(3, 7, weight=3, id=8)
G.add_edge(4, 6, weight=4, id=9)
G.add_edge(4, 7, weight=1, id=10)
G.add_edge(4, 8, weight=5, id=11)
G.add_edge(5, 9, weight=1, id=12)
return G, P
def sct(_G, _P, max_size):
G = _G
P = _P
'''
G, P = small_example()
'''
#calculate favorite child
favor_child = lp(G)
idx = 0
for node in G.nodes:
G.nodes[node]['favor'] = -1
for (i, j) in G.edges:
if favor_child[idx] == 0:
G.nodes[i]['favor'] = j
idx += 1
#sets
S = []
R = [T for T in G.nodes if G.in_degree[T] == 0]
ready = {}
urgent = {}
#main loop
time = 0
while(len(S) != G.number_of_nodes()):
#calculate ready time and urgent time
for T in R:
for proc in P.nodes:
r_time = 0
for pre in G.in_edges(T):
pre = pre[0]
t = G.nodes[pre]['t']
p = G.nodes[pre]['weight']
c = G[pre][T]['weight']
if G.nodes[pre]['p'] == proc:
r_time = max(r_time, t + p)
else:
r_time = max(r_time, t + p + c)
ready[(T, proc)] = r_time
for T in R:
u_time = 0
for pre in G.in_edges(T):
pre = pre[0]
t = G.nodes[pre]['t']
p = G.nodes[pre]['weight']
c = G[pre][T]['weight']
u_time = max(u_time, t + p + c)
urgent[T] = u_time
#calculate state of processor
for proc in P.nodes:
p = P.nodes[proc]
if p['l'] != -1:
T = p['l']
if G.nodes[T]['t'] + G.nodes[T]['weight'] > time:
p['s'] = 'busy'
elif G.nodes[T]['favor'] != -1:
favor = G.nodes[T]['favor']
if favor in R and ready[(favor, proc)] < urgent[favor]:
p['s'] = 'awake'
else:
p['s'] = 'free'
else:
p['s'] = 'free'
# print(p)
#schedule
avail = []
for proc in P.nodes:
p = P.nodes[proc]
#for free processor
if p['s'] == 'free':
for T in R:
if p['size'] + G.nodes[T]['memory'] > max_size:
continue
if ready[(T, proc)] <= time:
G.nodes[T]['t'] = time
G.nodes[T]['p'] = proc
S.append(T)
R.remove(T)
p['l'] = T
p['size'] += G.nodes[T]['memory']
avail.append(T)
break
#for awake processor
if p['s'] == 'awake':
for T in R:
if p['size'] + G.nodes[T]['memory'] > max_size:
continue
if urgent[T] <= time or (G.nodes[p['l']]['favor'] == T and ready[(T, proc)] <= time):
G.nodes[T]['t'] = time
G.nodes[T]['p'] = proc
S.append(T)
R.remove(T)
p['l'] = T
p['size'] += G.nodes[T]['memory']
avail.append(T)
break
#advance time
new_t = float('Inf')
for T in S:
new_t_p = G.nodes[T]['t'] + G.nodes[T]['weight']
# if T == 23:
# print(new_t_p)
if new_t_p > time and new_t_p < new_t:
new_t = new_t_p
for T in R:
for proc in P:
new_t_p = ready[(T, proc)]
if new_t_p > time and new_t_p < new_t:
new_t = new_t_p
for T in R:
new_t_p = urgent[T]
if new_t_p > time and new_t_p < new_t:
new_t = new_t_p
time = new_t
#add to R
for T in avail:
for suc in G.neighbors(T):
s = G.nodes[suc]
s['parent'] += 1
if s['parent'] == G.in_degree[suc]:
R.append(suc)
#report
#for t in G.nodes():
#print(''.join([G.nodes[t]['name'], ':', str(G.nodes[t]['p'])]))
#makespan
span = 0
for T in G.nodes():
t = G.nodes[T]['t'] + G.nodes[T]['weight']
span = max(span, t)
print(''.join(['makespan: ', str(span), ' microseconds']))
#computation time and memory on each processors
node = {}
comp = {}
memo = {}
for proc in P:
node[proc] = 0
comp[proc] = 0
memo[proc] = 0
for T in G.nodes():
node[G.nodes[T]['p']] += 1
comp[G.nodes[T]['p']] += G.nodes[T]['weight']
memo[G.nodes[T]['p']] += G.nodes[T]['memory']
for key in memo:
print(''.join(['P', str(key), ': ', str(node[key]), ' nodes, ', str(comp[key]), ' microseconds, ', str(memo[key]), ' bytes']))
return G, span
def lp(G):
'''
[e1,e2,e3,...,n1,n2,n3,...,w]
'''
#preprocess
num_node = G.number_of_nodes()
num_edge = G.number_of_edges()
LHS_VAL = []
LHS_I = []
LHS_J = []
RHS = []
#rule 1
row_count = 0
for i in range(num_edge):
append_val(i, row_count, 1, LHS_VAL, LHS_I, LHS_J)
RHS.append(1)
row_count += 1
for i in range(num_edge):
#eq = [0]*(num_node + num_edge + 1)
#eq[i] = -1
#LHS.append(eq)
append_val(i, row_count, -1, LHS_VAL, LHS_I, LHS_J)
RHS.append(0)
row_count += 1
#bound_e = [(0,1)] * num_edge
#rule 2
for i in range(num_node):
#eq = [0]*(num_node + num_edge + 1)
#eq[num_edge + i] = -1
#LHS.append(eq)
append_val(num_edge + i, row_count, -1, LHS_VAL, LHS_I, LHS_J)
RHS.append(0)
row_count += 1
# bound_n = [(0, None)] * num_node
# bound = bound_e + bound_n + [(None, None)]
#rule 3
for (i, j) in G.edges:
#eq = [0] * (num_node + num_edge + 1)
#eq[num_edge + i - 1] = 1
#eq[num_edge + j - 1] = -1
#eq[G[i][j]['id'] - 1] = G[i][j]['weight']
#LHS.append(eq)
append_val(num_edge + i - 1, row_count, 1, LHS_VAL, LHS_I, LHS_J)
append_val(num_edge + j - 1, row_count, -1, LHS_VAL, LHS_I, LHS_J)
append_val(G[i][j]['id'] -1, row_count, G[i][j]['weight'], LHS_VAL, LHS_I, LHS_J)
RHS.append(-G.node[i]['weight'])
row_count += 1
#rule 4
for n in G.nodes:
if G.out_degree[n] > 0:
#eq = [0] * (num_node + num_edge + 1)
for (i, j) in G.out_edges(n):
append_val(G[i][j]['id'] - 1, row_count, -1, LHS_VAL, LHS_I, LHS_J)
#eq[G[i][j]['id'] - 1] = -1
#LHS.append(eq)
RHS.append(1 - G.out_degree[n])
row_count += 1
#rule 5
for n in G.nodes:
if G.in_degree[n] > 0:
#eq = [0] * (num_node + num_edge + 1)
for (i, j) in G.in_edges(n):
append_val(G[i][j]['id'] - 1, row_count, -1, LHS_VAL, LHS_I, LHS_J)
#eq[G[i][j]['id'] - 1] = -1
#LHS.append(eq)
RHS.append(1 - G.in_degree[n])
row_count += 1
#rule 6
for n in G.nodes:
#eq = [0] * (num_node + num_edge + 1)
#eq[num_edge + n - 1] = 1
#eq[-1] = -1
append_val(num_edge + n - 1, row_count, 1, LHS_VAL, LHS_I, LHS_J)
append_val(num_node + num_edge, row_count, -1, LHS_VAL, LHS_I, LHS_J)
#LHS.append(eq)
RHS.append(-G.node[n]['weight'])
row_count += 1
#solve LP
goal = [0] * (num_node + num_edge + 1)
goal[-1] = 1
#for i in range(len(LHS)):
# print(LHS[i], RHS[i])
# s = CyClpSimplex()
#print "hello solver!"
#print "LHSS:", LHS
goal = matrix(to_float(goal))
#goal = matrix(float(goal))
LHS = spmatrix(LHS_VAL, LHS_J, LHS_I)
RHS = matrix(to_float(RHS))
#print "goal", goal
#print "LHS", LHS.size
#print "RHS", RHS
#print "bounds", bound
print("hello solver!")
solvers.options['maxiters'] = 10000
solvers.options['refinement'] = 1
res = solvers.lp(goal, LHS, RHS, solver='mosek')
print("goodbye solver!")
# res = sc.optimize.linprog(goal, A_ub=LHS, b_ub=RHS, bounds=bound, method='interior-point')
#print(res)
#print res
#print res['x']
x = res['x']
for i in range(len(x)):
if x[i] < 0.5:
x[i] = 0
else:
x[i] = 1
#print(x)
return x[:num_edge]
#lp(G)
#G = []
#P = []
#sct(G, P, 1e8)
#for g in G.nodes:
# print(G.nodes[g])