1.1多节点平台任务映射
要做的事情是将一个流式应用(streamapplication)的系统流图中的任务映射到一个多节点处理器的平台上，目标是最大吞吐率。假设处理每帧时，映射方案不变。在"steady-state schedule"的条件下，该问题被建模为了mixed integer programming问题。不考虑处理器之间的通信，该问题模型为
这个问题计算量很大，需要使用优化工具。
1.2 APML，analgebraic modeling language for mathematical programming
APML：一个优化问题建模语言，在高的层次描述问题
Solver：例如GLPK,CPLEX...，是底层的线性或非线性的数值计算软件
APML语言建模+solver计算→解决问题，中间有一个翻译的过程
1.3 Hello world
AMPL官网提供了AMPL语言教程，和一个在线的AMPL语言处理器（解释器？）
这个是AMPLGUIDE中的第一个例子
------------------------- 问题-------------------------------------------------
Maximize 25 X B + 30 X C
Subject to (1/200) X B + (1/140) X C ≤ 40
0 ≤ X B ≤ 6000
0 ≤ X C ≤ 4000
var XB; var XC; maximize Profit: 25 * XB+ 30 * XC; subject to Time: (1/200)* XB + (1/140) * XC <= 40; subject to B_limit: 0 <= XB <= 6000; subject to C_limit: 0 <= XC <= 4000;
-------------------------执行&结果-------------------------------------------
ampl: model prod0.mod;#reads the file into AMPL
ampl: solve;
MINOS 5.5: optimal solution found.
2 iterations, objective 192000
ampl: display XB, XC;
XB = 6000
XC = 1400
ampl: quit;
1.4 A linear programming model
• sets, like the products
• parameters, like the production and profitrates
• variables, whose values the solver is todetermine
• an objective, to be maximized or minimized
• constraints that the solution must satisfy.
------------- illustration--------------------------------------------
Given:
P, a set of products
a j = tons per hour of product j, for each j ∈P
b = hours available at the mill
c j = profit per ton of product j, for each j ∈P
u j = maximum tons of product j, for each j ∈P
Define variables: X j = tons of product j to bemade, for each j ∈P
Maximize:
Σ cj Xj
j ∈P
Subject to:
Σ ( 1/ a j ) X j ≤ b
j ∈P
0 ≤ X j ≤ u j , for each j ∈P
1.5 Minimax 问题求解
在不考虑通信开销的情况下，最优的调度就是如下问题的解：
其中cost是每个任务的耗时。这是一个minimalmax的问题。
Minimal max有点分段线性的感觉，但对于每个变量来说并不是分段线性的。
在AMPLGuide的piecewise一节中有讲这个问题，可以用AMPL语言建模为
set PROCESSORS;
set TASKS;
param cost {j in TASKS} >= 0; # cost per hour of work
var M;
var Assign {i in PROCESSORS, j in TASKS} binary;
minimize Max_Cost: M;
subject to M_def {i in PROCESSORS}:
M >= sum {j in TASKS} cost[j] * Assign[i,j];
subject to Supply {j in TASKS}:
sum {i in PROCESSORS} Assign[i,j] = 1;
这个问题的建模要点在于：
定义一个Max_Cost目标为M，对应于tau
然后来一系列约束：M>= sum {j in TASKS} cost[j] * Assign[i,j];
这样minimax就用线性表达式表达了
dat文件为
set PROCESSORS := p1 p2 p3 p4 p5 p6 p7 p8;
set TASKS:= t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13;
param: cost :=
t1 16
t2 13
t3 12
t4 10
t5 8
t6 15
t7 24
t8 11
t9 10
t10 6
t11 19
t12 22
t13 21;
1.6 用NEOS处理AMPL
NESO是一个在线的解最优化问题的服务器。NEOS配置好了各种solver，可以在上面选择和自己问题匹配的solver并提交AMPL文件，然后就能够得到问题的解。
NEOS的好处有几个：
-
不用自己下载并配置各种solver
-
不要钱
-
接口简单
上一节中的dat文件所描述的问题的结果，跟YALMIP相比，算得很快
CBC trunk: CBC trunk optimal, objective 25 116456 nodes, 1653530 iterations, 81.4266 seconds M = 25 Assign [*,*] (tr) : p1 p2 p3 p4 p5 p6 p7 p8 := t1 0 0 0 0 0 1 0 0 t10 0 0 1 0 0 0 0 0 t11 0 0 1 0 0 0 0 0 t12 0 0 0 1 0 0 0 0 t13 0 0 0 0 0 0 1 0 t2 0 0 0 0 0 0 0 1 t3 0 0 0 0 1 0 0 0 t4 1 0 0 0 0 0 0 0 t5 0 0 0 0 0 1 0 0 t6 1 0 0 0 0 0 0 0 t7 0 1 0 0 0 0 0 0 t8 0 0 0 0 0 0 0 1 t9 0 0 0 0 1 0 0 0
1.7YALMIP
YALMIP是在Matlab下的一个优化工具箱，语法也不复杂。
在没有安装外部solver的情况下，利用Matlab内置的bintprog能够解决我所面对的问题，但速度太慢，迭代次数上限需要在它提供的一个m源文件里面改。8个节点8个任务跑了3个小时，最终由于迭代次数超过了65536报错了。