Information Technology Reference
In-Depth Information
Kernighan-Lin.
This algorithm is one of the most commonly used in the class
of partition based methods. It heuristically divides the graph into sub-regions,
trying to minimize the cut, i.e. the number of edges that connect one sub-region
from the others.
Simulated Annealing.
It is a stochastic algorithm that iteratively swap the posi-
tion of nodes inside the graph trying to find the global minimum through con-
secutive solutions. The purpose of this technique is to minimize the number
of cross-wires during the global placement. The algorithm needs three data as
input:
- The graph nodes
.
- The minimum temperature that must be reached.
- The number of iteration that are necessary to obtain the final state.
V
The parameters used determine the eciency of the simulated annealing
algorithm, and these parameters must be chosen according to experience. While
simulated annealing can lead to very good results, its a stochastic method that
heavily relies on the parameters used, on the function used to generate random
numbers and generally requires a huge time to converge.
References.
Since the cross-wires minimization techniques here proposed are
based on algorithm taken from the literature, here some references are included
for interested readers. For the barycenter technique users can refer to [
42
,
43
]
where these algorithms were already applied to QCA technology. For Kernighan-
Lin technique the readers may refer to [
44
,
45
] while for simulated annealing
readers may refer to [
46
-
48
]. These were the starting point, the algorithms have
been reworked and adapted in order to be used on nanomagnet logic circuits.
4.2 Physical Mapping
During the physical mapping phase, the previous elaborated graph is trans-
formed into the final circuit layout. Due to the high complexity of today ICs,
the physical placement cannot be obtained in a single routing phase. For this
reason, a three steps approach is followed:
- Placement, where graph nodes are mapped to their correspondent logic gate
and they are initially placed on the layout.
- Global routing, where an iterative approach is used to find the optimum posi-
tion for logic gates.
- Detailed routing, where interconnection wires among gates are routed.
In Fig.
13
a general flow diagram is shown.
Every node of the graph is mapped into its corresponding logic gate and it
is placed into the circuit. Then, a global routing is performed. This process try
to place each logic gate in order to minimize the occupied area. After the blocks
positioning phase a detailed routing is performed among gates.
Search WWH ::
Custom Search