-
Emna Gharbi authoredEmna Gharbi authored
OptimizationModel.java 39.57 KiB
package tmltranslator.dsez3engine;
import com.microsoft.z3.*;
import myutil.TraceManager;
import tmltranslator.*;
import javax.swing.*;
import java.lang.reflect.Array;
import java.nio.channels.Channel;
import java.util.*;
public class OptimizationModel {
private Map<String, Integer> optimizedSolutionX = new HashMap<String, Integer>();
private Map<String, Integer> optimizedSolutionStart = new HashMap<>();
private InputInstance inputInstance;
private TMLMapping tmlMapping;
public TMLMapping getTmlMapping() {
return tmlMapping;
}
public void setTmlMapping(TMLMapping tmlMapping) {
this.tmlMapping = tmlMapping;
}
public OptimizationModel(InputInstance inputInstance) {
this.inputInstance = inputInstance;
}
public Map<String, Integer> getOptimizedSolutionX() {
return optimizedSolutionX;
}
public void setOptimizedSolutionX(Map<String, Integer> optimizedSolutionX) {
this.optimizedSolutionX = optimizedSolutionX;
}
public Map<String, Integer> getOptimizedSolutionStart() {
return optimizedSolutionStart;
}
public void setOptimizedSolutionStart(Map<String, Integer> optimizedSolutionStart) {
this.optimizedSolutionStart = optimizedSolutionStart;
}
public OptimizationResult findOptimizedMapping() {
Context ctx;
OptimizationResult result = null;
try {
// These examples need model generation turned on.
HashMap<String, String> cfg = new HashMap<String, String>();
cfg.put("model", "true");
ctx = new Context(cfg);
result = findOptimizedMapping(ctx);
Log.close();
if (Log.isOpen())
TraceManager.addDev("Log is still open!");
} catch (Z3Exception ex) {
TraceManager.addDev("Z3 Managed Exception: " + ex.getMessage());
TraceManager.addDev("Stack trace: ");
ex.printStackTrace(
System.out);
if (result == null) {
result = new OptimizationResult();
}
result.error = "Z3 Exception: " + ex.getMessage();
} catch (Exception ex) {
TraceManager.addDev("Unknown Exception: " + ex.getMessage());
TraceManager.addDev("Stack trace: ");
ex.printStackTrace(System.out);
if (result == null) {
result = new OptimizationResult();
}
result.error = "Z3 Unknown Exception: " + ex.getMessage();
}
return result;
}
public OptimizationResult findFeasibleMapping() {
Context ctx;
OptimizationResult result = null;
try {
// These examples need model generation turned on.
HashMap<String, String> cfg = new HashMap<String, String>();
cfg.put("model", "true");
ctx = new Context(cfg);
result = findFeasibleMapping(ctx);
Log.close();
if (Log.isOpen())
TraceManager.addDev("Log is still open!");
} catch (Z3Exception ex) {
TraceManager.addDev("Z3 Managed Exception: " + ex.getMessage());
TraceManager.addDev("Stack trace: ");
ex.printStackTrace(
System.out);
if (result == null) {
result = new OptimizationResult();
}
result.error = "Z3 Exception: " + ex.getMessage();
} catch (Exception ex) {
TraceManager.addDev("Unknown Exception: " + ex.getMessage());
TraceManager.addDev("Stack trace: ");
ex.printStackTrace(System.out);
if (result == null) {
result = new OptimizationResult();
}
result.error = "Z3 Unknown Exception: " + ex.getMessage();
}
return result;
}
public OptimizationResult findFeasibleMapping(Context ctx) {
OptimizationResult result = new OptimizationResult();
TraceManager.addDev("\nFind feasible Mapping");
//Decision variables
//Definition of Xtp as a matrix. Each cell corresponds to a combination of a task and a processor.
IntExpr[][] X = new IntExpr[inputInstance.getModeling().getTasks().size()][inputInstance.getArchitecture().getCPUs().size()]; //getCPUs returns only HwCPU elements
//TODO paths
//Definition of Ycw as a matrix. Each cell corresponds to a combination of a channel and a path.
// IntExpr[][] Y = new IntExpr[inputInstance.getModeling().getChannels().size()][tmlcpSequenceDiagrams.size()];
//Definition of start time variable for each task
IntExpr[] start = new IntExpr[inputInstance.getModeling().getTasks().size()];
//Mapping Constraints :
BoolExpr mapping_constraints = ctx.mkTrue();
//Matrix of constraints to define the interval of Xtp : 0 <= Xtp <= 1
BoolExpr[][] c_bound_x = new BoolExpr[inputInstance.getModeling().getTasks().size()][inputInstance.getArchitecture().getCPUs().size()];
//TraceManager.addDev("\nDefining the bounds of Xtp (1)");
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
X[t][p] = ctx.mkIntConst("X_" + taskCast.getID() + "_" + hwNode.getID());
// Constraints: 0 <= Xtp <= 1
c_bound_x[t][p] = ctx.mkAnd(ctx.mkLe(ctx.mkInt(0), X[t][p]),
ctx.mkLe(X[t][p], ctx.mkInt(1)));
// TraceManager.addDev(c_bound_x[t][p]);
}
}
//Constraint on start >=0
BoolExpr[] c_bound_start = new BoolExpr[inputInstance.getModeling().getTasks().size()];
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
start[t] = ctx.mkIntConst("start_" + taskCast.getID());
c_bound_start[t] = ctx.mkGe(start[t], ctx.mkInt(0));
mapping_constraints = ctx.mkAnd(mapping_constraints, c_bound_start[t]);
}
// TODO add the definition interval for Ycw
//CONSTRAINTS//
//Each task must be mapped to exactly 1 processing unit in its eligibility set:
// ∀t, SUM p (X tp) ≤ 1
//TraceManager.addDev("\nUnique task-CPU mapping constraints (3)");
BoolExpr[] c_unique_x = new BoolExpr[inputInstance.getModeling().getTasks().size()];
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
ArithExpr sum_X = ctx.mkAdd(X[t]);
c_unique_x[t] = ctx.mkLe(sum_X, ctx.mkInt(1));
// TraceManager.addDev(c_unique_x[t]);
}
//Feasible Task map: ∀t, SUM p in F(t) (X tp) = 1
//TraceManager.addDev("\nFeasible task-CPU mapping constraints (4)");
BoolExpr[] c_feasibleMapX = new BoolExpr[inputInstance.getModeling().getTasks().size()];
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
ArithExpr sum_X = ctx.mkInt(0);
for (HwNode hwNode : inputInstance.getFeasibleCPUs(taskCast)) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
sum_X = ctx.mkAdd(sum_X, X[t][p]);
}
c_feasibleMapX[t] = ctx.mkEq(sum_X, ctx.mkInt(1));
//TraceManager.addDev(c_feasibleMapX[t]);
}
//Memory size constraint: ∀p, ∀t, X tp × (bin + bout ) ≤ mem
//TraceManager.addDev("\nMemory size constraints (5)");
BoolExpr[][] c_mem = new BoolExpr[inputInstance.getArchitecture().getNbOfCPU()][inputInstance.getModeling().getTasks().size()];
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
IntExpr mem = ctx.mkInt(inputInstance.getLocalMemoryOfHwExecutionNode(hwNode).memorySize);
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
IntExpr bin_plus_bout = ctx.mkInt(inputInstance.getBufferIn(taskCast) + inputInstance.getBufferOut(taskCast));
ArithExpr bin_plus_bout_times_X = ctx.mkMul(bin_plus_bout, X[t][p]);
c_mem[p][t] = ctx.mkLe(bin_plus_bout_times_X, mem);
// TraceManager.addDev(c_mem[p][t]);
}
}
/*
//At least one route Constraint: ∀c, (t1,t2) in c; X t1p1 + X t2p2 − r p1p2 ≤ 1
TraceManager.addDev("\nAt least one route constraints (6)");
BoolExpr[] c_route = new BoolExpr[inputInstance.getModeling().getChannels().size()];
IntExpr[][] r = new IntExpr[inputInstance.getArchitecture().getCPUs().size()][inputInstance.getArchitecture().getCPUs().size()];
for (TMLChannel channel : (List<TMLChannel>) inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
//for each channel get producer and consumer
TMLTask producer = channel.getOriginTask();
int prodIndex = inputInstance.getModeling().getTasks().indexOf(producer);
TMLTask consumer = channel.getDestinationTask();
int consIndex = inputInstance.getModeling().getTasks().indexOf(consumer);
for (HwNode source : inputInstance.getArchitecture().getCPUs()) {
int src = inputInstance.getArchitecture().getCPUs().indexOf(source);
for (HwNode destination : inputInstance.getArchitecture().getCPUs()) {
int dst = inputInstance.getArchitecture().getCPUs().indexOf(destination);
//for each couple of processors TODO calculate rp1p2
r[src][dst] = ctx.mkInt(1);
ArithExpr Xp_plus_Xc = ctx.mkAdd(X[prodIndex][src], X[consIndex][dst]);
ArithExpr Xp_plus_Xc_minus_r = ctx.mkSub(Xp_plus_Xc, r[src][dst]);
c_route[c] = ctx.mkLe(Xp_plus_Xc_minus_r, ctx.mkInt(1));
TraceManager.addDev("Channel(" + channel.toString() + ") " + c_route[c]);
// mapping_constraints = ctx.mkAnd(c_route[c], mapping_constraints);
}
}
}
*/
//Scheduling: Precedence constraints: ∀c, τs (t cons ) ≥ τe (t prod )
// TraceManager.addDev("\nPrecedence constraints (11)");
BoolExpr[] c_precedence = new BoolExpr[inputInstance.getModeling().getChannels().size()];
for (Object channel : inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
TMLChannel channelCast = (TMLChannel) channel;
//for each channel get producer and consumer
TMLTask producer = channelCast.getOriginTask();
int prodIndex = inputInstance.getModeling().getTasks().indexOf(producer);
TraceManager.addDev("prodIndex" + prodIndex + "producer " + producer + inputInstance.getModeling().getTasks());
TMLTask consumer = channelCast.getDestinationTask();
int consIndex = inputInstance.getModeling().getTasks().indexOf(consumer);
ArithExpr wcetProducer = ctx.mkInt(0);
for (HwExecutionNode hwNode : inputInstance.getFeasibleCPUs(producer)) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
wcetProducer = ctx.mkAdd(wcetProducer, ctx.mkMul(X[prodIndex][p], ctx.mkInt(inputInstance.getWCET(producer, hwNode))));
}
ArithExpr endProducer = ctx.mkAdd(start[prodIndex], wcetProducer);
ArithExpr startC_minus_endP = ctx.mkSub(start[consIndex], endProducer);
c_precedence[c] = ctx.mkGe(startC_minus_endP, ctx.mkInt(0));
// TraceManager.addDev(c_precedence[c]);
mapping_constraints = ctx.mkAnd(mapping_constraints, c_precedence[c]);
}
//∀p∀t i ∀t j 6 = t i , ¬((X t i p = 1) ∧ (X t j p = 1)) ∨ ((τ s (t j ) ≥ τ e (t i )) ∨ (τ s (t i ) ≥ τ e (t j )))
//Scheduling: One single task running on CPU ∀t
//TraceManager.addDev("\n Same resource/no time overlap Constraints (12)");
BoolExpr c_monoTask[][][] = new BoolExpr[inputInstance.getArchitecture().getCPUs().size()][inputInstance.getModeling().getTasks().size()][inputInstance.getModeling().getTasks().size()];
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
for (Object taski : inputInstance.getModeling().getTasks()) {
int ti = inputInstance.getModeling().getTasks().indexOf(taski);
TMLTask taskiCast = (TMLTask) taski;
//Calculate End times of ti
ArithExpr wceti = ctx.mkInt(0);
for (HwExecutionNode ihwNode : inputInstance.getFeasibleCPUs(taskiCast)) {
int ip = inputInstance.getArchitecture().getCPUs().indexOf(ihwNode);
wceti = ctx.mkAdd(wceti, ctx.mkMul(X[ti][ip], ctx.mkInt(inputInstance.getWCET(taskiCast, ihwNode))));
}
ArithExpr endti = ctx.mkAdd(start[ti], wceti);
for (Object taskj : inputInstance.getModeling().getTasks()) {
int tj = inputInstance.getModeling().getTasks().indexOf(taskj);
TMLTask taskjCast = (TMLTask) taskj;
if (tj != ti) {
//Calculate End times of tj
ArithExpr wcetj = ctx.mkInt(0);
for (HwExecutionNode jhwNode : inputInstance.getFeasibleCPUs(taskjCast)) {
int jp = inputInstance.getArchitecture().getCPUs().indexOf(jhwNode);
wcetj = ctx.mkAdd(wcetj, ctx.mkMul(X[tj][jp], ctx.mkInt(inputInstance.getWCET(taskjCast, jhwNode))));
}
ArithExpr endtj = ctx.mkAdd(start[tj], wcetj);
BoolExpr alpha = ctx.mkAnd(ctx.mkEq(X[ti][p], ctx.mkInt(1)), ctx.mkEq(X[tj][p], ctx.mkInt(1)));
BoolExpr not_alpha = ctx.mkNot(alpha);
BoolExpr beta = ctx.mkOr(ctx.mkGe(start[ti], endtj), ctx.mkGe(start[tj], endti));
//
c_monoTask[p][ti][tj] = ctx.mkOr(not_alpha, beta);
// TraceManager.addDev("\n" + c_monoTask[p][ti][tj]);
mapping_constraints = ctx.mkAnd(mapping_constraints, c_monoTask[p][ti][tj]);
}
}
}
}
//Grouping remaining constraints of the model
// TraceManager.addDev("\nAll mapping constraints");
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
TMLTask taskCast = (TMLTask) task;
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
mapping_constraints = ctx.mkAnd(c_bound_x[t][p], mapping_constraints);
mapping_constraints = ctx.mkAnd(c_mem[p][t], mapping_constraints);
}
// Constraint: feasible unique mapping of tasks
mapping_constraints = ctx.mkAnd(c_unique_x[t], mapping_constraints);
mapping_constraints = ctx.mkAnd(c_feasibleMapX[t], mapping_constraints);
}
//Creating a solver instance
Solver s = ctx.mkSolver();
s.add(mapping_constraints);
if (s.check() == Status.SATISFIABLE) {
Model m = s.getModel();
Expr[][] optimized_result_X = new Expr[inputInstance.getModeling().getTasks().size()][inputInstance.getArchitecture().getCPUs().size()];
Expr[] optimized_result_start = new Expr[inputInstance.getModeling().getTasks().size()];
TraceManager.addDev("Proposed feasible Mapping solution:");
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
TMLTask taskCast = (TMLTask) task;
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
optimized_result_X[t][p] = m.evaluate(X[t][p], false);
TraceManager.addDev("X[" + taskCast.getName() + "][" + hwNode.getName() + "] = " + optimized_result_X[t][p]);
}
TraceManager.addDev("\n");
}
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
TMLTask taskCast = (TMLTask) task;
optimized_result_start[t] = m.evaluate(start[t], false);
TraceManager.addDev("start[" + taskCast.getName() + "] = " + optimized_result_start[t]);
}
result.result = "Feasible mapping found";
} else {
TraceManager.addDev("No suitable mapping could be found");
result.mappingFound = false;
}
return result;
}//findFeasibleMapping()
public OptimizationResult findOptimizedMapping(Context ctx) {
OptimizationResult result = new OptimizationResult();
TraceManager.addDev("\nFind an optimized Mapping");
//Decision variables
//Definition of Xtp as a matrix. Each cell corresponds to a combination of a task and a processor.
IntExpr[][] X = new IntExpr[inputInstance.getModeling().getTasks().size()][inputInstance.getArchitecture().getCPUs().size()]; //getCPUs returns only HwCPU elements
//Definition of start time variable for each task
IntExpr[] start = new IntExpr[inputInstance.getModeling().getTasks().size()];
//Definition of Y1: mapping variable of channel --> PE for transfer
IntExpr[][] Y1 = new IntExpr[inputInstance.getModeling().getChannels().size()][inputInstance.getArchitecture().getCPUs().size()];
//Mapping Constraints :
BoolExpr mapping_constraints = ctx.mkTrue();
//Matrix of constraints to define the interval of Xtp : 0 <= Xtp <= 1
BoolExpr[][] c_bound_x = new BoolExpr[inputInstance.getModeling().getTasks().size()][inputInstance.getArchitecture().getCPUs().size()];
//TraceManager.addDev("\nDefining the bounds of Xtp (1)");
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
X[t][p] = ctx.mkIntConst("X_" + taskCast.getName() + "_" + hwNode.getName());
// Constraints: 0 <= Xtp <= 1
c_bound_x[t][p] = ctx.mkAnd(ctx.mkLe(ctx.mkInt(0), X[t][p]),
ctx.mkLe(X[t][p], ctx.mkInt(1)));
// TraceManager.addDev(c_bound_x[t][p]);
}
}
//Constraint on start >=0
BoolExpr[] c_bound_start = new BoolExpr[inputInstance.getModeling().getTasks().size()];
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
start[t] = ctx.mkIntConst("start_" + taskCast.getName());
c_bound_start[t] = ctx.mkGe(start[t], ctx.mkInt(0));
mapping_constraints = ctx.mkAnd(mapping_constraints, c_bound_start[t]);
//TraceManager.addDev(c_bound_start[t].toString());
}
//Matrix of constraints to define the interval of Y1 : 0 <= Y1 <= 1
BoolExpr[][] c_bound_y1 = new BoolExpr[inputInstance.getModeling().getChannels().size()][inputInstance.getArchitecture().getCPUs().size()];
for (Object channel : inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
TMLChannel channelCast = (TMLChannel) channel;
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
Y1[c][p] = ctx.mkIntConst("Y1_" + channelCast.getName() + "_" + hwNode.getName());
// Constraints: 0 <= Y1 <= 1
c_bound_y1[c][p] = ctx.mkAnd(ctx.mkLe(ctx.mkInt(0), Y1[c][p]),
ctx.mkLe(Y1[c][p], ctx.mkInt(1)));
mapping_constraints = ctx.mkAnd(mapping_constraints, c_bound_y1[c][p]);
}
}
//CONSTRAINTS//
//Each channel must be mapped to exactly 1 processing unit:
// ∀ch, SUM p (Y 1) = 1
BoolExpr[] c_unique_y1 = new BoolExpr[inputInstance.getModeling().getChannels().size()];
for (Object channel : inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
TMLChannel channelCast = (TMLChannel) channel;
ArithExpr sum_Y1 = ctx.mkAdd(Y1[c]);
c_unique_y1[c] = ctx.mkEq(sum_Y1, ctx.mkInt(1));
mapping_constraints = ctx.mkAnd(mapping_constraints, c_unique_y1[c]);
}
//Each task must be mapped to exactly 1 processing unit in its eligibility set:
// ∀t, SUM p (X tp) ≤ 1
//TraceManager.addDev("\nUnique task-CPU mapping constraints (3)");
BoolExpr[] c_unique_x = new BoolExpr[inputInstance.getModeling().getTasks().size()];
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask); // TODO or use the local instance modeling
ArithExpr sum_X = ctx.mkAdd(X[t]);
c_unique_x[t] = ctx.mkLe(sum_X, ctx.mkInt(1));
//TraceManager.addDev(c_unique_x[t].toString());
}
//Feasible Task map: ∀t, SUM p in F(t) (X tp) = 1
//TraceManager.addDev("\nFeasible task-CPU mapping constraints (4)");
BoolExpr[] c_feasibleMapX = new BoolExpr[inputInstance.getModeling().getTasks().size()];
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
ArithExpr sum_X = ctx.mkInt(0);
TMLTask taskCast = (TMLTask) tmlTask;
for (HwNode hwNode : inputInstance.getFeasibleCPUs(taskCast)) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
sum_X = ctx.mkAdd(sum_X, X[t][p]);
}
c_feasibleMapX[t] = ctx.mkEq(sum_X, ctx.mkInt(1));
//TraceManager.addDev(c_feasibleMapX[t]);
}
//Memory size constraint: ∀p, ∀t, X tp × (bin + bout ) ≤ mem
//TraceManager.addDev("\nMemory size constraints (5)");
BoolExpr[][] c_mem = new BoolExpr[inputInstance.getArchitecture().getNbOfCPU()][inputInstance.getModeling().getTasks().size()];
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
IntExpr mem = ctx.mkInt(inputInstance.getLocalMemoryOfHwExecutionNode(hwNode).memorySize);
//TraceManager.addDev("local memory of " + hwNode.getName() + " is :" + inputInstance.getLocalMemoryOfHwExecutionNode(hwNode).getName());
for (Object tmlTask : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(tmlTask);
TMLTask taskCast = (TMLTask) tmlTask;
IntExpr bin_plus_bout = ctx.mkInt(inputInstance.getBufferIn(taskCast) + inputInstance.getBufferOut(taskCast));
ArithExpr bin_plus_bout_times_X = ctx.mkMul(bin_plus_bout, X[t][p]);
c_mem[p][t] = ctx.mkLe(bin_plus_bout_times_X, mem);
//TraceManager.addDev(c_mem[p][t].toString());
}
}
/*
//At least one route Constraint: ∀c, (t1,t2) in c; X t1p1 + X t2p2 − r p1p2 ≤ 1
TraceManager.addDev("\nAt least one route constraints (6)");
BoolExpr[] c_route = new BoolExpr[inputInstance.getModeling().getChannels().size()];
IntExpr[][] r = new IntExpr[inputInstance.getArchitecture().getCPUs().size()][inputInstance.getArchitecture().getCPUs().size()];
for (TMLChannel channel : (List<TMLChannel>) inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
//for each channel get producer and consumer
TMLTask producer = channel.getOriginTask();
int prodIndex = inputInstance.getModeling().getTasks().indexOf(producer);
TMLTask consumer = channel.getDestinationTask();
int consIndex = inputInstance.getModeling().getTasks().indexOf(consumer);
for (HwNode source : inputInstance.getArchitecture().getCPUs()) {
int src = inputInstance.getArchitecture().getCPUs().indexOf(source);
for (HwNode destination : inputInstance.getArchitecture().getCPUs()) {
int dst = inputInstance.getArchitecture().getCPUs().indexOf(destination);
//for each couple of processors TODO calculate rp1p2
r[src][dst] = ctx.mkInt(1);
ArithExpr Xp_plus_Xc = ctx.mkAdd(X[prodIndex][src], X[consIndex][dst]);
ArithExpr Xp_plus_Xc_minus_r = ctx.mkSub(Xp_plus_Xc, r[src][dst]);
c_route[c] = ctx.mkLe(Xp_plus_Xc_minus_r, ctx.mkInt(1));
TraceManager.addDev("Channel(" + channel.toString() + ") " + c_route[c]);
// mapping_constraints = ctx.mkAnd(c_route[c], mapping_constraints);
}
}
}
*/
//Scheduling: Precedence constraints: ∀c, τs (t cons ) ≥ τe (t prod )
// TraceManager.addDev("\nPrecedence constraints (11)");
BoolExpr[] c_precedence = new BoolExpr[inputInstance.getModeling().getChannels().size()];
for (Object channel : inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
//for each channel get producer and consumer
TMLChannel channelCast = (TMLChannel) channel;
TMLTask producer = channelCast.getOriginTask();
int prodIndex = inputInstance.getModeling().getTasks().indexOf(producer);
TMLTask consumer = channelCast.getDestinationTask();
int consIndex = inputInstance.getModeling().getTasks().indexOf(consumer);
//TraceManager.addDev("\nChannel(" + producer.getId() + "," + consumer.getId() + ")");
ArithExpr wcetProducer = ctx.mkInt(0);
for (HwExecutionNode hwNode : inputInstance.getFeasibleCPUs(producer)) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
wcetProducer = ctx.mkAdd(wcetProducer, ctx.mkMul(X[prodIndex][p], ctx.mkInt(inputInstance.getWCET(producer, hwNode))));
}
ArithExpr endProducer = ctx.mkAdd(start[prodIndex], wcetProducer);
ArithExpr startC_minus_endP = ctx.mkSub(start[consIndex], endProducer);
c_precedence[c] = ctx.mkGe(startC_minus_endP, ctx.mkInt(0));
//TraceManager.addDev(channelCast.getName() + "\n");
//TraceManager.addDev(c_precedence[c].toString());
mapping_constraints = ctx.mkAnd(mapping_constraints, c_precedence[c]);
}
//∀p∀t i ∀t j 6 = t i , ¬((X t i p = 1) ∧ (X t j p = 1)) ∨ ((τ s (t j ) ≥ τ e (t i )) ∨ (τ s (t i ) ≥ τ e (t j )))
//Scheduling: One single task running on CPU ∀t
//TraceManager.addDev("\n Same resource/no time overlap Constraints (12)");
BoolExpr c_monoTask[][][] = new BoolExpr[inputInstance.getArchitecture().getCPUs().size()][inputInstance.getModeling().getTasks().size()][inputInstance.getModeling().getTasks().size()];
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
for (Object taski : inputInstance.getModeling().getTasks()) {
int ti = inputInstance.getModeling().getTasks().indexOf(taski);
//Calculate End times of ti
ArithExpr wceti = ctx.mkInt(0);
TMLTask taskiCast = (TMLTask) taski;
for (HwExecutionNode ihwNode : inputInstance.getFeasibleCPUs(taskiCast)) {
int ip = inputInstance.getArchitecture().getCPUs().indexOf(ihwNode);
wceti = ctx.mkAdd(wceti, ctx.mkMul(X[ti][ip], ctx.mkInt(inputInstance.getWCET(taskiCast, ihwNode))));
}
ArithExpr endti = ctx.mkAdd(start[ti], wceti);
for (Object taskj : inputInstance.getModeling().getTasks()) {
int tj = inputInstance.getModeling().getTasks().indexOf(taskj);
if (tj != ti) {
//Calculate End times of tj
ArithExpr wcetj = ctx.mkInt(0);
TMLTask taskjCast = (TMLTask) taskj;
for (HwExecutionNode jhwNode : inputInstance.getFeasibleCPUs(taskjCast)) {
int jp = inputInstance.getArchitecture().getCPUs().indexOf(jhwNode);
wcetj = ctx.mkAdd(wcetj, ctx.mkMul(X[tj][jp], ctx.mkInt(inputInstance.getWCET(taskjCast, jhwNode))));
}
ArithExpr endtj = ctx.mkAdd(start[tj], wcetj);
BoolExpr alpha = ctx.mkAnd(ctx.mkEq(X[ti][p], ctx.mkInt(1)), ctx.mkEq(X[tj][p], ctx.mkInt(1)));
BoolExpr not_alpha = ctx.mkNot(alpha);
BoolExpr beta = ctx.mkOr(ctx.mkGe(start[ti], endtj), ctx.mkGe(start[tj], endti));
//
c_monoTask[p][ti][tj] = ctx.mkOr(not_alpha, beta);
// TraceManager.addDev("\n" + c_monoTask[p][ti][tj]);
mapping_constraints = ctx.mkAnd(mapping_constraints, c_monoTask[p][ti][tj]);
}
}
}
}
//Grouping remaining constraints of the model
// TraceManager.addDev("\nAll mapping constraints");
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
mapping_constraints = ctx.mkAnd(c_bound_x[t][p], mapping_constraints);
mapping_constraints = ctx.mkAnd(c_mem[p][t], mapping_constraints);
}
// Constraint: feasible unique mapping of tasks
mapping_constraints = ctx.mkAnd(c_unique_x[t], mapping_constraints);
mapping_constraints = ctx.mkAnd(c_feasibleMapX[t], mapping_constraints);
}
//OPTIMIZE CONTEXT
//Create an Optimize context
Optimize opt = ctx.mkOptimize();
//Assert a constraints into the optimize solver
opt.Add(mapping_constraints);
// Objective: minimize latency
//Creating an expression for latency
//Calculating end time of last task
TMLTask finalTask = inputInstance.getFinalTask(inputInstance.getModeling());
int finalTaskIndex = inputInstance.getModeling().getTasks().indexOf(inputInstance.getFinalTask(inputInstance.getModeling()));
ArithExpr wcet_last = ctx.mkInt(0);
int l = 0;
for (HwExecutionNode hwNode : inputInstance.getFeasibleCPUs(inputInstance.getFinalTask(inputInstance.getModeling()))) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
wcet_last = ctx.mkAdd(wcet_last, ctx.mkMul(X[finalTaskIndex][p], ctx.mkInt(inputInstance.getWCET(finalTask, hwNode))));
l += 1;
}
ArithExpr end_last = ctx.mkAdd(start[finalTaskIndex], wcet_last);
ArithExpr latency = ctx.mkSub(end_last, ctx.mkInt(0));
// Add minimization objective.
Optimize.Handle objective_latency = opt.MkMinimize(latency);
String outputToDisplay;
if (opt.Check() == Status.SATISFIABLE) {
Model m = opt.getModel();
Expr[][] optimized_result_X = new Expr[inputInstance.getModeling().getTasks().size()][inputInstance.getArchitecture().getCPUs().size()];
Expr[] optimized_result_start = new Expr[inputInstance.getModeling().getTasks().size()];
Expr[][] optimized_result_Y1 = new Expr[inputInstance.getModeling().getChannels().size()][inputInstance.getArchitecture().getCPUs().size()];
tmlMapping = new TMLMapping<>(inputInstance.getModeling(), inputInstance.getArchitecture(), false);
outputToDisplay = "The optimal mapping solution is:\n\n";
outputToDisplay = outputToDisplay + "(1) Spatial mapping of tasks:\n";
outputToDisplay = outputToDisplay + "\nTASK --> PLATFORM NODE\n";
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
//evaluate optimal solution
optimized_result_X[t][p] = m.evaluate(X[t][p], true);
TMLTask taskCast = (TMLTask) task;
if (Integer.parseInt(optimized_result_X[t][p].toString()) == 1) {
//mapping of task on hwExecutionNode
tmlMapping.addTaskToHwExecutionNode(taskCast, (HwExecutionNode) hwNode);
//mapping of R/W channels on local memory of hwExecutionNode TODO get(0)
if (!taskCast.getReadChannels().isEmpty())
tmlMapping.addCommToHwCommNode(taskCast.getReadChannels().get(0), inputInstance.getLocalMemoryOfHwExecutionNode(hwNode));
if (!taskCast.getWriteChannels().isEmpty())
tmlMapping.addCommToHwCommNode(taskCast.getWriteChannels().get(0), inputInstance.getLocalMemoryOfHwExecutionNode(hwNode));
outputToDisplay = outputToDisplay + "\n" + taskCast.getName() + " --> " + hwNode.getName();
}
optimizedSolutionX.put("X[" + taskCast.getName() + "][" + hwNode.getName() + "] = ", Integer.parseInt
(optimized_result_X[t][p]
.toString()));
// TraceManager.addDev("X[" + task.getName() + "][" + hwNode.getName() + "] = " + optimized_result_X[t][p]);
}
TraceManager.addDev("\n");
}
outputToDisplay = outputToDisplay + "\n\n(2) Temporal mapping of tasks:\n";
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
optimized_result_start[t] = m.evaluate(start[t], false);
TMLTask taskCast = (TMLTask) task;
//optimizedSolutionStart.put("start[" + taskCast.getName() + "] ", Integer.parseInt(optimized_result_start[t].toString()));
// TraceManager.addDev("start[" + task.getName() + "] = " + optimized_result_start[t]);
}
// reordering and displaying schedule
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
TreeMap<Integer, String> treeHwNode = new TreeMap<>();
outputToDisplay = outputToDisplay + "\n" + hwNode.getName() + " : ";
for (Object task : inputInstance.getModeling().getTasks()) {
int t = inputInstance.getModeling().getTasks().indexOf(task);
TMLTask taskCast = (TMLTask) task;
if (Integer.parseInt(optimized_result_X[t][p].toString()) == 1) {
treeHwNode.put(Integer.parseInt(optimized_result_start[t].toString()), taskCast.getName());
}
}
for (Map.Entry<Integer, String> entry : treeHwNode.entrySet()) {
outputToDisplay = outputToDisplay + entry.getValue() + " at " + entry.getKey() + " ; ";
}
}
outputToDisplay += "\n\n";
for (Map.Entry<String, Integer> entry : optimizedSolutionStart.entrySet()) {
outputToDisplay = outputToDisplay + entry.getKey() + " = " + entry.getValue() + "\n";
}
//mapping of communication channels
outputToDisplay = outputToDisplay + "\n\n(3) Spatial mapping of channels onto controllers:\n";
for (Object channel : inputInstance.getModeling().getChannels()) {
int c = inputInstance.getModeling().getChannels().indexOf(channel);
TMLChannel channelCast = (TMLChannel) channel;
for (HwNode hwNode : inputInstance.getArchitecture().getCPUs()) {
int p = inputInstance.getArchitecture().getCPUs().indexOf(hwNode);
//evaluate optimal solution
optimized_result_Y1[c][p] = m.evaluate(Y1[c][p], true);
if (Integer.parseInt(optimized_result_Y1[c][p].toString()) == 1) {
//TODO Add this mapping in tmlmapping
// mapping of R/W channels on local memory of hwExecutionNode TODO get(0)
/* if (!taskCast.getReadChannels().isEmpty())
tmlMapping.addCommToHwCommNode(taskCast.getReadChannels().get(0), inputInstance.getLocalMemoryOfHwExecutionNode(hwNode));
if (!taskCast.getWriteChannels().isEmpty())
tmlMapping.addCommToHwCommNode(taskCast.getWriteChannels().get(0), inputInstance.getLocalMemoryOfHwExecutionNode(hwNode));
outputToDisplay = outputToDisplay + "\n" + taskCast.getName() + " --> " + hwNode.getName();
}*/
outputToDisplay += "\nChannel(" + channelCast.getOriginTask().getTaskName() + "," +
channelCast.getDestinationTask().getTaskName() + ") --> " + hwNode.getName();
}
}
}
TraceManager.addDev(outputToDisplay);
result.mappingFound = true;
result.resultingMapping = tmlMapping;
} else {
outputToDisplay = "No suitable mapping could be found";
TraceManager.addDev(outputToDisplay);
result.mappingFound = false;
}
result.result = outputToDisplay;
return result;
}
}