Programming and Data Types

Program 3a -- Vector Comparison, with Loop

This program scans two sorted, input vectors and finds the elements that are common to both. It returns the indices of these common elements.

There are two versions of this program. This version, "Program 3a", processes the vectors using a `while` loop. The version shown afterward, as "Program 3b", replaces the loop with vectorized code. When run on MATLAB without acceleration, there is a big difference in performance between the two. When run with acceleration, there is no significant difference at all.

 Operating System MATLAB 6.1 MATLAB 6.5 Performance Gain Windows 10.6 sec. 0.1 sec. x 106.0 Linux 24.0 sec. 0.1 sec. x 240.0 Solaris 1 min., 4.7 sec. 1.5 sec. x 43.1

• ```function [aIndex, bIndex] = vfind_scalar(avec, bvec)

avecLen = length(avec);
bvecLen = length(bvec);

% Size aIndex and bIndex to be large enough
outlen = min(avecLen, bvecLen);
aIndex = zeros(outlen,1);
bIndex = zeros(outlen,1);

n  = 0;
ai = 1;
bi = 1;

while (ai <= avecLen || bi <= bvecLen)
% Get vector elements at indices ai and bi
A = avec(ai);
B = bvec(bi);

% If equal, record indices where elements match
if A == B
n = n + 1;
aIndex(n) = ai;
bIndex(n) = bi;
end

% Advance index of avec, when appropriate
if A <= B
if ai < avecLen
ai = ai + 1;
else
break;
end
end

% Advance index of bvec, when appropriate
if A >= B
if bi < bvecLen
bi = bi + 1;
else
break;
end
end
end

% Snip aIndex and bIndex to correct size
aIndex = aIndex(1:n);
bIndex = bIndex(1:n);
```

In preparation for running the program, you'll need to create two sorted vectors having some number of common elements. The following statements create vectors `a` and `b`, append the elements from a third vector, `c`, to both, and then sort. This gives vectors `a` and `b` at least 20,000 common elements.

• ```a = rand(200000,1);
b = rand(260000,1);
c = rand(20000,1);
a = sort([a;c]);
b = sort([b;c]);
```

Now pass `a` and `b` into the function shown above. Use the `tic` and `toc` functions to track how much time it takes to execute.

• ```tic;  [ia, ib] = vfind_scalar(a, b);  toc
```

What Makes It Faster

MATLAB accelerates every line in this program. The code in the `while` loop is what matters most since this is what takes up nearly all of the program execution time. Consider the following factors.

Supported Data Types and Array Shapes.   All of the code in the program operates on vectors of type `double`. This is one of the data types and array shapes that supports acceleration.

Conditional Expression Evaluates to Scalar.   The expressions in the `while` and `if` statements all evaluate to scalar values. For example,

• ```while (ai <= avecLen || bi <= bvecLen)
```

No Disqualifying Statements in Loop.   Every line of code in the `while` loop qualifies for acceleration. This means that every iteration of the loop can execute at a higher speed without being interrupted to separately process any disqualifying lines.

Function Calls and Overloading.   The only functions called are MATLAB built-ins. No M-file or MEX-file functions are called and no operations are overloaded for the data types being used.

 Program 2 -- Relaxation Algorithm Program 3b -- Vector Comparison, Vectorized