Search component¶

Component description¶

The Search component specifies the algorithm which is used to navigate the search space. Its primary functions are selecting the circuit configuration to be validated next, expanding the search space by defining new circuit configurations to be generated, and evaluating the results of the approximation process by analyzing the circuit statistics generated by the Estimation component.

CIRCA’s Search implementations are:

Simulated Annealing¶

Description¶

Initially, the simulated_annealing search starts with the original circuit and a temperature of 1.0. During the search a node, i.e., a circuit, is randomly selected. Depending on the acceptance function, the selected node is either accepted or rejected. A node which improves the target metric is always accepted. A node which worsens the target metric may be accepted under the probability of

$random[0.0,1.0) < e^{-\frac{\Delta D}{T}}.$

$$\Delta D$$ represents the change in the target metric and $$T$$ the current temperature. If a node is accepted, its quality is verified. If the node is valid, the node is expanded, i.e., its neighboring nodes are generated, and its neighbors represent then the open-list. If the node is being rejected or invalid, another node from the open-list is randomly selected.

For each temperature $$T$$, the equilibrium has to be reached, i.e., equilibrium number of iterations have to be performed, before the temperature $$T$$ is lowered by

$temperature = temperature * \alpha.$

After the minimal temperature $$T_{Min}$$ is reached, the search terminates.

Notes and restrictions

• The search uses an initial temperature of 1.0.

Configuration options¶

Method:

simulated_annealing

TMin:

The minimal temperature at which the search terminates. Must be $$\geq 0$$.

Alpha:

Rate at which the temperature is reduced after equilibrium is reached. Must be $$\geq 0$$.

Equlibrium:

Number of iterations performed at each temperature.

Heuristic:

Specifies the target metric directly or uses a heuristic to express the merit of the node. The value is used to compute $$\Delta D$$ to determine whether a node is accepted or not.

Area: (default) The circuit’s hardware area is considered as target metric. For the computation of $$\Delta D$$ the relative hardware is used: $$\Delta D = \frac{area_{new} - area_{old}}{area_{old}}$$.

Monte Carlo Tree Search (MCTS)¶

Description¶

Monte Carlo tree search (MCTS) is a stochastic best-first search technique that exploits the generality of random sampling to build an efficient search algorithm. In each iteration, MCTS performs four main steps: selection, expansion, simulation and update. The selection step always starts from the root node of the search tree and attempts to reach at a leaf node while using the UCT score of each nodes as a heuristics in the path.

$UCT(node_{i}) = \frac{W_{i}}{V_{i}}+ C \sqrt{\frac{\ln(V_{N})}{V_{i}}}$

where $$W_i$$ is the reward value of the $$node_i$$, and $$V_i$$ is the number of visits of the $$node_i$$. Moreover, $$V_N$$ shows the number of visits for the parent of $$node_i$$, and $$C$$ represents the exploration constant which trades off between exploration and exploitation in the search tree.

The expand step adds new children nodes to the search tree. The simulate step then evaluates the node’s statistics and then calculates the weighted reward for the node based on the following formula:

$Reward_{node} = \alpha * area\_savings + \beta * delay\_savings + \gamma * power\_savings$

This completes one iteration of the MCTS. The search terminates when the allocated search budget to MCTS is exhausted.

Configuration options¶

Method: mcts Number of iterations for the search. Constant value used in the UCT formula (usually ranges [0-2.5]).

Jump Search (JS)¶

Description¶

The Jump Search search method seeks to minimize the runtime of the approximation process by minimizing the number of expensive synthesis and verification steps. JS operates in two phases:

Phase 1 (path planning): Determine a path through the search space, starting from the original circuit to the boundaries of the search space. In phase 1, the AxCs found, are being evaluated using the Figure of Merit (FOM):

$FOM(AxC) = \sum \limits_{cands \in AxC} \sqrt{\frac{Err(c)}{MaxE(c)}} \times \frac{if_{Area}(c)}{|if_{Err}(c)| + 1}$

The FOM takes into account the normalized error of the candidates within the AxC to balance the selection, as well as two impact factors, iferr and ifarea. The two impact factors of each candidate are being determined in a pre-processing step. Employing the FOM to evaluate the AxCs makes any invocation of synthesis or verification obsolete, and thus, significantly reduces the runtime of the approximation process.

Phase 2: JS makes the assumption that the deeper a node is on the path, the more aggressive are the applied approximation to that AxC, and thus, the larger are the expected savings. In phase 2, employing synthesis and verification is inevitable; however, to minimize the number of invoked synthesis and verification steps, a binary search is utilized, finding the deepest, valid node on the path.

Note

For a more detailed description, please see our paper presented at the 4th AxC workshop at the DATE‘19 conference and our paper presented at the GLSVLSI‘19 conference.

1. Witschen, H. Ghasemzadeh Mohammadi, M. Artmann, and M. Platzner, “Jump Search: A Fast Technique for the Synthesis of Approximate Circuits,” Presented at the Fourth Workshop on Approximate Computing (AxC ‘19) 2019, Florence, Italy, 2019.
1. Witschen, H. Ghasemzadeh Mohammadi, M. Artmann, and M. Platzner, Jump Search: A Fast Technique for the Synthesis of Approximate Circuits, In the proceedings of the Great Lakes Symposium on VLSI 2019 (GLSVLSI ‘19), 2019, Tysons Corner, VA, USA. ACM, New York, NY, USA, 6 pages. https://doi.org/10.1145/3299874.3317998.

Configuration options¶

Method: ImpactFactorsErr: jump_search Dictionary containing the impact factors iferr of each candidate. Example: ImpactFactorsErr = {'Cand_Adder_0': 0.16, 'Cand_Mult_0': 0.4, 'Cand_Adder_1': 0.914}  Dictionary containing the impact factors ifarea of each candidate. Example: ImpactFactorsArea = {'Cand_Adder_0': 0.25, 'Cand_Mult_0': 0.412, 'Cand_Adder_1': 0.09} 

Back to the User Guide