
| problem   | master square   | squares to place   |           |
|-----------|-----------------|--------------------|-----------|
| instance  | size            | number             | largest   |
| 1         | 112 × 112       | 21                 | 50 × 50   |
| 2         | 228 × 228       | 23                 | 99 × 99   |
| 3         | 326 × 326       | 24                 | 142 × 142 |
| 4         | 479 × 479       | 24                 | 175 × 175 |
| 5         | 524 × 524       | 25                 | 220 × 220 |

| size   | time    | speedup with k SPUs   | time   |     |      |         |       |
|--------|---------|-----------------------|--------|-----|------|---------|-------|
| 1 SPU  | 2       | 4                     | 8      | 12  | 16   | 16 SPUs |       |
| 1      | 14.844  | 1.9                   | 4.9    | 8.1 | 11.3 | 16.6    | 0.894 |
| 2      | 30.395  | 1.5                   | 4.4    | 6.7 | 10.0 | 14.4    | 2.105 |
| 3      | 55.973  | 1.6                   | 2.9    | 6.5 | 12.7 | 14.1    | 3.963 |
| 4      | 75.915  | 1.8                   | 3.0    | 5.4 | 9.3  | 15.4    | 4.933 |
| 5      | 143.436 | 2.1                   | 3.7    | 6.7 | 10.7 | 15.1    | 9.517 |

## 5.4 Magic Squares

The magic square problem is listed as prob019 in CSPLib [6] and consists in placing the numbers
{1,2···N
2} on an N × N square, such that the sum of the numbers in all rows, columns and the two diagonal is the same. The constant value that should be the sum of all rows, columns and the two diagonals can be easily computed to be N(N
2 +1)/2.

The modeling for AS/Cell involves N
2 variables X1*,...,*XN2 . The error function of an equation X1 +X2 +...+Xk = b is defined as the value of X1 +X2 +...+Xk −b. The combination operation is the sum of the absolute values of the errors. The overall cost function is the addition of absolute values of the errors of all constraints. A configuration with zero cost is a solution.

Table 8 details the average running times (in seconds) for several instances of this problem together with the speedup obtained when using different numbers of SPUs. Using 16 SPUs, the obtained speedup increases with the size of the problem to reach 22 for the largest instance.

It is worth noticing that this benchmarks is one of the most challenging: Constraint programming

| #SPUs      | average case   | worst case   |         |      |
|------------|----------------|--------------|---------|------|
| time (sec) | speedup        | time (sec)   | speedup |      |
| 1          | 143.436        | 1.0          | 456.470 | 1.0  |
| 2          | 66.775         | 2.1          | 217.330 | 2.1  |
| 4          | 39.180         | 3.7          | 117.410 | 3.9  |
| 8          | 21.481         | 6.7          | 64.330  | 7.1  |
| 12         | 13.467         | 10.7         | 47.170  | 9.7  |
| 16         | 9.517          | 15.1         | 27.550  | 16.6 |
