================
Search component
================

* :ref:`Input component <user_guide_input>`
* :ref:`Quality assurance component <user_guide_qa>`
* :ref:`Approximation component <user_guide_approx>`
* :ref:`Estimation component <user_guide_estimation>`
* **Search component**
* :ref:`Output <user_guide_output>`

.. _user_guide_search:

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 :ref:`Estimation component <user_guide_estimation>`.

CIRCA's Search implementations are:
    - :ref:`gradient descent (or hill climbing) <gradient_descent>`, 
    - :ref:`Simulated Annealing <simulated_annealing>`, 
    - :ref:`Monte Carlo Tree Search <mcts>`, and 
    - :ref:`Jump Search <jump_search>`.


.. _gradient_descent:

Gradient Descent Search
-----------------------

Description
***********

The ``gradient_descent`` Search implementation uses a circuit configuration's *area* value and models it as a function of the configuration's current error bounds and approximation method. With this model of the search space in mind, a modified `gradient descent <https://en.wikipedia.org/wiki/Gradient_descent>`_ search algorithm is utilized to approach a minimum of that function. The starting point for the search is the original circuit.

To expand the search space, all *neighbors* of the current circuit configuration are generated. The neighbors of a configuration differ from the current configuration in either the approximation method or one error metric with an increased error bound.

The neighbors are then categorized into three groups by their *area* values: One group for circuits with *lower area* than the current circuit (*negative gradient*), one group for circuits with *the same area* (*zero-gradient*) and one group for circuits with *higher area* (*positive gradient*). The circuits from the first group with *the lowest area* are appended to a list of configurations to inspect later. More configurations, also from the other groups, are added to that list according to an *Effort* parameter set in the configuration file.

Depending on the configuration, either the best circuit from the list or a random circuit is then used as the new current circuit configuration for the next iteration. This cycle continues until the list is empty. This is the case if a local area minimum has been reached or the quality constraints allow no further area improvement.

.. admonition:: Notes and restrictions

    * This Search implementation considers exclusively the *area* values of the circuits and thus only leads to reliable area improvements.
    * The *Effort* parameter can be used to configure how many circuit configurations are inspected. The options vary from a straight-forward continuous area reduction to an exhaustive brute-force style search. This may lead to significant differences in runtime between the *Effort* levels.

Configuration options
*********************

:``Method``: ``gradient_descent``

:``Effort``: The effort level of the search, determines how many circuit configurations will be inspected. Possible values are integers ``0`` to ``6``:

    .. todo:: Update (and maybe reduce) the effort levels

    :``0``: Only negative gradients are inspected
    :``1``: All negative and 5 randomly chosen 0-gradients are inspected
    :``2``: All negative and 20 randomly chosen 0-gradients are inspected
    :``3``: All negative and randomly chosen 25% of 0-gradients are inspected
    :``4``: All negative and randomly chosen 50% of 0-gradients are inspected
    :``5``: All non-positive gradients are inspected
    :``6``: Take all gradients into account (pos., neg., and zero)

:``SelectStrategy``: (optional) Specifies whether the best (lowest gradient) or a random circuit configuration from the list will be used as starting point for the next iteration. Possible values are

    :``best``: (default) Take the best configuration
    :``random``: Take a random configuration


.. _simulated_annealing:

Simulated Annealing
-------------------

.. todo:: Add text

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 

.. math:: 

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

:math:`\Delta D` represents the change in the target metric and :math:`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 :math:`T`, the *equilibrium* has to be reached, i.e., *equilibrium* number of iterations have to be performed, before the temperature :math:`T` is lowered by

.. math::

    temperature = temperature * \alpha.

After the minimal temperature :math:`T_{Min}` is reached, the search terminates.

.. admonition:: 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 :math:`\geq 0`.

:``Alpha``: Rate at which the temperature is reduced after equilibrium is reached. Must be :math:`\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 :math:`\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 :math:`\Delta D` the relative hardware is used: :math:`\Delta D = \frac{area_{new} - area_{old}}{area_{old}}`.


.. _mcts:

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. 

.. math:: 

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

where :math:`W_i` is the reward value of the :math:`node_i`, and :math:`V_i` is the number of visits of the :math:`node_i`. Moreover, :math:`V_N` shows the number of visits for the parent of :math:`node_i`, and :math:`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:

.. math::
    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``

:``Budget``: Number of iterations for the search.

:``Scaler``: Constant value used in the UCT formula (usually ranges [0-2.5]).

.. _jump_search:

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): 

        .. math::

            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, if\ :sub:`err` and if\ :sub:`area`. 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.

    - L. Witschen, H. Ghasemzadeh Mohammadi, M. Artmann, and M. Platzner, "`Jump Search: A Fast Technique for the Synthesis of Approximate Circuits <http://embedded.unina.it/AxC19/>`_,” Presented at the Fourth Workshop on Approximate Computing (AxC '19) 2019, Florence, Italy, 2019. 

    - L. 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``: ``jump_search``

:``ImpactFactorsErr``: Dictionary containing the impact factors if\ :sub:`err` of each candidate. Example: 

    .. code-block:: none 

        ImpactFactorsErr = {'Cand_Adder_0': 0.16, 'Cand_Mult_0': 0.4, 'Cand_Adder_1': 0.914}

:``ImpactFactorsArea``: Dictionary containing the impact factors if\ :sub:`area` of each candidate. Example: 

    .. code-block:: none

        ImpactFactorsArea = {'Cand_Adder_0': 0.25, 'Cand_Mult_0': 0.412, 'Cand_Adder_1': 0.09}




~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

:ref:`Back to the User Guide <user_guide_built_ins>`