Parallel Computing with OpenMP & C 1: Introduction

Tags

OpenMP, parallel

So, I’m taking a class this year on high performance computing, and I figure’d I might as well kill two birds with one stone: write some blog posts, and also get some studying done.  Let’s get to it!

What Is OpenMP?

OpenMP is an API for working with shared memory parallel computers.  Essentially everyone now owns one of these machines, as any multi-core machine is a shared memory parallel machine.  What it isn’t is a tool for GPU programming or programming on distributed memory systems (like a Beowulf cluster).

OpenMP is one of the fastest and easiest ways to squeeze extra performance our of modern multicore CPUs.

How to Set Up OpenMP?

Unlike some parallel tools (I’m looking at you CUDA 2 years ago), OpenMP is ridiculously easy to set up.  If you are running a Debian-like system, it is just:

apt-get install libgomp1

And that’s it!  All you need to do now is compile your code, as you normally would, with gcc and the -fopenmp flag

gcc  -fopenmp

How easy is that?

In the next post, we will write some simple C code using OpenMP.

Illegal Poetry

Tags

philosophy, poetry, programming

I have always had a problem with the concept of intellectual property.  The great western tradition of post-enlightenment values have always placed the free flow of art and ideas on a pedestal, as a sacrosanct cornerstone of a just society.  That the ideas living in our heads and flowing from our lips were the domain of no king, pope, or policeman is the one of the most important cultural norms that has emerged from the enlightenment into modern liberal democracies.  The legal constructs associated with intellectual property, in my evaluation, cannot be reconciled with this.  A corpuscle of information cannot be at once free to be spoken or expressed and also be the property of some individual and corporation.  Information Theory, the fantastic work pioneered by Claude Shannon, only swells my distaste for intellectual property.  We know now that with simple coding, all information is reducible to a common binary form.  Film, print, music, photography: all is merely a collection of ordered bits.  Which makes the idea of owning information all the more ridiculous, as the process can be just as easily reversed:  A song can be represented by a string of Shakespeare quotations, a movie can be rendered in musical score.  As an illustration  of this, I’ve written a short program that takes any file and converts it to a long, rambling nonsense-poem.  Poetry as Piracy.

Making the Wordlists

The first step is generating a set of words to use to generate our poems, categorized by their grammatical type.  To do this, I downloaded the English wiktionary.  I then used grep, sed, and awk to split it into plain lists of words:  nouns, past tense verbs, present participle verbs, and adjectives.  I then shuffled these lists, and trimmed them down so that their length was a multiple of 2.  I didn’t need to do this, but it simplified the work slightly.  In the end, I was left with 17 bits worth of information stored in each noun (131,072 words), 13 bits in each past-tense verb (8192), 13 bits in each present-participle verb (8192), and 15 bits for each adjective.

Sentence Skeletons

I then decided on two rough sentence skeletons:

The ADJECTIVE NOUN PAST-VERBED the ADJECTIVE NOUN.

ADJECTIVE NOUN is PRESENT-VERBING the ADJECTIVE NOUN.

Each of those sentences can store 77 bits of information.  A 1Mb file, for example, will require roughly 10,000 sentences, or about a novelette worth of words.  If that 1 Mb file was a copyrighted song, you would not in fact have the freedom to print and distribute your nice new novel (not that you would want to, it would be random nonsense.)

Encoding the File

Now, 77 bits is a bit awkward.  Just choosing between each sentence type gives me 1 bit of information.  I also get punctuation at the end.  If I end each sentence with either a period, exclamation mark, two exclamation marks, or three exclamation marks, that gets me an extra two bits of information.  This gets me up to 80 bits per sentence, or 10 bytes.  I can now easily encode my data as nonsense poetry!  I use the first bit to select which tense of verb, the second two decide if I get a period or exclamation series, and the rest determine the sentence itself.  If my file isn’t nicely divisible into base 10, I simply add an additional line at the end:

All that remains are NUM memories and NUM regrets.

Where NUM is the base-10 representation of the remaining bytes in the first case, and the number of bytes remaining in the second instance (as a long string of leading zeros will get truncated in converting to decimal).

Decoding the File

Decoding the file is as simple as just reading in each line, checking what sentence type it is, and what the punctuation at the end is, and returning it to the original binary form!

Sunset Time Series

Tags

art, photography, sunset, vancouver island

Inspired by a reddit image post (which I cannot for the life of me find again), I decided to take a series of photos of the sunset from my parents’ house at Cedar-by-the-Sea, Vancouver Island. I many photos over the course of several hours using a digital camera fixed in position on a tripod.

I thought it would look good to blend the images one into the other, so I wrote a quick python script using the Python Image Library. The script blends consecutive images using linear interpolation. An artistic choice to make was how wide the blended regions should be. I tried everything from relatively thin blending regions:

