# Pattern Matching

The pattern matching kernel is extracted from the feature-aided tracking portion of the integrated radar-tracker application [1]. Fundamentally, this step entails overlaying two length-N vectors a and t and computing a metric that quantifies the degree to which these two vectors match. In general, the vector t is chosen from a set of reference vectors referred to as the*template library*. The metric used for matching is the weighted MSE (mean square error) &epsilon,

(1)

where w

_{k}, k = 1, 2, ..., N is the vector of weights. The optimal weights for the feature-aided tracker have been computed empirically. In the kernel benchmark, we provide a generic weighting vector. The calculation done in Equation (1) is performed on data that has been converted to decibels (the "dB domain"). This is done because the raw power output from a signal processing system can vary by many orders of magnitude. However, conversion of patterns between the power domain and the dB domain is performed during the course of the benchmark: this requires the use of a number of logarithm and exponentiation functions. The operation count for these functions is implementation-dependent, and so the workload we give has three components: a count of the number of calls to the exponent function, a count of the number of calls to the logarithm function, and a count of the operations in the rest of the benchmark. Before the two profiles can be overlaid, they may need to be shifted in range to the left or right, and the magnitude of the profiles may need to be scaled to match. The optimal shift and gain values can be found through brute force by computing the MSE for each combination of shift and gain values, then taking the minimum MSE. However, by noting that the MSE is a parabolic function of the shift and gain, we can find the optimum shift and gain values at the global minimum by first finding the optimal shift, then finding the optimal gain value. A summary of this procedure is shown in Figure 1:

for each of K patterns for each of Sr shift values calculate MSE value with shifted pattern Choose shift value with smallest MSE for each of Sm magnitude values calculate MSE value with scaled pattern Choose gain value with the smallest MSE

Figure 1. Outline of the pattern match kernel.

The parameters of interest for the pattern matching benchmark are the length of the pattern vectors, the size of the template pattern library, and the number of shift and scale operations performed. These parameters are given for two data set sizes in Table 1.

Table 1: Pattern matching parameters.

Parameter Name |
Description | Values | |

Set 1 | Set 2 | ||

N | Pattern length | 64 | 128 |

K | Number of patterns | 72 | 256 |

S_{r} |
Number of shifts | 21 | 43 |

S_{m} |
Number of magnitude scalings | 21 | 21 |

W_{1} |
Workload: log_{10} function calls |
4.61 × 10^{3} |
32.8 × 10^{3} |

W_{2} |
Workload: 10^{x} function calls |
4.61 × 10^{3} |
32.8 × 10^{3} |

W_{3} |
Workload: Other floating-point ops (flops) | 1.20 × 10^{6} |
13.6 × 10^{6} |