Intel® Hyperflex™ Architecture High-Performance Design Handbook

ID 683353
Date 10/04/2021
Public

A newer version of this document is available. Customers should click here to go to the newest version.

Document Table of Contents

2.4.1.1. Shannon’s Decomposition

Shannon’s decomposition plays a role in Hyper-Optimization. Shannon’s decomposition, or Shannon’s expansion, is a way of factoring a Boolean function. You can express a function as F = x.Fx + x′Fx′ where x.Fx and x′Fx′ are the positive and negative co-factors of the function F with respect to x. You can factor a function with four inputs as, (a, b, c, x) = x.(a, b, c, 1) + x′.F(a, b, c, 0), as shown in the following diagram. In Hyper-Optimization, Shannon’s decomposition pushes the x signal to the head of the cone of input logic, making the x signal the fastest path through the cone of logic. The x signal becomes the fastest path at the expense of all other signals. Using Shannon’s decomposition also doubles the area cost of the original function.

Figure 41. Shannon's Decomposition
Figure 42. Shannon's Decomposition Logic ReductionLogic synthesis can take advantage of the constant-driven inputs and slightly reduce the cofactors, as shown in the following diagram.
Figure 43. Repeated Shannon's DecompositionThe following diagram shows how you can repeatedly use Shannon's decomposition to decompose functions with more than one critical input signal, thus increasing the area cost.

Shannon’s decomposition can be an effective optimization technique for loops. When you perform Shannon’s decomposition on logic in a loop, the logic in the loop moves outside the loop. The Compiler can now pipeline the logic moved outside the loop.

Figure 44. Loop Example before Shannon's DecompositionThis diagram shows a loop that contains a single register, four levels of combinational logic, and an additional input. Adding registers in the loop changes the functionality, but you can move the combinational logic outside the loop by performing Shannon’s decomposition.

The output of the register in the loop is 0 or 1. You can duplicate the combinational logic that feeds the register in the loop, tying one copy’s input to 0, and the other copy’s input to 1.

Figure 45. Loop Example after Shannon's DecompositionThe register in the loop then selects one of the two copies, as the following diagram shows.

Performing Shannon’s decomposition on the logic in the loop reduces the amount of logic in the loop. The Compiler can now perform register retiming or Hyper-Pipelining on the logic you remove from the loop, thereby increasing the circuit performance.