Auto-Parallelizing Compiler From Codeplay

Max Romantschuk writes "Parallelization of code can be a very tricky thing. We've all heard of the challenges with Cell, and with dual and quad core processors this is becoming an ever more important issue to deal with. The Inquirer writes about a new auto-parallelizing compiler called Sieve from Codeplay: 'What Sieve is is a C++ compiler that will take a section of code and parallelize it for you with a minimum hassle. All you really need to do is take the code you want to run across multiple CPUs and put beginning and end tags on the parts you want to run in parallel.' There is more info on Sieve available on Codeplay's site."

Comments

Reentrant?

[Psychotria]

Forgive me if I'm wrong (I've not coded parallel things before), but if the code is re-entrant, does this go a long way towards running the code in parallel? Obviously there are other factors involved here, like addressing memory, but this is thought of in re-entrant programming. I'm not sure what the difference is... please enlighten me :-)

Re:Reentrant?

[Anonymous Coward]

Reentrancy is a factor, because it's a class of dependencies, but there are many other dependencies.

Consider a for loop: for (int i=0; i100; i++)doSomething(i);

Can this be parallelized? Perhaps the author meant it like it's written there: First doSomething(0), then doSomething(1), then ... Or maybe he doesn't care about the order and doSomething just needs to run once for each i in 0..99. The art of automatic parallelization is to find overspecifications like the ordered loop where order isn't really necessary. If nothing in doSomething depends on the outcome of doSomething with a different i, they can be run in parallel and in any order. Suppose each doSomething involves a lengthy calculation and an output at the end. Then they can't simply run in parallel, because the output is a dependency: As written, the output from doSomething(0) comes before doSomething(1) and so on. But the compiler could still run the lengthy calculation in parallel and synchronize only the fast output at the end. The more of these opportunities for parallelism the compiler can find, the better it is.

Re:Reentrant?

[644bd346996]

In the case of the for loop, that is really a symptom of the fact that c-style languages don't have syntax for saying "do this to each of these". So one must manually iterate over the elements. Java does have the for-each syntax, but it is just an abbreviation of the "for i from 0 to x" loop.

Practically all for loops written are independent of order, so they could be trivially implemented using MapReduce. That one change would parallelize a lot of code, with no tricky compiler optimizations.

Re:Reentrant?

[mrchaotica]

Interesting! I'd never heard of "map and reduce" before, but it seems like just the sort of idiom that would be useful for the program I'm getting ready to write.

Would it make sense to have an interface for it like this in C:

void map(int (*op)(void*), void** data, int len);

Where the implementation could be either a for loop:

void map(int (*op)(void*), void** data, int len)
{
int i;
for(i = 0; i < len; i++) {
(*op)(data[i]);
}
}

or an actual parallel implementation, such as one using pthreads or running on a GPU?

Re:Reentrant?

[jd]

Simple version: Parallel code need not be re-entrant, but all re-entrant code is parallel.

More complex version: There are four ways to run a program. These are "Single Instruction, Single Data" (ie: a single-threaded program), "Single Instruction, Multi Data" (SETI@Home would be an example of this), "Multi Instruction, Single Data" (a good way to program genetic algorithms) and "Multi Instruction, Multi Data" (traditional, hard-core parallelism).

SIMD would need to be re-entrant to be parallel, otherwise you can't be running the same instructions. (Duh. :) SIMD is fashionable, but is limited to those cases where you are operating on the data in parallel. If you want to experiment with dynamic methods (herustics, genetic algorithms, self-learning networks) or where you want to apply multiple algorithms to the same data (eg: data-mining, using a range of specialist algorithms), then you're going to be running a vast number of completely different routines that may have no components in common. If so, you wouldn't care if they were re-entrant or not.

In practice, you're likely to use a blend of SIMD, MISD and MIMD in any "real-world" program. People who write "pure" code of one type or another usually end up with something that is ugly, hard to maintain and feels wrong for the problem. On the other hand, it usually requires the fewest messaging and other communication libraries, as you're only doing one type of communication. You can also optimize the hell out of the network, which is very likely to saturate with many problems.

Re:Reentrant?

[prencher]

Not quite; http://labs.google.com/papers/mapreduce.html

Re:Reentrant?

[mrchaotica]

Well, I meant in the more general sense (i.e., your mention of "MapReduce" eventually lead me to find this).

Re:Reentrant?

[MillionthMonkey]

Java does have the for-each syntax, but it is just an abbreviation of the "for i from 0 to x" loop.

I would be very surprised if nobody's tried to work around this problem with AOP and annotations. It would be trivial to code parallelization with a method interceptor.

On a multiprocessor machine the JVM will assign threads to individual CPUs. Your interceptor would populate an array of N threads, assign each thread a number, wrap the annotated method in a callback with a finally {lock.notify()} at the end, synchronize on the lock, start all worker threads, and wait on the lock N times.

The client programmer would annotate a method this way:

@parallelizable(threadIndex = "processorNum")
public void doSomething(int processorNum, Object otherParameter, int etc) {...}

The value of the named int parameter would then be replaced with the thread index by the interceptor, and doSomething() would query that parameter and execute its portion of the for loop.

Or you could apply data parallelization, like parallel Fortran, that supported a meta language in the comments. You'd declare an array and then annotate each dimension with compiler directives like *, BLOCK, or SCATTER. BLOCK split the array in contiguous chunks across N CPUs, SCATTER assigned elements to CPUs so that element i went to the (i mod N) -th CPU, and * was for array dimensions that you didn't want to distribute. So instead of passing down a thread index the annotation would apply to arrays and array dimensions, or preferentially to list collections (to avoid having to copy an array into N subarrays):

@parallelizable(array-names="politicians, donors, amounts, votes" array-distributions="[BLOCK], [SCATTER], [BLOCK,SCATTER], [*,BLOCK]")
public void findPatterns(List politicians, Donor[] donors, float[][] amounts, List> votes) {...}

But this is all really ugly. It would have been so much easier if the language were just designed properly.

Re:Reentrant?

[gerddie]

"Practically all for loops written are independent of order"

I risk to differ:

      istream datafile("datafile.txt", "r");
      vector<float> val(N);
      for (size_t i = 0; i < N-1; ++i) {
              datafile >> val[i];
              if (!datafile.good())
                  throw fileread_exception("datafile.txt");
      }

      for (size_t i = 0; i < N-1; ++i)
                val[i] = val[i] - val[i+1];

Re:Reentrant?

[funfail]

Also check out this: http://www.joelonsoftware.com/items/2006/08/01.htm l

Re:Reentrant?

[I Like Pudding]

Practically all for loops written are independent of order, so they could be trivially implemented using MapReduce.

That is a very large, very unsupported assumption to be making. It certainly doesn't hold true for the code I've seen in the wild and have written myself.

Re:Reentrant?

[HiThere]

Unfortunately, in many of the languages that I'm aware of that implemented foreach, the language itself specifies sequential execution. Some of these are recent languages, too! E.g., D (Digital Mars D) is a language so new that it's 1.0 release was this January. It specifies that foreach is executed sequentially. So, I believe, does Python. This has always seemed to me like lack of foresight, but I didn't write the languages, or even the specs, so I don't have enough room to complain seriously. (I did comment during the D design phase, but it was ignored.)

Re:Reentrant?

[Anonymous Coward]

