Montag, 16. November 2009

My parallel literal propagation - Speedup and Efficiency

For a computer scientist there is not a lot that satisfies you more than realizing that things work exactly the way you want them to. Even more so, when you have spent quite some quality time on coming that far.

Today I've given the parallel literal propagation module a shot and benchmarked it with some of last years benchmark files. What I see is, that my parallel algorithm scales very well for increasing number of cores or threads. On a fixed number of cores, it even cotinues scaling further when starting more threads than cores are available. This indicates good cache usage, but so far I've not investigated. After all, the speedup is about 5,3 (in comparison to the single-threaded version). I disinguish two different forms of the term 'efficiency' (which relates to the fact, that I can schedule multiple threads on a single processor core). In the traditional sense, the efficiency for the speedup of 5 accounts to 69%, which is an excellent score.

Hopefully, I'll soon be back with further results that prove me right - I'm moving towards parallel unit propagation and conflict detection.

Donnerstag, 12. November 2009

"Research in Europe"

Hi folks,

on Friday I was invited to an informational event on research fundings in Heidelberg, as I'm currently looking for interested and interesting sponsors to support further research. It was organized by KoWi, an institution that coordinates Research and Development throughout Europe and that is funded by the German Research Foundation. It was very interesting to get in touch with the different scholarship programmes and research institutions.

Also, I received very positive feedback on my research plan and ideas - so let's start it up!

Montag, 2. November 2009

Multicore programming - but what comes next?

For some time now, I'm completely dissatisfied with the technical possibilities, software developers have when writing multithreaded applications. Basic parallel structures like parallel loops and fundamental synchronization mechanisms are definitely needed and it's a good thing programmers have those language constructs at hand. At university today we educate our students to
- be able to use these mechanisms correctly and
- point out the problems, that will most probably still arise when doing it
...well...

At the moment we develop software for 2 up to 32 cores. It might still be feasible for us humans to think that far - to think that parallel - but what if we wake up one nice sunny day and have hundreds of cores on a regular CPU? I mean, what's the point in offering 'parallel-for' when developing software with millions and billions lines of code that should run effectively on hundreds of CPUs? According to Intel and AMD, this day will come. In less then a decade.

Last week I had an interesting conversation with Carsten Schumm from SUN Microsystems. He presented some of the problems they currently experience in engineering multicore-capable applications and solutions. I have been thinking about this problem a lot and I think we need a new programming paradigm.

For now I can say:
I don't know what the solution could be, but I really fancy the idea to be part of it...

Freitag, 30. Oktober 2009

First goal accomplished: "Parallel literal propagation"

As the project goal for October, I wanted to have a running version of what I call 'parallel literal propagation' which I use to fork threads on a many-core system. This may not be a giant leap for mankind and rather a small step for a man, but I am positive that my resulting parallel SAT-engine stands somewhere in between.
Would be a respectable result for a SAT-engine though...

Donnerstag, 1. Oktober 2009

Intel Threading Building Blocks

Intel recently updated its Threading Library (TBB) to version 2.2. Now, the concurrent data types use iterators as return types. As I tried to find good and useful documentation and source code examples literally the whole day, I'd like to share this info.

I found some general Visual Studio Projects in C++ and C# outlining some of the capabilities of TBB. The guys at Aeshen provide small, but realistic scenarios for their example projects. Some more examples are contained in the stable release packages. In contrast to that, the official TBB site is full of...well, let's call it "generic information" - except for the Reference Guide which lists all template functions and signatures.

Mittwoch, 30. September 2009

The first steps...

Fine.
The first month is almost over, so let's briefly summarize what has happened:

After the initial setup phase at university I got myself up to speed with current algorithmic improvements in SAT-solving. The community published a lot of interesting papers on solving propositional logic. I'm wondering though, why parallelization does not seem to be an interesting area of software engineering.

During the first month of debugging, profiling and analyzing I came up with some promising research projects based on MiniSAT. The first experiments prove me right - we'll see what comes next.

It's an interesting time that lies ahead, so I conclude with this:
"I never think about the future - it comes soon enough" (Albert Einstein)