program TwoDimensionalKnapsackProblemOnSIMDComputers; (*{{{ documentation and bibliographic reference*) (* Casiano Rdoriguez Leon. Centro Superior de Informatica. *) (* Universidad de La Laguna. July, August 1992. *) (* This Pascal ll program is based in the work of *) (* Darrel R. Ulm and Pearl Y. Wang. *) (* "Solving a Two-Dimensional Knapsack Problem on SIMD computers" *) (* 1992 International Conference on Parallel Processing *) (* Research notes: study the way to reduce the number of processors *) (* or at least to generalize the algorithm for any number of procesors *) (* Study the implementation for a transputer network. *) (* I don't agree with the comlexity analysis. Why they consider constant*) (* time for the maximum send operation? *) (*}}} *) (*{{{ const and types*) const max = 8; type rectangle = record l,w : integer; cost : integer end; collection = array [1..max] of rectangle; solution = array [1..max] of integer; vector = array [0..max] of integer; matrix = array [0..max] of vector; (*}}} *) (*{{{ variables*) var obj : collection; z : solution; n : integer (* number of objects *); L, W, LplusW : integer; (* knapsack dimensions *) F, sum : matrix; (*}}} *) (*{{{ readData*) procedure readData; var i : integer; begin (*{{{ information*) writeln('**SOLVING A TWO DIMENSIONAL KNAPSACK PROBLEM ON SIMD COMPUTERS**'); writeln; writeln('This program solves a 2 dimensional knapsack problem where'); writeln('objects that have been packed in a knapsack must be retrievable'); writeln('using edge-to-edge cuts. The algorithm is a parallelization of a'); writeln('dynamic programming algorithm that appears in the paper:'); writeln('solving a two dimensional knapsack problem on SIMD computers'); writeln('by D. R. Ulm and P. Y. Wang.'); writeln('1992 International Conference on Parallel Processing'); writeln('E-MAIL: dulm@mcs.kent.edu and pwang@cs.gmu.edu'); writeln; (*}}} *) write('Number of objects = '); read(n); i := 1; write('Knapsack dimensions L W = '); read(L); read(W); LplusW := L+W; while (i <= n) do begin write('object[',i,'] (l w cost) = '); read(obj[i].l); read(obj[i].w); read(obj[i].cost); i := i+1; end; end; (*}}} *) (*{{{ writeData*) procedure writeData; var i,j : integer; begin i := 1; while (i <= L) do begin j := 1; while (j <= W) do begin write(' F['); write(i, ','); write(j); write('] = ',F[i][j]); j := j+1; end; i := i+1; writeln; end; end (* writeData *); (*}}} *) begin readData; (*{{{ parallel i,j do F[i][j] := 0*) parallel 0..L do var i : integer; begin i := name; parallel 0..W do F[i][name] := 0; end; (*}}} *) (*{{{ parallel i,j do F[i][j] := max { cost[k] / l[k] <= i and w[k] <= j}*) var k : integer; begin k := 1; while k <= n do begin parallel 1..L do var i : integer; begin i := name; parallel 1..W do var j : integer; begin j := name; if (i >= obj[k].l) and (j >= obj[k].w) then if F[i][j] <= obj[k].cost then F[i][j] := obj[k].cost; end (* parallel 1..W *); end (* parallel 1..L *); k := k+1; end (* while *); end (* var k *); (*}}} *) (*{{{ diagonalization phase*) var diag : integer; begin diag := 3; while (diag <= LplusW) do begin parallel 1..L do var i : integer; begin i := name; parallel 1..W do var j, k : integer; begin j := name; (*{{{ *) if ((diag div 2) <= (i+j)) and (i+j <= diag) then begin sum[i][j] := F[i][j]+F[diag-i-j][j]; if i = (diag - j) then (*{{{ F[diag-j][j] := max {F[k][j] / diag/2 - j <= k <= diag-j}*) begin k := (diag div 2) -j; if k < 1 then k := 1; while k <= i do begin if sum[k][j] > F[i][j] then F[i][j] := sum[k][j]; k := k+1; end; end (* if *); (*}}} *) sum[i][j] := F[i][j]+F[i][diag-i-j]; if j = (diag - i) then (*{{{ F[i][diag-i] := max {F[i][k] / diag/2 - i <= k <= diag-i}*) begin k := (diag div 2) - i; if k < 1 then k := 1; while k <= j do begin if sum[i][k] > F[i][j] then F[i][j] := sum[i][k]; k := k+1; end; end (* if *); (*}}} *) end (* if *); (*}}} *) end (* var j *); end (* var i *); diag := diag+1; end (* while *); end (* var diag *); (*}}} *) writeData; end.