Hello Mudassar,
to determine the cost of communication between two processes
probably you are looking for something like:
var x{pi in Processes, ni in 1..ceil(p/k), ki in 1..k}, binary;
var comcost{pi in Processes, pj in Processes : pj > pj}, >=
b_inside_nodes;
s.t. constraint{pi in Processes, pj in Processes, ni in
1..ceil(p/k), nj in 1..ceil(p/k) : pj > pj, ni != nj} :
comcost[pi,pj] >= (comm[pj,pi]+comm[pi,pj])
* (b_inside_nodes
+ (b_across_nodes-b_inside_nodes)
* ( sum{ki in 1..k} x[pi,ni,ki] + sum{kj in 1..k} x[pj,nj,kj]
- 1 ));
minimize sum{pi in Processes, pj in Processes : pj > pj}
comcost[pi,pj];
Best regards
Xypron
On 21.10.2011 18:41, Mudassar Majeed wrote:
Dear All,
I am trying to solve a problem using ILP and
have some problem. If some genius can help me out, I will be
very thankful. I am using glpsol to solve it. Following is the
code and the explanation.
I have p cores and k cores per node, where number of nodes are
ceil(p/k). I have some processes, where card(Processes) > p.
Every process i communicates with some other processes (more
than one), such that comm[i,j] gives how much
communication i performs with j (Communication that j performs
with i is in comm[j,i]). Now as I said there are ceil(p/k) nodes
each having k cores, a core will have more than one processes
mapped to it. Secondly any two processes
that communicate with each other and that are mapped to some
cores in the same node have a weight assigned to each
communication b_within_node. Similarly for two processes mapped
to two separates cores on different nodes will have
costly communication given as a weight in b_across_nodes. The
objective is to assign the processes to cores (in nodes) such
that the overall communication cost is minimum. I have defined a
variable x{pi in Processes, ni in 1...ceil(p/k), ki in 1..k},
binary.
if x[pi, ni, ki] = 1 then it means process pi is assigned to
core ki of node ni. I have used another variable z that shows
the communication cost of process pi (that process pi sends to
others) and then tried to minimize the maximum cost a process
can have. In
this way, it will provide me such solution in x (the mappings of
processes to cores) such that communication will be balanced,
that means those processes that communicate more will come on
the same node etc.
I have written the code, now I have reached to a problem where
it becomes quadratic (see the first constraint). If somebody
understands my problem then suggest me how can I convert this
constraint into linear, as the solver warns me of multiplication
of linear variables is
not allowed.
Code is as follows. Please help me in it. Thanks in Advance.
best regards,
Mudassar Majeed.
/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
/* The set of processes that will execute on different cores */
set Processes;
/* Total number of cores */
param p;
/* Number of cores per node */
param k;
/* The communication cost between processes with ranks i and j
*/
param comm{i in Processes, j in Processes};
/* Weight communicating across the nodes between two processes
*/
param b_across_nodes;
/* Weight communicating within a node between two processes */
param b_within_node;
/* x is a binary variable that shows where process pi resides on
core ki of node ni */
/* If there are p cores and k cores per node then the number of
nodes will be ceil(p/k) */
var x{pi in Processes, ni in 1..ceil(p/k), ki in 1..k}, binary;
var z;
s.t. comm_from_each_proc{pi in Processes}: z >= sum{ni in
1..ceil(p/k), ki in 1..k} x[pi,ni,ki] *
(sum{qi in Processes, nq in
1..ceil(p/k), kq in 1..k: (pi != qi)}x[qi,nq,kq]*comm[pi,qi] *
(if (ni != nq) then b_across_nodes else b_within_node));
minimize timespan: z;
s.t. mapped{pi in Processes}: sum{ni in 1..ceil(p/k), ki in
1..k} x[pi, ni, ki] = 1;
data;
set Processes := 1 2 3 4 5 6 7 8 9 10 11 12;
param p := 6;
param k := 2;
param comm: 1 2 3 4 5 6 7 8 9 10 11 12 :=
1 0 2 5 6 2 8 5 2 5 6 3 7
2 3 0 3 5 6 4 8 2 7 4 6 2
3 5 4 0 5 7 2 3 2 7 5 9 3
4 2 3 2 0 6 4 6 3 2 5 4 3
5 6 4 6 3 0 5 3 2 6 4 5 2
6 5 3 2 4 2 0 4 3 7 3 4 1
7 7 4 5 6 2 8 0 4 2 2 3 4
8 7 6 5 3 4 6 2 0 1 5 2 4
9 8 7 2 3 1 6 4 6 0 7 5 2
10 5 4 6 8 1 1 2 3 6 0 3 5
11 6 2 5 4 8 3 1 1 4 2 0 4
12 4 3 4 1 1 3 4 1 2 4 5 0;
param b_across_nodes := 10;
param b_within_node := 3;
end;
/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
|