problem with algorithm for two threads

[here we go]

Hello.
I'm new to thread programming and designing algorithims which are
using two cores of CPU. I've written a simple programme that
calculates Fast Walsh Transform and it works great but only on one
core. I've tried many times to rewrite the code for two cores (so that
cpu will be used in 100%) but due to my lack of knowledge in this area
I've failed.
I would really appreciate if someone could rewrite only the algorithm
or give some hints. Below is working code for one core (haven't placed
my attempts for two with pthread_create and other stuff).

Input: length of array (must be power of 2 for e.g 8) and array
created from file. The file contains only numbers 0 and 1 for example
11010011
Output: for input length ile=8 and file containing 11010011 the output
should be: tab=[5 -1 -1 1 1 -1 3 1]

#include <stdio.h>
#include <stdlib.h>

int *tab; //our array
long long int ile; //length of array


int main(void)
{
int ile,i=0,tmp;
FILE *pl;
char c;

printf("Table length: ");
scanf("%d",&ile);
tab = (int*)malloc(ile*sizeof(int*));
pl=fopen("myfile8.txt","r");
c=fgetc(pl);

while(c!=EOF)
{
tmp=atoi(&c);
tab=tmp;
c=fgetc(pl);
i++;
}

long long int a,b,dist,start,block,pair,el1,el2;
dist = 1;
start=ile;
do
{
el1=0; //=0
start=start/2;
for(block=start; block>0; block--)
{
el2=el1+dist;
for(pair=0;pair<dist;pair++)
{
a=tab[el1];
b=tab[el2];
tab[el1]=a+b;
tab[el2]=a-b;
el1++;
el2++;
}
el1=el2;
}
dist=dist*2;
}
while(dist!=ile);

for(i=0;i<ile;i++) printf("tab: %d\n",tab);
return 0;
}

 

[Jens Thoms Toerring]

I'm new to thread programming and designing algorithims which are
using two cores of CPU. I've written a simple programme that
calculates Fast Walsh Transform and it works great but only on one
core. I've tried many times to rewrite the code for two cores (so that
cpu will be used in 100%) but due to my lack of knowledge in this area
I've failed.

First of all the C language as such has no support for threading,
you have to use whatever extensions your system has. So this group
isn't really the best to ask in. comp.programming.threads looks a
lot more like what you should consider.

I would really appreciate if someone could rewrite only the algorithm
or give some hints. Below is working code for one core (haven't placed
my attempts for two with pthread_create and other stuff).

This group isn't about algorithms but about the C language. And
if you write to a different group where this is topical I would
strongly recommend that you give a description of what the Fast
Walsh Transform does instead of just posting your implementation.

But then there are several C related issues with your program
that I will try to address:

#include <stdio.h>
#include <stdlib.h>

int *tab; //our array

Actually, it's a pointer to the array you will allocate...

long long int ile; //length of array

This variable will be inbisible in main() since you have a
variable with the same name defined in main().

int main(void)
{
int ile,i=0,tmp;
FILE *pl;
char c;

printf("Table length: ");
scanf("%d",&ile);
tab = (int*)malloc(ile*sizeof(int*));

First of all, this is wrong because you need an array of ints
and not of int pointers. Also casting the return value of malloc()
doesn't buy you anything. Since you included <stdlib.h> the com-
piler already knows what type malloc() returns and converts it
automatically from a void to an int pointer. And third 'ile'
is the local variable defined above and not yet initialized,
so it contains some random value. So, after giving 'ile' a value,
make that

tab = malloc( ile * sizeof( int ) );

or, for simpler maintaince

tab = malloc( ile * sizeof *tab );

Since you don't do any error checking in your program I will
assume that you have removed it for brevity's sake. If not
you should definitely consider checking all function calls that
may return an indication of failure.

pl=fopen("myfile8.txt","r");

while(c!=EOF)

You defined 'c' to be a char and a char can never have the value
of EOF. EOF simply doesn't fit into a char and thus it gets trun-
cated to something else. Thus always store the return value of
getc() in an int.

{
tmp=atoi(&c);

This can't work. atoi() operates on a string, i.e. a char array
with a '\0' character somewhere to indicate the end of the string.
But you pass it the address of a single char. Accidentally, some
memory in the vincinity of 'c' may contain a '\0' (or some value
that makes stoi() stop) but that's only by sheer luck and isn't
going to ever work reliably.

tab=tmp;
c=fgetc(pl);
i++;
}

This whole loop could be simplified and corrected, given that
'c' is defined as an int) to

