Changes

← Older edit

Top Solo

13,982 bytes added, 03:31, 8 March 2013

→‎Issues Encountered

I am going to try and profile and optimize the following function from the CImg Library.

This function creates triangles on the screen and allows the user to make them clump up by clicking the mouse buttons.

This function, like others in the CImg_demo.cpp library uses the <CImg.h> library. This is a massive library that contains functions and routines responsible for displaying and preparing the environment for Image and Video processing. My function 'Filled Triangles' uses this library and its resources extensively.

Compilation with profiling on Mac OSX:

=== ~~Summary of Findings ===~~ The ~~execution of the program takes roughly 3.10~~ Program - 20 seconds (depending on how long you are measuring the calculations of triangle animations). it should be noted that this application initially was an application that relied upon user input for execution and for termination. I have modified this initial behavior by ensuring the while loop (which generates the triangles) executes only for a maximum of 1000 iterations. The time measured in this assignment is for every 1000 iterations of this loop. ~~=== Profiling Results ===~~The results if the initial profile shows that the execution time is most greatly consumed when drawing the triangles out to the screen one at a time. It seems like this can be optimized by offloading this drawing to n threads based on n triangles to be drawn. But this is subject to change because of any additional complexity that may be introduced that may include interoperability with both the GPU and CPU. There is another for loop which sets the dimensions for each triangle one by one in linear time O(n ). This process can also be out-sourced to the GPU in n threads for n triangles. I would need to determine if this process also involves interoperability between the CPU and GPU. ~~The complexity of the entire program is O(n^3). There is a for loop for setup, a while loop for accepting user input and another for loop for drawing the triangles.~~ ~~Also the times recorded can be increase if the maximum loop iterations increase ie: 10000,100000,1000000. This will identify the same relationship but with higher task time.~~ =Filled Triangles == ~~Amdahls Law Calculations ===~~ Since there are 100 Triangles generated then we can theoretically create 100 threads for each triangle. The draw_line, draw_triangle, and draw_image functions take up 16 percent(0.38 + 0.08 + 0.06 / 3.10) of the execution time of the application in seconds. Plugging that into the equation using 100 cores we get: ~~S100 = 1/ 1 - 0.16 + 0.16 / 100~~ = ~~1.18 seconds or 1.2 seconds speedup rounded up PER 1000 iterations of the while loop to draw these triangles.~~ ~~Will I work on this Project?~~If I can optimize this function or any other function within the CImg library I will continue with this project. If it is not possible to optimize this project within the given time of the course then it will be difficult to continue on with this project and I will have to work with someone else's project. But my initial plan is to continue with this project unless I am told otherwise.

<source lang=~~== Makefile changes ===~~ I have made changes to the original Makefile that was provided with this library. I have customized it to compile for profiling by default. A new build can be generate by cleaning the old build (eg: make clean). The source can be compiled by running make <platform> eg: macosx, linux. You will need to download a third party program to allow you to run the 'make' command on Windows but the execution is the same. it can also be run on windows using visual Studio or on the command line("~~cl.exe must be in the environnent PATH variable~~cpp"). ~~=== Build Instructions ===~~ ~~make <platform> eg: macosx, linux etc.~~ ~~<pre~~>

// Item : Filled Triangles

}

</~~pre~~source>

=== Initial Profile (on OpenSUSE Linux at Seneca) ===

<pre>

=== Modified Makefile for Profiling ===

<~~pre~~source lang="bash">

CIMG_FILES = CImg_demo

gmic

~~#---------------------------------~~

~~# Set correct variables and paths~~

~~#---------------------------------~~

CIMG_VERSION = 1.5.4

endif

~~#--------------------------------------------------~~

~~# Set compilation flags allowing to customize CImg~~

~~#--------------------------------------------------~~

# Flags to enable strict code standards

endif

~~#-------------------------~~

~~# Define Makefile entries~~

~~#-------------------------~~

.cpp:

$(CIMG_GDI32_LDFLAGS)" \

all

</source>

=== Makefile changes ===

I have made changes to the original Makefile that was provided with this library. I have customized it to compile for profiling by default. A new build can be generate by cleaning the old build (eg: make clean). The source can be compiled by running make <platform> eg: macosx, linux. You will need to download a third party program to allow you to run the 'make' command on Windows but the execution is the same. it can also be run on windows using visual Studio or on the command line("cl.exe must be in the environnent PATH variable").

