Dec
30

The joy of programming

This year I graduated and landed a job at Logica. Besides that I have been traveling and relaxed (or at least tried to) in the days off between school and work. I have spent some time working now and during that time I obtained the Java programming certificates OCP JP and OCP WCD. I just read a blogpost that said ‘programming isn’t fun anymore’ and I agree with the arguments the authors provide.

One of the first things that I noticed while working with Java is that a lot of the programming is done using frameworks. Sometimes those frameworks are a little bit too high level in my opinion and take away some fun in programming. I just rolled out of college and have some experience with C++ and other languages. I always liked the possibilities C++ gave me, the language is flexible and problems can be solved in different ways. Some more optimal, some more elegant, some more verbose, some more difficult and some more unsafe.  However, I like thinking about the problem at hand and be able to express myself in the way I want. Libraries often provide a set of features and you can use them on your way to solving your problem.

Now, after working a while with Java, it seems things are more the other way around. Lot’s of frameworks exist, each solving a problem. You then use these ‘higher level’ frameworks to do the job. This higher level aspect often makes it more difficult to alter details in the way the problem is solved. It’s not really about analytical thinking and devising a fun and good solution, but more about finding/using the right frameworks. Every time a better solution comes to somebody’s mind, they quite often introduce a new framework which replaces the previous one. This was easy to notice while studying for the OCP WCD exam. It tests for obsolete frameworks, which are replaced by other obsolete frameworks, which are replaced by other obsolete frameworks. It’s still useful to know these frameworks because there will always be projects out there that use them. Which kind of emphasizes the idea I am trying th sketch: new frameworks are introduced all the time and projects in the field are using a mix of them. This almost impossible to track. I would prefer having the core functionality in libraries and actual solutions developed by programmers working on the project.

This is just a personal opinion/observation, of which I got triggered to write about by the blog post of Eric Allman.

Apr
12

Parallelizing, how much does it matter?

Ever wondered how much benefit you get when you write a program that utilizes more than just one processor? Since I am working on a project where scalability is one of the goals, I asked myself that question. I came to realize that Linear speedup is quite hard to achieve. You have to consider the overhead of splitting jobs and managing the communication. But how much benefit do you get from distributing the workload over multiple processors?

As I was searching the web for this I stumbled upon Amdahl’s Law. Amdahl’s law finds maximum expected speed improvement when only one part of the system is improved. In parallel computing it is used to get the maximum speedup expectation when processors are added to the system. The law looks like this:

Amdahl's Law

Amdahl's Law

The P stands for the fraction of the program that can be parallelized. (1-P) denotes the serial fraction, this fraction cannot be parallelized and has to be executed in serial. N is the number of processors in the system. Let’s see what kind of results it gives. Let’s assume that the total running time of a program would be 24 hours, whereof 2 cannot be parallelized. This would make p = 22/24 ≈ .917 and (1-p) =2/24 ≈ .083. The following table shows the speedup factor if N increases.

Speedup for P = .917 under Amdahl’s Law

Processors (N) Speedup Factor Processors (N) Speedup Factor
1 1.000 9 5.409
2 1.847 10 5.724
3 2.573 20 7.761
4 3.203 50 9.868
5 3.754 100 10.850
6 4.240 500 11.788
7 4.673 1000 11.917
8 5.060 2500 11.995

At first, the performance gain is quite high. But the relative speedup decreases as the number of processors increase and the maximum speedup expectation levels off at 12 in our example. Why 12? Because 24/12 = 2, 2 represents the part of the program that could not be parallelized and has to be executed in serial.

Another way of looking at the problem, is by varying the fraction that cannot be parallelized, the serial fraction (1-P). Then we can see how much speedup you get for a constant number of processors. Let’s make N = 1024. The speedup according to Amdahl is:

Speedup under Amdahl’s law for s + p = 1 and N = 1024

Speedup under Amdahl’s law for s + p = 1 and N = 1024 source

The curve is very steep and to get high performance increases by adding more processors, the serial fraction of the program must be very low. To achieve a factor 100 speedup, only 0.9% of the program can be serial. Overall, Amdahl’s law states that the influence of the serial fraction grows with the number of processors.  This information is extracted from this document.

Some cases exist where it is impossible to parallelize. One classic example is the Fibonacci function:

Fk+2 = Fk + Fk+1

The output of the function depends on previously computed values.(I read this at here) The complete opposite is a case where no or very little dependencies exist between the parts of a parallel problem and no or little communication is required. This is often named an embarrassingly parallel problem. The Graphical Processing Unit (GPU) is a good example of hardware that does embarrassingly parallel computations. SETI@Home, a scientific experiment to detect extraterrestrial intelligence, analyses radio signals in an embarrassingly parallel way.

