Multi-Core vs Multi-Threaded

If a program is multi-threaded, it does not mean that it is suitable for multi-core. Multi-threaded programs are (were) written to synchronize between themselves. And to synchronize between themselves, they use various locking mechanisms such as mutexes, spin locks (with in kernel), semaphores etc. For most user level programs (for example, those that use pthreads), whenever a thread wants to synchronize, it would try to acquire a lock. If a lock is already held, then the acquiring thread would go to sleep in a queue. Sleeping means kernel taking over control, doing a context switch, running a scheduling algorithm to find out the best candidate to run and running it.

In the case of a single CPU or a CPU with a single core, this is necessary because without this, another thread cannot run and release the lock. But in case of multi core CPU, the thread may be running on another core, while the thread on the current core is being put to sleep. It may get ready sooner because the other thread might have released the lock. This way, on a multi-core CPU, context switching poses lot of overhead that the scalability is not linear, but sub-linear. That is, the kernel comes into way too much for multi-threaded programs with syncrhonization that the performance begins to hurt after adding some cores.

Robert Graham at ErrataSec has a very nice article on multi-threaded vs multi-core programs. He mentions that the performace of a system peaks at 4 cores and begins to decline after that.

And the comments section mentioned about “Erlang” which works very well for the multi-core platforms. Should take a look at it once.

Some very important points to note from that post:

  • Unable to increase clock speeds, chip companies have been adding extra logic to increase the throughput – like multiple instructions per clock cycle, multiple cores etc.
  • Multi-threaded programs are not multi-core ready.
  • For multi-core, we need more independent execution, rather than mutually synchronizing models.
  • Avoid sharing as much as possible.
  • Do a “Divide and Conquer” w.r.t sharing – that is maintain own states, and merge them/join them when needed to get the required state.
  • Use lock free versions of data structures. Use stuff such as RCU.
  • Two basic models in multi-core: pipelining and worker thread models. Former is like a assembly line, while the latter is like a bunch of robots doing everything from start to end. When there is something to share, put a pipeline stage there. When work can be done independently, worker thread model is desirable.

Data Alignment and Memory Accesses

IBM’s developerworks has an article on data alignment and these are some of the facts worth noting:

  • Some processors completely lack the support for unaligned data access.
  • Complex hardware jugglary is needed to support unaligned data access.
  • Some processors trap to CPU on such accesses (PPC does so for 64-bit floating point access) and the OS does the labor to load the register with proper data.
  • Whether they support or not, I guess the address bus that runs from CPU to memory just does not contain the lower “n” address bits depending on the memory access granularity.
  • PPC does support 32-bit unaligned data access.
  • Aligned memory access is a must for atomicity purposes. Failing to do so, could lead to synchronization problems and corruption. Can this aligned memory spawn across two pages? Is it possible?

The N-Queens Problem

The N-Queens Problem goes as follows: In a NxN square chess board, place all the queens so that they cannot kill each other – technically, it means no two queens can be in the same row/column/diagonal. As they say, part of the problem is solved by properly (mathematically or otherwise) phrasing the problem.

What does it mean to say the two queens are in the same row/column/diagonal? If we take $latex¬†(r1, r2 .. r8)$ to be the row numbers of the queen for the columns 1 to 8, then for any i,j¬†such that i¬†is not equal to j, then if ri not equal to¬†rj, it means that the two queens in question are not in the same column and same row. But how to make sure they are not in the same diagonal? Note that (ri, i)¬†represents the co-ordinate for a queen on the chessboard. Two queens are in the same diagonal if one of the following is true: ri + i = rj + j or rii = rj – j. I took a 3×3 square and worked out to understand this.

Once these conditions are met, then it is more or less straight forward to do the actual check – loop over all values of column and row – if there is any failure, backtrack and start fresh with new values. Backtracking is one of the most elegant (may not be efficient) solutions to this problem.

A slightly related problem is detecting cycles in a di-graph (or a simple graph for that matter): This again takes a node, puts it in the list and tries to find its neighbors and adds them to the list, when it sees any neighbor (to be added) as the initial node, there is a cycle and it is noted. I will shortly come up with code for both of these problems.


What I Learned From edX

