Book review "Structured parallel programming" - M. McCool, A. Robison, J. Reinders

Date Tags Books

I just finished  Structured parallel programming, by M. McCool, A. Robison, J. Reinders. Personally, I am not enthusiastic about this book, and not because of lack of quality, but because I am probably not the right target.

The book presents typical patterns for parallel programming (map, reduce, scan) and in particular as implemented by Cilk Plus, ArBB, OpenMP, TBB and OpenCL. Given that I already know most of the parallel programming patterns, I didn't really learn anything new on this regard, but it was a good refresh nevertheless. The book strong point is, in my opinion, the detailed exposition of how the patterns are implemented by the five different parallel programming environments, something that is invaluable if you already know one environment (say, OpenMP) and you want to try or migrate something else. The code snippets are clear, to the point, and in C++.

If you are completely new to parallel programming, this book is probably not for you. If you want to learn strengths and shortcomings of the different parallel environments, compare their syntax, get an idea of alternative solutions, and an overall refresh of your already solid background in parallel programming, I definitely recommend it.


The von Neumann method revisited: a letter from a reader

It's always a source of extreme satisfaction when someone contacts you about a post you made, and even more so when the mail actually answers an open question I had about generalizing the von Neumann method. If you don't recall what's about, it was about getting a fair coin throw from an unfair coin. I wondered if it was possible to generalize it to any number of faces (a coin is a 2 face die), but left the issue unsolved and moved on.

A few days ago, I received a mail from Albert Rafetseder, which I copy here verbatim except for minor presentation adjustments. Thank you Albert for the interest and the cool research

Hello Stefano,

by chance I came across your blog (via some Python PEP discussion you participated in), finding your post from August on the von Neumann method. I have pondered the question of a von Neumann die, too, and my solution is this: Observe that the von Neumann coin method can extract an unbiased coin flip from those strings of flips of length 2 that are permutations on the set S of all possible outcomes of the biased coin S = {0, 1}:

Permutations P(S) = {01, 10}.

There are Length(S)! possible permutations, i.e. the extracted unbiased "random gadget" is a coin again.

If you consider a die with S = {1, 2, 3, 4, 5, 6}, then P(S) = {123456, 123465, 123564, 123546, .... }, and the extracted unbiased random gadget is a Length(S)! = 6! = 720 facet thing. Unless, of course, you simply group the permutations by some property to reduce the number of unbiased results, e.g. grouping all 120 of them that had a "1" in the first roll, and so on for every s in S.

By different grouping, I believe you could fabricate an unbiased random gadget for every divisor of 720, too; similarly, you could use a biased n-sided die rather than a six-sided one. And maybe you could increase the efficiency of the scheme by taking into account how the pips on opposing sides usually add up to seven ([that is:] probabilities of opposing sides of a real die are somewhat complementary, although they usually do not complement in an absolute sense, i.e. not q=1-p). This conjecture is problematic: first, I have nothing to its support other than that I think the physics would work this way in a real die. Second, this (sub-)complementary property does not hold in general for a simulated die as the probabilities for each side could be anything. Third, no joy for "dies" with an odd number of sides, obviously.

As it often goes, you and I are not the first people to ponder this question. Here are other's peoples approaches: this one and especially this which lists a rich source of prior as well.

Also, optimization of von Neumann's coin method exist that don't throw away so many 00 or 11 results. [This method] has a multi-level approach for extracting unbiased bits from longer strings of flips, indeed asking at the very end "Now, how do you simulate an unbiased die with a biased die". (Well, we know now). This is a collection of further reading material on Stackexchange. I haven't read this pdf, but it seems to take up the efficiency/optimization idea too.

After stealing so much of your valuable time, allow me to mention one further paper that describes computations that can be done using random numbers of unknown probability distribution. I personally find late Philippe Flajolet's work always worth a read.

With that, thank you for your blog post reminding me of this interesting topic (and stimulating me to write up my thoughts on it).

Best regards, Albert.

I will hopefully explore in more details with actual code after my next series is finished. I built a NAS from scratch and I have a long series of posts ready to ship starting next month. I want to keep the post chain uninterrupted, but I really wanted to publish your mail as soon as I could. For this reason, I couldn't research any further on your insights, but they are definitely worth of interest for future posts. Stay tuned!


Fair throw from an unfair coin

Date

Imagine you are given an unfair coin. You don't know how unfair it is, nor which side (head or tails) is produced more frequently than the other. How do you perform a fair throw with it ?

Enter the von Neumann method. It's really simple: throw the coin twice. If the results are the same, discard the result; if the results are different, choose the first one.

How does it work ? It's rather easy. Suppose the coin returns head 90 % of the times, and the remaining 10 % returns tail. We give actual probabilities here for the sake of discussion, but you don't need to know how unfair is the coin in order to apply this method. If you throw the coin two times

  • the probability of throwing two times head is 0.9 * 0.9 * 100 = 81 %
  • of getting two tails is, of course 0.1 * 0.1 * 100 = 1 %.
  • the probability of throwing tail followed by head is 0.1 * 0.9 * 100 = 9 %
  • and finally, the probability of throwing head followed by tail is 0.9 * 0.1 * 100 = 9 %.