In the case of the for loop, that is really a symptom of the fact that c-style languages don't have syntax for saying "do this to each of these".

I've only coded a small compiler for a comp sci course, but from my readings on parallel computing, recommend Orielly's "High Performance Computing" book as a quick introduction, optimizing C and fortran compilers have been able to handle this stuff sense the late seventies. You don't need a parallel compiler for this as this is used on single processor systems. You need to get the floating point operations out so that you can keep the pipelines of the FPU's full. They aren't perfect but the compiler should be able to tell something like this:

for(i = 0; i = 10; i++) x[i] = x[i]*5 + 3;

doesn't have any cross dependencies so can be run in parallel. All it has to do is see that all of the tokens for variables in the executable block of the for loop are all ready available at time of entry into the for loop. Not a big issue. The challenge is when there are dependancies, but doing things in a smart order will allow you to do some things in parallel.

Re:Reentrant?

[nuzak]

> Or you could apply data parallelization, like parallel Fortran

Fortress does all loops in parallel by default. You have to explicitly tell it when you want a serial loop.

Re:Reentrant?

[nuzak]

I think I replied to the wrong message (I can't claim it was a typo since I quoted it after all). But anyway, Fortress does all loops in parallel by default, you have to explicitly tell it when you want serial execution.

Python cares so little about parallelism that it still uses a single monolithic lock around the interpreter, so you can't even make reasonable use of threads except for I/O waits. But no imperative language can just throw in something as drastic as auto-parallelism without rewriting basic assumptions about flow control -- you can't simply handwave it in.

Re:Reentrant?

[MillionthMonkey]

Fortress does all loops in parallel by default. You have to explicitly tell it when you want a serial loop.

Fortress does, but Fortran-90 didn't. It was strictly a SISD language and had to be extended in HPF with javadoc-style hacks as I described above so that the compiler knew how to link against the MPI libraries and produce an executable that could take advantage of data parallelism on SIMD/MIMD architectures. The whole thing was one big hack. I think starting with Fortran 95 they began to incorporate features at the language level to support data parallelism. It sounds like it didn't go well because now they're working on a successor language. I have no idea what's been going on with Fortran, having not had to work with it in over ten years.

Re:Reentrant?

[Anonymous Coward]

foreach (item in list)
{
        list2.insert(item);
}
print list2;

Maybe I care about the ordering of list2 is the same as list? Should I be forced to not have the convenience of using foreach?

Re:Reentrant?

[Bill Dog]

No, you may still have the convenience, you would just have to use:
1) A destination container that supported "random-access" writes, to pre-allocated slots, and
2) An overload of the foreach statement that recognized when you were going to express the body of the loop in an index-based fashion/template.
For example:

foreach ( index at list )
{
        list2[ index ] = list[ index ];
}

Re:Reentrant?

[644bd346996]

Why would you manually write code to copy a list? Also, this would be the same as calling Map with an identity function.

FPP

[DigitAl56K]

Frtprallps
is arle ot

Re:FPP

[Anonymous Coward]

