I copied the code on page 16 of the Cilk 5.4.6 Reference Manual, it is theCilk version of the fibonacci code. Iadded the line:
#include
to the code.
Butwhen I compiled the code I got the follwing error:
cilk: 5: error expected constructor destructor or type conversion before 'int'
line 5 is the line
cilk int fib (int n)
What is causing this error?
Newport_j
The word, "cilk" is causing the error in the line:
cilk int fib (int n)
Oh, snap! You're using the wrong manual. You should be using the Cilk++ manual:
http://software.intel.com/file/23634
Cilk5 is an MIT extension to C. It's a different product.
Okay, so other than changing the compiler, how do I get the code shown above to compile? Is the only way to get it to compile is to change the compiler?
Newport_j
You can probably change the following things:
1. Change all "spawn" to "cilk_spawn"
2. Chagne all "sync" to "cilk_sync"
3. Change main() to cilk_main()
4. Remove all bare "cilk" keywords.
5. Add #include to the top of the file.
6. You will find a redundant cilk_spawn in the implementation of fib(). You can remove it.
I noticed that by doing what you said in the first five steps above, I get a race condition. If I remove one of the cilk_spawn statements, will thatcorrect it? Also, which one do you recommend thatI remove and why? They are as follows:
cilk_spawn fib (n-1)
cilk_spawn fib (n-2)
Also, does one hvae to use the -g option when compiling a Cilk program to run in cilkscreen?
Newport_j
What variable is being raced on?
Re: cilk_spawn -- the second one is redundant. If it spawns and another worker steals the continuation, it will immediately sync. All workers involved are inconvenienced. The second spawn was necessary in Cilk5 because you _couldn't_ both spawn and call the same function. Functions that were allocated on the heap _had_ to be spawned. In Cilk++, this was no longer the case. You now have a choice for Cilk functions.
What variable is being racred on?
I am not sure how to answer that question. I ran Cilkscreen on the compiled version of fibonacci, with the corrections made,and the output was:
1 error found by Cilkscreen
process killed by signal 10
So I guess it was not a data race. Please be aware thta I am using a sngle processor laptop so i can only use the analytical tools that apply to that.
Newport_j
Cilkscreen runs the application sequentially, no matter how many cores you have. One of the nice things about it is that, if your program is deterministic,it can infer whether there is a race for any schedule of the program on the input set you ran.
Was that all of the output Cilkscreen gave you? Would you post the exact code you compiled and ran?
The code for the program that gave the race condiiton is shown below. I am having trouble duplicating the other error,I will post it whenI havethe errorduplicated.
#include
#include
#include
int fib (int n)
{
if (n<2) return n;
else
{
int x, y;
x = cilk_spawn fib (n-1);
y = cilk_spawn fib (n-2);
cilk_sync;
return (x+y);
}
}
int cilk_main (int argc, char *argv[1])
{
int n, result;
n = atoi(argv[1]);
result = cilk_spawn fib (n);
printf("Result: %d\n", result);
return 0;
}
I cannot show the output from a screen shot of the linux screen; I will simply duplicate it here:
Race Condition on location0X8078ecc
Result 832040
1 error found by Cilkscreen
It clearly indicates a race condition, but I am not sure what variable is being raced on.
Finally, when you said it a earlier post in this thread that I could eliminate one
6. You will find a redundant cilk_spawn in the implementation of fib(). You canremove it.
In that you meant to eliminate the cilk_spawn designation, not the complete line.
Say from this:
x = cilk_spawn fib (n-1);
y = cilk_spawn fib (n-2);
to this
x = cilk_spawn fib (n-1);
y = fib (n-2);
This is similar to a paper I found about reducers by Matteo Frigo. You did not mean to eliminate the whole line. That would ruin the logic of the code.
Newport_j
That's right. I wasn't clear: When I say "remove the cilk_spawn" I mean just the keyword and not the whole line.
---
The race is in cilk_main(). It seems there is more than I had said in converting Cilk5 code to Cilk++ code. You have to remove the cilk_spawn in cilk_main() as well. The race is on the variable result. The printf statement can happen in parallel with the spawned fib(), so result may not be assigned by the time it executes and you will get junk data.
I am surprised that this was all the data Cilkscreen gave you. Try compiling your program with -g and run Cilkscreen on it (without removing the race) and see if it gives you more.
I see what you say, but I have one question: running cilkscreen does determine if there is a race conditon. Now fromcilkscreen's output (which is hard to show since I take a screenshot of the output and then Ifind thatI cannot copy and paste it onto the Forum screen) I cannot tellwhat variable is being raced. I can see from the logic that result is being raced. I would just like to have cilkscreen tell it to me.
Someday the raced variable may not be so obvious.
Newport_j
That's why I say try compiling with -g so that debugging symbols are retained. I believe it at least gives you the file and line number.
This is the output i get when I compile the fibonacci cilk code with the -g option and run cilkscreen. I get a error message and a memory location, but no variable name.
/Desktop/cilk/examples/fibonacci$ cilkscreen ./fibo_cilk 30
Race condition on location 0x8ae1ecc
write access at 0x8048aae: (/home/james/Desktop/cilk/examples/fibonacci/fibonacci.cilk:26, __cilk_spawn_fib_003+0x5e)
read access at 0x8048b61: (/home/james/Desktop/cilk/examples/fibonacci/fibonacci.cilk:28, _Z9cilk_mainQiiPPc+0x71)
called by 0x8048e7e: (_ZN4cilk9main_wrapEQiPv+0x4e)
called by 0xb609ad14: (_Z20cilk_run_wrapper_intQvPv+0x34)
called by 0xb609ca7d: (__cilkrts_init_helper+0x4)
Result: 832040
1 error found by Cilkscreen
I am repeating the steps as I said, there is everything except a variable name and/or a line number. That is why I am repeating the steps. I think I did something wrong.
Newport_j
I stand corrected. There are line number 26 and 28 concerning the race condition. The whole cilkscreen output gives that to you.
Is there a way short of removing cilk_spawn in main that can eliminate this race condition?
Newport_j
Okay. Those names are still mangled, and I'm sure there's a way to demangle them, but I don't know what the proper gcc incantation is.
---
You could put a cilk_sync on the line immediately following the cilk_spawn. But that cilk_spawn isn't buying you anything. The real work is in fib().
I think I have found a way to stop that data race, but I am afraid it is a kludge. If I put a cilk_sync statement right after the printf statement there is no data race. I am not sure why this works. I got the idea from reading you response immediately above.
As a former GPU programmer, I always thought it a good idea to use a minimum of sync statements in parallel programming. So maybe that is why itshouldnot beused there.Sync statememts in parallel programming slow things down; use them sparingly.
I did not recieve an answer to this query so I ask again. I was able to stop getting a data race error, by simply putting a cilk_sync; comment into the main program.
I do not think it a good idea however. There is no disccusion of this particular case in the Programmers Guide.
The cilk_sync command followedthe cilk_spawn and printf command that called fibonaccifunction. This works, it stop the data race error from cilkview, but what is wrong with it? It could not be correct.
The original shown below.
I think I have found a way to stop that data race, but I am afraid it is a kludge. If I put a cilk_sync statement right after the printf statement there is no data race. I am not sure why this works. I got the idea from reading you response immediately above.
As a former GPU programmer, I always thought it a good idea to use a minimum of sync statements in parallel programming. So maybe that is why itshouldnot beused there.Sync statememts in parallel programming slow things down; use them sparingly.
Newport_j
If you spawn fib(), you need to sync before you can use the result. (Otherwise you have a race). Since your main program prints the result immediately, you will need to sync immediately. A spawn followed immediately by a sync does not give any benefit and actually adds overhead. What is your reluctance to simply removing the cilk_spawn from the call to fib() in main()?
P.S., if you pipe the output of Cilkscreen through 'c++filt', it will demangle the function names for you.
What is your reluctance to simply removing the cilk_spawn from the call to fib() in main()?
I have no reluctance. I was just curious as to why this worked. It seemed it should not have. Anyway, it does add overhead (asI suspected) and should be avoided.
P.S., if you pipe the output of Cilkscreen through 'c++filt', it will demangle the function names for you.
Could you expand on this? I am relatively new to Cilk programming so I do not understand the PS statement. Please expand.
Newport_j
> I have no reluctance. I was just curious as to why this worked. It
seemed it should not have. Anyway, it does
> add overhead (asI suspected)
and should be avoided.
Oh, I see what you mean. I don't see why adding a cilk_sync AFTER the printf should help. It looks to me like the race is still there, since result is not determinite when the printf tries to use it. Strange. Can you post the exact code that works but shouldn't?
>>P.S., if you pipe the output of Cilkscreen through 'c++filt', it will demangle the function names for you.
>Could you expand on this? I am relatively new to Cilk programming so I do not understand the PS statement.
c++filt is a program available on gcc implementations. It will take any text that contains mangled C++ names and unmangle them. For example, the output of the Unix nm command will contain mangled names if called on an object file that was produced from a C++ source. Piping the output through c++filt makes the results easier to read. I was suggesting that you pipe the output of cilkscreen to c++filt. I do not have a version of Cilk++ for gcc handy right now, but I think that there is a custom version of c++filt in the Cilk++ package. (The one that comes with stock gcc won't work with Cilk-mangled names.)
-Pablo
"Name mangling" is also called "Name decoration."It is a technique to encode addtional information into names.The Wikipedia article on it gives a good description. http://en.wikipedia.org/wiki/Name_mangling
Consider the output you posted from Cilkscreen:
Race condition on location 0x8ae1ecc write access at 0x8048aae: (/home/james/Desktop/cilk/examples/fibonacci/fibonacci.cilk:26, __cilk_spawn_fib_003+0x5e) read access at 0x8048b61: (/home/james/Desktop/cilk/examples/fibonacci/fibonacci.cilk:28, _Z9cilk_mainQiiPPc+0x71) called by 0x8048e7e: (_ZN4cilk9main_wrapEQiPv+0x4e) called by 0xb609ad14: (_Z20cilk_run_wrapper_intQvPv+0x34)called by 0xb609ca7d: (__cilkrts_init_helper+0x4)
The function name _Z9cilk_mainQiiPPcn is mangled, or decorated to encode the function parameters and return type. This is how C++ allows you to overload function names, so for example you can have functions with the same name that take different parameters.
As Pablo noted, c++filt will convert _Z9cilk_mainQiiPPcn to it's clear-text form of
int cilk_main(int, char **)
- Barry