# Stochastic-Based Spin-Programmable Gate Array with Emerging MTJ Device Technology
## 5 CAD Algorithms
### Placement Algorithm  
Our placement software for the S-FPGA is based on a simulated annealing approach with a cost function especially designed to match the routing fabric of the stochastic-based SPGA. For a island-style FPGA, the placement normally uses metrics such as wirelength as well as some measure of the routability and delay. If applying the same methodology to the SPGA, minimizing these metrics will not be able to exploit the configurable logic output and logic granularity of a SLB, which almost certainly results in less efficiency. The placement procedure of the SPGA architecture differs from the island-style FPGA in a fundamental way: its successful routing relies heavily on configuring some SLBs as variable-output logic blocks. To achieve high logic density, the routing resource in a SPGA should be distributed non-uniformly based on the routing demands between each pair of logic blocks. As a result, all SLBs must be configured and positioned as part of the placement process.  
```
1:\(p\leftarrow\) RandomPlacement()
2:\(T\leftarrow\) InitialTemperature()
3:\(g\leftarrow\) g(\(\mathcal{A}\),\(p\))
4:freeze_count \(<\) 50
5:while (ExitCriterion() is FALSE) do
6: changes \(\leftarrow\) 0
7: trials \(\leftarrow\) 0
8:\(c\leftarrow\) EvaluateCost(\(g\),\(b\))
9:while (InnerLoopCriterion() is FALSE) do
10: trials \(\leftarrow\) trials + 1
11:\(p_{\text{new}}\leftarrow\) RandomSwap(\(p\))
12: IncrementalRoute(\(g\)(\(\mathcal{A}\),\(p_{\text{new}}\)), \(b\))
13:\(\Delta c\leftarrow\) EvaluateCost(g(\(\mathcal{A}\), \(p_{\text{new}}\))) \(-\)\(c\)
14:if\(\Delta c<\) 0 /*downhill move*/ then
15: changes \(\leftarrow\) changes + 1
16:\(p\gets p_{\text{new}}\)
17:\(g\leftarrow\) g(\(\mathcal{A}\), \(p\))
18:\(c^{*}\leftarrow\) EvaluateCost(g(\(\mathcal{A}\), \(p_{\text{new}}\)))
19:endif
20:if\(\Delta c>\) 0 /*uphill move*/ then
21:\(r\leftarrow\) Random(0,1)
22:if\(r<e^{-\frac{M}{T}}\)then
23:\(s\gets p_{\text{new}}\)
24:\(g\leftarrow\) g(\(\mathcal{A}\), \(p\))
25:endif
26:endif
27:endwhile
28:\(T\leftarrow\) UpdateTemperature()
29:if\(c^{*}\) changes then
30: freeze_count \(\leftarrow\) 0
31:endif
32:if\(\frac{changes}{trials}<\) 0.01 then
33: freeze_count \(\leftarrow\) freeze_count + 1
34:endif
35:endwhile
```  
**Algorithm 2** The placement algorithm of SPGA.  
We now describe some of functions referred to in Algorithm 2 in more detail. ExitCriterion() make sure the freeze_count is less than a predetermined number, which is set equal to 50. InnerLoopCriterion() is true if trials \(<\) TRIALS and changes \(<\) CHANGES. Both constants TRIALS and CHANGES are related to the problem size. We set TRIALS and CHANGES equal to 10 W and 0.01 W, respectively. Given a placement of SLB blocks and the benchmark design, the first step of evaluating the cost is to perform the routing using the Steiner tree algorithm. It is well-known that most Steiner tree problems are NP-complete, i.e., thought to be computationally hard. To simplify our placement algorithm and to combat the intractability, we use a heuristic [34], in which we compute the Euclidean minimum spanning tree to approximate the Euclidean Steiner tree problem. Let \((x_{i,j},y_{i,j})\) be the cost pair for a SLB block located at \((i,j)\). \(x_{i,j}\) be the total number of routed signals along both \(x\)- and \(y\)-directions above the SLB block \((i,j)\), \(y_{i,j}\) be the total number of routed signal turns above the SLB \((i,j)\),  
\[\bar{x}=\frac{1}{MN}\sum_{i=1}^{M}\sum_{j=1}^{N}x_{i,j},\ \bar{y}=\frac{1}{MN}\sum_{i=1}^{M}\sum_{j=1}^{N}y_{i,j} \tag{2}\]\[c=\sqrt{\frac{1}{MN}\sum_{i=1}^{M}\sum_{j=1}^{N}x_{i,j}^{2}-\tilde{x}^{2}}+\sqrt{ \frac{1}{MN}\sum_{i=1}^{M}\sum_{j=1}^{N}y_{i,j}^{2}-\tilde{y}^{2}} \tag{3}\]  
The value of cost \(c\) roughly reflects the variance of the demand for routing resource from all SLB blocks. Intuitively, small \(c\) means high placement quality in terms of the overall routability.