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

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)

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)

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. );

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

12. generate

13. genvar i;

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

15. begin:loop_assign

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

17. end

18. endgenerate

20. // stage 1,comp

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

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

23. generate

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

25. begin:loop_comp

26. always@(posedge clk)

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

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

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

30. end

31. else begin

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

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

34. end

35. end

36. endgenerate

38. // stage 2,

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

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

41. generate

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

43. begin:loop_megs2

44. meg u_s2meg(

45. .clk(clk),

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

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

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

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

50. .max1(s2_max[i]),

51. .max2(s2_min[i])

52. );

53. end

54. endgenerate

55. // stage 3,

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

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

58. generate

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

60. begin:loop_megs3

61. meg u_s3meg(

62. .clk(clk),

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

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

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

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

67. .max1(s3_max[i]),

68. .max2(s3_min[i])

69. );

70. end

71. endgenerate

73. // stage 4,

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

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

76. generate

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

78. begin:loop_megs4

79. meg u_s4meg(

80. .clk(clk),

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

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

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

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

85. .max1(s4_max[i]),

86. .max2(s4_min[i])

87. );

88. end

89. endgenerate

91. // stage 5,

92. meg u_s5meg(

93. .clk(clk),

94. .g1_max(s4_max[0]),

95. .g1_min(s4_min[0]),

96. .g2_max(s4_max[1]),

97. .g2_min(s4_min[1]),

98. .max1(max1),

99. .max2(max2)

100. );

101. endmodule

103. module meg#(

104. parameter DW = 8

105. )

106. (

107. input clk,

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

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

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

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

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

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

114. );

115. always@(posedge clk)

116. begin

117. if(g1_max>g2_max) begin

118. max1 <= g1_max;

119. if(g2_max>g1_min)

120. max2 <= g2_max;

121. else

122. max2 <= g1_min;

123. end

124. else begin

125. max1 <= g2_max;

126. if(g1_max>g2_min)

127. max2 <= g1_max;

128. else

129. max2 <= g2_min;

130. end

131. end

132. 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.

Welcome communication engineers and FPGA engineers to follow the public account

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!!

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):

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

(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!

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