Can you achieve more speedup than the number of processors you add? Apparently it exists and it´s called super linear speedup. Wikipedia has a short section on this. One possible cause of super linear speedup is the effect of caching with adding more processors. The total cache size grows as processors are added, resulting less memory accesses, dramatically reducing memory access time. This can lead to a big performance increase where speedups of more than 100 are possible when you add 100 processors!

Mar
14

Distributed Document Search Using Hadoop

I have always appreciated speed when programming. Past week I read Google´s MapReduce paper. The document was easy to read and inspired me to use it as part of the prototype for my internship. The basis of my internship assignment is analyzing internal text documents and providing a search features.

MapReduce is programming model and implementation for large scale data processing, usually running on a computer cluster with hundreds or thousands of PC’s. It hides the details of parallelization, synchronization, fault-tolerance, data distribution and load balancing. This makes parallel programming (a lot) easier, especially for newcomers. Google’s implementation is proprietary, but an open source project called Hadoop provides a full featured MapReduce implementation along with several other interesting sub-projects.

Hadoop Logo

Hadoop was initially started by Yahoo! and is now hosted as an open source project at Apache. It is now used by many other companies. A standard implementation comes with common utilities, a distributed file system(HDFS) and a MapReduce implementation and is written in Java (other languages can be used too!). One of the sub-projects, HBase, is a distributed database modeled after Google Bigtable. Nice features of these projects is that they scale out easily by just adding more machines.

I will be using these projects for text document analysis within Logica. I already have a hello world running. Using Hadoop is not too hard. You basically write a program consisting of a Map and Reduce method, compile and package that into a jar and push it into Hadoop for execution. Later on I will also test the scalability and fault-tolerance. If I add a sever, will it go faster? If yes, how much? Also, operations should not fail and data should not be lost if one of the nodes inside the network suddenly fails. I wonder what happens if I just pull the plug on one of the machines while processing documents, let’s see what happens.. :)

Feb
12

Demonstration of Face Recognition

Recently I started an open source project on Google code. It is basically a framework that makes face detection and face recognition easier. The project is currently capturing a web-cam video feed, but in the future it can be extended easily to capture from a video file. For more information you can look at the project page.

I figured people want to see some of its capabilities first, before considering it. I mean, that´s what I would value. I created a short demonstration that graphically shows the capabilities of the framework. You will see that it is not 100% stable, but that has a lot to with lighting and the power of my laptop. You can see the demonstration here:

Feb
03

Internship @ Logica

After not being able to arrange a graduation internship in the United States, I contacted two companies in the Netherlands: Logica and Sogyo. Even though I was late due to the arrangements in the U.S., both of them still had openings and they were inviting me for an interview. I have nothing negative to say about either Sogyo or Logica, which made the choice quite hard. After careful review of the information I collected during the interviews I decided to go with Logica.

At Logica I will mainly be doing research on High Performance Computing and distributed systems. The fields interest me because more and more problems need more computing power, or benefit from the distributed nature offered by some of these new systems.

The next thing for me to do is find a room in Rotterdam city, and I have to find it fast! If luck is on my side, I will be set-up and ready to go by the beginning of next week.

Feb
01

Boost C++ Library Compilation

Compiling the Boost C++ libraries can be tricky for beginners. This was one of my very first tutorials and it shows how to build boost manually. You can of course get the precompiled binaries from BoostPro consulting but if your platform is not available or you want more control over the build specs, building boost yourself is the way to go. I posted the tutorial on youtube, you can find it here: Compiling and configuring Boost C++ libraries for Visual Studio 2010.

A very good text guide can be found on stack overflow right here: how-to-use-boost-in-visual-studio-2010, it covers more details and also shows how to build optional libraries like Boost.Python, Boost.MPI, Boost.Bzip filters, Boost.Zlib filters, and Boost.Regex ICU support (those all need external sources).

Download source code here (Visual Studio 2010 project):  HelloBoost Project

Jan
29

OpenCV compilation and configuration video tutorial

Recently I created a video tutorial for compiling OpenCV 2.1.0 with Threading Building Blocks support using Visual Studio 2010. For new users the compilation of this library, together with the configuration of Visual Studio 2010 might be hard. This video tutorial aims to mitigate some of the problems and shows you how to do it, step by step.

My voice tone is not really good and active, sorry for that. This was the first time I created a tutorial, so it was a new experience for me too. I hope it helps some you out. If you have any questions, let me know.

Compiling and configuring the OpenCV library for use with Visual Studio 2010

Download the source code project here: OpenCVConfiguration Project

Jan
29

Hello there!

Just set up my website to display some of my personal information and work. I will soon start with publishing my résumé /cv on this site, along with information open-source project I have started. I would be happy to receive any comments (and criticism).