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,

where wk, 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.
Description Values
Set 1Set 2
N Pattern length 64 128
K Number of patterns 72 256
Sr Number of shifts 21 43
Sm Number of magnitude scalings 21 21
W1 Workload: log10 function calls 4.61 × 103 32.8 × 103
W2 Workload: 10x function calls 4.61 × 103 32.8 × 103
W3 Workload: Other floating-point ops (flops) 1.20 × 106 13.6 × 106


1. W. Coate and M. Arakawa. Preliminary design review: Feature-aided tracking for the PCA integrated radar-tracker application. Project Report PCA-IRT-5, MIT Lincoln Laboratory, Lexington, MA, October 2004.