Maximizing and Finding the Second Maximum Value Using FPGA

Welcome FPGA engineers to join the official WeChat group.

Implement a module on FPGA to find the maximum value and second maximum value among 32 inputs, given in one clock cycle. (This question is from a forum, an interview question; if you find it inappropriate, please leave a message to delete it.)

Clickthe blue wordsto follow us, FPGA Home – the best and largest pure FPGA engineering community in China

Maximizing and Finding the Second Maximum Value Using FPGA

From my personal point of view, this is a very good interview question:

  • Firstly, this is probably a simplification of problems encountered in some machine learning algorithms, making it a meaningful question;

  • Secondly, this question requires not only FPGA coding skills but also many possibilities for algorithm optimization;

Of course, the bit width of the input may affect the final solution and implementation possibilities. However, within a certain range, such as 8 or 32, the solution should be consistent, only affecting the final frequency. The following text will analyze this question in detail. (The question does not specify how to handle duplicate elements; here it is assumed that the maximum and second maximum values can be the same, i.e., counting duplicate elements.)

1. Solution

From the algorithm itself, the process of finding the maximum and second maximum values is very simple; through two traversals: the first to find the maximum value, the second to find the second maximum value; the algorithm complexity is O(2n). It is obviously impossible for FPGA to complete such a complex operation in one cycle, and generally requires pipeline design. Under this method, the entire structure is as follows:

  1. By comparison, find the maximum value, using a pipeline to compare pairs, 32-16-8-4-2-1 can find the maximum value with 5 clock delays;

  2. Since the second maximum value needs to be determined, it is necessary to maintain the coordinates of the maximum value during the process of finding the maximum value;

  3. Clear the value at the maximum coordinate (set to minimum)

  4. By pipeline implementation of pairwise comparisons, 32-16-8-4-2-1, after 5 clock delays can find the second maximum value;

This solution has several drawbacks, including: the delay for finding the maximum and second maximum values requires 5 clock delays each, the total delay will exceed 10 cycles; resource usage is relatively high, maintaining the coordinates of the maximum value and the clearing operation consume a lot of resources, and to calculate the second maximum value, it is necessary to store inputs for several cycles, which consumes a lot of registers.

Another idea is to consider finding the maximum and second maximum values simultaneously. Since this logic is relatively complex, it can be pipelined, as shown in the figure below. (For 8 inputs, 32 inputs need to increase two levels)

Maximizing and Finding the Second Maximum Value Using FPGA

In this, the sort module completes the sorting of 4 inputs, obtaining the maximum and second maximum values output. Sorting 4 numbers is relatively complex, and this process takes about 2-3 cycles to complete. For 32 inputs, the input data goes through 32-16-8-4-2 to get the result, with a delay of about 10 cycles.

2. Divide and Conquer

If you need to implement a specific algorithm on FPGA, then find a suitable method to implement it; but if you want to achieve a specific function, then you need to find an excellent and suitable method for FPGA implementation.

Finding the maximum and second maximum values is a very incomplete sorting process, with a simple search complexity of O(2n), which is not conducive to hardware implementation. For sorting, whether it is quicksort or merge sort, both use the divide and conquer approach. If we try to solve this problem using the divide and conquer method, consider when there are only 2 inputs, one comparison can yield the output, resulting in an ordered array of length 2. If there are two ordered arrays, then two comparisons can yield the maximum and second maximum values. Using the merge sort approach, the complexity of finding the maximum and second maximum values is O(1.5n) (i.e., n/2+n/2+n/4…, not sure if I calculated it wrong). Using the merge sort approach is more efficient from an algorithmic time complexity perspective.

So is this solution suitable for FPGA implementation? The answer is definitely yes. The locality of divide and conquer is suitable for FPGA’s pipeline implementation, as shown in the block diagram below. (For 8 inputs, 32 inputs need to increase two levels)

Maximizing and Finding the Second Maximum Value Using FPGA

In this, the meg module has two levels of comparators, generally, it can be completed in 1 clock cycle, and the input data goes through 32-32-16-8-4-2 to get the result, with a delay of 5 clock cycles. The implementation code is as follows:

Code

 
  1. module test#(

  2. parameter DW = 8

  3. )

  4. (

  5. input clk,

  6. input [32*DW-1 :0] din,

  7. output [DW-1:0] max1,

  8. output [DW-1:0] max2

  9. );

  10. wire[DW-1:0] d[31:0];

  11. generate

  12. genvar i;

  13. for(i=0;i<32;i=i+1)

  14. begin:loop_assign

  15. assign d[i] = din[DW*i+DW-1:DW*i];

  16. end

  17. endgenerate

  18. // stage 1,comp

  19. reg[DW-1:0] s1_max[15:0];

  20. reg[DW-1:0] s1_min[15:0];

  21. generate

  22. for(i=0;i<16;i=i+1)

  23. begin:loop_comp

  24. always@(posedge clk)

  25. if(d[2*i]>d[2*i+1])begin

  26. s1_max[i] <= d[2*i];

  27. s1_min[i] <= d[2*i+1];

  28. end

  29. else begin

  30. s1_max[i] <= d[2*i+1];

  31. s1_min[i] <= d[2*i];

  32. end

  33. end

  34. endgenerate

  35. // stage 2,

  36. wire[DW-1:0] s2_max[7:0];

  37. wire[DW-1:0] s2_min[7:0];

  38. generate

  39. for(i=0;i<8;i=i+1)

  40. begin:loop_megs2

  41. meg u_s2meg(

  42. .clk(clk),

  43. .g1_max(s1_max[2*i]),

  44. .g1_min(s1_min[2*i]),

  45. .g2_max(s1_max[2*i+1]),

  46. .g2_min(s1_min[2*i+1]),

  47. .max1(s2_max[i]),

  48. .max2(s2_min[i])

  49. );

  50. end

  51. endgenerate

  52. // stage 3,

  53. wire[DW-1:0] s3_max[3:0];

  54. wire[DW-1:0] s3_min[3:0];

  55. generate

  56. for(i=0;i<4;i=i+1)

  57. begin:loop_megs3

  58. meg u_s3meg(

  59. .clk(clk),

  60. .g1_max(s2_max[2*i]),

  61. .g1_min(s2_min[2*i]),

  62. .g2_max(s2_max[2*i+1]),

  63. .g2_min(s2_min[2*i+1]),

  64. .max1(s3_max[i]),

  65. .max2(s3_min[i])

  66. );

  67. end

  68. endgenerate

  69. // stage 4,

  70. wire[DW-1:0] s4_max[1:0];

  71. wire[DW-1:0] s4_min[1:0];

  72. generate

  73. for(i=0;i<2;i=i+1)

  74. begin:loop_megs4

  75. meg u_s4meg(

  76. .clk(clk),

  77. .g1_max(s3_max[2*i]),

  78. .g1_min(s3_min[2*i]),

  79. .g2_max(s3_max[2*i+1]),

  80. .g2_min(s3_min[2*i+1]),

  81. .max1(s4_max[i]),

  82. .max2(s4_min[i])

  83. );

  84. end

  85. endgenerate

  86. // stage 5,

  87. meg u_s5meg(

  88. .clk(clk),

  89. .g1_max(s4_max[0]),

  90. .g1_min(s4_min[0]),

  91. .g2_max(s4_max[1]),

  92. .g2_min(s4_min[1]),

  93. .max1(max1),

  94. .max2(max2)

  95. );

  96. endmodule

  97. module meg#(

  98. parameter DW = 8

  99. )

  100. (

  101. input clk,

  102. input [DW-1 :0] g1_max,

  103. input [DW-1 :0] g1_min,

  104. input [DW-1 :0] g2_max,

  105. input [DW-1 :0] g2_min,

  106. output reg [DW-1:0] max1,

  107. output reg [DW-1:0] max2

  108. );

  109. always@(posedge clk)

  110. begin

  111. if(g1_max>g2_max) begin

  112. max1 <= g1_max;

  113. if(g2_max>g1_min)

  114. max2 <= g2_max;

  115. else

  116. max2 <= g1_min;

  117. end

  118. else begin

  119. max1 <= g2_max;

  120. if(g1_max>g2_min)

  121. max2 <= g1_max;

  122. else

  123. max2 <= g2_min;

  124. end

  125. end

  126. endmodule

3. Others

Simple testing of the above code on the previous generation device (20nm FPGA), the 8bit data input module can synthesize to a very high frequency, with a logic level of about 5 levels. For the entire project, the bottleneck will not occur in this part. The 32bit data input frequency will not be very high due to the large data width, but by making the meg module one level pipeline, it will hardly become the bottleneck of the entire system.

In the case of 32-bit 32 inputs, the data input width is 1024 (not IO input, but internal signal). Previously, such a large width of data may not be used in communication/digital signal processing, but for AI applications on FPGA, thousands of bits of input should be very common, which will indeed affect the final implementation effect on FPGA. To make machine learning algorithms run better on FPGA, both algorithms and FPGA need to work together.

Maximizing and Finding the Second Maximum Value Using FPGA

Welcome communication engineers and FPGA engineers to follow the public account

Maximizing and Finding the Second Maximum Value Using FPGA

The largest FPGA WeChat technology group in the country

Welcome everyone to join the national FPGA WeChat technology group, this group has tens of thousands of engineers, a group of engineers who love technology, here FPGA engineers help each other, share, with a strong technical atmosphere!Quickly call your friends to join!!

Maximizing and Finding the Second Maximum Value Using FPGA

Press and hold to join the national FPGA technology group

FPGA Home Components City

Advantageous component services, if needed, please scan the code to contact the group owner: Jin Juan Email: [email protected] Welcome to recommend to procurement

ACTEL, AD part of the advantageous ordering (operating the full series):

Maximizing and Finding the Second Maximum Value Using FPGA

XILINX, ALTERA advantageous spot or ordering (operating the full series):

Maximizing and Finding the Second Maximum Value Using FPGA

(The above components are part of the models, for more models please consult the group owner Jin Juan)

Service concept: FPGA Home Components self-operated City aims to facilitate engineers to quickly and conveniently purchase component services. After several years of sincere service, our customer service is spread across large listed companies, military scientific research units, and small and medium-sized enterprises. The biggest advantage is emphasizing the service-oriented concept, and achieving fast delivery and favorable prices!

Direct brand: Xilinx ALTERA ADI TI NXP ST E2V, and more than a hundred component brands, especially good at components subject to US embargo against China,Welcome engineer friends to recommend us to procurement or consult us directly!We will continue to provide the best service in the industry!

Maximizing and Finding the Second Maximum Value Using FPGA

FPGA technology group official thanks to brands: Xilinx, intel (Altera), microsemi (Actel), LattIC e, Vantis, Quicklogic, Lucent, etc.

Leave a Comment

×