Is it possible to spawn a pointer to a function?

Is it possible to spawn a pointer to a function?

Is it possible to spawn a pointer to a function, i.e. spawn a function that is embedded in a data structure?

16 帖子 / 0 全新
最新文章
如需更全面地了解编译器优化,请参阅优化注意事项

Any function that has Cilk++ linkage can be spawned. Bear in mind, however, that the linkage affects the type of the pointer. The following code will not work:

void (*f) ();
f = foo;
cilk_spawn f();

Instead, Cilk++ linkage must be specified in the pointer type:

void (__cilk *f) ();
f = foo;
cilk_spawn f();

---

Edit: I should have used this opportunity to plug Cilk Plus, which does not have these linkage distinctions and where any function can be spawned:

http://software.intel.com/en-us/articles/intel-cilk-plus/

Consider the following scenario:F spawned F1 and F2F1 spawned T and waits in syncT failedNow I want F2 to spawn T2 before F1 exits the sync.So - I need to signal F1 that although T terminated, it needs to wait in sync for another spawned function.Hope this scenario is clear...Is it possible to support such execution?

You can do it, but it's evil.

The real issue is that spawns are opportunities for parallelism. But in the end, it's up to the scheduler to decide how much parallelism is exploited. So if the code doesn't make sense without the spawns and syncs, we sayit's taboo. You can devise methods of forcing the scheduler to do certain things, but you're now fighting with the language (and producing obfuscated code) rather than working with it.

What is the use case, if I might ask?

The use case:Lets say you want to spawn a transaction on a shared structure, and then perform some (unrelated) work and then sync.If the transaction is aborted, I want to spawn it again (retry) after a while, by another spawned function.I want the sync to wait until the transaction commits successfully, but do not want the transaction to keep the processor busy.On the other hand, I do not want the sync of the function which re-spawned the transaction to wait for the re-spawned transaction sync.Lets say you want to spawn a transaction on a shared structure, and then perform some (unrelated) work and then sync.If the transaction is aborted, I want to spawn it again (retry) after a while, by another spawned function.I want the sync to wait until the transaction commits successfully, but do not want the transaction to keep the processor busy.On the other hand, I do not want the sync of the function which re-spawned the transaction to wait for the re-spawned transaction sync.I do have all the syncs, and let them beopportunisticbut need a way to "bind" a function to a sync, so that this function may hit the sync only when successful, and otherwise be re-spawned by other spawned functions.Hope this makes sense, or at least is more clear.

Are you saying something like this?

void foo () {
bool done = false;
while (!done) {
done = cilk_spawn do_transaction();
do_some_other_work();
cilk_sync;
}
}

arg =do_transaction;void foo () {
bool done = false;
cilk_spawn do_transaction(arg);
do_some_other_work();
cilk_sync;
}void do_transaction(arg) {if (conflict) arg.status=pend pend=argelse commit} void bar(){cilk_spawn(bar1)cilk_spawn(pend)do_some_other_work();sync}Now - only whendo_transaction commits, I want foo to sync, and bar should sync regardless ofdo_transaction.

Every function syncs with its children before it exits. foo() is going to sync whether the cilk_sync is explicit or not since there's nothing left in the function.

Note: cilk_sync is not a global thing. It doesn't wait for _all_ parallel work to be done. Only the children it spawned.

What I need is actually extension to cilk:A. X=pend() - function stops running but is not complete.B. spawn(X) - continue foo from the point it called pend().Do these extensions make any sense?

You could break pend() into two functions and then spawn the one that represents the second half.

---

Looking over your pseudo-code, again, it looks like you are trying to implement a multithreaded algorithm rather than a parallel algorithm. The distinction is that:

1.A multithreaded algorithm requires multiple threads, whereas a parallel algorithm does not.

2. A parallel algorithm is structured, whereas a multithreaded algorithm tends to be more free-form.