You can see how the probabilities of the mixed events (Tail-Head and Head-Tail) is the same. If you discard homogeneous cases Head-Head and Tail-Tail, accept only the mixed results and pick one of the throws as the right one, you will obtain the same probability of obtaining a head and tail, that is 50/50, a fair coin. The only problem with this method is that you may have to discard a very high number of throws. The method will be slower to yield a result, but the result is guaranteed to be fair. In the limit of a completely unfair coin that returns the same face every time, you will never get a result. I wonder how this can be generalized to an unfair n-faces die.


Random number generator hardware

Date

Suppose you want to generate a large number of random dice rolls for a computer program. How do you do it ? With a robotic dice rolling machine, of course

Why would anyone need such device, I hear you ask? Well, software random number generators are technically not perfectly random, and if you have to reassure a crowd of people complaining about your rolls' randomness, this solution is straightforward, creative, and a real pleasure to read in its gory and unexpected technical issues.


The insane clauses of a university's contract for a researcher position

Date

Despite having left academia for good, and for all the best reasons, all my circle of friends and professional contacts is mostly in academia. Some time ago a friend forwarded me the following contract for a researcher position in a university of a non-European country.

It should not come as a surprise that, in some countries, what we consider slavery is still a thing, but you would not expect to be a thing in written form. I report here only the paragraphs that are important, removing the boilerplate stuff. I also render the amounts in euros for ease of comparison. I leave the introductory opening, because it makes a nice (read: creepy) contrast. I will put my comments directly following the relevant fragments.

The two parties, in a spirit of valuable consideration and friendly
cooperation, agree to sign this Contract and pledge to fulfill
conscientiously all the duties and obligations stipulated in it.

Yeah, sure.

Employee’s annual salary will be 44.000 EUR (3683 EUR/mo). Social
insurances are included and all kinds of taxes and fees have to be paid
by Employee. 90% of the annual salary will be paid as follows: Employee
will be paid 1900 EUR monthly and the rest, which is set as the annual
research reward, will not be paid until Employee has passed the annual
evaluation. And the other 10% of the annual salary will be paid by the
end of the next year when Employee has passed the annual evaluation.

Meaning that, depending on the actual cost of living, one might be forced to work at a loss until the annual research award is given (if it's given). Note, additionally, that these amounts are before taxes, that there's no pension contribute, nor any entitled vacation.

Employee shall observe the laws, decrees and relevant regulations
enacted by the country's government and shall not interfere in its
internal affairs.

Good morning fascism, it's been a while. The definition of "interfere" is up to free interpretation, of course, especially when scientific research interferes with political decisions. We've seen this already, and it didn't turn out well. I will also add that the research topic is potentially source of political distress.

Employee shall be evaluated and supervised by Employer according to the
duties and obligations stipulated in the Contract

The obligations (which I am not showing here) are extremely detailed requirements for number of publications, quality of journals, teaching duties, all with undefined collaborators at discretion of the Employer.

In the annual evaluation of Employee, if Employee publishes one
research paper fewer than the required number, EUR 5700 shall be
deducted from his/her annual salary during the 1st and 2nd years of the
term of this contract and EUR 4300 shall be deducted from his/her annual
salary during the 3rd and 5th years of the term of this contract. But
all the deducted money will be returned to Employee if he manages to
complete all the duties and obligations by the end of the employment
period.

Yeah, I am sure anybody would be glad to work like that, under the whims of referees. And not let's even consider what happens if you get sick, or have any problem preventing you to publish due to either a collaborator's resignation, a broken instrument, or any other unforeseen circumstance like it always happens in scientific research, in particular of the experimental on-the-field kind (which is the one we have here).

We talked about resignation. Well, that's another "funny" point. Read this:

VI. Revision, Cancellation and Termination of the Contract
 1. Both parties should abide by the Contract and should refrain from
revising, canceling, or terminating the Contract without mutual
consent.

Meaning you can't quit for the duration of the contract (5 years).

4. Under the following circumstances, Employer may terminate this
Contract in the form of written notice to Employee:
 (1) Where Employee does not perform his/her duty or is incompetent to
perform his/her duty
 and remains to be incompetent after Employer’s warning.
 (2) Where Employee has been proven to use fraud and deception
information in the applying materials such as health, education,
political performance, academic position and other documents.
 (3) Employee has serious discipline breach behaviors or involvement in
criminal activities.
 (4) Employee unauthorized departure from office prior to the end of his
term without consent.

Except for some reasonable points, point 4 restates that you can't quit. Unless there's mutual consent, you are not authorized to depart from your office before the end. It's debatable if, in this case, the word "office" is meant as "work room" or "duty", but considering what comes next...

VII. Breach Penalty
 1. Employee shall pay liquidated damages to Employer if the Contract is
terminated due to the occurrence of circumstances described above. The
liquidated damages amount for 3 times of the monthly wages Employee has
received.
 2. Employee shall notify Employer three months in advance if Employee
asks to cancel the Contract before the term of this Contract expires.
After Employer’s consent, Employee shall pay liquidated damages to
Employer and the liquidated damages amount for 3 times of the monthly
wages Employer has received.

So if you are fired, or if you quit (assuming they let you go through mutual consent) you have to repay three times what you got until then.

What. The. Hell!

Needless to say, the offered position was refused. I can't imagine anybody sane in his mind accepting it.


What happened to ForTheScience?

Date

There have been quite some changes in the past 24 hours, and a few more will follow:

  • I changed the theme to Garland. I kept the green theme because I like it and it's the traditional color of the chemistry degree in my native city. The theme is not perfect, and I am tweaking it as I write. I will also have to check past posts to see if they behave correctly.
  • As a passionate (but inexperienced) beekeeper and gardener, I decided to start a new blog at Gaia.ForTheScience.org. It will mainly focus on my personal adventures in outdoor and non-computer-related activities, such as gardening, beekeeping, and cooking (Italian cooking, specifically), with a scientific eye and strong accent on discovery and experimentation that can be useful to others. I decided for the split because I expect the audience to be different: I already have plenty of movies and pictures to post, but I felt this blog as not appropriate for this content.
  • I removed the failed experiment of wavemol.org, which I started during a relatively well-received, but not financed application for a Marie Curie grant I applied for. After the grant was declined, I kept the domain trying to reinvent its purpose, but I found myself not particularly driven to do any more work on it. For a while, I helped a friend and hosted the p4vasp code, and received good traffic, but after the code was moved to a dedicated site, the traffic declined to spambots and I decided to terminate it for good. The URL now redirects to this blog.
  • I will soon remove WPML translations. The plugin has gone commercial, and I am not posting a lot in Italian to justify the transition. I don't know how the current Italian posts will be handled after the removal, but my guess is that they will collapse into the current blog timeline. I might still post in Italian and provide translation posts, but they will appear directly in the current progression. I doubt this will be excessively annoying for current readers, as I normally post translations when the English post is no longer on the main page or the RSS scope.
  • I removed the redundant twitter lateral pane, leaving more screen for code and scripts that occasionally ended up being hard to read or to copy/paste. I will keep posting updates on twitter every time there's a new post (it's automatic)

