$1.$

Question $1$

Anneal Placement

Consider this small placement of $6$ gates in a small $6$x$6$ grid.

Each gate is drawn as a circle with number $(16).$ Assume the gate is located at the center of the grid cell, and its $($X$,$ Y$)$ coordinates are taken from the column $($X$)$ and row $($Y$)$ coordinates in the figure. There are $4$ nets, labeled A$,$ B$,$ C and D$,$ connected as follows:

Net A: gates $1,2,5$

Net B: gates $1,3$

Net C: gates $2,3,4$

Net D: gates $1,4,6$

A simple illustration of each net is also shown on the placement grid.

We now swap gates $5$ and $6,$ as shown in the diagram. Assume this happens inside a simulated annealing placer, and that the current temperature is T$=10.$ We use HPWL as the cost function.

Do this:

Compute $$L $=($new HPWL after swap$)($old HPWL before swap$).$ To be clear: if the wirelength increases, this is a positive number; if it decreases, it is a negative number.

Compute the acceptance probability that this swap of gates $5$ and $6$ will be accepted at this temperature. Round your solution $($a number$)$ to $3$ decimal places, e$.$g$.,0\mathrm{.}871$ or $0\mathrm{.}094.$

Which of these are correct statements?

$10$ points

The acceptance probability for the swap is $0\mathrm{.}819.$

The acceptance probability for the swap is $0\mathrm{.}741.$

If we choose a random value R uniformly in $[0,1]$ and we get R$=0\mathrm{.}345,$ we accept the swap.