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
Parameter Name	Description	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₁	Workload: log₁₀ function calls	4.61 × 10³	32.8 × 10³
W₂	Workload: 10^x function calls	4.61 × 10³	32.8 × 10³
W₃	Workload: Other floating-point ops (flops)	1.20 × 10⁶	13.6 × 10⁶

Reference

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.