FJTask: A Java Fork/Join Framework

Last week I made a post about a pure Java x86 emulator which showed interesting performance. That surprised us because we know think that Java tends to be slower compared to other languages, like C++.

Today I’d like to talk about FJTask, a Java framework that supports the Fork/Join programming style. This is also a pure Java code, and according to Doug Lea’s studies this framework can be used to resolve problems even faster than similar approaches in C/C++.

The Fork/Join is a design technique for writing parallel algorithms. These algorithms have the divide-and-conquer principle and therefore are nearly always recursive, repeatedly splitting subtasks until they are small enough to solve using simple methods.

Why not to use the common java.lang.Thread class? Because Java threads are general purpose and have a lot of routines that are useless for the Fork/Join technique, and having those thing will cost just too much. One of the applications that Lea made to test FJTask was the classic Fibonacci function, and it got to ran at least thirty times faster with FJTask rather than using the java.lang.Thread class. And of course, as it is pure Java code maintains the portability of Java programs.

FJTask split the main task in several smaller tasks which are given to a number workers threads which might solve the tasks. The number of workers usually correspond to the number of available CPUs. What is interesting is that each worker maintains runnable tasks in its own scheduling queue. When a worker gets out of tasks it can “steals” from other workers. What is even more interesting is that when a worker can’t steal tasks from other threads, instead of keep and keep trying it will rest for a few and then continue trying to steal. That design allow that unoccupied workers don’t stress out the CPU with “useless” processes. The way FJTask access data structures  (FIFO, LIFO queues) also help to improve the runtime.

Compared to other frameworks like Cilk (which the FJTask design is based on), FJTask performs better in most applications. Although it generally performs worse on programs that mainly do floating point computations on arrays and matrices.

With FJTask we can see that is possible to do good parallel processing in pure Java, and this framework provides a convenient interface for programmers who can build portable parallel applications following few design rules and design patterns.

Publicado en CS 527,English,Software Engineering | Sin comentarios

Dejar un Comentario

Por favor, se cortés y comenta sobre el tema. Tu e-mail nunca será publicado.

*

Sitios de interés