Determining if a number is power of two, is very old design problem. Various solutions to this already exists but performance of these solutions is evaluated based on software requirements only. But normally efficiency of algorithm depends on means to deliver it, Hardware performance is evaluated here for three such algorithms and shown that there is stark gap between software performance and hardware performance. Hardware evaluation parameters are also briefly discussed (from ASIC design Flow point of view). Towards the end, a noble method is proposed & evaluated to determine if number is power of 2.
In digital systems, integers are represented in terms of bits & binary numbers. The binary numeral system represents numeric values using two symbols, typically 0 and 1. More specifically, binary is a positional notation with a radix of two. A decimal number can be represented in binary system by following equation
N = bn.2n +bn-1.2n-1 + … + b1.21 + b0.20
In numeral world, For a number to be power of "radix", one and only one position can have value of 1. For example in decimal systems, for a number to be power of 10, only one digit can be 1. Similarly in binary systems, a number is power of 2 if one and only one bit has value of 1. All we have to do is to count the number of 1's to determine if a number is power of two. As it is evident, digital systems provide inherent advantage to solve this problem because information is stored in binary format.
First three existing methods are brifly discussed with associated Verilog RTL snippet. All of these methods are based on number of 1s.
Because of inherent difference in the way resources are allocated between software/processor and dedicated hardware, having same evaluation strategy for algorithm is not good enough. Hardware Performance of each algorithm is ranked based on following parameters
- Code Size – Affects designer productivity & bug count. It is determined based on number of written lines in Verilog RTL.
- Complexity – Algorithmic Complexity, increased bug count with increasing complexity. This is little subjective (Solely based on my observation)
- Basic Gate Count & Timing – Indicates "native" hardware resource requirement for implementation. To determine this parameter, Design Compiler is used with relaxed constraints (100 MHz for TSMC 0.18 library).
- Optimizable – Indicates if algorithm is suitable for further optimizations. To determine optimizability, Design Compiler is run with tight constraints (1 GHz for TSMC 0.18 library).
Generally, Software performance of algoritm is calculated based on number of cycles taken on a hypothetical processor. Number of cycles are also determined to show the difference between HW performance and software performance.
Next: Design Implementation 1 – Simple Count Mechanism