Examples

Learning about a library is a lot easier if you have access to some examples. This page seeks to supply these examples in the form of real-life programming problems like the NQueens problem, or the prime sieve of Eratosthenes.

Algorithmically these examples won’t be explained in detail, but we’ll attempt to clarify the use of BSPy in them.

Prime Sieve

This algorithm is a parallel version of the prime sieve of Eratosthenes.

# Import the library
import BSPy
from math import *

# Defining the parallel function which takes a BSPObject as first argument
def spmd(bsp: BSPy.BSPObject, n):
    # Grabbing the cores and own pid as variables
    p = bsp.cores
    s = bsp.pid

    # If this processor is processor 0
    if s == 0:
        # Send the variable `n` to everyone.
        for i in range(p):
            bsp.send(n, i)

    # Synchronise, so the messages get sent.
    bsp.sync()

    # Grab the variable `n` that has just been sent.
    max_n = bsp.move()
    sqrt_n = floor(sqrt(max_n))
    sieveList = Sieve(sqrt_n+1)

    # Generate list of primes this core has to do and comb them
    per_core = max_n / p
    start = max(2, s*per_core) # make sure we don't count 0 and 1
    end = min(max_n, (s+1)*per_core)
    primeList = Comb(sieveList, start = start, end = end)
    primeAmount = len(primeList)

    # Send the amount of primes we found to proc 0.
    bsp.send(primeAmount, 0)
    # Synchronise, so the messages get sent.
    bsp.sync()

    # If this is processor 0
    if s == 0:
        total = 0
        for i in range(p):
            # Add each of the p subtotals to total
            total += bsp.move()

        print("Total:", total)


def Sieve(n: int):
    # Initialize primes array
    primes = [1]*n
    for i in range(n):
        primes[i] = i

    # Start sieving
    foundPrimes = 0
    for i in range(2,n):
        # if i isn't sieved out, discard its multiples
        if primes[i] != 0:
            foundPrimes += 1
            for j in range(2*i, n, i):
                primes[j] = 0

    # Fill primeList
    primeList = []
    for i, x in enumerate(primes[2:]): # Discard the first 2 elements (0, 1)
        if x != 0:
            primeList.append(i+2)

    return primeList


def Comb(primesSieved: list, start: int, end: int):
    # Do some type cleanup
    start = int(start)
    end = int(end)
    # Initialize checklist
    numbers = [1]*(end-start)

    # comb out the non-primes
    for prime in primesSieved:
        # x*primeList[i] - start --> needs to be positive
        pSieveSqrd = prime**2

        # Ensure we we don't try to access weird indicies
        if start > pSieveSqrd:
            # If the start is larger than psquared, define jStart
            # at the next index to cross off
            if start % prime == 0:
                jStart = start
            else:
                jStart = start + (prime - start % prime)
        else:
            jStart = pSieveSqrd

        # Do the sieving
        for j in range(jStart, end, prime):
            numbers[j - start] = 0


    # Go through the sieved list
    primesList = []
    counter = 0
    for i, x in enumerate(numbers):
        if x != 0:
            primesList.append(start+i)

    return primesList


# Enclose BSPy.run()
if __name__ == '__main__':
    n = 10**5
    # Run the function spmd on 4 cores with extra argument n.
    BSPy.run(spmd, 4, n)

NQueens

Another common example is the NQueens problem. This specific algorithm implementation also times how long it takes to find all the solutions.

# Import the library
import BSPy

N = 10
max_number = 10**2
counter = 0

# Note that the NQueens function takes in a BSP object as first argument.
def NQueens(BSP):
    def isSafe(N, board, row, col):
        # Check this row on the left side
        for i in range(col):
            if board[row][i]:
                return False

        # Check upper diagonal on left side
        i = row
        j = col
        while i >= 0 and j >= 0:
            if board[i][j]:
                return False
            i -= 1
            j -= 1

        # Check lower left diagonal
        i = row
        j = col
        while i < N and j >= 0:
            if board[i][j]:
                return False
            i += 1
            j -= 1

        return True

    def solveNQUtil(N, board, col, s):
        # Return true if all queens are placed
        if col == N:
            global counter
            counter += 1
            return True

        res = False
        for i in range(N):
            if isSafe(N, board, i, col):
                board[i][col] = 1
                res = solveNQUtil(N, board, col + 1, s) or res

                board[i][col] = 0

        return res

    def solveNQ(N, s, p):
        board = [[0] * N for x in range(N)]

        i = s
        while i < N:
            board[i][0] = 1
            solveNQUtil(N, board, 1, s)

            board[i][0] = 0

            i += p
        return

    #######################
    ## Start BSP segment ##
    #######################

    # Start timing
    tic = BSP.time()
    # Get processor data
    p = BSP.cores
    s = BSP.pid

    # If we are proc 0, send `N` to all processors
    if s == 0:
        for i in range(p):
            BSP.send(N, i)

    # Synchronise, so that the messages actually get sent
    BSP.sync()
    # Grab the message we just received and store it locally
    boardSize = BSP.move()

    # Solve this processor's part of the NQueens problem
    solveNQ(boardSize, s, p)

    # Synchronise to ensure everyone is done computing
    BSP.sync()

    # Send our solution counter to every processor
    for i in range(p):
        BSP.send(counter, i)

    # Synchronise to actually send the messages
    BSP.sync()

    # Add the sub-totals to the total
    total = 0
    for i in range(p):
        total += BSP.move()

    # Stop the timer
    toc = BSP.time()

    # Only proc 0 needs to print.
    if s == 0:
        print("we found {} solutions in {} seconds.".format(total, toc - tic))


# Note the if statement again.
if __name__ == '__main__':
    BSPy.run(NQueens, 4)