Program 3: Parallel Fractal Generation Using ISPC Solution

Now that you're comfortable with SIMD execution, we'll return to parallel Mandelbrot fractal generation (like in program 1). Like Program 1, Program 3 computes a mandelbrot fractal image, but it achieves even greater speedups by utilizing both the CPU's four cores and the SIMD execution units within each core.




In Program 1, you parallelized image generation by creating one thread

for each processing core in the system. Then, you assigned parts of

the computation to each of these concurrently executing

threads. (Since threads were one-to-one with processing cores in

Program 1, you effectively assigned work explicitly to cores.) Instead

of specifying a specific mapping of computations to concurrently

executing threads, Program 3 uses ISPC language constructs to describe

*independent computations*. These computations may be executed in

parallel without violating program correctness (and indeed they

will!). In the case of the Mandelbrot image, computing the value of

each pixel is an independent computation. With this information, the

ISPC compiler and runtime system take on the responsibility of

generating a program that utilizes the CPU's collection of parallel

execution resources as efficiently as possible.




You will make a simple fix to Program 3 which is written in a combination of

C++ and ISPC (the error causes a performance problem, not a correctness one).

With the correct fix, you should observe performance that is over forty times

greater than that of the original sequential Mandelbrot implementation from

`mandelbrotSerial()`.







# Program 3, Part 1. A Few ISPC Basics (10 of 20 points) ###




When reading ISPC code, you must keep in mind that although the code appears

much like C/C++ code, the ISPC execution model differs from that of standard

C/C++. In contrast to C, multiple program instances of an ISPC program are

always executed in parallel on the CPU's SIMD execution units. The number of

program instances executed simultaneously is determined by the compiler (and

chosen specifically for the underlying machine). This number of concurrent

instances is available to the ISPC programmer via the built-in variable

`programCount`. ISPC code can reference its own program instance identifier via

the built-in `programIndex`. Thus, a call from C code to an ISPC function can

be thought of as spawning a group of concurrent ISPC program instances

(referred to in the ISPC documentation as a gang). The gang of instances

runs to completion, then control returns back to the calling C code.




__Stop. This is your friendly instructor. Please read the preceding paragraph again. Trust me.__




As an example, the following program uses a combination of regular C code and ISPC

code to add two 1024-element vectors. As we discussed in class, since each

instance in a gang is independent and performing the exact

same program logic, execution can be accelerated via

implementation using SIMD instructions.




A simple ISPC program is given below. The following C code will call the

following ISPC code:




------------------------------------------------------------------------

C program code: myprogram.cpp

------------------------------------------------------------------------

const int TOTAL_VALUES = 1024;

float a[TOTAL_VALUES];

float b[TOTAL_VALUES];

float c[TOTAL_VALUES]

 

// Initialize arrays a and b here.

 

sum(TOTAL_VALUES, a, b, c);

 

// Upon return from sumArrays, result of a + b is stored in c.




The corresponding ISPC code:




------------------------------------------------------------------------

ISPC code: myprogram.ispc

------------------------------------------------------------------------

export sum(uniform int N, uniform float* a, uniform float* b, uniform float* c)

{

// Assumption programCount divides N evenly.

for (int i=0; i<N; i+=programCount)

{

c[programIndex + i] = a[programIndex + i] + b[programIndex + i];

}

}




The ISPC program code above interleaves the processing of array elements among

program instances. Note the similarity to Program 1, where you statically

assigned parts of the image to threads.




However, rather than thinking about how to divide work among program instances

(that is, how work is mapped to execution units), it is often more convenient,

and more powerful, to instead focus only on the partitioning of a problem into

independent parts. ISPCs `foreach` construct provides a mechanism to express

problem decomposition. Below, the `foreach` loop in the ISPC function `sum2`

defines an iteration space where all iterations are independent and therefore

can be carried out in any order. ISPC handles the assignment of loop iterations

to concurrent program instances. The difference between `sum` and `sum2` below

is subtle, but very important. `sum` is imperative: it describes how to

map work to concurrent instances. The example below is declarative: it

specifies only the set of work to be performed.




-------------------------------------------------------------------------

ISPC code:

-------------------------------------------------------------------------

export sum2(uniform int N, uniform float* a, uniform float* b, uniform float* c)

{

foreach (i = 0 ... N)

{

c[i] = a[i] + b[i];

}

}




Before proceeding, you are encouraged to familiarize yourself with ISPC

language constructs by reading through the ISPC walkthrough available at

<http://ispc.github.com/example.html. The example program in the walkthrough

is almost exactly the same as Program 3's implementation of `mandelbrot_ispc()`

in `mandelbrot.ispc`. In the assignment code, we have changed the bounds of

the foreach loop to yield a more straightforward implementation.




**What you need to do:**




1. Compile and run the program mandelbrot ispc. __The ISPC compiler is currently configured to emit 8-wide AVX2 vector instructions.__ What is the maximum

speedup you expect given what you know about these CPUs?

Why might the number you observe be less than this ideal? (Hint:

Consider the characteristics of the computation you are performing?

Describe the parts of the image that present challenges for SIMD

execution? Comparing the performance of rendering the different views

of the Mandelbrot set may help confirm your hypothesis.)




We remind you that for the code described in this subsection, the ISPC

compiler maps gangs of program instances to SIMD instructions executed

on a single core. This parallelization scheme differs from that of

Program 1, where speedup was achieved by running threads on multiple

cores.







# Program 3, Part 2: ISPC Tasks (10 of 20 points) ###




ISPCs SPMD execution model and mechanisms like `foreach` facilitate the creation

of programs that utilize SIMD processing. The language also provides an additional

mechanism utilizing multiple cores in an ISPC computation. This mechanism is

launching _ISPC tasks_.




See the `launch[2]` command in the function `mandelbrot_ispc_withtasks`. This

command launches two tasks. Each task defines a computation that will be

executed by a gang of ISPC program instances. As given by the function

`mandelbrot_ispc_task`, each task computes a region of the final image. Similar

to how the `foreach` construct defines loop iterations that can be carried out

in any order (and in parallel by ISPC program instances, the tasks created by

this launch operation can be processed in any order (and in parallel on

different CPU cores).




**What you need to do:**




1. Run `mandelbrot_ispc` with the parameter `--tasks`. What speedup do you

observe on view 1? What is the speedup over the version of `mandelbrot_ispc` that

does not partition that computation into tasks?

2. There is a simple way to improve the performance of

`mandelbrot_ispc --tasks` by changing the number of tasks the code

creates. By only changing code in the function

`mandelbrot_ispc_withtasks()`, you should be able to achieve

performance that exceeds the sequential version of the code by over 40 times!

How did you determine how many tasks to create? Why does the

number you chose work best?

3. _Extra Credit: (2 points)_ What are differences between the thread

abstraction (used in Program 1) and the ISPC task abstraction? There

are some obvious differences in semantics between the (create/join

and (launch/sync) mechanisms, but the implications of these differences

are more subtle. Here's a thought experiment to guide your answer: what

happens when you launch 10,000 ISPC tasks? What happens when you launch

10,000 threads?




_The smart-thinking student's question_: Hey wait! Why are there two different

mechanisms (`foreach` and `launch`) for expressing independent, parallelizable

work to the ISPC system? Couldn't the system just partition the many iterations

of `foreach` across all cores and also emit the appropriate SIMD code for the

cores?




_Answer_: Great question! And there are a lot of possible answers. Come to

office hours.