A good parallel language will do good load balancing on arbitrary parallel algorithms, whereas this is very difficult when multithreading, yourself. The structure of parallel languages should allow arbitrary scalability up to the parallelism of the algorithm, whereas manually multithreading tends to allow scalability up to the number of threads you write into your algorithm.

Some benefits of parallel algorithms are that they tend to be far easier to read, understand,and debug than multithreaded ones. Parallel extensions, like Cilk, allow you to prove things about the scalability and correctness of your code.

On the other hand, parallel algorithms don't easily do certain things that multithreaded algorithms can do. A prime example is creating a queue of work that's accessed via mutex. Likewise, creating n threads to listen to n ports on a network is a multithreaded thing to do, and not parallel.

There are also certain parallel constructs for which no infrastructure has been written in Cilk++ (as opposed to, e.g., TBB which has many more). But your pseudo-code looks a lot like something that wants to use pthreads (or Windows threads) rather than a parallel extension.

Is there a way to implement pend/resume for spawned cilk functions?

Split it into two functions.

The problem: I don't want the parent of T to sync when T pends. I want it to sync after T resumes and succeeds + when T pends I do not want the CPU to see T...is such execution possible in cilk?

If the parent doesn't sync, what is it going to do when do_other_work() returns? If you don't want it to sync, you can make it wait until the second part of T has been executed. But then why not simply have it do the second part, itself?

OK,let me start from the beginning:I want to support transactions in Cilk.So - I spawn a few "application threads" (AT).Each AT can spawn transactions that are not a barrier. I.e.: E=dequeue will not spawn, but enqueue(x) will.An AT may spawn transactions and perform other work in between.At some point, the AT will need to sync. At that point it will wait for all spawnedtransactions(and other spawned functions).However, unlike other functions, transactions may abort, as they hit other transactions that may belong to other AT. Now, if transaction T1 hit T2, I want T1 to pend and T2 to resume it when it commits. T1 and T2 may belong to AT1 and AT2. Still. AT1 should wait T1 to sync while AT2 waits for T2, even though T1 resumed T2. While AT1 waits for T1, it can steal work, for example, T3 from AT3.

I see.

This sounds like a multi-threaded algorithm-- something that would be much easier and simpler using pthreads or Windows threads.

Right at the beginning, the idea of spawning "a few application threads" is something that has no serial meaning and is not a good fit for parallel language extensions or libraries. On the other hand, it is exactly the kind of thing for which pthreads and Windows threads were designed.

To put it another way, when you start thinking about how individual threads should operate and the protocols for interacting with one another, you're doing the scheduling.

It looks to me like this algorithm requires a pool of threads for which there is a global queue of transactions on which they are waiting. When there is a collision, the "loser" should pick up the transaction from the "winner" and recommit. Since there is other work to do, you should create more threads to do the other work. When an AT has nothing to do, it should yield the CPU and even sleep for a few millisecondsafter enough yields without work.

Let me contrast this with a more parallel-style algorithm (an unrelated algorithm):

I have some serial algorithm that I can solve using divide-and-conquer. Each time I divide it n ways, I am going to spawn n - 1 parts and call the last one. Note: I am not creating threads with my spawns. Underneath, the scheduler will decide how many threads will be created and which spawns _actually_ lead to parallel work and which ones don't. Maybe all spawns will realize parallelism, or maybe none of them. The algorithm is oblivious to such things.

The toy example we tend to use is fibonnacci:

int fib (int n) {
int a, b;
if (n < 2) return n;
a = cilk_spawn fib(n - 1);
b = fib(n - 2);
cilk_sync;
return a + b;
}

It's a toy because there is a serial O(lg(n)) algorithm to calculate values of fib. But it's a good example because it should be clear that for large values of n we really don't want enough threads running on the machine to try to realize all of the parallelism. If threads were spawned at each cilk_spawn the machine would get bogged down in threads.

Cilk really exists for serial algorithms that can expose potential parallelism. Pthreads and Windows threads exist for algorithms where you need to be thinking about threading protocols.

发表评论

登录添加评论。还不是成员?立即加入