=== Build Instructions ===

This Makefile and application is cross-platform.

make <platform> eg: macosx, linux etc.

I have successfully built this application on the following platforms: Windows 7, OpenSuse linux and Mac OSX Lion.

=== Summary of Findings ===

The execution of the program takes roughly 3.10 - 20 seconds (depending on how long you are measuring the calculations of triangle animations). it should be noted that this application initially was an application that relied upon user input for execution and for termination. I have modified this initial behavior by ensuring the while loop (which generates the triangles) executes only for a maximum of 1000 iterations. The time measured in this assignment is for every 1000 iterations of this loop.

=== Profiling Results ===

The results if the initial profile shows that the execution time is most greatly consumed when drawing the triangles out to the screen one at a time. It seems like this can be optimized by offloading this drawing to n threads based on n triangles to be drawn. But this is subject to change because of any additional complexity that may be introduced that may include interoperability with both the GPU and CPU.

There is another for loop which sets the dimensions for each triangle one by one in linear time O(n ). This process can also be out-sourced to the GPU in n threads for n triangles. I would need to determine if this process also involves interoperability between the CPU and GPU.

The complexity of the entire program is O(n^3). There is a for loop for setup, a while loop for accepting user input and another for loop for drawing the triangles.

Also the times recorded can be increase if the maximum loop iterations increase ie: 10000,100000,1000000. This will identify the same relationship but with higher task time.

=== Potential Parallelization Candidates ===

Upon analyzing this function I discovered two possible areas where I could optimize the code using threads sent to the GPU. The first is a for loop which sets the attributes for 100 triangles in serial. This task can be done in parallel using 100 threads on the GPU.

for (int k = 0; k<100; ++k) {

posx[k] = (float)(cimg::rand()*img0.width());

posy[k] = (float)(cimg::rand()*img0.height());

rayon[k] = (float)(10 + cimg::rand()*50);

angle[k] = (float)(cimg::rand()*360);

veloc[k] = (float)(cimg::rand()*20 - 10);

color[k][0] = (unsigned char)(cimg::rand()*255);

color[k][1] = (unsigned char)(cimg::rand()*255);

color[k][2] = (unsigned char)(cimg::rand()*255);

~~all~~ opacity[k] = (float)(0.3 + 1.5*cimg::rand());

}

</pre>

The second instance where this is possible is a bit tricky. It involves another serial for loop. The purpose of this loop is to draw each of the triangles on the screen and manipulate them later on. I am not 100 percent sure this can be done in parallel in practice but in theory it should be possible because the application is drawing out each triangle one by one.

<pre>

// Draw each triangle on the background image.

