Simulated Annealing — TimberWolf (Part 1–2).
An overview to the Timber Wolf Algorithm.
Placement and routing are done in three steps by TimberWolf. Using simulated annealing, the cells are arranged in the first step to reduce the anticipated wire length. Feed-through cells are placed as needed in the second step, the wire length is reduced again, and preliminary global routing is completed. In the third step, when practicable, local alterations in the location are made to decrease the number of wire tracks necessary.
The following are the TimberWolf simulated annealing parameters.
Move Generation Function
To produce new configurations from the present configuration, two approaches are employed. Either a cell is randomly picked and moved to a random spot on the chip, or two cells are randomly picked and swapped. The algorithm’s performance was shown to be influenced by r, the ratio of displacements to interchanges. According experimental data, the method performs best with 3<r<8.
Cell mirroring around the horizontal axis is also performed, but only when a displacement is denied and only in around 10% of the cases chosen at random. A temperature-dependent range limiter is also used to restrict the distance that a cell may travel. Because the range limiter’s span is initially double that of the chip, no restricting is done over a wide range of high temperatures. With increasing temperature, the span falls logarithmically:
Inner Loop Criterion
A set number of movements per cell is tried at each temperature. This number is a user-specified parameter. As the number of movements per cell increases, the ultimate wire length reduces monotonically. However, when the number of movements rises, the reduction in ultimate wire length decreases, resulting in significant increases in CPU time. The ideal number of movements per cell is determined by the circuit’s size.
Cooling Schedule and Stopping Criterion
An analogy to the crystallisation process may be used to describe the cooling timetable. It is critical to drop the temperature steadily around the melting point in order to obtain a flawless crystal structure. Most of the movements are allowed since the annealing process begins at a very high temperature, 1 = 4,000,000. The cooling schedule is depicted as follows:
The temperature is rapidly lowered at beginning [a(T) = 0.8]. The temperature is then gradually decreased in the medium temperature range [a(T) = 0.95]. This is where the majority of the processing takes place. The temperature drops significantly in the low temperature range [Q(T) = 0.8]. Figure below depicts the resulting cooling schedule.
This blog would be followed by blogs on Futuristic advancements in Simulated Annealing where more nuances about Simulated annealing would be explored.
This Blog has been published as a part of a blog series on the topic “VLSI Cell Placement Techniques” which is a Co-Curriculum activity in our college (Vishwakarma Institute Of Technology, Pune) which is aimed at giving the students a comprehensive understanding of the Industry Practices in the field of Digital Design. We hope this blog has been a informative read for you.
