We have seen that planes contain multiple values arranged in a rectangular grid. We have learned how to create unique values at each PE in the grid and how to select sets of those values using activity. We know that the subsets that we select may contain none, some, or all of the PEs in a plane. But, we have not yet seen how to tell if the selected subset is empty, non-empty, or full.
Consider a simple convergence algorithm such as Newton's method for computing square roots of positive integers. The code in C looks like
int IntSqrt(int value)
{
int sqrt, last_sqrt;
sqrt = value; last_sqrt = 0;
while (sqrt != last_sqrt)
{
last_sqrt = sqrt;
sqrt= (last_sqrt + value / sqrt) / 2;
}
return sqrt;
}
This algorithm iterates until no further changes are found in the solution (sqrt) and then returns that value.
Let us play computer and use 10 for the initial value of value.
Iteration sqrt last_sqrt
1 10 0
2 5 10
3 3 5
4 3 3
Using the value of 10, the while statement was executed 4 times.
The variable value can take on values as large as 2^31-1. It can be shown that 18 iterations are required for values that large.
The above program works for scalar integers. How do we write the equivalent program for planes? We know how to write the statements to do all the arithmetic operations but we do not know how to terminate the loop. We could use a for loop and always iterate a fixed number of times. But, because a plane contains more than one value, we would have to assume that we always needed to iterate 18 times.
IntPlane IntSqrt(IntPlane value)
{
PlaneSize ps(value);
IntPlane sqrt(ps), last_sqrt(ps);
sqrt = value; last_sqrt = 0;
for (int i = 0; i < 18; i++)
{
last_sqrt = sqrt;
sqrt= (last_sqrt + value / sqrt) / 2;
}
return sqrt;
}
If a plane contained values that were only less than 200, we would be wasting a lot of time.
We could Select the values greater than some threshold and iterate 18 times for them and fewer times for the rest.
IntPlane IntSqrt(IntPlane value)
{
PlaneSize ps(value);
IntPlane sqrt(ps), last_sqrt(ps);
sqrt = value; last_sqrt = 0;
{Select active(value > 200);
for (int i = 0; i < 18; i++)
{
last_sqrt = sqrt;
sqrt= (last_sqrt + value / sqrt) / 2;
}
}
{Select active(value <= 200);
for (int i = 0; i < 5; i++)
{
last_sqrt = sqrt;
sqrt= (last_sqrt + value / sqrt) / 2;
}
}
return sqrt;
}
This is a expensive solution because we are now iterating 23 times!
We need to know if some PEs are in a set. We can do this with the Any method. This method simply returns a scalar 1 if there are any 1s in a BitPlane and a scalar 0 otherwise. We can now write an intelligent and efficient version of the square root function for planes by asking the question are there any values of sqrt that have not converged?
IntPlane IntSqrt(IntPlane value)
{
PlaneSize ps(value);
IntPlane sqrt(ps), last_sqrt(ps);
sqrt= value; last_sqrt = 0;
while ((sqrt != last_sqrt).Any())
{
last_sqrt = sqrt;
sqrt= (last_sqrt + value / sqrt) / 2;
}
return sqrt;
}
This code iterates only until all the values of sqrt in all the PEs converge(1).
When every value of sqrt is equal to every value of last_sqrt, the BitPlane created by the expression (sqrt != last_sqrt) will contain only zeros and the Any method will return a zero too, causing the while loop to terminate.
The Any method looks at every PE. For example, suppose we are concerned with the question are there any values of x equal to 5 for which the values of y are 0? We can write this as
if (((y == 0) & (x == 5)).Any())
{
...
}
Using Any, we can now determine if a subset is empty or not.
How can we determine if a subset is full? The following phase will return a scalar one if the subset is full(2).
~(~set).Any();
We are simply asking if there are any that are not in the subset.
If there are none, the subset is full.
We can now determine if a subset contains none, any, or all PEs in a set. Can we determine if there are 0, 1, or more than 1 in a subset? When would we like to know?
Let us assume that we have a BitPlane x that defines some subset of PEs. We can determine how many PEs are in this set by using the Count method. This method returns a count of the number of 1s in a BitPlane. The statement
printf("There are %u PEs in x.\n", x.Count());
could be used to print this number.
Perhaps we wish to know the ratio of positive to negative values in the subset of plane y defined by x.
The following code would do this.
int ratio = (x & (y >= 0)).Count() / (x & (y < 0)).Count();
The percent of positive values would be calculated by
int percent = (100 * (x & (y >= 0)).Count()) / x.Count();
{Select active(sqrt != last_sqrt); ... }
in the while loop, but this is unnecessary as this algorithm will not change values that have converged already.