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 <[email protected]>
To: Mudassar Majeed <[email protected]>
Cc: "[email protected]" <[email protected]>
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;
>
>/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
>_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
