## 4 Experiment Evaluation
### Results and Discussion  
HBM and FHBM throughputs for the Snort, ClamAV type 1, and ClamAV type 3 pattern sets are respectively shown in Figures 4-6. Various head sizes were used to evaluate both algorithms. As shown in Figure 4a, HBM throughput values for head sizes between 3000 and 6000 states were similar. At a head size of 7000, the throughput value sharply increased from 339 MB/s to 555 MB/s. Since HBM partitions an AC-DFA into head and body parts according to a pre-defined head size to determine the maximum depth of states that can be put in the head part, a comparable situation was observed when the head size was increased from 11,000 to 12,000 states. However, as we discussed in an earlier section, the number of states at any specific depth can be very large, which stops HBM from fully utilizing its head size, resulting in poor throughputs. More specifically, the purpose of the head part of a HBFA is to provide fast transition between states that will be accessed more frequently. Since the head part utilizes fully-populated state transition tables (STTs), which can be accessed quickly but require more storage, it may lead to poor memory and throughput performance if the number of states in the head part is not controlled properly. Table 4 lists the numbers of states at different depth ranges for the Snort, ClamAV type 1, and ClamAV type 3 pattern sets. Suppose that the maximum head size is 6000 states. For the Snort pattern set, since the combined number of states at depths 1, 2, and 3 was 6204, only the states at depths 1 and 2 could be moved to the head part. This explains why the head size did not exert any impact on HBM throughput at head sizes ranging from 3000 to 6000 states. In contrast, as long as the head size did not exceed 17,000 states, FHBM throughput increased as head size increased. The reason is that FHBM is capable of fully utilizing head size by intelligently partitioning the head and body states. Both HBM and FHBM throughputs were kept between 762 and 787 MB/s when head sizes were 17,000 states or higher. Since each state had to store 256 entries for child states, and with each entry consuming two bytes, each state consumed 2 \(\times\) 256 bytes. The storage requirement for a head part with 17,000 states is 8.5 MB, which exceeds the L3 cache size, therefore larger head sizes did not enhance throughput. Furthermore, since most state access occurred at lower depths (\(\leq\)4) (Table 5), partitioning additional depths to the head part also did not enhance throughput. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Depths** & **Snort** & **ClamAV Type 1** & **ClamAV Type 3** \\ \hline \(\leq\)2 & 2039 & 3499 & 675 \\ \(\leq\)3 & 6204 & 7813 & 1765 \\ \(\leq\)4 & 11,100 & 12,349 & 3110 \\ \(\leq\)5 & 16,340 & 17,093 & 4652 \\ \(\leq\)6 & 21,564 & 21,919 & 6348 \\ \(\leq\)7 & 26,785 & 26,779 & 8145 \\ \(\leq\)8 & 31,955 & 31,642 & 10,050 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Number of states at different depth ranges. Figure 4: Throughput value plotted against head size for the Snort pattern set. Figure 5: Throughput value plotted against head size for the ClamAV type 1 pattern set. Figure 6: Throughput value plotted against head size for the ClamAV type 3 pattern set. As shown in Figure 5, the HBM and FHBM algorithm results for ClamAV type 1 exhibited a throughput-head size relationship similar to that for Snort. This is explained by the similar numbers of states at different depths for the two pattern set types (Table 4). Note that both algorithms achieved higher throughputs for the ClamAV type 1 pattern set. Given a match ratio of 1% and head size of 20,000 states, FHBM throughput was 903 MB/s for ClamAV type 1 and 775 MB/s for Snort. As shown in Table 3, the percentage of patterns exceeding 16 bytes in the ClamAV type 1 pattern set (i.e., 93.7%) was much higher than that in the Snort pattern set (i.e., 43.9%).