Parallel Algorithms are Strange

I am currently reading about the P-RAM (Parallel Random Access Machine), which is kind of the Turing Machine for parallel algorithms.
This machine consists of a bunch of CPUs acting on a shared memory. It is very similar to current SIMD and multiprocessing implementations, apart from the memory. The kind of memory access for P-RAM comes in different flavors. Reads and writes can be concurrent or exclusive. Usually, when you talk about P-RAM you imply the CREW P-RAM. This means concurrent reads, but exclusive writes. This sounds rather natural, since reading (from RAM or rather from a cache) could happen concurrently on most real machines, but writes should be exclusive, otherwise it is not clear which result will actually be stored. The latter aspect is usually not implemented by real hardware, so a bit of trickery needs to be done. There seem to be publications on this topic.
Much nicer would be a real CRCW P-RAM, which in literature is also called the W-RAM. This is a very general parallel machine, and it allows for some very efficient algorithms. For example, take a look at the following program, which computes the minimum value of an array: 

import random

minimum = None
n = 10
M = [ 0 ] * n
C = [ int(1000 * random.random()) for x in range(0, n) ]

print C

for i in range(0, n):
    for j in range(0, n):
        if C[i] < C[j]:
            M[j] = 1

for i in range(0, n):
    for j in range(0, n):
        if M[i] == 0 and i < j:
            M[j] = 1

for i in range(0, n):
    if M[i] == 0:
        minimum = C[i]

print minimum
On a sequential machine, this algorithm obviously runs in O(n^2) time and O(n) space. Your standard implementation of a sequential array-minimum computation would run in O(n) with O(1) space. However, if you were to have a CRCW P-RAM, you could change all the outer for-loops to parallel-for loops, similar to what you can do in OpenMP. Assuming that you have O(n^2) processors available, which is not that unthinkable nowadays anymore, this will reduce the whole time complexity to O(1), with O(n) space complexity. Awesome, isn’t it?

Xcode 4.3, boost and the directory /Developer

Xcode 4.3 changed a lot. Most notably, all the stuff that was once under /Developer now resides under /Application/Xcode.app/Contents/Developer. And the SDKs have moved under the *.platform subdirectories. This breaks a lot of stuff. Especially auto-detecting build systems, such as boost jam. Will write back when I have some work arounds…

Update: I prepared a quick-fix for boost, so it compiles with Xcode 4.3 and builds the framework (see boost ticket #6686. However, I still get compile errors in my project, since clang is very picky and complains about boost:

I think this might be a genuine boost bug. It’s probably already known, but I haven’t checked. Will post another update when I find something.
The quick fix is also available in my github repo, see here.

Update 2: This is a known error, and it has been fixed in later revisions of boost (I am using 1.48 right now). The solution here is that instead of size, there should be size_arg. I wonder how this could ever have worked…

What about C++11 in Xcode?

This started out as a very small problem: I am using C++, Objective C++ and Objective C mixed in one project. This usually works pretty well. However, when including MapKit, the compiler choked on an Objective C++ file. It seems the MapKit.h header wants to use isinf(). This function has been introduced with ISO C 99, but it it is not included in ISO C++ 98. Hence the failure of Xcode’s gcc and clang compilers.

To work around this problem I was thinking of trying to set the project settings to use ISO C++ 11, or C++ 0x, since Xcode’s compilers are not that up to date. This is pretty easy:

And I guess this would work for most people. However, I am also using boost in this project. And I guess it is rather up to date, concerning the new language specification. However this also means that there is a problem with clang’s support of the language. I get a ton of errors in boost when switching to C++ 0x in clang:

In short, I think the C++ 11 support is not quite there yet with Xcode 4.2 and clang 3.0. I will try to post updates when future Xcode releases are coming out. If, alternatively, someone has hints on how to compile boost with clang 3.0, I am also glad to try that out.

Update: There is a fork on gitorious of the boost on iPhone build script, which already uses the clang compiler. I hacked the script even more to use –std=c++0x as a flag and it builds fine. Now I will try to link this new framework to an iOS project compiled with clang using C++ 0x.

Update 2: I found the root of the problem. The fantastic people over at #boost on freenode helped me figuring it out. In short: boost::fusion defines nil, which is an Objective C keyword. Thus we get lots of problems. Objective C defines nil and Nil in objc/objc.h. A minimal program that compiles successfully:

#include <boost/phoenix/core/reference.hpp>
#import <CoreFoundation/CoreFoundation.h>

int main()
{
    return 1;
}

Using this command line: 

/Developer/Platforms/iPhoneOS.platform/Developer/usr/bin/clang++ 
-isysroot /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS5.0.sdk 
-framework Foundation -Fpath/to/boost/framework --std=c++0x -arch armv7 
-stdlib=libc++ -mthumb -miphoneos-version-min=5.0 foo.mm -o foo

If you swap the to include / import statements, the program will not compile, since now the ObjC nil makes boost break. There is a boost ticket tracking this issue, with a proposed patch attached, which renames the boost nil to nil_.

Update 3: The patch works fine, but now I get internal compiler errors from clang. The compile triggers a segmentation violation at some point during the compilation of my project. I guess clang 3.0 is still a bit experimental. I submitted a bug report and will revert to using the default settings of Xcode for the time being.

Using gpsbabel and a USB to serial adapter on OS X to read out a Garmin GPS

For a couple of years I have been owning a Garmin eTrex GPS receiver. It’s a nice little tool, pretty ruggedized and reliable. I use it to track for example hiking tracks and also sometimes for Geocaching. It has a serial interface for downloading the data. However, my MacBook Pro does not have a serial port. So I bought one of the ubiquitous Digitus USB to Serial adapters. With this and gpsbabel (sudo port install gpsbabel, if you have MacPorts), it is really easy to download the track data for example to a KML file to be viewed in Google Earth:

gpsbabel -t -i garmin -f /dev/cu.usbserial-XXXXXX -o kml -F mytracks.kml

The XXXXXX in the device filename varies from device to device, you probably can also use /dev/cu.usbserial-* as the device filename, if you have only one of these things attached to your computer. It is important not to use the tty device file, since it seems not to work. I do not know yet what the exact difference is, but I will come back when I found out.

BibTeX bibliography title

The other day I was using the moderncv document class to create a CV. I also added my publications to the CV, which was supposed to be in German. BibTeX created a section “Literatur” for this. Obviously, I wanted the title of the bibliography to be “Publikationen” instead. When using the german package of babel, you can change the bibliography title like this in the LaTeX preamble: 

addtocaptionsgerman{renewcommand{refname}{Publikationen}}

Clementine Player

A couple of years back, I was a big fan of Amarok, the music player. Then came along a rewrite and version 2.0, and I also switched to OS X. The version 2.0 was not very nice, stable or useful. The OS X version was very hard to install, due to the KDE dependencies. So I ditched Amarok. I replaced it with CogX for a while, and now I am using the horrid iTunes and the wonderful mpd (together with MPoD and Theremin). But today I read about the Clementine Player. It’s a cross platform Amarok 1.4 fork. And after 10 minutes of testing, I think it’s wonderful!