Program 4: Iterative `sqrt` Solution

Program 4 is an ISPC program that computes the square root of 20 million

random numbers between 0 and 3. It uses a fast, iterative implementation of

square root that uses Newton's method to solve the equation ${\frac{1}{x^2}} - S = 0$.

The value 1.0 is used as the initial guess in this implementation. The graph below shows the

number of iterations required for `sqrt` to converge to an accurate solution

for values in the (0-3) range. (The implementation does not converge for

inputs outside this range). Notice that the speed of convergence depends on the

accuracy of the initial guess.




Note: This problem is a review to double-check your understanding, as it covers similar concepts as programs 2 and 3.





**What you need to do:**




1. Build and run `sqrt`. Report the ISPC implementation speedup for

single CPU core (no tasks) and when using all cores (with tasks). What

is the speedup due to SIMD parallelization? What is the speedup due to

multi-core parallelization?

2. Modify the contents of the array values to improve the relative speedup

of the ISPC implementations. Describe a very-good-case input that __maximizes speedup over the sequential version of the code__ and report the resulting speedup achieved (for both the with- and without-tasks ISPC implementations). Does your modification improve SIMD speedup?

Does it improve multi-core speedup (i.e., the benefit of moving from ISPC without-tasks to ISPC with tasks)? Please explain why.

3. Construct a very-bad-case input for `sqrt` that __minimizes speedup for ISPC with no tasks__. Describe this input, describe why you chose it, and report the resulting relative performance of the ISPC implementations. What is the reason for the loss in efficiency?

__(keep in mind we are using the `--target=avx2` option for ISPC, which generates 8-wide SIMD instructions)__.

4. _Extra Credit: (up to 2 points)_ Write your own version of the `sqrt`

function manually using AVX2 intrinsics. To get credit your

implementation should be nearly as fast (or faster) than the binary

produced using ISPC. You may find the [Intel Intrinsics Guide](http://software.intel.com/en-us/articles/intel-intrinsics-guide)

very helpful.