That's nice. It worked well. There is another question. I have added the balancing of (computational) loads on each cores as well. I have seen the following model solves (with given data) and processes are bound to the cores with perfect balance of loads and communication cost. See the objective function, I have added z with commcost to balance both. But if commcost has a bigger value as compared to z then commcost will diminish the effect of z and only balance of communication will be done. I need to bring commcost and z to the same scale such that balance of both is done. Here is the updated code.
regards,
Mudassar
/* 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;
/* Load on the process with rank i */
param load{i in Processes};
/* 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 comcost{pi in Processes, pj in Processes : pi > pj}, >= b_within_node;
var z;
s.t. load_on_each_core{ni in 1..ceil(p/k), ki in 1..k}: z >= sum{pi in Processes} x[pi, ni, ki] * load[pi];
s.t.
comm_cost{pi in Processes, pj in Processes, ni in 1..ceil(p/k), nj in 1..ceil(p/k) : (pi > pj) and (ni != nj)}:
comcost[pi,pj] >= (comm[pj,pi]+comm[pi,pj])*(b_within_node + (b_across_nodes-b_within_node)*(sum{ki in 1..k} x[pi,ni,ki] + sum{kj in 1..k} x[pj,nj,kj] - 1));
minimize timespan: z + sum{pi in Processes, pj in Processes: pi > pj} comcost[pi,pj];
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 load [1] 4 [2] 5 [3] 3 [4] 8 [5] 7 [6] 4 [7] 2 [8] 2 [9] 6 [10] 9 [11] 1 [12] 1;
param comm: 1 2 3 4 5 6 7 8 9 10 11 12 :=
1 0 0 0 0 0 0 0 2 0 0 0 0
2 0 0 0 0 0 0 0 0 7 0 0 0
3 0 0 0 0 6 0 0 0 0 0 9 0
4 0 0 0 0 0 0 0 0 0 5 0 0
5 0 0 6 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 1
7 0 0 0 0 0 0 0 0 0 0 0 0
8 7 0 0 0 0 0 0 0 0 0 0 0
9 0 7 0 0 0 0 0 0 0 0 0 0
10 0 0 0 8 0 0 0 0 0 0 0 0
11 0 0 5 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 3 0 0 0 0 0 0;
param b_across_nodes := 10;
param b_within_node := 3;
end;
Life is the name of establishing a clear balance between hard work and praying to God for success. The one who could find out and order the major milestones of life in a proper way and acted upon them is successful. Faith in, and obedience to Allah, one's values, contribution for (nation, family & human beings), career, earning, extra activities and hobbies.... The best ordered list of milestones of life...!!!
From: Xypron <address@hidden>
To:
Mudassar Majeed <address@hidden>
Cc: "address@hidden" <address@hidden>
Sent: Friday, October 21, 2011 9:49 PM
Subject: Re: I need help to convert quadratic problem into linear
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;
/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/