Exchangeable components

Search component overview

Search component

The Search component controls how the search space (modeled as a tree-like graph structure) is traversed, i.e., which nodes to approximate and validate next and when to terminate the approximation process. This also means that the Search component must manage already visited nodes, soon to be visited nodes, and “anomalies” in the search space, such as recurring circuit configurations, on its own.

Structure of the search space

Term definitions

To talk about the concepts of the search space more efficiently, we first define some terms and explain their meaning. The figure above visualizes the terms.

Candidate:

A candidate is a part of the input circuit which can be approximated independently and then inserted back into the input circuit to replace its own original variant, thereby creating an approximated version of the whole input circuit. The set of candidates of the input circuit is generated during the Input stage before the approximation process begins. For each candidate there must be at least one approximation method and at least one error metric with an upper bound specified.
Variant:

We denote an approximated version of a candidate as variant. Each variant has a unique candidate, but candidates generally have multiple variants. The original, non-approximated version of a candidate is called original variant. Variants are uniquely identified by the ID of their candidate in conjunction with an error bound for each error metric and exactly one approximation method.
Circuit configuration:
 

Assume the input circuit has the candidates \((C_1,C_2,\ldots,C_n)\) and each candidate \(C_j\) can be represented by one of its variants \(\{V_{1}^{(j)},V_{2}^{(j)},\ldots,V_{m}^{(j)}\}\). We call the tuple of variants \(\left(V_{x}^{(1)},V_{y}^{(2)},\ldots,V_{z}^{(n)}\right)\) the configuration of the circuit in which each candidate \(C_j\) is replaced by one of its variants \(V_{i}^{(j)}\). A circuit configuration is unique.
Node:

A node in the search space represents a single circuit configuration \(\left(V_{x}^{(1)},V_{y}^{(2)},\ldots,V_{z}^{(n)}\right)\) and is treated as a node (or vertex) in a graph. It is connected to its parent node and to its child nodes (or children) once they are created. The children of a node represent circuit configurations which differ from the node (their parent node) in exactly one variant, i.e., one variant \(V_{i}^{(j)}\) is replaced by another variant of that candidate \(C_j\) and all other variants remain the same. The new variant of that candidate is not arbitrary, but must have either a different approximation method or a single error bound increased by one step. Note that nodes representing the same configuration can be created by different parent nodes, so that some nodes in the search space may have multiple parent nodes (this is the reason why the search space is not really a tree). The node representing the circuit configuration with only original variants is called the root node. It does not have a parent node.

Nodes are represented by Node instances which contain all necessary information about the circuit configuration represented by the graph node. A Node instance can generate its children with the generateChildren method. These nodes are freshly generated each time the method is called and neither do they have any file representations nor are they stored in any data structure, i.e., at first, they are temporary objects iwth the minimal required information. The search can then decide whether these nodes are generated by the approximation stage or simply discarded.

Functions

setup(gen_info: GeneralInformation, root_node: Node): None

The setup method can be used to initialize the component by storing the GeneralInformation instance and the search space’s root node. The default implementation does exactly these two things. This is where you should initialize data structures and variables based on the CandidateSet instance in GeneralInformation, which is complete at this point and defines all possible circuit configurations that can occur in the search space.

hasTerminated(): Boolean

This is a simple query issued at the start of every iteration. It should return True if and only if the search has finished and there is nothing left for the component to do. When this happens, the approximation process stops and the output is generated.

Note

Note that by implementing this method incorrectly you can run into an infinite loop, so make sure to double check your termination conditions!

popNextNode(): Node

The popNextNode method is called once at the start of every iteration and it will return one Node instance. The returned instance is validated by the QualityAssurance component. Only if it is validated successfully, the other methods of the Search component are called in that iteration. With this in mind, you should implement your Search component in a way that supports multiple consecutive calls of this function.

In the context of the search space graph, the returned Node marks the current position in the search space. Note that, if it is validated successfully, you can use this fact to generate new nodes from this position to explore the search space step by step.

expandSearchSpace(): List<Node>

The expandSearchSpace method is the first method which is called if a node was successfully validated. It returns a list of newly generated Node instances which will then be approximated and analyzed, i.e., they will receive files for their variants and circuits and their stats dictionaries will be filled with values for the metrics supported by the Estimation component.

To create a better intuition for the purpose of this method, imagine a search space tree with only the current node in it. The expandSearchSpace method returns a list of all hidden nodes which are possible candidates for exploration in the next iterations and marks them for the other components so they can discover them and fill them with information. In many cases, it makes sense to simply return the children of the current node.

evaluateNodes(): None

The evaluateNodes method is called at the end of each iteration if the current node was validated successfully. It gives you the chance to process the results of the Approximation and Estimation stage before popNextNode is called again. The Nodes that were returned by expandSearchSpace have now been approximated and filled with statistics to evaluate. As a rule of thumb, in this method you should create a sorted list of all Nodes you want to validate, using the statistics generated by the Estimation component.

Back to the Developer Guide