
| size   | time   | speedup with k SPUs   | time   |     |      |         |       |
|--------|--------|-----------------------|--------|-----|------|---------|-------|
| 1 SPU  | 2      | 4                     | 8      | 12  | 16   | 16 SPUs |       |
| 1400   | 6.227  | 2.7                   | 3.7    | 6.0 | 7.2  | 11.2    | 0.556 |
| 1600   | 7.328  | 1.8                   | 3.4    | 6.0 | 7.5  | 10.1    | 0.727 |
| 1800   | 11.559 | 2.0                   | 3.7    | 6.4 | 9.4  | 10.9    | 1.062 |
| 2000   | 13.802 | 1.7                   | 3.1    | 6.1 | 9.5  | 10.6    | 1.303 |
| 2200   | 18.702 | 2.3                   | 3.5    | 6.2 | 10.0 | 10.8    | 1.735 |
| 2400   | 21.757 | 2.1                   | 3.3    | 5.5 | 7.1  | 10.2    | 2.129 |
| 2600   | 29.890 | 1.8                   | 3.8    | 6.9 | 8.6  | 11.0    | 2.716 |

| #SPUs      | average case   | worst case   |         |      |
|------------|----------------|--------------|---------|------|
| time (sec) | speedup        | time (sec)   | speedup |      |
| 1          | 29.890         | 1.0          | 105.030 | 1.0  |
| 2          | 17.071         | 1.8          | 84.750  | 1.2  |
| 4          | 7.941          | 3.8          | 29.540  | 3.6  |
| 8          | 4.362          | 6.9          | 14.590  | 7.2  |
| 12         | 3.490          | 8.6          | 8.830   | 11.9 |
| 16         | 2.716          | 11.0         | 6.160   | 17.1 |

other. All squares have different sizes and they fully cover the master square (there is no spare capacity).

The smallest solution involves 21 squares which must be packed into a master square of size 112.

Since the system we are basing our work on (Adaptive Search) only deals with permutation problems, we have modeled this problem as a set of N variables whose values corresponds to the sizes of the squares to be placed, in order - this is not the best modeling but complies with the requirements of the available implementation. Each square in a configuration is placed in the lowest and leftmost possible slot.

Moving from a configuration to another consists in swapping 2 variables. To compute the cost of a configuration, the squares are packed as explained above. As soon as a square does not fit in the lowest/leftmost slot the placement stops. The cost of the configuration is a formula depending on several criteria on the set of non placed squares (number of non-placed squares and the size of the biggest) and on remaining slots in the master square (sum of heights, largest height, sum of widths). As usual, a configuration is a solution when its cost drops to zero.

We tried 5 different instances of this problem taken from [6, 2] whose input data are summarized in table 5. Table 6 presents the data associated to the average case for these instances. Running 16 SPUs, the speedup ranges from 11 to 16 depending on the instance.

As previously explained, our modeling is not the best one: a modeling explicitely using variables to encode X and Y coordinates of each square would be clearly better as done in a Constraint Programming modeling. Nevertheless, AS/Cell performs rather well and the most difficult instance (number 5) is solved in less than 10 seconds with 16 SPUs. Table 7 provides more information for this instance both for the average case and the worst case (together with the associated speedups). In this problem linear speedups are obtained: with 16 SPUs, both the average and worst case times are about 16 times lower.