for (int k = 0; k<num; ++k) {

const int

x0 = (int)(posx[k] + rayon[k]*std::cos(angle[k]*cimg::PI/180)),

y0 = (int)(posy[k] + rayon[k]*std::sin(angle[k]*cimg::PI/180)),

x1 = (int)(posx[k] + rayon[k]*std::cos((angle[k] + 120)*cimg::PI/180)),

y1 = (int)(posy[k] + rayon[k]*std::sin((angle[k] + 120)*cimg::PI/180)),

x2 = (int)(posx[k] + rayon[k]*std::cos((angle[k] + 240)*cimg::PI/180)),

y2 = (int)(posy[k] + rayon[k]*std::sin((angle[k] + 240)*cimg::PI/180));

if (k%10) img.draw_triangle(x0,y0,x1,y1,x2,y2,color[k],opacity[k]);

else img.draw_triangle(x0,y0,x1,y1,x2,y2,img0,0,0,img0.width()-1,0,0,img.height()-1,opacity[k]);

img.draw_triangle(x0,y0,x1,y1,x2,y2,white,opacity[k],~0U);

// Make the triangles rotate, and check for mouse click event.

// (to make triangles collapse or join).

angle[k]+=veloc[k];

if (disp.mouse_x()>0 && disp.mouse_y()>0) {

float u = disp.mouse_x() - posx[k], v = disp.mouse_y() - posy[k];

if (disp.button()) { u = -u; v = -v; }

posx[k]-=0.03f*u, posy[k]-=0.03f*v;

if (posx[k]<0 || posx[k]>=img.width()) posx[k] = (float)(cimg::rand()*img.width());

if (posy[k]<0 || posy[k]>=img.height()) posy[k] = (float)(cimg::rand()*img.height());

}

</source>

=== Amdahls Law Calculations ===

Since there are 100 Triangles generated then we can theoretically create 100 threads for each triangle. The draw_line, draw_triangle, and draw_image functions take up 16 percent(0.38 + 0.08 + 0.06 / 3.10) of the execution time of the application in seconds. Plugging that into the equation using 100 cores we get:

S100 = 1/ 1 - 0.16 + 0.16 / 100

= 1.18 or 1.2 speedup is theoretically achievable rounded up PER 1000 iterations of the while loop to draw these triangles.

Will I work on this Project?

If I can optimize this function or any other function within the CImg library I will continue with this project. If it is not possible to optimize this project within the given time of the course then it will be difficult to continue on with this project and I will have to work with someone else's project. But my initial plan is to continue with this project unless I am told otherwise.

=== Issues Encountered ===

'''Gprof on MacOSx with Intel processor'''

The profiling tool gprog does not work on the macbooks with an Intel processor installed (I have Intel Core i5). This was verified by numerous internet resources and annoying personal experience.

'''Makefile builds EVERYTHING'''

The Makefile shipped with this open source library is programmed to build all of the modules located in CImg_demo.cpp. I had to modify the Makefile to only build the specified function within the library of Image processing functions

== Assignment 2 ==

This assignment involved GPU programming the functions I had speculated I could process concurrently. After further analysis I determined that the second for loop cannot be processed in parallel without converting some underlying API functions to device functions. These functions are used in multiple areas in the framework so I did not pursue changing the framework too much. The first for loop however contained independent data that could be executed in parallel so I went ahead and created kernels for that code. I also noticed that the function made a call to cimg::rand(). This is obviously a function that returns random numbers. Luckily CUDA also has multiple libraries that perform these functions. Off the top of my head: Thrust and CURAND do. I went with CURAND because it has the word "rand" in it and that's what I need. hehe

=== Kernels ===

/*

* Setup and initialize curand with a seed

*/

__global__ void initCurand(curandState* state){

int idx = blockIdx.x * blockDim.x + threadIdx.x;

curand_init(100, idx, 0, &state[idx]);

__syncthreads();

}

/*

* CUDA kernel that will execute 100 threads in parallel

* and will populate these parallel arrays with 100 random numbers

* array size = 100.

*/

__global__ void initializeArrays(float* posx, float* posy,float* rayon, float* veloc,

float* opacity ,float* angle, unsigned char* color, int height,

int width, curandState* state, size_t pitch){

int idx = blockIdx.x * blockDim.x + threadIdx.x;

curandState localState = state[idx];

posx[idx] = (float)(curand_normal(&localState)*width);

posy[idx] = (float)(curand_normal(&localState)*height);

rayon[idx] = (float)(10 + curand_normal(&localState)*50);

angle[idx] = (float)(curand_normal(&localState)*360);

veloc[idx] = (float)(curand_uniform(&localState)*20 - 10);

color[idx*pitch] = (unsigned char)(curand_normal(&localState)*255);

color[(idx*pitch)+1] = (unsigned char)(curand_normal(&localState)*255);

color[(idx*pitch)+2] = (unsigned char)(curand_normal(&localState)*255);

opacity[idx] = (float)(0.3f + 1.5f *curand_normal(&localState));

__syncthreads();

}

// check for any errors returned by CUDA API functions.

void errCheck(cudaError_t err, const char* msg){

if (err != cudaSuccess)

std::cout<< msg << ": " << cudaGetErrorString(err) << std::endl;

}

</source>

=== Body Code ===

// check for any errors returned by CUDA API functions.

void errCheck(cudaError_t err, const char* msg){

if (err != cudaSuccess)

std::cout<< msg << ": " << cudaGetErrorString(err) << std::endl;

}

/*---------------------------

Main procedure

--------------------------*/

int main() {

// Create a colored 640x480 background image which consists of different color shades.

CImg<float> background(640,480,1,3);

cimg_forXY(background,x,y) background.fillC(x,y,0,

x*std::cos(6.0*y/background.height()) + y*std::sin(9.0*x/background.width()),

x*std::sin(8.0*y/background.height()) - y*std::cos(11.0*x/background.width()),

x*std::cos(13.0*y/background.height()) - y*std::sin(8.0*x/background.width()));

background.normalize(0,180);

// Init images and create display window.

CImg<unsigned char> img0(background), img;

unsigned char white[] = { 255, 255, 255 }, color[100][3];

CImgDisplay disp(img0,"[#6] - Filled Triangles (Click to shrink)");

// error handling

cudaError_t err;

// Define random properties (pos, size, colors, ..) for all triangles that will be displayed.

float posx[100];

float posy[100];

float rayon[100];

float angle[100];

float veloc[100];

float opacity[100];

// Define the same properties but for the device

float* d_posx;

float* d_posy;

float* d_rayon;

float* d_angle;

float* d_veloc;

float* d_opacity;

unsigned char* d_color;

// CURAND state

curandState* devState;

// allocate memory on the device for the device arrays

err = cudaMalloc((void**)&d_posx, 100 * sizeof(float));

errCheck(err, "cudaMalloc((void**)&d_posx, 100 * sizeof(float))");

err = cudaMalloc((void**)&d_posy, 100 * sizeof(float));

errCheck(err,"cudaMalloc((void**)&d_posy, 100 * sizeof(float))");

err = cudaMalloc((void**)&d_rayon, 100 * sizeof(float));

errCheck(err,"cudaMalloc((void**)&d_rayon, 100 * sizeof(float))");

err = cudaMalloc((void**)&d_angle, 100 * sizeof(float));

errCheck(err,"cudaMalloc((void**)&d_angle, 100 * sizeof(float))");

err = cudaMalloc((void**)&d_veloc, 100 * sizeof(float));

errCheck(err,"cudaMalloc((void**)&d_veloc, 100 * sizeof(float))");

err = cudaMalloc((void**)&d_opacity, 100 * sizeof(float));

errCheck(err,"cudaMalloc((void**)&d_opacity, 100 * sizeof(float))");

err = cudaMalloc((void**)&devState, 100*sizeof(curandState));

errCheck(err,"cudaMalloc((void**)&devState, 100*sizeof(curandState))");

size_t pitch;

//allocated the device memory for source array

err = cudaMallocPitch(&d_color, &pitch, 3 * sizeof(unsigned char),100);

errCheck(err,"cudaMallocPitch(&d_color, &pitch, 3 * sizeof(unsigned char),100)");

// launch grid of threads

dim3 dimBlock(100);

dim3 dimGrid(1);

/* Kernel for initializing CURAND */

initCurand<<<1,100>>>(devState);

// synchronize the device and the host

cudaDeviceSynchronize();

/*Kernel for initializing Arrays */

initializeArrays<<<1, 100>>>(d_posx, d_posy, d_rayon, d_veloc, d_opacity, d_angle,

d_color, img0.height(), img0.width(), devState, pitch);

// synchronize the device and the host

cudaDeviceSynchronize();

// get the populated arrays back to the host for use

err = cudaMemcpy(posx,d_posx, 100 * sizeof(float), cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy(posx,d_posx, 100 * sizeof(float), cudaMemcpyDeviceToHost)");

err = cudaMemcpy(posy,d_posy, 100 * sizeof(float), cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy(posy,d_posy, 100 * sizeof(float), cudaMemcpyDeviceToHost)");

err = cudaMemcpy(rayon,d_rayon, 100 * sizeof(float), cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy(rayon,d_rayon, 100 * sizeof(float), cudaMemcpyDeviceToHost)");

err = cudaMemcpy(veloc,d_veloc, 100 * sizeof(float), cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy(veloc,d_veloc, 100 * sizeof(float), cudaMemcpyDeviceToHost)");

err = cudaMemcpy(opacity,d_opacity, 100 * sizeof(float), cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy(opacity,d_opacity, 100 * sizeof(float), cudaMemcpyDeviceToHost)");

err = cudaMemcpy(angle,d_angle, 100 * sizeof(float), cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy(angle,d_angle, 100 * sizeof(float), cudaMemcpyDeviceToHost)");

// pitch of color array is 3+1 padded

err = cudaMemcpy2D(color,4,d_color,pitch,3 *sizeof(unsigned char),3, cudaMemcpyDeviceToHost);

errCheck(err,"cudaMemcpy2D(color,pitch,d_color,100*3,3 *sizeof(unsigned char),100* sizeof(unsigned char), cudaMemcpyDeviceToHost)");

// measuring time it takes for triangle animations in 1000 iterations

int i = 0, num = 1;

// Start animation loop.

while (!disp.is_closed() && !disp.is_keyQ() && !disp.is_keyESC() && i < 1000) {

img = img0;

i++;