Location of Most Significant ‘ON’ Bit

reply.gifKnowing location of most significant bit in a given number has lots of application in Hardware, mainly in packet priority queueing. Easy way to determine this is to put a simple priority encoder but performance of this solution is not very good. In the Article, one more implementation is presented with better performance.

Main Article
By SVTechie on November 24, 2005

Imagine a scenario (Real application in Packet Manager) in which there are 4 ports, each having a bit, indicating data availablity at the port. Out of all 4 ports, Port 3 is assigned highest priority, meaning if data is available on port 3, data will be transferred regardless even if other ports have more or old data. Priority for other ports is assigned in decreasing order with port 0 having lowest priority. Priority Logic implementation for this scenario can be following. Construct a 4-bit number, each bit indicating data availability for corresponding port and determining the location of most significant 'ON' bit.

Above example can be solved easily by simple priority encoder implementation but for an application with great number of ports, this implementation may not be good enough. In this article, performance of simple priority encoder scheme is evaluated for 32 bit number. Then binary search based algorithm is introduced which has higher performance. Following is implementation for simple priority encoder.

 

 Simple Priority Encoder RTL
 module only1 (
     input wire [31:0] inb,
     input wire clk,
     input wire rst_n,
     output reg [4:0] loc,
     output reg val
     );

     reg if_1;
     reg [4:0] nval;
     integer i;

     always @(*) begin
       if_1 = 0;
       nval = 0;
       for (i = 31; i >= 0; i = i – 1) begin
         if (~if_1 & inb[i]) begin
           nval = i;
           if_1 = 1;
         end
       end
     end

     always @(posedge clk or negedge rst_n) begin
       if (~rst_n)
          loc <= 1'b0;
       else
          loc <= nval;
     end

     always @(posedge clk or negedge rst_n) begin
       if (~rst_n)
          val <= 1'b0;
       else
          val <= if_1;
     end

endmodule

HW performance is (Please Read This Article for HW Performance Parameters Discussion.)

    • Code Size – 32 (Less the better)  
    • Complexity – 8/10 on simplicity scale. (More the better – Little Subjective)
    • Basic Gate Count & Timing –  Area is 1185 micron2 (Less the better), Critical Path Delay 7.31ns(Less the better)
    • Optimizable – Area is 3500 micron2(Less the better), Critical Path Delay 1.19ns (Less the better)

Next: Design Implementation 2 – Binary Search Based Mechanism

Leave a Reply

Your email address will not be published. Required fields are marked *