New Data Structures and Algorithms for Logic Synthesis and Verification by Luca Gaetano Amaru

Author:Luca Gaetano Amaru
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

3.4.2 Depth-Oriented MIG Algebraic Optimization

To optimize the depth of a MIG , we aim at reducing the length of its critical path. A valid strategy for this purpose is to move late arrival (critical) variables close to the outputs. In order to explain how critical variables can be moved, while preserving the original functionality, consider the general case in which a part of the critical path appears in the form M(x, y, M(u, v, z)). If the critical variable is x, or y, no simple move can reduce the depth of M(x, y, M(u, v, z)). Whereas, if the critical variable belongs to M(u, v, z), say z, depth reduction is achievable. We focus on the latter case, with order for the variables arrival time (depth). Such an order can arise from (i) an unbalanced MIG whose inputs have equal arrival times, or (ii) a balanced MIG whose inputs have different arrival times. In both cases, z is the critical variable arriving later than u, v, x, y, hence the local depth is . If we apply the distributivity axiom from left to right (), we obtain where z is pushed one level up, reducing the local depth to . Such technique is applicable to a broad range of cases, as all the variables appearing in M(x, y, M(u, v, z)) are distinct and independent. However, there is a size penalty of one extra node. In the favorable cases for which associativity axioms (, ) apply, critical variables can be pushed up with no penalty. Furthermore, where majority axiom applies , it is possible to reduce both depth and size. As noted earlier, there exist cases for which moving critical variables cannot improve the overall depth. This is because (i) the optimal depth is reached or (ii) we are stuck in a local minimum. To move away from a local minimum, the reshape process is useful. The reshape and critical variable push-up processes can be iterated over a user-defined number of cycles, called effort. Such MIG-depth algebraic optimization strategy is summarized in Algorithm 3.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.