The modem dialup handshake analyzed

Date Tags modem

Those of you old enough to get internet connection with an empty can of beans connected to a string will probably remembered a coal-powered tool of the time, the modem. Its shrieks filled the beginning of an evening of bad GIFs, short web pages with <blink> tags, and plenty of telnet and IRC sessions. The memorable combination of sounds was a bit of a mystery to me, but I found this extremely interesting blog post detailing the negotiation phase, step by step, directly on the spectrogram. Worth checking out if you ever wondered what your modem was saying.


Lack of usability in Gnome/Ubuntu

Maybe I should file a bug report on this, but it's a nice example of lack of usability due to colliding needs: the need for a scrollbar in the terminal, and the need for window resizing.

As you can see, the popup scrollbar always follows the mouse pointer, making it impossible to get the resize operation. This happens in the bottom-right corner as well. The only way to perform resizing is to either use the top right corner, or to "trick" the scrollbar by moving the mouse pointer in a particular way, something made even more difficult by the fact that this area is one or two pixels wide.

This is so wrong from the usability point of view that I am surprised nobody caught it.


Telepresence robot: giving wheels to an iPad

Date

I really love this thing.

It is a telepresence robot with a stabilizer (similar to a Segway) which mounts an iPad as a "face". I have no use for it, yet I'd really love to have one. Now imagine having a full exoskeleton version...


iSight stops working? Check google talk plugin.

Date

Occasionally, my iSight stopped working, even in the middle of a Skype video session, with the camera in full control of Skype. Any effort to re-enable the camera failed with a "Camera in use by another application" message. I could not wrap my head around the issue, until I investigated a bit and I think I managed to understand what's going on.

Occasionally, during video chat, Skype detaches from the camera in order to switch resolution, probably to scale it accordingly to current bandwidth conditions. During this split second, it may happen that the google talk browser plugin takes over the camera, and never relinquishes it. The camera is now stuck with google talk, Skype can't grab it anymore, and so for all other camera applications. The only solution appears to be a reboot.

I was able to fix the problem by issuing

ps uaxw |grep Firefox

which may produce the following output

sbo     21173   0.0  0.1   414040   2492   ??  S     5May11   0:07.47
        /Applications/Firefox.app/Contents/MacOS/plugin-container.app/
        Contents/MacOS/plugin-container /Library/Internet Plug-Ins/
        googletalkbrowserplugin.plugin -omnijar /Applications/Firefox.app/
        Contents/MacOS/omni.jar 21168 gecko-crash-server-pipe.21168
        org.mozilla.machname.855559451 plugin

The solution is to kill this process with the appropriate pid (in this case, 21173).

kill 21173

this frees the camera without a reboot.