while ( ( c = getc( pl ) ) != EOF )
tab[ i++ ] = c - '0';

In a real program you probably guard against wrong values of
'ile' - if that's too small you will otherwise write past the
end of you 'tab' array.

long long int a,b,dist,start,block,pair,el1,el2;

Defining new variables after the first executable statement is
a C99 feature, older compilers will chole on it (just as a hint
so you don't wonder when it doesn't compile with a different
compiler).

dist = 1;
start=ile;
do
{
el1=0; //=0
start=start/2;
for(block=start; block>0; block--)
{
el2=el1+dist;
for(pair=0;pair<dist;pair++)
{
a=tab[el1];
b=tab[el2];
tab[el1]=a+b;
tab[el2]=a-b;
el1++;
el2++;
}
el1=el2;
}
dist=dist*2;
}
while(dist!=ile);

Actually, this algorithm doesn't look as if it would be
suitable for parallelization (and what you want to use
threads for otherwise?) since it looks a lot as if the
newly calculated elements depend directly on elements cal-
culated before. But I may have gotten a wrong impression...

for(i=0;i<ile;i++) printf("tab: %d\n",tab);
return 0;
}

Regards, Jens

 

[Ben Bacarisse]

I'm new to thread programming and designing algorithims which are
using two cores of CPU. I've written a simple programme that
calculates Fast Walsh Transform and it works great but only on one
core. I've tried many times to rewrite the code for two cores (so that
cpu will be used in 100%) but due to my lack of knowledge in this area
I've failed.
I would really appreciate if someone could rewrite only the algorithm
or give some hints. Below is working code for one core (haven't placed
my attempts for two with pthread_create and other stuff).

You need to ask in comp.programming.threads and I think you'll need to
outline your plan at the very least. Just posting single-threaded code
and saying "can't run on multiple cores" may not get you good answers.

Input: length of array (must be power of 2 for e.g 8) and array
created from file. The file contains only numbers 0 and 1 for example
11010011
Output: for input length ile=8 and file containing 11010011 the output
should be: tab=[5 -1 -1 1 1 -1 3 1]

#include <stdio.h>
#include <stdlib.h>

int *tab; //our array
long long int ile; //length of array

There's no apparent reason for these to be here. Local variables are
better in almost all cases (and that includes most multi-threaded
programs).

int main(void)
{
int ile,i=0,tmp;
FILE *pl;
char c;

printf("Table length: ");
scanf("%d",&ile);
tab = (int*)malloc(ile*sizeof(int*));

tab = malloc(ile * sizeof *tab);

is a neat and simple way to write this.

pl=fopen("myfile8.txt","r");

It's a very good idea to get into that habit of checking things that
might fail. scanf, malloc and fopen all fall into this category.

c=fgetc(pl);

while(c!=EOF)
{
tmp=atoi(&c);

Ouch! &c is not the start of a string -- there is no terminating
null character unless c itself is 0.

Using atoi would work if c was a two-element array:

char c[2] = {0};

and you read the input into c[0] and converted it using atoi(c) but if
the input always '0' or '1'...

tab=tmp;

tab[1] = c == '1';

would work.

c=fgetc(pl);
i++;
}

The canonical way to write this would be:

while ((c = fgetc(pl)) != EOF && i < ile)
tab[i++] = c == '1';

Note that I've added a test to avoid overflowing the size of tab.

long long int a,b,dist,start,block,pair,el1,el2;
dist = 1;
start=ile;
do
{
el1=0; //=0
start=start/2;
for(block=start; block>0; block--)
{
el2=el1+dist;
for(pair=0;pair<dist;pair++)
{
a=tab[el1];
b=tab[el2];
tab[el1]=a+b;
tab[el2]=a-b;
el1++;
el2++;
}
el1=el2;
}
dist=dist*2;
}
while(dist!=ile);

I don't think you can be sure that this condition is certain to become
false.

for(i=0;i<ile;i++) printf("tab: %d\n",tab);
return 0;
}

Finally, I'd want to add more space. For example, most people would
write the last loop like this:

for (i = 0; i < ile; i++)
printf("tab: %d\n", tab);

 

[here we go]

Thank a lot Jens for a quick and concrete answer. I will definately
rewrite code taking into consideration your hints.

 

[here we go]

Thanks Jens and Ben for exact and fast answers. I will definately
rewrite the code taking into consideration those hints.