Been studying “Introduction to Computer Science and Programming with Python” on edX. Reached through midterm. Learned/Realized the following:

  • Been very bad at testing, in writing extensive unit test cases
  • is very lazy in writing tests, thinking about tests


Here is the scrabble program:

# Problem #1: Scoring a word
def getWordScore(word, n):
    Returns the score for a word. Assumes the word is a valid word.

    The score for a word is the sum of the points for letters in the
    word, multiplied by the length of the word, PLUS 50 points if all n
    letters are used on the first turn.

    Letters are scored as in Scrabble; A is worth 1, B is worth 3, C is
    worth 3, D is worth 2, E is worth 1, and so on (see SCRABBLE_LETTER_VALUES)

    word: string (lowercase letters)
    n: integer (HAND_SIZE; i.e., hand size required for additional points)
    returns: int >= 0
    score = 0
    for i in word:
        score += SCRABBLE_LETTER_VALUES[i]

    score = score * len(word)

    if len(word) == n:
        score += 50

    return score

# Problem #2: Make sure you understand how this function works and what it does!
def displayHand(hand):
    Displays the letters currently in the hand.

    For example:
    >>> displayHand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    for letter in hand.keys():
        for j in range(hand[letter]):
             print letter,              # print all on the same line
    print                               # print an empty line

# Problem #2: Make sure you understand how this function works and what it does!
def dealHand(n):
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    numVowels = n / 3
    for i in range(numVowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
    for i in range(numVowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
    return hand

# Problem #2: Update a hand by removing letters
def updateHand(hand, word):
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not modify hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)

    # dictionary, contains the hand after dealing with the word
    modifiedHand = hand.copy()
    for i in word:
        modifiedHand[i] = modifiedHand[i] - 1
    return modifiedHand

# Problem #3: Test word validity
def isValidWord(word, hand, wordList):
    Returns True if word is in the wordList and is entirely
    composed of letters in the hand. Otherwise, returns False.

    Does not mutate hand or wordList.
    word: string
    hand: dictionary (string -> int)
    wordList: list of lowercase strings
    if word not in wordList:
        return False

    wordDict = getFrequencyDict(word)
    for i in wordDict.keys():
        if wordDict[i] > hand.get(i, 0):
            return False

    return True

# Problem #4: Playing a hand

def calculateHandlen(hand):
    Returns the length (number of letters) in the current hand.
    hand: dictionary (string-> int)
    returns: integer
    return sum(hand.values())

def playHand(hand, wordList, n):
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    * The user may input a word or a single period (the string ".") 
      to indicate they're done playing
    * Invalid words are rejected, and a message is displayed asking
      the user to choose another word until they enter a valid word or "."
    * When a valid word is entered, it uses up letters from the hand.
    * After every valid word: the score for that word is displayed,
      the remaining letters in the hand are displayed, and the user
      is asked to input another word.
    * The sum of the word scores is displayed when the hand finishes.
    * The hand finishes when there are no more unused letters or the user
      inputs a "."

      hand: dictionary (string -> int)
      wordList: list of lowercase strings
      n: integer (HAND_SIZE; i.e., hand size required for additional points)
    # Keep track of the total score
    totalScore = 0
    # As long as there are still letters left in the hand:
    while calculateHandlen(hand) > 0:
        # Display the hand
        # Ask user for input
        input = raw_input('Enter word, or a "." to indicate that you are finished: ')
        # If the input is a single period:
        if input == '.':
            # End the game (break out of the loop)
        # Otherwise (the input is not a single period):
        elif not isValidWord(input, hand, wordList):
            # If the word is not valid:
            # Reject invalid word (print a message followed by a blank line)
            print "That is not a valid word. Please choose another word"
        # Otherwise (the word is valid):
            currentWordScore = getWordScore(input, n)
            totalScore += currentWordScore
            # Tell the user how many points the word earned, and the updated total score, in one line followed by a blank line
            print '"%s" earned %d points. Total: %d points' % (input, currentWordScore, totalScore)
            # Update the hand 
            hand = updateHand(hand, input)           
    # Game is over (user entered a '.' or ran out of letters), so tell user the total score
    print "Total score: %d points." % totalScore

# Problem #5: Playing a game

def playGame(wordList):
    Allow the user to play an arbitrary number of hands.

    1) Asks the user to input 'n' or 'r' or 'e'.
      * If the user inputs 'n', let the user play a new (random) hand.
      * If the user inputs 'r', let the user play the last hand again.
      * If the user inputs 'e', exit the game.
      * If the user inputs anything else, tell them their input was invalid.
    2) When done playing the hand, repeat from step 1    
    currentHand = {}
    while 1:
        key = raw_input("Enter n to deal a new hand, r to replay the last hand, or e to end game:")
        key = key.lower()
        if key == 'e':
        elif key == 'n':
            currentHand = dealHand(HAND_SIZE)
            playHand(currentHand, wordList, HAND_SIZE)
        elif key == 'r':
            playHand(currentHand, wordList, HAND_SIZE)
            print "Invalid input, try again"

