I'm having problems with an assesment I have to hand in. Can anyone help me. Please find the details below or visit http://www.csd.abdn.ac.uk/~jrl/teaching/CS3008/assessment/asst1.htm

My task is to speed up the computation without losing accuracy.

The time taken by the program is taken to be that returned for user time ( the time the CPU spends on your computation), given by
time prog when run on sol for a size of 1000*1000 pixels.

The final program should produce the same results as the original. Check this by writing out, to a file, the array produced by the original, and comparing any new results with this gold standard.

(Clarification:[21 Oct 2003] you should check that all 1000*1000 cells are the same.)

It is also possible to generate a much smaller output file by creating a signature -
Consider an array of 3 unsigned integers (buckets).
Initialise these to zero, then add
cells 0, 3, 6, ... into the zeroth bucket
cells 1, 4, 7, ... into the middle bucket
cells 2, 5, 8, ... into the last bucket.
(Every cell in the 2D array is to be added into some bucket).
The sequence of values in the array of buckets is the signature, and will be the same if created from identical 2D arrays of cells.
However, we may want an array of 1, 3, 17, or n buckets - the number of buckets should be a constant.

You are advised to try speeding up the computation by improving pixval, in which the computer spends most of its effort ( see man prof).

You should think about

Compiler optimisation
The CC compiler accepts flags for degrees of optimisation
-O1 .. -O5
-fast

Reorganising the program
Some program forms run faster than others.

Loop unrolling
Current computers work fastest on sequences without branches.
Re-arrange the program to cut down branches.

Algebraic reorganisation
you are welcome to work at the level of the underlying algebra. Remember that some variables are complex.

Inlining functions
A C++ compiler accepts the keyword inline as a request to the compiler to avoid a function call by planting code where the function is called.
The syntax is

inline double fn( int ss) { return ss+8.4;};

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

#include <iostream>
#include <complex>

using namespace std;

typedef complex<double> Complex;

const int size = 1000;

int pix[size][size];

int pixval( double xx, double yy)
{
Complex z = 0;
Complex c(xx,yy);
int j;
for (j = 0 ; j < 1000 && abs(z) < 2 ; ++j)
z = z*z+c;
return j / 20;
}

void fillpix(double x0, double y0, double xinc, double yinc)
{
int x, y;
for( x = 0 ; x < size ; ++x)
for( y = 0 ; y < size ; ++y)
pix[x][y] = pixval( x0+x*xinc, y0+y*yinc);
}

int main()
{
fillpix(0.2, 0.2, 0.001, 0.001);
for (int y = 0 ; y < size; y+=(size/60)){
for (int x = 0 ; x < size; x+=(size/20))
cout << char( ' '+pix[y][x]);
cout << endl;
}
}

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

For heaven's sake man did you read the big bold letters "DO NOT ask a homework question unless you have already attempted to solve the problem yourself"?

We love to answer programming questions, homework or otherwise, but you have to try them first. When you say "I'm having trouble", but you don't say exactly where you are having trouble, it makes me think you're actually just not wanting to put the time in to do this yourself.

Please review this page to get advice on what to do to get answers to your homework questions.

-SN

I may have missed something here...

"Can anyone help me. Please find the details below or visit..."

Where is your list of things that you have done to meet this objective? Where is your attempt at a code modification to increase this code's optimization? We need to see some work on your end, not just the specs of your assignment...

Check:
http://www.computing.net/programming/wwwboard/forum/7407.html

IR

I have tried the following. Can't get it to compile. I'm getting errors with the add and mult???

#include <stdio.h>
#include <math.h>

// Get the number of processor clock ticks
// This is for gcc3.x compiler only, if you have some
// other compiler, you need something else here
#define RDTSC(llptr) { \
__asm__ __volatile__ ( \
"rdtsc" \
: "=A" (llptr) ); }

typedef struct complex Complex;
struct complex {
double real;
double imag;
};

#define size 1000
#define limit 1000

// if your compiler supports inline functions, then try it
#define HAS_INLINE /*inline*/

int pix[size][size];

// use pointers
HAS_INLINE Complex mult(const Complex *a, const Complex *b)
{
Complex res;
res.real = a->real * b->real - a->imag * b->imag;
res.imag = a->real * b->imag + a->imag * b->real;
return res;
}

// use pointers
HAS_INLINE Complex add(const Complex *a, const Complex *b)
{
Complex res;
res.real = a->real + b->real;
res.imag = a->imag + b->imag;
return res;
}

// don't do sqrt()
// instead of sqrt(x) < 2, do x < 4
HAS_INLINE double Cabs(const Complex *a)
{
return a->real * a->real + a->imag * a->imag;
}

int pixval(double xx, double yy)
{
Complex z = { 0, 0 };
Complex c;
int j;
c.real = yy;
c.imag = xx;
for (j = 0; j < limit && Cabs(&z) < 4; j += 1) {
Complex t = mult( &z, &z);
z = add( &t, &c);
}
return j / 20;
}

void fillpix(double x0, double y0, double xinc, double yinc)
{
int x, y;
double xd, yd;
for (x = 0, xd = x0; x < size; ++x, xd += xinc ) {
for (y = 0, yd = y0 ; y < size; ++y, yd += yinc ) {
// mathematically, multiplication is repeated addition
// computationally, it isn't due to small errors caused by
// floating point numbers being approximations
// this leads to some small differences in the results
#if 1
pix[x][y] = pixval( xd, yd ); // about 1% quicker than repeated multiply
#else
pix[x][y] = pixval( x0 + x * xinc, y0 + y * yinc );
#endif
}
}
}

int main()
{
unsigned long long t1, t2;
int x, y;
RDTSC(t1);
fillpix(-2.0, -2.0, 4.0 / size, 4.0 / size);
RDTSC(t2);
fprintf( stderr, "time=%lld\n", t2-t1 );
for (y = 0; y < size; y += (size / 20)) {
for (x = 0; x < size; x += (size / 50))
printf("%c", ' ' + pix[y][x]);
printf("\n");
}
return 0;
}

Just wondering how this is going. Did you get it compile yet?

What errors are you getting with Add and Mult... The code compiles in Dev-C++ for the most part and does not fall far from what was given to you by your instructor. Using GCC, the code you have will not compile due to a segmentation fault. Ensure you have the right formulas for complex number addition and multiplication. What compiler are you using and what are your exact error messages?

IR