Computer Science

Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask

It’s just one day before traveling to the US to present “Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask” in the the 24th ACM Symposium on Operating Systems Principles (SOSP). I am really glad that I will have the opportunity to share the knowledge we collected in over a year of hard work. You can get a copy of the paper here.

This publication is about understanding the low-level details of the hardware (e.g., the cache-coherence protocol) and how they affect synchronization (and sharing of data in general) in software. If you want to better understand your hardware, to optimize your system/application, or to understand why something scales or does not scale, I believe you will be interested in reading the paper.

We also published the software we developed to perform this study as the SSYNC synchronization suite (SSYNC stands for Simple Synchronization). If the information in the paper is not sufficient for your needs, or if you have a hardware platform that is not very similar with the ones we used in the paper, then you can use the tools and libraries of SSYNC to evaluate your own platform.

SSYNC is available at and contains:

  • ccbench: a tool for measuring the latencies of the hardware cache-coherence protocol
  • libslock: a library with cross-platform implementations of various locking algorithms
  • libssmp: a message passing library optimized for x86, SPARC, and Tilera platforms
  • TM2C: the first software Transactional Memory for Many-Cores

I hope you will enjoy reading the paper 🙂

Functional instead of Object Oriented Programming at CMU

Recently, Robert Harper, a Professor of Computer Science at Carnegie Mellon University (CMU) posted about the new introductory CS curriculum at CMU.

Two new courses has been introduced and one more is planned. The first two are about Functional and Imperative Programming respectively. The third one will be a course on Data Structures and Algorithms.

At the same time, Object-Oriented programming is removed from the introductory curriculum, because it is considered both anti-modular and anti-parallel, thus unsuitable for a CS curriculum.

The Standard ML programming language will be used for the Data Structures and Algorithms course. SML was also my first functional programming language while taking the Programming Languages I course during my Diploma. Although it is a “clean” and easy to go language, I would prefer a more inherently parallel language to be used instead. Erlang could be a good candidate!

I vote for this change :-). This shift “against” Object-Oriented programming is a natural one since Parallel Programming is a necessity in the Multi-core era.. An old joke (which is actually stolen from a joke about regular expressions) says:

You have to solve a problem. The problem has certain performance requirements. You decide to use Java and threads.. You have to solve two problems.

Not P==NP for now..

Some time ago (January 19, 2011), Vladimir Romanov announced that he had found a polynomial time solution for the 3-SAT NP-Complete problem. As I mentioned on the first related post, if this was true it would immediately suggest that P==NP.. A nice article about what would be the implications of this equality can be found in Wikipedia.

The time for such a proof (or the opposite one, which is consider to be more probable) has not come yet. Yesterday, with a comment to his blog, Vladimir Romanov announced that there is a problem with the solution that need to be corrected:

Thank you for your attention to my work. You’d better suspend your investigations.
A shortcoming possibly exists in the filtration procedure which requires an amendment.

Best regards,
V. R.

Parallelizing simple algorithms : Fibonacci

This entry is part 2 of 2 in the series Parallelizing simple algorithms
Fibonacci Blocks

Fibonacci Blocks

It took me a little more than I expected, but finally I managed to write the first post for the Parallelizing simple algorithms series.

As I “promised”, I will start these series by parallelizing the Fibonacci Number sequence generation. As you probably already know, Fibonacci numbers are the integer sequence produced by the following relationship:

   F0 = 0
   F1 = 1
   Fn = Fn-2 + Fn-1

The resulting sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .

Lets start with programming!

Read the rest of this entry »

3-SAT polynomial time solution? If true then P==NP

Complexity classes

Complexity classes

One of the biggest questions in the CS always was (is) if P==NP, or P!=NP.

I just read a post announcing an article called “Non-Orthodox Combinatorial Models Based on Discordant Structures” by the author V. F. Romanov (

According to the author:

The article presents a constructive proof of effective resolvability of 3-SAT problem, accompanied by description of a polynomial algorithm created for the named purpose.

If this statement is correct, and the algorithm really solves the 3-SAT problem in polynomial time, then P==NP (since 3-SAT is  NP-complete). Although the article, in my opinion, looks too draft for such an important topic, if it will be proven correct, one of the biggest findings in CS will be unveiled.

Lets see..