please, remove this shadow over me and show me the meaning of this, since obviously I am not as smart as you (or the other people who said it was funny

Re:FPP

[MarkRose]

"first parallel post"

Re:FPP

[thrawn_aj]

"first parallel post" Oh noes DigitAl56K, how did he crack your code? :P Probably thinks in parallel himself =D.

Re:FPP

[Z0mb1eman]

It's funny to anyone who's ever tried debugging a multithreaded app using output statements. :p

(I'm explaining someone else's programming joke on Slashdot... I've reached a new low).

Re:FPP

[dascandy]

Frtprle ot
is aallps

You spelling-clot.

This is Awesome

[baldass_newbie]

I loved 'Clocks'. Oh wait, Codeplay...not Coldplay.
Nevermind.

Oh look. A duck.

Re:This is Awesome

[NotQuiteReal]

You have confused Auto-Parallelizing Compiler From Codeplay

For
Auto-Compiling Code from ParallelPlay
or
Auto-Play Parallelizer from Complay
or something...

Re:This is Awesome

[Criminally Insane Ro]

it's like html code for c++

openMP

[Anonymous Coward]

and what the difference between this and openMP ?

Re:openMP

[compact_support]

Just a vendor's incompatible me-too implementation. I'm sure there are some semantic differences and maybe some new features, but it's the same thing. This product may also be aimed more at multicore desktops than SMP big iron like openmp is. I'm partial to MPI (Specifically, OcamlMPI) myself. 20 cores at 4.3 cpu-days and it was trivial to achieve >99% CPU utilization on all nodes.

Re:openMP

[ioshhdflwuegfh]

and what the difference between this and openMP ? On the page 7 of The Codeplay Sieve C++ Parallel Programming System, 2006 you'll find section that describes "advantages" of codeplay over openmp, but nothing terribly exciting. Codeplay allows you indeed to better automatize parallelization but is at the same time also limited to a narrower set of optimizations compared to openmp.

Re:openMP

[init100]

This product may also be aimed more at multicore desktops than SMP big iron like openmp is.

And the difference would be?

Re:openMP

[compact_support]

A dual core desktop is a different environment than a 128-way ccNUMA system. NUMA systems need to account for local and far memory, even though it's all one address space. There's a lot of optimization that could be done for desktops simply by trimming out all that complicated tuning logic that's used for running on larger systems.

Re:openMP

[Xyrus]

OpenMP is targeted at shared memory, multi-processor systems. For example, OpenMP could be used on the dual and quad core systems. For distributed systems, such as super-computing clusters you need the capability to pass messages quickly and efficiently between nodes (different machines). In this case, you use a message passing library (MPI being the most common).

This sounds like it can do both, as well as determine what parts of the code can be parallelized.

~X~

Hey! Let's reinvent OpenMP!

[Anonymous Coward]

And call it "automatic" while we're at it.

Shouldn't this be at http://ads.slashdot.org/ instead of http://it.slashdot.org?

Interesting, but..

[DigitAl56K]

The compiler will put out code for x86, Ageia PhysX and Cell/PS3. There were three tests talked about today, CRC, Julia Ray Tracing and Matrix Multiply. All were run on 8 cores (2S Xeon 5300 CPUs) and showed 739, 789 and 660% speedups respectively.

That's great - but do the algorithms involved here naturally lend themselves to the parallelization techniques the compiler uses? Are there algorithms that are very poor choices for parallelization? For example, can you effectively parallelize a sort? Wouldn't each thread have to avoid exchanging data elements any other thread was working on, and therefore cause massive synchronization issues? A solution might be to divide the data set by the number of threads and then after each set was sorted merge them in order - but that requires more code tweaking than the summary implies. So I wonder how different this is from Open/MT?

Re:Interesting, but..

[DigitAl56K]

Gah! "OpenMP".

Re:Interesting, but..

[Anonymous Coward]

or example, can you effectively parallelize a sort? Wouldn't each thread have to avoid exchanging data elements any other thread was working on, and therefore cause massive synchronization issues?

Yes you can, take a look a Merge sort (or quick sort, same idea). You split up the large data set into smaller ones, sort those and recombine. That's perfect for parallization -- you just need a mechanism for passing out the orginal elements and then recombining them.

So if you had to sort 1B elements maybe you get 100 computers and give them each 1/100th of the data set. THat's manageable for one computer to sort easily. THen just develop a service that hands you the next element from each machine, and you pull off the lowest one.

Re:Interesting, but..

[Anonymous Coward]

How redundant. You just gave exactly the same solution as the post you replied to.

Re:Interesting, but..

[DigitAl56K]

If you read my post, this is exactly what I suggested. The actual point was that it requires more than simply putting "beginning and end tags" on the code, e.g. it is not automatic.

I would also ask this of CodePlay: If your compiler is automatic, why do we need to add beginning and end tags? :)

Re:Interesting, but..

[ioshhdflwuegfh]

do the algorithms involved here naturally lend themselves to the parallelization techniques the compiler uses? What do you mean?

Are there algorithms that are very poor choices for parallelization? yes, finite state machines.

Re:Interesting, but..

[maxwell demon]

Is there any modern programming language which doesn't provide a sort function in its standard library? Because if you use that, the vendor can simply provide a parallelized version, and you don't have to compare if the vendor parallelized that function manually, or the compiler parallelized it automatically, of even a mixture of both.

Re:Interesting, but..

[maxwell demon]

s/compare/care/

Re:Interesting, but..

[SSCGWLB]

You have a good point; both matrix multiply and ray tracing are embarrassingly parallel problems. They lend themselves to this type of optimization.

Consider a two NxN matrices, A and B, multiplied together to make a matrix C. Each element of C (Cij), is the sum of Ai[0..N] and Bj[0..N]. This is an almost trivial parallelization problem, commonly one of the first coding exercise learned in a parallel processing class.

IMHO, this is interesting but has a long way to go before its useful for anything but a narrow set of problem.

Re:Hey! Let's reinvent OpenMP!

[Duncan3]

You got it.

snake oil

[oohshiny]

I think anybody who is claiming to get decent automatic parallelization out of C/C++ is selling snake oil. Even if a strict reading of the C/C++ standard ends up letting you do something useful, in my experience, real C/C++ programmers make so many assumptions that you can't parallelize their programs without breaking them.

Re:snake oil

[TubeSteak]

"All you really need to do is take the code you want to run across multiple CPUs and put beginning and end tags on the parts you want to run in parallel"

The compiler isn't going to know if you're doing something stupid or not.
In other words: use at your own risk.

The old adage of "garbage in, garbage out" still applies.

Re:snake oil

[mastershake_phd]

"All you really need to do is take the code you want to run across multiple CPUs and put beginning and end tags on the parts you want to run in parallel" The compiler isn't going to know if you're doing something stupid or not. In other words: use at your own risk. The old adage of "garbage in, garbage out" still applies.

But how are you supposed to know exactly how something is going to run under this? Even with a good understanding of what your trying to do and (hopefully) what exactly the compiler is doing you still might get some weird results under certain situations. It might work buts its still going to take lots of trial and error, or at least a lot of verification.

Re:snake oil

[ariels]

TFA specifically mentions that you need to mark up your code with sieves:

1. A sieve is defined as a block of code
   contained within a sieve {} marker and
   any functions that are marked with sieve.
   
2. Inside a sieve, all side-effects are delayed
   until the end of the sieve.
   
3. Side effects are defined as modifications
   of data that are declared outside the
   sieve

The compiler can use this information to decide what parts of the code can safely be parallelized. Adding the "sieve" keyword can change the semantics of the code, adding it correctly is your responsibility.
Not sure I find the particular concept appealing for programming -- just trying to straighten out the claim of the article.

Re:snake oil

[maxwell demon]

But how are you supposed to know exactly how something is going to run under this?

The semantics of that construct is well-defined.

Of course from the short description it's not entirely clear to me if the compiler actually implements that semantics, or simply relies on you to honor it (e.g. is it possible to call a non-sieve function from within a sieve function or block? In that case, the compiler cannot reasonably implement the semantics). There's a precedent for the second type of semantics: restrict.

But if the semantics is enforced, you know exactly what you get.

Re:snake oil

[oohshiny]

TFA specifically mentions that you need to mark up your code with sieves:

TFA claims it's auto-parallelizing and says:

What Sieve is is a C++ compiler that will take a section of code and parallelize it for you with a minimum hassle. All you really need to do is take the code you want to run across multiple CPUs and put beginning and end tags on the parts you want to run in parallel.

If "sieves" have all the restrictions you mention, then both the claim that it's "auto-parallelizing" and the description in the article are false advertising.

The compiler can use this information to decide what parts of the code can safely be parallelized.

No, that's also misleading. You don't give the compiler information based on which it decides what is safe. Rather, you simply tell the compiler to parallelize a section using language semantics that differ radically from C++ and it blindly does it. We've had such C and C++ extensions for many years. It may be the best possible design tradeoff in C++, but it is not new and it certainly isn't "auto-parallelizing".

Prefer OpenMP

[drerwk]

I have some small amount of experience with OpenMP http://openmp.org/ , which allows one to modify C++ or Fortran code using pragmas to direct the compiler regarding parallelization of the code. And the Codeplay white paper made this sound much like it implements one of the dozen or so OpenMP patterns. I am fairly skeptical that Codeplay has any advantage over OpenMP, but the white paper lists some purported advantages. I will not copy them here and take the fun out of reading them for yourself. I will list OpenMP advantages.
1: OpenMP is supported by Sun, Intel, IBM, $MS(?) etc, and implemented in gcc 4.2.
2: OpenMP has been used successfully for about 10 years now, and is on a 2.5 release of the SPEC.
3. It is Open - the white paper for Codeplay mentions it being protected by patents. (boo hiss)
4. Did I mention that it is supported in gcc 4.2 which I built it on my Powerbook last week and it is very cool?

So maybe Codeplay is a nice system. Maybe they even have users and can offer support. But if you are looking to make your C++ code run multi-threaded with the least amount of effort I've seen ( It is still effort! ) take a look at OpenMP. In my simple tests it was pretty easy to make use of OpenMP, and I am looking forward to trying it on a rather more complicated application.

Re:Prefer OpenMP

[PhrostyMcByte]

Don't forget the other end of the development spectrum - Visual C++ 2005 has builtin OpenMP support too.

Re:Prefer OpenMP

[drerwk]

The Powerbook reference should have identified me as an acolyte of Steve! Add to that I am stuck in my day job using VS 2003 for some management reason I forget at the moment. But that aside, do you use OpenMP in VS2005, or know of people who are doing so? I just went over the full 2.5 spec so I can map out some strategy for trying OpenMP with our existing software. It is almost 1M lines, and was not designed with Multi-threading in mind. I do think there will be places I can use OpenMP, and the ability to specify exactly where and how gives me some optimism.

Re:Prefer OpenMP

[PhrostyMcByte]

I use it sometimes, for simple things. Most of the time I do my own threading though - VC2005 requires you to distribute a vcomp.dll with your app which is a bit of a turnoff.

Re:Prefer OpenMP

[jd]

Personally, I would agree with you. I have to say I am not fond of OpenMP - I grew up on Occam, and these days Occam-Pi blows anything done in C out of the water. (You can write threads which can auto-migrate over a cluster, for example. Even OpenMOSIX won't work at a finer granularity than entire processes, and most compile-time parallelism is wholly static after the initial execution.)

On the other hand, OpenMP is a far more solid, robust, established, reputable, reliable solution than Codeplay. The patent in Codeplay is also bothersome - there aren't many ways to produce an auto-parallelizing compiler and they've mostly been done. This means the patent either violates prior art (most likely), or is such "black magic" that no other compiler-writing company could expect to reproduce the results and would be buying the technology anyway. It also means they can't ship to Europe, because Europe doesn't allow software patents and has a reputation of reverse-engineering such code (think "ARC-4") or just pirating/using it anyway (think: pretty good privacy version 2, international version, which had patented code in it)

Re:Prefer OpenMP

[Anonymous Coward]

Hmm. Looks like CodePlay are a European company ( based in Edinburgh, Scotland), so not a problem there then.

Re:Prefer OpenMP

[thanasakis]

This is good stuff. Did you use any special flags to compile it? How about posting a nice walkthrough somewhere? Unfortunately xcode ships with 4.0.1 and fink with 4.1.something.

Regards,
Athanasios

Re:Prefer OpenMP

[drerwk]

Advance warning: the work is hardly complete. I've been keeping some notes so that I could post a walk through. And I have not done the step of pointing XCode at the 4.2 that I built. See: http://alphakilo.com/openmp-on-os-x-using-gcc-42/
Mostly I seem to have been lucky that 4.2 compiled as is on my Powerbook, because it did not do so on my Dual G5 which is of course where I would like to use OpenMP. I'll have to figure out what is on my PB that is not on my G5. And I have an 8 core linux box at work that I might go to instead.
One request Athanasios. If you do try this, I'd like some feedback. Thanks.

Re:Prefer OpenMP

[thanasakis]

Thanks very much, I'll try to do that in my MacBook during the week, and will let you know.

best regards

Athanasios

Re:Prefer OpenMP

[spectecjr]

Why is distributing a small DLL a turn off? Visual Studio comes with a built in installation package creator - which is really how you wanna distribute apps anyway. I mean, unless you're sending out viruses and zombies.

Re:so..

[maxume]

I'm impressed. The website you are pimping by posting dozens of inane comments to /. doesn't even have any ads on it.

Yup

[PhrostyMcByte]

For the majority of apps, OpenMP is enough. That is what this looks like - a proprietary OpenMP. It might make it easier than creating and managing your own threads but calling it "auto" parallelizing when you need to mark what to execute in parallel is a bit of a stretch.

For apps that need more, it is probably a big enough requirement that someone knowledgable is already on the coding team. Which isn't to say that a compiler/lang/lib lowering the "experience required" bar wouldn't be welcomed, just that I wish these people would work on solving some new problems instead of re-tackling old ones.

The main purpose of these extensions seems to be finding a way to restrict the noob developer enough that they won't be able to abuse threading like some apps love to do. That is a very good thing in my book! (Think Freenet, where 200-600 threads is normal.)

don't worry guys, i got you....

[teknopurge]

int id = getCurrentProcessorOrCellUniqueID();
int modulo = 3; // change this to your liking
 
// elite auto-parallelization logic. shouts to the boyz in tha h00d! Hi mom!
if((id % modulo) == 0){
// do proc or cell specific code based on mod
}else if((id % modulo)) == 1){
// you get the idea....
}

Just doing my part to save you some $$$$. (dolla, bills yall!)

How long has Sun Studio had "-xautopar"?

[Anonymous Coward]

Yep, it's in there.

And it works, too.

Ok

[Psychotria]

So, anything within the loop (using your example) cannot depend on i-1 being known? So, for the loop:

for (i = 0; i doSomething (i);

doSomething() cannot know or infer i-1. Is that right? So doSomething() really has to regard i as (almost) random. So the loop becomes:

for (i = 0; i doSomething (uniqueRand (i/RANDMAX*100);

No wonder it's so complicated and hard to debug ;-)

2 ways to faster code.

[AHuxley]

In Capitalist West no hassle for you to submit slashvertisement about faster proprietary compiler.
In Soviet Russia no hassle to get compiler source code as slashvertisement links to you.

Re:2 ways to faster code.

[Anonymous Coward]

MOD PARENT UP.

As I have recently been working in parallel computing, it was very disgusting to find such a hot topic be a slashvertisement

BOO

Been done...

[TheRealMindChild]

I have my 'Mips Pro Auto Parallellizing Option 7.2.1' cd sitting right next to my Irix 6.5 machine... and I know it's YEARS old

Re:Been done...

[adrianmonk]

I have my 'Mips Pro Auto Parallellizing Option 7.2.1' cd sitting right next to my Irix 6.5 machine... and I know it's YEARS old

Oh, are we having a contest for who can name the earliest auto-parallelizing C compiler? If so, I nominate the vc compiler on the Convex computers. The Convex C-1 was released in 1985 and I believe had a vectorizing compiler from the start, which would make sense since it had a single, big-ass vector processor (one instruction, crap loads of operands -- can't remember how many, but it was something like 64 separate values being added to another 64 separate values in one single instruction).

I personally remember watching somebody compile something with it. It was really neat to watch -- required no special pragmas or anything, just plain old regular C code, and it would produce an annotated copy of your file telling you which lines were fully vectorized, partly vectorized, etc. You could, of course, tweak the code to make it easier for the compiler to vectorize it, but even when you did, it was still plain old C code.

Re:Been done...

[Temkin]

I have my 'Mips Pro Auto Parallellizing Option 7.2.1' cd sitting right next to my Irix 6.5 machine... and I know it's YEARS old

I was thinking the same thing. I remember playing with "-xautopar" option in Sun's compiler way back in 1996. I just checked and it's still there. The problem was always making sure loops didn't have dependancies on the loop counter, and only had one exit.

Sun gives away the whole Sun Studio compiler suite now days, complete with OpenMP and all the profiling tools. They have a Linux port too.

I smell astroturf...

Re:Been done...

[andrewzx1]

I coded on a Convex and I used this option. It worked for basic loops but I liked coding in Convex assembly. It was a lot like PDP assembly.

Not a big deal

[the100rabh]

For what I have seen is that this system just parallelizes only the part of the code in sieve instead of the whole code. How is this better than others. Please can someone enlighten me on that.

Re:Not a big deal

[Anonymous Coward]

If it's like other compilers (Sun, IBM) that do this and which I've worked with, it likely looks for things like loops, larger control structures, other shit.

Think of automatic parallization like C : it gets close to machine level code but if you want the real deal you write important bits in assembler.

Re:Not a big deal

[ioshhdflwuegfh]

For what I have seen is that this system just parallelizes only the part of the code in sieve instead of the whole code. How is this better than others. Please can someone enlighten me on that. If this part of the code happens to be the one where most of your CPU time is spent,...

Re:Not a big deal

[the100rabh]

Right dude but how is seive better than finding checking for the loops and large structures by other compilers

Re:Not a big deal

[the100rabh]

thats what other compilers do by themselves right...

Re:Not a big deal

[ioshhdflwuegfh]

thats what other compilers do by themselves right... Most compilers can't even detect that, let alone parallelize it, thus profilers and programmers and all the jazz with OpenMP, MPI, Codeplay, HPF, Ocam...

Re:Hey! Let's reinvent OpenMP!

[grub]

Our SGI compilers at work come with an -apo (automatic parallization optimization) command line option. That one option cost us a pretty penny. It's nice to see other people getting in on the action.

Snippet from the manpage, highlighting is mine:

-apo, -apokeep, -apolist
For -n32 and -64, it invokes the Auto-Parallelizing Option
(APO), which automatically converts sequential code into
parallel code by inserting parallel directives where it is
safe and beneficial to do so. Specifying -apo also sets the
-mp option. Both -apokeep and -apolist produce a listing
file, file.list. Specifying -apokeep retains file.anl and
file.m, which can be used by the parallel analyzer, ProDev
ProMP (see the EXAMPLES section). When the -IPA option is
specified with -apokeep, the default settings for IPA
suboptions are used with the exception of -IPA:inline, which
is set to OFF.

APO is invoked only if you are licensed for it. For licensing
information, see your sales representative.

For more information on APO, its directives, and command-line
options, see MIPSpro C and C++ Pragmas.

When specifying the -o32 option on the cc command line, -apo
invokes the IRIS Power C analyzer (PCA). See the -pca option
description.

Could this possibly be for real?

[__aailob1448]

I'm no parallelization expert but it seems to me that a compiler that reliably gives you a scaling factor above 80% would be a huge deal. Is it really possible to achieve those kind of results across the board? Or is this a bunch of bull.

Re:Could this possibly be for real?

[init100]

Nothing new here, move along.

Jokes aside, this is bull. It requires the coder to mark sections that he wants to run in parallel, making the "automatic" part a bit of a stretch. And then, there already is a system that does this, and has done it for 10 years. It's called OpenMP, and features wide industry support in compilers such as the upcoming gcc 4.2, MS Visual Studio .NET 2005, the Intel compiler suite and compilers from traditional SMP vendors such as IBM and SGI.

SmartVariables is a good alternative to MPI / PVM

[Anonymous Coward]

Let's see if I can teach any old dogs some new trix.

Here is a quote from the SmartVariables white-paper:

"The GPL open-source SmartVariables technology works well as a replacement for both MPI and PVM based systems, simplifying such applications. Systems built with SmartVariables don't need to worry about explicit message passing. New tasks can be invoked by using Web-Service modules. Programs always work directly with named-data, in parallel. Tasks are easily sub-divided and farmed out to additional web-services, as needed - without worry of breaking the natural parallelism. If two or more tasks ever access data of the same name and location, then that data is automatically shared between them - without need for additional parallel programming constructs. Instead of using configuration files with lists of available machines, a shared SmartVariables List object (with a commonly accepted name, like "machines@localhost") could easily hold the available host names, which can then be used for dynamic task allocation. The end-result is that SmartVariables-based parallel systems need only reference and work with distributed data, and don't need to manage it. Automatic sharing means there is no need to worry about explicit connection, infrastructure, or message-passing code. Instead, applications only need agree on the names used for their data. Names and object locations are easily managed by using a SmartVariables based Directory-Service as an additional layer of object indirection."

The rest of this paper is here: http://www.smartvariables.com/doc/DistributedProgr amming.pdf

A single code-base works on Apple / Linux / Windows.
Complete code and docs at http://smartvariables.com/

Sounds like multi-threading AND NOT Parallelizing

[mrnick]

I read the article, the information at the company's web site and even white papers written on the compiler. And although I did see one reference to "Multiple computers across a network (e.g. a "grid")" there was no other mention of it.

When I think of Parallelizing software, after getting over my humors mind thinking of a virus that paralyzes users, what comes to mind is clustering. When I think of clustering the train of thought directs me to Beowulf and MPI or it's predecessor PVM. Though I can find no information that supports the concept of clustering in any manner.

Again I did see a reference to: "Multiple computers across a network (e.g. a "grid")" but according to Wikipedia grid computing is defined "A grid uses the resources of many separate computers connected by a network (usually the Internet) to solve large-scale computation problems. Most use idle time on many thousands of computers throughout the world."

Well, that sounds like the distributed SETI project and the like, which would seem even more ambitious than a compiler that would help write MPI code for Beowulf clusters.

From all the examples this looks like a god compiler for writing code that will run more efficiently on multi-core and multi-processor systems but would not help you in writing parallel code for clustering.

Though, this brings up a concept that many people forget. Even people that I would consider to be rather intelligent on the subject of clustering often forget this. And that is that if you have an 8 computer cluster with each node running on a system with dual-core Intel CPU installed that if you write parallel code for it using MPI you are benefiting from 8 cores in parallel. Many people that write parallel code forget about multi-threading. To benefit from all 16 cores in a cluster I just described the code would have to be written multi-threaded and parallel. One of the main professors involved in a clustering project at my university stated to me that in their test environment they were using 8 dell systems with dual-core Intel CPU so in total they had the power of 16 cores. Since he has his Ph. D. and all I didn't feel the need to correct him and explain that unless his code was both parallel and multi-threaded he was only getting the benefit of 8 cores. I knew he was not multi-threading because they were not even writing the code in MPI rather they were using Python and batching processes to the cluster. From my knowledge Python cannot write multi-threaded applications. Even if it can I know they were not (from looking at their code).

Sometimes it's the simplest things that confuse the brightest of us....

Nick Powers

neither useless nor compelling

[kokorozashi]

The trick to taking advantage of future processors like the ones architecture futurists such as David Patterson envisions when he talks about "manycore" chips is to make parallel programming easy. Making the programmer puzzle out the parallelism for himself isn't the way to do that. We already know pre-emptive threading is too difficult for most; putting pervasively parallel programming (PPP) in human hands would be even worse. A proper approach to PPP involves inventing a new language, not adding warts to C++, which already has more than enough of its own, thank you very much.

are you sure your prof is wrong?

[Chirs]

Assuming their cluster management system knows that each node is dual core, can you explain why they couldn't run two processes on each node?

Sad...

[jd]

I mean, it was only running on two threads AND showed clear signs of excess barrier operations at the end of every character. From here on out, I expect first parallel posts to run over at least four threads and not be sequentially-coherent. The world is moving towards async! Don't let first posts suffer with past limitations!

Where's the torrent?

[timecop]

I'd like to evaluate this new technology.

C++... great...

[Anonymous Coward]

Just what we need, another C++ crutch.

Can't we just let that wretched language die already?

Re:C++... great...

[Haeleth]

Can't we just let that wretched language die already?

Not until you find a better alternative that provides the same performance.

Yes, there are still plenty of performance-critical applications. I sure wouldn't want to run an OS written in Python, or a movie compressor written in Ruby. Heck, many such things are still written in C; you should be damn grateful even C++ gets a look-in...

Re:C++... great...

[Anonymous Coward]

Why did you mention interpreted languages as being replacements for compiled ones?

Many algorithms can be implemented in functional languages and actually run significantly faster than C/C++, and as a plus, functional languages, by nature, are ridiculously easy to parallelize without the mess of the threading models we use for C/C++ today.

Re:C++... great...

[Anonymous Coward]

Um, I'd not sure I'd trust really timing-critical applications in 'C'. There's very good reasons why the language permits embedded assembler code.

AC

Re:C++... great...

[masterkumon]

concur, C won't be left. Java is still far away from C in low level programming and perfomance. perils of javaschool

WCF - Dotnet 3.0

[MickDownUnder]

This is a feature of WCF - Windows Communication Foundation in .NET 3.0 (part of Win V). WCF is designed for next gen CPUs with large numbers of cores. It spawns worker threads for you as needed and sychronises these calls for you automatically. You have the option of manually creating and sychronising threads, but out of the box it does it all for you behind the scenes. Just imagine coding for a machine with 1024 cores! It's obvious that writing software as we've done in the past where you manually spawn threads and sychronise them is never going to effectively use such hardware. You are obviously going to have a framework like WCF (or this compiler) that takes advantage of this for you. Maybe the wow has started now after all hmm? ;) I love being flame bait ... especially when I'm right.

Re:WCF - Dotnet 3.0

[ioshhdflwuegfh]

This is a feature of WCF - Windows Communication Foundation in .NET 3.0 (part of Win V). WCF is designed for next gen CPUs with large numbers of cores. Which is to say you can't use it now, but in the future.

Just imagine coding for a machine with 1024 cores! wow!

Maybe the wow has started now after all hmm? Or maybe wow has alredy started in the future? In your fertile imagination?

Re:WCF - Dotnet 3.0

[init100]

This is a feature of WCF - Windows Communication Foundation in .NET 3.0 (part of Win V). WCF is designed for next gen CPUs with large numbers of cores. It spawns worker threads for you as needed and sychronises these calls for you automatically. You have the option of manually creating and sychronising threads, but out of the box it does it all for you behind the scenes.

So WCF takes care of parallelizing your compute-intensive tasks for you? Sorry, but I don't believe you. It might spawn threads for communication-related tasks, but those aren't really compute-intensive anyway.

Re:WCF - Dotnet 3.0

[MickDownUnder]

No you can use it now. It was released in November. I'm implementing a solution with it as we speak and yes it is eliminating the code I once would have written to spawn worker threads and sychronise them... So I think youre the one with the fertile imagination, which seems to be focused on denial.

Re:WCF - Dotnet 3.0

[ioshhdflwuegfh]

No you can use it now. It was released in November. I'm implementing a solution with it as we speak and yes it is eliminating the code I once would have written to spawn worker threads and sychronise them... So I think youre the one with the fertile imagination, which seems to be focused on denial. Sorry for the slow reply, I've been busy converting my OpenMP code into .NET 3 and, oh boy, you're right, wow, it sure does run on 1024 cores like a charm... oops, my provider of the connection with future has just denied me service... well, nevermind, future is in the future, who can deny me that? Maybe I'll just stick with Linux for a while...

Re:Sounds like multi-threading AND NOT Parallelizi

[Anonymous Coward]

sorry to do the anonymous coward thing, but i'm too lazy to make an account. If he has several processes running at once on each node, the OS schedules them on different cpu's, using the dual core. That's what an OS does.

mod parent up

[blackcoot]

i was just going to ask "who cares, openmp does this already" now i know that i don't care. it's not nearly as interesting as the work done out of nasa greenbelt on a project called ace (which actually is a genuinely automatic parallel compiler that targets clusters rather than cpus --- really kickass concept). my very limited experience with openmp is that i prefer the mpi approach. that said, i don't think mpi or openmp are really the right answer -- it takes a language that was designed from the ground up to do parallel execution "right". in this case, i think things like HP fortran actually hurt rather than help because they're very familiar which ends up being a bad thing because they're most like something that doesn't solve the problem.

Wow - Deterministic Concurrency

[Anonymous Coward]

Deterministic concurrency is a great aid for debugging - no more race conditions, no more heisenbugs, no more visibly different program behaviour on 1 core, 2-core, hyper-threading, Quad Core, 8 Core, and whatever the Intel and AMD road maps bring out in the future. Looks good for the sanity of all those programmers who have ever had problems manifest only on one machine after testing!

This Sieve programming seems also to make it easier to target the PS3, which has gotten a bad rap as being notoriously difficult to program well. Who wants to break programs into tiny chunks that DMA work in and results out, instead of letting some automated system translate a higher level program into that low level programming model? Its about time that getting decent returns on parallelisation was easy. Its also time for the low level OS threading APIs (Posix, Win32) to be forgotten and buried. No more locking, data races, dead locks, and general programming complexity in order to get any speed up out of multi-core systems.

I also like the idea of buying a Physics processor unit (PPU) and having an automatic speed boost in my programs.

Re:SmartVariables is a good alternative to MPI / P

[Anonymous Coward]

Perhaps some programmers would like their code to run in parellel without a GPL viral license infection?

RapidMind

[khaledh]

This looks similar to RapidMind, which is a software development platform that, among other things, "Enables applications to run in a data-parallel way." (I'm not affiliated with them.)

Re:RapidMind

[Nappa48]

Finally someone mentions Rapidmind!
I guess that its just not as popular right now, shame really because its pretty easy to get into. Still learning though since i AM new to both C and Rapidmind! College gets in the way alot...meh

single process uses 1 core unless multi-threaded

[mrnick]

The operating system on a multiple-core machine can split up the processes but one process can only run on one core unless it has been written in a multi-threaded fashion.

In parallel processing general each machine is running one part of a program, thus one program, and unless that program is multi-threaded as well as parallel then it can only use one core per node on a cluster.

Though, someone who writes multi-threaded parallel applications should be held in high esteem! I don't know any such coders.

Nick Powers

Is this better than OpenMP?

[Anonymous Coward]

So, I fail to see what's new about this. As has been mentioned before, OpenMP auto-parallelizes for SMP systems quite well, as long as you know what you're doing. Like anything done in parallel, if you don't figure out where your data and algorithm dependencies are you'll hose your program. If Sieve does some sort of dependency analysis, that would be interesting, but I doubt it would catch all problems. In fact, I imagine it's provably impossible to auto-parallelize in the general case -- it will likely be proven equivalent to the halting problem eventually.

What would be new is when someone substantially improves on MPI. Auto-parallelizing a FOR loop is amusing, doing the same for a complex algorithm moving data around in a cluster, well, that's a different sort of difficult.

Anyway, no matter how many libraries and tools come out to ease the pain, parallel programming is frigging hard. In fact, the more automagic the compiler, the harder it will be to debug when the inevitable race condition sneaks through. Combine this with lowering the bar for parallel programming and letting more idiots in and we can look forward to some truly horrific code. If you make it so any idiot can code, any idiot will!

Why C++

[impeachgod]

Why use C++? Aren't there languages that support parallelizing better, like the functional ones? Or perhaps develop your own language tuned to parallelizing.

Re:Why C++

[Anonymous Coward]

Why use C++? Aren't there languages that support parallelizing better, like the functional ones? Or perhaps develop your own language tuned to parallelizing.

Because C++ has power, because C++ is alive, because C++ has speed, and... more importantly...

Because there are a lot of today's applications built on C++, working applications that work today, and won't need a new, unstable version for years because it was re-written from scratch in a new language.

Every three or five years, we've got a new very cool framework that will be obsolete three or five years after. No one will refactor from scratch an existing application once every three years, just to have this new shining concept, if a viable and simple enough alternative is offered in the existing application language.

What C++ applications need is not a new language, because today C++ application will never adopt it (who will pay for the months/years developpement costs just to switch language?). What C++ applications need is evolution of the language.

Think about how C++ evolved from C, and remains compatible, which eased a lot slow and constant evolution of a living application from C to C++. The next C++ (C++++, or, perhaps ++C?) will need to be compatible enough with C++ and C to enable C++ and C code mixing within one's library or executable.

Not that we need a ++C. C++ is alive enough today. Ok, looking at boost or templates, some would call is cancer metastasis. But is this truly warts, or is this the fear of new concepts introduced in an otherwise familiar language? Perhaps C++ don't need a new language. Perhaps what C++ needs is C++ language evolution and C++ developpers' cognitive evolution.

Re:single process uses 1 core unless multi-threade

[julesh]

The operating system on a multiple-core machine can split up the processes but one process can only run on one core unless it has been written in a multi-threaded fashion.

In parallel processing general each machine is running one part of a program, thus one program, and unless that program is multi-threaded as well as parallel then it can only use one core per node on a cluster.

Though, someone who writes multi-threaded parallel applications should be held in high esteem! I don't know any such coders.

Have you considered that if you run two copies of the process on each node, it will use both cores?

Re:single process uses 1 core unless multi-threade

[Mad Merlin]

I think the parent's point was that the cluster management system could simply batch out two individual (single threaded) processes to each node (for a total of 16 processes over 8 nodes), rather than just a single process per node. This may or may not work, depending on how the processes communicate over the network, but it is certainly a substantially easier task than writing a multi-threaded distributed program in most any case.

OpenMP can support clusters

[mi]

Intel's compiler (icc), available for Linux, Windows, and FreeBSD extends OpenMP to clusters.

You can build your OpenMP code and it will run on clusters automatically. Intel's additional pragmas allow you to control, which things you want parallelized over multiple machines vs. multiple CPUs (the former being fairly expensive to setup and keep in sync).

I've also seen messages on gcc's mailing list, that talk about extending gcc's OpenMP implementation (moved from GOMP to mainstream in gcc-4.2) to clusters the same way.

Nothing in OpenMP prevents a particular implementation from offering multi-machine parallelization. Intel's is just the first compiler to get there...

The beauty of it all is that OpenMP is just compiler pragmas — you can always build the same code with them off (or with a non-supporting compiler), and it will still run serially.

Re:OpenMP can support clusters

[init100]

You can build your OpenMP code and it will run on clusters automatically.

Won't that require some runtime support, like mpirun in MPI (that takes care of rsh/ssh-ing to each node and starting the processes)?

Re:OpenMP can support clusters

[mi]

Won't that require some runtime support, like mpirun in MPI (that takes care of rsh/ssh-ing to each node and starting the processes)?

Well, yes, of course. You also need the actual hardware too :-)

This is beyond the scope of the discussion, really — all clusters require a fair amount of work to setup and maintain. But we are talking about coding for them here...

Re:OpenMP can support clusters

[blackcoot]

the beauty of ace is that it didn't need any of that stuff. it just worked (tm).

Re:OpenMP can support clusters

[init100]

You also need the actual hardware too

At work, I have (I work at a supercomputing center).

Nothing new

[UtilityFog]

Cilk has been around for years, indeed it won the ICFP 1998 programming contest.

Auto-parallelizing?

[Anonymous Coward]

How can be automatic a compiler that needs you to mark the parallel sections? It just simplify the use of threads, but you still have to find parallelism and write your code parallel. It is like OpenMP...

Re:single process uses 1 core unless multi-threade

[Celandine]

And the parent was correct -- the original poster is talking nonsense. I'm running MPI code on a cluster consisting of some single-core machines, some 2-CPU boxes, and some 2-CPU 2-core systems. All the cores are in use.

Minimum hassle?

[thewiz]

'What Sieve is is a C++ compiler that will take a section of code and parallelize it for you with a minimum hassle."

What does the compiler do, taunt you with harsh language while it compiles your code?

Re:Minimum hassle?

[Anonymous Coward]

Sometimes those warnings can sound like personal attacks. :(

batching code to a cluster is just silly

[mrnick]

Well then you would have non multi-threaded code and non parallel code as well. There are only 2 ways to have jobs run on a cluster.

1) Write the code using MPI or it's predecessor PVM.
2) Have non parallel code that has separate programs that each handle a part of the data and batch it to nodes on the cluster.

Method 2 is either done as an initial step to help determine how to split up your processing so you could use that information to write a MPI or PVM version or by people that don't know how to write parallel code (MPI or PVM) but still want to be able to use some of the power their cluster provides.

If you chose method 2 and never intended to modify your code to be parallel then I wouldn't go bragging about your great cluster to anyone that knows much about clusters because once they figured out what you were doing they would be shocked at your ignorance and consider it very humorous that you went to so much trouble to build a cluster but never learned how to use it properly.

So, yes you could use method 2 and batch each node 2 batches and in most cases the operating system would run the second batch it received on a unique core compared to it's first batch though you could not guarantee that since the operating system might think it's better to have both on the same CPU depending on what other processes were running on the system at that given time.

But, what if you had nodes in your cluster that have varying numbers of cores / CPUs on each system? This is quite common. So, you could have a cluster that had 20 single core machines 40 dual-core machines and 10 8-core machines. So, if you could use all of the core on all the machines you would have the potential of 180 cores worth of computing power.

To take advantage of this using batching you would have to have 180 separate programs, each that handled the calculation of 1 / 180 th of the complete solution and have written your batch script so that it knows how to allocate those batches based upon the number of cores a machines has. And again, there would be no guarantee that there would be no instances where a node would have a single core running more than 1 batch, except for the single core machines. This uncertainty would increase as the number of cores on a node increased. for example if you sent 8 batches to a node with 8 cores it would be very unlikely that each batch would be running on a unique core, meaning you could assume that at least 1 core was running multiple batches and at least 1 core was running no batches.

What is even more common is that you have a cluster of varying numbers of nodes with unknown numbers of cores / CPU in each node. In this scenario it would be impossible to batch your code in a manner that would take advantage of all the cores available, not to mention that it would also be impossible to make sure that every node was even participating. In this scenario the only way you could guarantee that your code took advantage of all the nodes and all the cores / CPU of each node would be to write your code in parallel mode (via MPI or PVM) and that the code was also written in a multi-threaded fashion.

It may be more difficult to write parallel code than batching non parallel code, for someone who doesn't know how to write MPI or PVM code. And if any of your nodes contained multiple core / CPU it would be even more difficult to write a parallel version of the code that could take advantage of the additional cores on the nodes that had them. But, if you really wanted to take maximum advantage of all the available resources in your cluster then you would have to write parallel code that is multi-threaded.

It's not as difficult as it sounds since the segments of code that could be parallelized would also be the same segments that would lend themselves to be multi-threaded. Both require segments of code where all iterations do not have dependences on previous or subsequent iterations of the same code segment. Some code can be written in parallel and some must be wr

Re:batching code to a cluster is just silly

[Mr. Hankey]

I do work in a HPC environment, and we have a number of clusters available which are utilized through batch processing as well as software interfaces such as OpenMPI.

In defense of the batch system, assuming we definine parallel as "at the same time", and not "inter-node communication", one should be fine with the multiple processes approach. There are a number of commercial and open source schedulers which will do the work for you, including node weighting for systems with different numbers of processors and/or processor speeds. As long as the nodes are not doing anything else, the OS schedulers do the right thing.

Given that it's simpler to write, debug and verify single threaded code, pushing multiple instances of an application to a cluster's nodes can reduce development time. Not requiring direct communication between the nodes also allows execution the same application on multiple clusters as seen in grids, indeed even multiple architectures. It also lowers network overhead, unless you introduce InfiniBand or Myranet interfaces (which are costly.)

Re:SmartVariables is a good alternative to MPI / P

[init100]

It may or may not be easier to program, but will it perform well enough? Does it support high-speed low-latency interconnects like Myrinet or Infiniband? Will it perform well enough to make up for the high price of such interconnects? Gigabit Ethernet performance is not enough on such systems, as latency is a major factor, and the latency of Ethernet is typically high compared to HPC interconnects.

Re:single process uses 1 core unless multi-threade

[init100]

This may or may not work, depending on how the processes communicate over the network, but it is certainly a substantially easier task than writing a multi-threaded distributed program in most any case.

Actually, if the message passing implementation is done right, communication between processes on the same node is done though shared memory, and not network communication. Actually mixing threading and message passing in the application code just means unnecessary complexity in this case.

Re:Sounds like multi-threading AND NOT Parallelizi

[init100]

Sounds like multi-threading AND NOT Parallelizing

Both multi-threading and message passing systems are parallel systems, they are just different subsets of the parallel computing paradigm. You cannot really claim with any authority that multithreading isn't parallel computing, and that only message passing is.

Multithreading is used on a shared memory multiprocessor, and message passing is used on distributed memory multiprocessors. They are just two different ways of implementing parallel code, and none of them is more parallel than the other.

Well, that sounds like the distributed SETI project and the like, which would seem even more ambitious than a compiler that would help write MPI code for Beowulf clusters.

Actually, the parallelization is much more complex in the cluster case than in the distributed computing (e.g. SETI@Home) case. Distributed systems are often processing data packages that are inherently independent of one another, and require no communication between the compute nodes at all. In this case, parallelization just amounts to splitting the work into pieces and handing out to the worker nodes, as well as collecting and aggregating the results.

Clusters, on the other hand, are primarily used for tasks that need (often intense) cooperation between the compute nodes to solve, such as solving large systems of linear equations. Such parallelization is much harder, and I won't hold my breath waiting for such a compiler to appear.

Re:Sounds like multi-threading AND NOT Parallelizi

[I Like Pudding]

Mod parent down

Anything when more than a single thread or process is executing simultaneously is parallel. Anything running on multiple computers at the same time can also be called parallel, but is more precisely (and commonly) referred to as clustered or distributed computing. These are the commonly agreed upon meanings.

Since he has his Ph. D. and all I didn't feel the need to correct him and explain that unless his code was both parallel and multi-threaded he was only getting the benefit of 8 cores.

Or you could (very obviously) start two instances per node.

Gay

[JavaPunk]

You know how I know your gay? You use codeplay.

How about an auto-commenting compiler

[heroine]

How about an auto-commenting compiler. All you have to do is put tags in it where you want comments and it automatically comments them.

Seriously, Sieve sounds so trivial and meaningless, it's the ultimate silicon valley startup. How about something more valuable like an auto-vectorizing compiler that really works.

Modern CPU and existing compilers

[Wolfier]

Already implement "auto-parallelization" of sorts. It's called "out of order" execution - code specificially written with this in mind can perform quite a bit faster - all you have to do is to create separate independent sections of code.

It's time for the C and C++ to include || proc

[SETIGuy]

Even if it's something as simple as a parallel for loop and synchronized variables it would help immensely.

sync int total=0;
par (i=0;i<100;i++) {
int j=0; // Thread local, of course
static int k; // Implied sync.
DoSomething(i,&j);
k++;
total+=j;
} // implied wait for thread completion

It'll even compile on old compilers with a "#define par for" and "#define sync".

It's long past time for this.

For what it's worth

[Almahtar]

C++ does have such statements: http://cppreference.com/cppalgorithm/index.html. Check out "for_each" for an example.

Re:For what it's worth

[644bd346996]

Yes, the STL does have for_each and transform. But they use several iterators and a functor. This means that they are a) ugly and b) not parallel.

MOD PARNET UP - NOT TROLL!

[Anonymous Coward]

It's a quote from "The 40 Year Old Virgin"!

David: You know how I know you're gay?
Cal: How?
David: You like Coldplay.

Re:SmartVariables is a good alternative to MPI / P

[convolvatron]

new? 10 inches from my head i have a 2 volume collection edited by
shapiro called 'concurrent prolog' published in 1986 which uses the concept of named
streams to communicate between concurrent processes, which to a
large extent are treated as variables in the language. i could
find an earlier reference, but it would be more work than turning 60 degrees.

try harder

Word of advice.

[jd]

Never, ever tell a Scotsman that they're a European. Doubly so if they're into their fourth single-malt and second haggis of the morning.

Re:Why C++ (Check out Sisal)

[Anonymous Coward]

There is a significant history of languages that are designed from the ground up to support multiple kinds of parallelism. Here is one example

http://sisal.sourceforge.net/

Parallelism is hard. Trying to slap a layer of automatic parallelism on a existing non-parallel language is unlikely to achieve a lot. It may help in some specific instances, but to get really good speedup you need to provide extra information. This is the OpenMP model. A language like Sisal provides the compiler even more information about parallel operation, and can intrinsically get better results.

"for each FOO in BAR do STUFF;" [Re:Reentrant?]

[codergeek42]

Actually, C++'s STL containers do have such a utility: std::for_each (part of the standard header.

Re:"for each FOO in BAR do STUFF;" [Re:Reentrant?]

[codergeek42]

Sorry, that ending part should have been "(part of the <algorithm> standard header)."

Damn HTML stuffs...

Efficiency vs Ease of programming

[mrnick]

If you ever have free time and the computer time... write a simple algorithm that benefits from parallel processing and write one using MPI and the other by breaking up a program into batchable units and see which one is more efficient. I haven't tested this but my money would be on MPI. This is one of those cases where programmers can't argue about it not worth optimizing your code since running in a cluster is so that you can get more performance so any optimization that you can incorporate into your code the better.

It may indeed be easier to write the code but if it efficiency is effecting performance on your cluster that has a problem take longer than it would have taken you to write the more efficient version. Though only testing will let you know.

Nick Powers

Re:Efficiency vs Ease of programming

[Mr. Hankey]

It really depends on the problem; some do benefit from MPI, but often these are utilizing algorithms where interprocess communication can be used to share results or prune the input set. For problems where you just need to crunch a large set of data in discrete processes, results are independent, and pruning cannot happen, batch scheduling can be at least as efficient when done properly.

Yes, that does sound like a valid use of batching

[mrnick]

I can see that. I suppose I was thinking of the cases where intercommunications between the nodes is important. If you don't need intercommunication between nodes then batching would most likely be just as efficient.

Nick Powers

WTF?

[woolio]

ow about an auto-commenting compiler. All you have to do is put tags in it where you want comments and it automatically comments them.

Do you really know the difference between a compiler and an development environment?

What "comments" is a compiler going to derive from your code? Something like "EAX will contain the result of the last add." is NOT going to be a useful comment in most situations. What do you expect the *compiler* to be able to tell you about *your* code?

And I believe it is widely held that comments should often describe higher-level things (such as what a function does, when it can be called, requirements on its inputs/outputs) -- things other than just what the following code literally does...

In C/C++, things like this do not help anyone:

++i; // increment i by one.

The idea of a compiler modifying the source code is a bit stupid and dangerous.

And in lowlevel implementation, vectorized processing, parallel processing, and multi-threaded processing are all entirely different. The granularity they operate at dictates how efficiently they can parallelize things.

One could automatically parallelize a simple for loop on a Beowulf cluster of 10000 nodes each with the latest processors... It just make take a few million times longer to run than it would on a single 80386 PC from the 1990s...