To almost completely blended images:

In the end, however, I decided that what looked the best was actually to have no blending, but rather sharp boundaries between the images. This actually accentuates the effect I was going for, which was to show the changing light over time. Blending the images together actually lessens the effect, rather than enhancing it as had hoped. I plan to get the finished product printed and framed:

Here’s the code for the script I used (apologies for quick-and-dirtiness):

import sys
from PIL import Image

def imageblend(imdir, numimages = 5, blendwidth=0):
    if not blendwidth%2 == 0:
        raise Exception('blendwidth not even')

    im = Image.open(imdir+"im1.jpg")
    (width, height) = im.size

    for i in range(1, numimages):
        imnum = i+1
        centre = i*width/numimages - 1

        im_i = Image.open(imdir+'im%d.jpg'%(imnum))

        for x in range(blendwidth):
            col_ind = centre - (blendwidth/2) + x +1
            col_box = (col_ind, 0, col_ind+1, height-1)
            col_o = im.copy().crop(col_box)
            col_i = im_i.copy().crop(col_box)
            col = Image.blend(col_o, col_i, float(x)/blendwidth)
            im.paste(col, col_box)

        rest_box = (centre+blendwidth/2+1, 0, width-1, height-1)
        rest = im_i.copy().crop(rest_box)
        im.paste(rest, rest_box)

    im.save(imdir+"im_output.jpg")

def main():
    imdir = sys.argv[1]
    imageblend(imdir)

if __name__=='__main__':
    main()
 

Backup Your Google Life: gback

Tags

backup, cloud, coding, computers, gback, google

There was a rant that bounced up and down the tubes of the internet this week, talking about how one poor fellow migrated all of his important data into google services, only to have google pull the digital rug out from under him by deleting his account after it was algorithmically flagged.  This sucks, but one thing I have always been pestered about is the importance of regular backups.  Just because google is “the cloud” doesn’t mean your data is in a deadly limbo state of potential destruction if you don’t back it up.  The problem is, backing up a machine you control is damn easy, while backing up your cloudified data is not.

Programming Mathematical Functions with Taylor Polynomials

Tags

arduino, astronomy, coding, math, programming, taylor series

Taylor Series Approximation of Sine

I’ve been thinking of writing an astronomical toolkit for Arduino, to help users build their own go-to telescope mounts, satellite trackers, heliostats, and other cool amateur astronomy equipment.  As anyone who has ever worked with astronomical coordinate systems know, since astronomers treat the sky as a 2 dimensional spherical surface, most calculations involving positions on this surface involve a good deal of trigonometry.  While the Arduino library includes built-in functions for sine and cosine, it lacked the inverse trigonometric functions arcsine and arccosine.  These are necessary if you ever need to convert a length ratio into an angle.  It is impossible to convert between different sky coordinate systems (like Horizontal and Equatorial, the two most common) without access to these functions.  In today’s post, I’ll show you how I wrote my own arcsin() and arccos() functions using Taylor polynomials.

Basic Data Plotting with Matplotlib Part 3: Histograms

Tags

matplotlib, programming, science, technology

Continuing my series on using python and matplotlib to generate common plots and figures, today I will be discussing how to make histograms, a plot type used to show the frequency across a continuous or discrete variable.  Histograms are useful in any case where you need to examine the statistical distribution over a variable in some sample, like the brightness of radio galaxies, or the distance of quasars.

Basic Data Plotting with Matplotlib Part 2: Lines, Points & Formatting

Tags

matplotlib, programming, science, technology

Continuing my series on using matplotlib and python to generate figures, I’d like to get now to the meat of the topic: actually making a figure or two.  I’ll be starting with the simplest kind of figure: a line plot, with points plotted on an X-Y Cartesian plane.

Basic Data Plotting with Matplotlib Part 1: Introduction

Tags

matplotlib, programming, science, technology

I’m sure many of my fellow scientists spend a relatively large chunk of their time making plots, graphs, and figures of one sort or another.  There are a plethora of cool tools out there for doing this, from proprietary tools like Mathematica or IDL to free software kits like GNUplot.  While GNUplot is useful and handy (and IDL is powerful and expensive), I’m a python guy primarily, so I like my tools to interface well with my existing code, and has a more pythonic interface.  For this, I turn to matplotlib, a powerful suite for generating all sorts of plots from python.

Accidental Pilish: Unintentionally Constrained Writing in English Literature

Tags

computer science, constrained writing, gutenberg, language, nlp, Pilish, writing

Background:

This post is a little late for Pi Day, but it’s never a bad time for discourse related to everyone’s favourite mathematical constant. Twas on Pi Day of this year that I somehow came across this site, which describes the Constrained Writing task of Pilish, in which the length of each word in letters corresponds to the digits of pi:

