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