# Build data structures used for entire session and play game
if __name__ == '__main__':
    wordList = loadWords()
    playHand({'n':1, 'e':1, 't':1, 'a':1, 'r':1, 'i':2}, wordList, 7)



Here is the python version of the hangman, one of the problem sets in the edX course:

# Load the list of words into the variable wordlist
# so that it can be accessed from anywhere in the program
wordlist = loadWords()

def isWordGuessed(secretWord, lettersGuessed):
    secretWord: string, the word the user is guessing
    lettersGuessed: list, what letters have been guessed so far
    returns: boolean, True if all the letters of secretWord are in lettersGuessed;
      False otherwise
    for i in secretWord:
        if i not in lettersGuessed:
            return False

    return True

def getGuessedWord(secretWord, lettersGuessed):
    secretWord: string, the word the user is guessing
    lettersGuessed: list, what letters have been guessed so far
    returns: string, comprised of letters and underscores that represents
      what letters in secretWord have been guessed so far.
    guessedWord = ""
    for i in secretWord:
        if i in lettersGuessed:
            guessedWord += i
            guessedWord += " _ "

    return guessedWord

def getAvailableLetters(lettersGuessed):
    lettersGuessed: list, what letters have been guessed so far
    returns: string, comprised of letters that represents what letters have not
      yet been guessed.
    for i in "abcdefghijklmnopqrstuvwxyz":
        if i not in lettersGuessed:
            availableLetters += i

    return availableLetters

def hangman(secretWord):
    secretWord: string, the secret word to guess.

    Starts up an interactive game of Hangman.

    * At the start of the game, let the user know how many 
      letters the secretWord contains.

    * Ask the user to supply one guess (i.e. letter) per round.

    * The user should receive feedback immediately after each guess 
      about whether their guess appears in the computers word.

    * After each round, you should also display to the user the 
      partially guessed word so far, as well as letters that the 
      user has not yet guessed.

    Follows the other limitations detailed in the problem write-up.
    wordLen = len(secretWord)
    numGuesses = 8
    guessedLetters = ""
    print "Welcome to the game, Hangman!"
    print "I am thinking of a word that is " + str(wordLen) + " letters long"
    while numGuesses > 0:
        availableLetters = getAvailableLetters(guessedLetters)
        print "-------------"
        if isWordGuessed(secretWord, guessedLetters):
            print "Congratulations, you won!"
        print "You have %d guesses left." % numGuesses
        print "Available letters: " + availableLetters
        guess = raw_input("Please guess a letter: ")
        if len(guess) > 1:
            print "Please enter only one letter"
        guess = guess.lower()
        if guess not in availableLetters:
            print "Oops! You've already guessed that letter: " + getGuessedWord(secretWord, guessedLetters)
        elif guess in secretWord:
            guessedLetters = guessedLetters + guess
            print "Good Guess: " + getGuessedWord(secretWord, guessedLetters)
            guessedLetters = guessedLetters + guess
            print "Oops! That letter is not in my word: " + getGuessedWord(secretWord, guessedLetters)
            numGuesses -= 1

    if numGuesses == 0:
        print "Sorry, you ran out of guesses. The word was " + secretWord

# When you've completed your hangman function, uncomment these two lines
# and run this file to test! (hint: you might want to pick your own
# secretWord while you're testing)

secretWord = chooseWord(wordlist).lower()