The first word in this sentence has 3 letters, the next word 1 letter, the next word 4 letters, and so on, following the first fifteen digits of the number π.  A longer example is this poem with ABAB rhyme scheme from Joseph Shipley’s 1960 book Playing With Words:

But a time I spent wandering in gloomy night;

Yon tower, tinkling chimewise, loftily opportune.

Out, up, and together came sudden to Sunday rite,

The one solemnly off to correct plenilune.

Michael Keith, the author of the above website, has created several works in Pilish, including a full-length book covering the first 10,000 digits of pi!

Trying to write under such constraints can feel extremely awkward, but this made me wonder: How often would strings of words adhering to the constraints of Standard Pilish occur unintentionally? Afterall, with the amount of text out there – the sheer rate at which words are being put together by people all over the world every second of every day – it is to be expected that these things should occur with some frequency p > 0. Such is the Law of Large Numbers.

In order to determine this, I would need a large data set. Luckily, such things are readily available. I settled upon the Project Gutenberg ebook catalog – specifically the union of the July 2006 DVD (17,000 books) and the March 2007 Science Fiction Bookshelf CD (most of PG’s Sci-Fi titles). Altogether, this gave me almost 9GB of text (although I later discovered this contained many duplicates, it’s still a hell of alot of words!)

Next I hacked together a small python script which would find, for each file, the longest string of Standard Pilish. Code for this can be checkedout from my SVN repository: http://svn.nfitz.net/pilish

Results:

Somewhat disappointingly, the longest of any Pilish string was 8 digits of pi. The vast majority of books had a longest Pilish string of around 3-5 words. See the histogram below (note the logarithmic scale in the y-axis).

Five books achieved this 8-digit benchmark, listed below, with the section of Pilish text bolded:

• The Winning of Barbara Worth, by Harold B Wright (1872-1944)

Dismounting and throwing the reins over his horse’s head he came to her smiling, sombrero in hand. “Buenas dias, Senorita. Please may I have a drink?”

“Certainly, Mr. Holmes ; help yourself.” She pointed to the olla hanging in the shade of the ramada.

• Humphrey Bold- A Story of the Times of Benbow, by Herbert Strang

I was weary of the humdrum life of idling on shore or aimless sailing up and down the channel. The admiral’s was a peaceful mission, and no fighting was expected, but I felt a great curiosity to behold new scenes.

• Captain Cook’s Journal During the First Voyage Round the World, by James Cook (1728-1779)

And I have a great Objection to firing with powder only amongst People who know not the difference, for by this they would learn to despise fire Arms and think their own Arms superior, and if ever such an Opinion prevailed they would certainly attack you, the Event of which might prove as unfavourable to you as them.

• Lectures on Modern History, by Baron John Emerich Edward Dalberg Acton (1834-1902)

One was part of the empire, the other was enclosed in Poland, and they were separated by Polish territory. They did not help each other, and each was a source of danger for the other. They could only hope to exist by becoming stronger. That has been, for two centuries and a half, a fixed tradition at Berlin with the rulers and the people. They could not help being aggressive, and they worshipped the authority that could make them successful aggressors.

• Anne Bradstreet and Her Time, by Helen Campbell (1839-1918)

With the most ambitious of the longer poems–“The Four Monarchies”– and one from which her readers of that day probably derived the most satisfaction, we need not feel compelled to linger. To them its charm lay in its usefulness. There were on sinful fancies; no trifling waste of words, but a good, straightforward narrative of things it was well to know, and Tyler’s comment upon it will be echoed by every one who turns the appallingly matter-of-fact pages…

That last one is the only of the five to have one word of double-digit length, thus covering two digits of pi (‘straightforward = 15 letters = ’15’).

Future Work:

I would like to do a similar analysis of an even larger dataset of more modern language. One possibility is a full archive of Wikipedia. I wonder what is the longest string of unintentional Pilish ever produced?

Another interesting question is how the maximum length of Pilish sections in a document scales with the length of the document, and how well this can be modelled with a simple statistical model such as a Markov Chain.

python makes everything easy

As I was sitting at my desk at work, watching code roll by as my Monte Carlo runs worked, I thought about how nice it would be to go do something else while I waited for data.  An email notifier wouldn’t be enough, as I might want to be away from wifi.  Then I remembered that Bell has an email to text message gateway, number@txt.bell.ca .  In the course of ~10 minutes, I was able to whip up a python script that will send me a short email notifying me that my jobs have completed.  All I have to do is add a line at the end of a script with the python script and the job name, and it will send me a message as soon as the script run completes.  I simply store the password for my local smtp server in ~/.pass, and it fires of texts like magic.  Python makes everything easy.  Code after the jump.