Title: EE4218_EHSD / Technology Mapping
On every note of this deck, unless a note says otherwise:
Title: EE4218_EHSD::Technology Mapping
Logo: tum_logo.png

Front: What is technology mapping?
Back: Converts the technology independent network resulting from logic optimization by matching pieces of the network with the logic cells available.

Front: What does the algorithm attempt while performing technology mapping?
Back: Minimize area, while meeting user constraints.

Front: What is the output of technology mapping?
Back: Network of technology cells

Front: What is the three step procedure for technology mapping?
Back: 1. Decomposition
2. Partitioning
3. Matching and Covering

Front: What is done in step one when performing technology mapping?
Back: Decomposition. Boolean function is restructured into subject graph.

Front: What is done in step two when performing technology mapping?
Back: Partitioning. Partitions the big network into sub-networks.

Front: What is done in step three when performing technology mapping?
Back: - Find matches between patterns and regions of cells in the subject graph
- Use patterns to cover the subject graph

Front: What is the most common choice for primitives when decomposing a network?
Back: NAND2and INV

Front: True or False. The library cells must be decomposed in logic decomposition.
Back: True.

Front: How is the subject network reduced in the partitioning step.
Back: Reduced to many multi-input, single-output networks.

Front: Why is the subject network partitioned?
Back: Reduces the size of covering problem.

Front: What are implications of the partitioning of the subject network?
Back: - Might reduce problem difficulty
- Hurts the quality of the final solution

Front: Describe the partitioning algorithm.
Back: - Mark vertices with multiple out degrees
- Edges whose tails are marked as vertices define the partition boundary

Front: What are the two main types of pattern matching?
Back: - Structural matching
- Boolean matching

Front: How does the structural matching algorithm work?
Back: Identifies if a pattern tree is isomorphic to a subgraph of the subject tree recursively

Front: What are problems with structural matching?
Back: - Trees only
  - No matching across fanout nodes
  - No XOR gates
- Imperfect matchings: Different structure, same function not identified.

Front: Explain the concept behind boolean matching.
Back: - Relies on matching the pattern to the subject network logically
- Decomposition independent

Q: Patterns that match [...] will always match with boolean
matching, but not necessarly the other way.
A: structurally
Title: EE4218_EHSD::Technology Mapping

Front: How does boolean matching work?
Back: Matching of two functions f and g involves comparing to functions for equivalence and finding and assignments of the cluster variables to pattern inputs.
Functional equivalence.

Front: How can Equivalence of functions be grouped into categories?
Back: - NPN-equivalent
- PN-equivalent
- P-equivalent

Front: What is NPN equivalence?
Back: Equivalent under input negation, input permutation and output negation.

Front: What is PN equivalence?
Back: Equivalent under input permutation and output negation.

Front: What is P equivalence?
Back: Equivalent under input permutation.

Front: What are boolean signatures?
Back: Signature of a Boolean function is a compact representation that characterizes some of the properties of Boolean functions.

Front: How are boolean signatures used?
Back: As filters to reduce computation.

Front: Examples for boolean signatures?
Back: - Symmetries of a function
- Number of unate/binate variables.

Front: What are unate variables?
Back: A unate variable in a Boolean function has a consistent polarity (always appears as x or !x , but not both).

Front: What are binate variables?
Back: A binate variable appears in both forms (x and !x) in the function.

Q: DAG covering is [...].
A: NP hard
Title: EE4218_EHSD::Technology Mapping

Q: Tree-covering-by-tree is [...].
A: in P
Title: EE4218_EHSD::Technology Mapping

Front: What are the two steps in tree-covering-by-tree?
Back: 1. Treeifying
2. Dynamic Programming

Front: How does tree-covering-by-tree dynamic programming algorithm work?
Back: - Visit subject tree bottom up
- At each vertex attempt to match:
  - Locally rooted sub-tree to all library cells
  - Find best match and record

Front: What is Polarity Assignment in tree-covering-by-tree?
Back: - Optimal polarity assignment
- All connections between base gates are replaced by inverter pairs
  - Connections to or from inverters don't need to be replaced
- Transformation applied to subject and pattern graphs.

Front: How is FPGA technology mapping achieved?
Back: - Decomposition and partitioning are still done to reduce the problem to a manageable size
- Matching and covering done differently, as we have LUTs or MUXs.

Front: How are SOP expressions of a single-output function partitioned into groups that are then assigned to LUTs (n-input LUTs)?
Back: - If the function has a total of nvariables, the entire function can be implemented in ONE table
- Else, groups of SOP terms need to be assigned to different tables
-> Modified Bin Packing

Front: How does the Modified Bin Packing algorithm work?
Back: - Iterate the following steps until all product term:
  - Select the product term with the most variables
  - Place it into any table where it fits, otherwise new table
- When all product terms done, iterate the following
  - Declare the table with the fewest unused variables as final and associate a variable with it
  - Assign this variable to the first table that can accept
Procedure terminated when only one table is left.

Front: Does the Modified Bin Packing algorithm always compute an optimal solution?
Back: No it is a heuristic.

Front: What is Packing?
Back: - Step after matching and covering.
- Logic block packing groups several LUTs and registers into one logic block under constraints

Front: How does Packing work?
Back: Form of clustering: partition size
- Dividing a netlist into several pieces, under constraints e.g. maximum
- Optimizing a goal such as minimizing the number of connections that cross partitions