I am looking for a compute-intensive C/C++ algorithm to multithread using the recently released Cilk++ programming platform (targeted at multicore programming, in particular bringing serial algorithms into the multicore realm).Any advice, or interest in playing around with the download?thanks in advance.

When you say 'serial algorithms' to parallel algorithms are you referring to loop-level optimisation?//Many serial apps are difficult to make parallel in my opinion, for a number of reasons. It will be necessary to task/data *decompose* first for optimal speedup. Like starting over again.

Some algorithms are in fact inherently serial, but others (for example, many Monte Carlo simulations) yield nicely to multithreading with Cilk++. We're looking for more good test cases, so we're interested in knowing which problems you consider both important and computationally expensive.

MC applications are *relatively* straightforward. The big challenge in my opinion is to resolve the 'curse of dimensionality' and new algorithms are needed. What about algos that are not feasible on single processors but might give acceptable speedup on multi-core?

some sobering thoughts on parallel programming from Donald Knuth QuoteAndrew: Vendors of multicore processors have expressed frustration at the difficulty of moving developers to this model. As a former professor, what thoughts do you have on this transition and how to make it happen? Is it a question of proper tools, such as better native support for concurrency in languages, or of execution frameworks? Or are there other solutions?Donald: I don’t want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrific

QuoteOriginally posted by: imirmanSome algorithms are in fact inherently serial, but others (for example, many Monte Carlo simulations) yield nicely to multithreading with Cilk++. We're looking for more good test cases, so we're interested in knowing which problems you consider both important and computationally expensive.You might also look at trading platforms as both a more heterogeneous example of parallel computing and as an example in which latency, not throughput, is the dominant goal. The processes for ingesting streams of real-time messages from the markets, deciding what to buy/sell, output trading directives, tracking order status, and maintaining a coherent picture of the portfolio involve a lot of different types of threads of computation that inter-couple at various points.

QuoteOriginally posted by: Cuchulainnsome sobering thoughts on parallel programming from Donald Knuth QuoteDonald: I don’t want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrificGiven that both the low-level architectures (e.g., multicore CPUs) and the high-level architectures (e.g. cloud computing) are moving in the direction of increasing parallelism, the onus seems on software folk to create a paradigm for parallel computing.Part of me wonders whether procedural languages are simply the wrong tool for parallel problems because procedural is inherently serial. This seems like a Sapir-Whorf problem and perhaps some prevailing languages just don't give us the right words to speak fluently about parallel computing.Perhaps it's time to take a step back and enumerate what we need to talk about when constructing code for parallel environments. These might include:1. Partitioning whole problems into parallel sub-elements (is this an object decomposition problem?)2. Understanding or immunizing against out-of-order execution (avoiding the trap of assumed sequences)3. Dealing with asynchronous or synchronous coupling between parallel sub-elements.4. Aggregating results from parallel sub-elements into a coherent whole.5. Picking the right granularity -- just because something can be parallel, doesn't mean it should be parallel.6. Understanding the resource trade-offs for creating/maintaining/aggregating 2N parallel sub-elements vs. N or understanding N+1 sub-elements vs. N or understanding M sub-elements vs. N processing units.What's interesting to me are the cases in which the algorithm seems inherently serial, but the problem is definitely parallel. For example, recursive algorithms for the factorial function (and many algorithms like it) look serial, but the actual function can be very parallel (with as many as N-1 threads if one seeks minimum latency). What language should we use to talk about a problem so that it's easier (or at least as easy) to speak of the parallel version as to speak of the serial version?

QuotePart of me wonders whether procedural languages are simply the wrong tool for parallel problems because procedural is inherently serial. This seems like a Sapir-Whorf problem and perhaps some prevailing languages just don't give us the right words to speak fluently about parallel computing.Exactly!And what developers are doing is using their existing (Whorf) languages to merge them with parallel processing. It will be sub-optimal in my experience. For example, no way will it be possible using any mainstream language to model *load balancing* because these languages are just too low-level. They just don't have the vocabulary to let us think about it.But parallel applications can be analysed using *graph theory* and then doors start opening (shortest paths, network analysis etc.) This is called a data dependency graph and this language is rich enough to let us model these applications.I am already starting to reach this barrier already (you realise all the more when you have to explain it to someone!). And what is essential imo is that you must decompose parallel systems asap. The programming language will leave you in the lurch if you do not.My advice: keep a clear head.