Parallella Community

So on another thread the claim of parallel programming being difficult was labelled 'hogswash', which I just couldn't let pass unchallenged. Given that it was off-topic there i've started this thread to discuss it.

Despite a couple of decades of experience and a particular personal interest in this area I still find that parallel programming is considerably more difficult than serial programming. There are certainly cases that aren't much more work if you're familiar with the mechanics like I am, but you can't ever say it's no more work. And at the other end of the spectrum it's a completely different kittle of fish entirely - it can be way more work.

Some languages (erlang?) or language features (like java's lambda) give you certain features of multi-programming essentially for free but if you don't know them already or they aren't available in your language then that doesn't help you a lot. Good abstractions help (or even make the problem tractable in the first place) but they are still things one needs to learn above basic serial programming.

I know one of the stated goals of this project is to make highly parallel programming accessible to everyone but I don't see how it will make anything easier on it's own. Other than by the experience it allows and by the exposure to the low-level details which are usually hidden in todays programming languages, and perhaps the ability to experiment freely outside a proprietary or academic lab or vendor-supplied sdk (which are all very good things though, imo).

I'm of the opinion that the best way to implement scalable multi-processing is just to avoid it in the first place. This doesn't mean not using it but by using abstractions which make it effectively dissapear. e.g. async message passing work-queues/co-routines/job dispatch pools, independent processing kernels, etc. i.e. where there is a clear dilineation between ownership of data and no need for additional synchronisation. Sometimes it can't be hidden but it can still be kept isolated such as using LDS across an opencl workgroup. And mutex's and the like should only be used to implement higher-level abstractions. Any other approach quickly creates so much complexity one cannot test for or guarantee correct operation and you spend too much time debugging the scaffolding and not the code which does the actual work.

I am not overly experienced with all that, but thought I give my 2 cents. My only (small) experience with parallel programming was with MPI-programs where you distribute your data between the cores you got assigned and then every core computes with his data set and from time to time you need to exchange results with neighbors or broadcast results.
I thought it was much more demanding to program than sequential programs. This was mainly because you wrote one line of code and had to keep in mind that the variables may have different values and dimensions for every process at the same time and had to try to avoid data exchange as it would take quite a lot of time.

In the other thread also multi-threading was mentioned. This is IMHO easier to follow because you may spawn multiple threads, but each thread has usually it's own sequential program it runs. Although this generally adds complexity and can lead to odd problems I find it easier to what I wrote above. That's why I like the parallella idea you have a "normal" dual core processor you have the cluster-like epiphany and even an FPGA. So there is enough to test and learn for me without the need to put a server rack or similar in my basement (problem is, I don't have a basement).

My 2 cents..parallel programming can be very easy or very hard depending on the the application and the platform. Here are a couple of examples from the past.


Case #1: Random Verilog Simulations of chip
-Each machine runs a unique single threaded program (generated from a random seed) on a Verilog model of the chip and compares the output of a golden reference simulator. If the two results match,the test passes.
-using "bsub" or similar load sharing program to schedule a job across a set of N machines connected by a reasonably fast network.
-All machines share the same file system
-"zero" time spent on parallel programming, just had to do "man".
Conclusion: Parallel programming is trivial. Program is severely compute bound and there is no inter processor communication.


Case#2: A parallel 2D FFT implemenation
-Speed up a 2D FFT by creating a parallel version that runs on 16 cores
-Bare metal ANSI-C programming with limited library support for barriers and mutexes.
-Lots of time spent at the algorithm level creating a parallel FFT that would map to the Epiphany architecture("thesis")
-LOG(N) algorithm needing careful orchestration to not be I/O bound
-Lots of time spent on race debugging!
-Example code by Yaniv here: https://github.com/adapteva/epiphany-ex ... ster/fft2d
Conclusion: Difficult, but not impossible.

Most programs probably falls somewhere in between these two extremes.

Our long term goal is to work on improving the quality of life for the select few who need to work at the bare metal layer (hopefully these will be folks working exclusively on programming infrastructure) and to create a framework by which the rest of us will have a moderately easy time.

Based on the history of single threaded system, I suspect we will eventually settle on a a combination of high performance libraries, languages, and run time systems to get the job done.

Andreas

I'm very much a neophyte here in this Land Of The Parallel, and I've been thinking and reading alot about this stuff. Currently I've been contemplating all sorts of problem spaces and trying to find the parallelism within. Also by seeking that you also ( even if only implicitly ) discover serial aspects too. I think you have to start there in the problem domain ( as will most/all programming ) before moving down to detail. Otherwise you might miss something really important.

You can find concurrency and related issues in all sorts of places. Try your local Safeway, as I did by hanging around a bit after my purchases, and watching. With the trolley for instance, all four wheels have to work to get it around the place properly, so that's a dependency right there. You browse around the supermarket and plonk you choice of wares in the trolley, along with everyone else wandering about in a fashion quite unrelated ( generally ) to each other. Different shopping lists you see. But there might be some resource contention, which could be that Last Packet Of Pringles but might also be simply space in the aisle to argue over and/or I'm in a bloody hurry so get out of the way. Matter, space and time are the currencies there.

Then you have to pay, and in doing so you enter The Checkout District. Ah, what a microcosm of behaviours on display ( casus belli anyone? ). There you have an array of queues, each working simultaneously to transact money for goods, and the choice becomes which one to line up in? So there's load balancing in action with all sorts of concerns to reach a conclusion. This queue looks long but the trolleys are mainly lightly loaded, though another queue has only three people but each has two full trolleys. Which is my best choice? Exactly what am I optimising anyway ? So there's a type of product/hypothesis being performed : [trolleys times (load per trolley)] is proportional to [time to process]. Why don't they open another register? That would get things moving. And what about the self-serve registers? Here's another factor : you have to now judge how good the 'general member of the public' is at self service. For that matter what assumptions do you make about the 'trained' staff in the regular queues? Don't they put on the trainees on Sundays?

Thus you get to 'your turn' for the scanning. Now it's a remarkable fact that the checkout person, and yourself, doesn't have to worry about the order of presentation of items to the scanner. Not on cost grounds anyway. The total will remain the same, so that's commutative addition in action. Also I could have split my goods up into two trolleys, and get my son to go through another checkout ( or in the same queue after me for that matter ) and here we have associativity of grouping of the items. Same total again ( well, it should be ). But there is a 'hidden' dependency here : you have to form each subtotal from separate transactions completely first, and then you can add them to get a grand total.

And then when you're done, there's the car park to conquer. Groan! Let's not go there .....

So two points I make :

(a) Go to the problem space first.

(b) Parallelism isn't as esoteric as it sounds. It applies to everyday stuff.

[ Exercise : have a second look/thought at your local petrol outlet next time you fill up. What comparisons/contrasts can you make with respect to the supermarket? ]

Cheers, Mike.

( edit ) DownUnda at least we have rounding to the nearest five cents on totals. That could depend on grouping couldn't it? Likewise real-world floating point operations ( ie. limited length representation ) are not truly associative particularly if you have 'bigs' and 'smalls' in the mix.

( edit ) Safeway is optimising too, and they'd have concurrency thoughts within say, their payroll. So are all employees equal in utility to the company? They have to spend money ( eg. call in staff to run another register ) which deducts from their profit, to service the customer's transactions. This is real, because they don't get paid if I don't agree to transact. Though that offsets against my need for the goods. After all, I can walk away from a trolley ( not yet paid for ) if I'm not happy from waiting ( or price, or quality, or sizes, or .... ) and never go back there again. But that means I have to go somewhere else .... concurrency in where you shop and for what goods anyone ? Ah, patterns and patterns .... I'll stop now!

However some probless are intrinsically unable to be parallellised.

If somebody was to offer me a 1 core cpu running at 16Hz I would take that over 16 x 1GHz CPUs any day. coding for a single thread is a lot simpler, and can be used on wider range of problems..

However nobody is offering me a 16GHz CPU, and not for $99 either!

Well, if you want to go for gold ( or go mad trying ) then try to solve, not approximate, the Travelling Salesman Problem in polynomial time. Here the question is whether a parallel approach can gouge out the intrinsic factorial behavior. That's nasty .....

Cheers, Mike.

If anything, I think it would be a useful way to show processor scaling on the Epiphany versus other processors.