Posted by virantha on Thu 28 September 2017

Part 3 - Building a Fast Event-Driven Simulator for Concurrent Systems of Hardware Processes Using Curio and Python 3.6

This is the third in my series on using Curio to build an event-driven simulator for hardware processes. The first two parts can be found here: Part 1, Part 2. We're going to use the simulator framework to implement a distributed and concurrent hardware palindrome checker in less than 50 lines of code.

1   Palindrome checker

Let's define what the checker must do as follows:

  • The input string is a sequence of characters that arrives one by one.
  • With each character's arrival, the palindrome checker must output a boolean representing whether the sequence seen so far is a palindrome or not.
  • As an example, if the sequence "abbab" is sent in (left-most character first), then the checker should output True, False, False, True, False.
  • For generality and scalability, the checker must be composed of N processes (where N is the length of the input sequence) that each use O(1) storage(memory).

2   A solution

One way to approach such a problem is to think about it recursively. Let's say that we're about to receive the k th character, and we know something about the k-1 sequence containing a palindrome or not. Can we immediately determine whether the new sequence with the k th character is a palindrome?

It turns out that we can, if we keep track of what the first character we saw is. The new sequence formed by adding the k th character is a palindrome if and only if this new character is identical to the first character, and the remaining sequence book-ended by these is also a palindrome.

Palindrome recursive formulation

Here's some pythonic pseudo-code that implements such a recursive solution:

def is_palindrome(s):
    if len(s) <=1:    # A zero or one character string is a palindrome
        return True
    else:
        first = s[0]
        last = s[-1]
        return (first==last) and is_palindrome(s[1:-1])

3   A concurrent process

Now, how can we implement such a solution using a set of processes that communicate with each other via channels? In essence, all we do is unroll all the calls in the recursive construction above into a set of sequentially connected processes! (you can think of it as expanding out the call stack).

Let's start with a simple process I will call Pal, shown below. It has, on the left side, an input port C on which it receives a sequence of characters, and an output port Ans which sends out whether the last received character caused a palindrome to be formed or not. It then passes the character received out on Cr and receives an answer on Ansr which is True if the sequence to the right is a palindrome or not.

Palindrome recursive formulation

This process will implement the pseudo-code above, like so:

from curio import run
from chp import *

class Pal(Process):
    C: InputPort
    Ans: OutputPort
    Cr: OutputPort
    Ansr: InputPort

    async def exec(self):
        # Do the first char (so we store it)
        first = await self.C.recv()
        is_palindrome = True
        await self.Ans.send(is_palindrome)

        while True:
            x = await self.C.recv()
            is_palindrome = (x==first and is_palindrome)
            self.advance_local_time()
            await self.Ans.send(is_palindrome)
            await self.Cr.send(x)
            is_palindrome = await self.Ansr.recv()

First, I import the framework defined in the previous article (I'm calling it chp.py, and you can download it in the gist at the end of this article)

Then, I define the Pal process as a subclass of a Process and specify its input and output ports to match our figure above. Then, I implement the pseudo-code in the exec coroutine method. The code outside the while True statement implements the base case where the length is 1; each time a character is received, the answer is True. Then, for each new character received, I can compute whether the new sequence is a palindrome by comparing the first value seen to the current value, and AND ing with whether the previous sequence was a palindrome. The result is sent out on Ans.

Then, the code implements the recursive call by propagating the new character to the remainder of the sequence on the right, and receiving its result on Ansr.

4   The environment

At this point, we need to implement a Process to supply the characters in the sequence to be checked. Here's the Env (environment) process:

class Env(Producer):

    R: OutputPort
    A: InputPort
    def __init__(self, name, string):
        super().__init__(name)
        self.string = string

    async def exec(self):
        for i in range(len(self.string)):
            await self.R.send(self.string[i])
            is_palindrome = await self.A.recv()
            self.message(f'{self.string[:i+1]} - {is_palindrome}')
            self.advance_local_time()

Remember to subclass from Producer if you have a process like this that generates values unconditionally. You can initialize this process with the string to be checked. In the exec coroutine, the process repeatedly sends out each character of the string, leftmost first. It receives a result (True if a palindrome) and then prints a message.

5   Instantiate the system

Now, let's instantiate the environment, and set of processes for a sample string. Here, we're going to check the string 'A man a plan a cat a ham a yak a yam a hat a canal Panama' (minus the spaces, of course!)

async def system():
    string = 'amanaplanacatahamayakayamahatacanalpanama'
    env = Env('env', string)
    pals = []
    for i in range(len(string)):
        pals.append(Pal(f'pal[{i}]'))


    connect(env.R, pals[0].C)
    connect(env.A, pals[0].Ans)
    for i in range(len(string)-1):
        connect(pals[i].Cr, pals[i+1].C)
        connect(pals[i+1].Ans, pals[i].Ansr)

    await run_all()

run(system(), with_monitor=True)

We instantiate one Env process, and then one Pal process for each character in the input string. Then we connect up the processes, and call run_all.

6   Let's run it!

Here's the complete code that we've built so far on top of our framework (only 44 lines of code!):

from curio import run
from chp import *

class Pal(Process):
    C: InputPort
    Ans: OutputPort
    Cr: OutputPort
    Ansr: InputPort

    async def exec(self):
        # Do the first char (so we store it)
        first = await self.C.recv()
        is_palindrome = True
        await self.Ans.send(is_palindrome)

        while True:
            x = await self.C.recv()
            is_palindrome = (x==first and is_palindrome)
            self.advance_local_time()
            await self.Ans.send(is_palindrome)
            await self.Cr.send(x)
            is_palindrome = await self.Ansr.recv()

class Env(Producer):

    R: OutputPort
    A: InputPort
    def __init__(self, name, string):
        super().__init__(name)
        self.string = string

    async def exec(self):
        for i in range(len(self.string)):
            await self.R.send(self.string[i])
            is_palindrome = await self.A.recv()
            self.message(f'{self.string[:i+1]} - {is_palindrome}')
            self.advance_local_time()

async def system():
    string = 'amanaplanacatahamayakayamahatacanalpanama'
    env = Env('env', string)
    pals = []
    for i in range(len(string)):
        pals.append(Pal(f'pal[{i}]'))


    connect(env.R, pals[0].C)
    connect(env.A, pals[0].Ans)
    for i in range(len(string)-1):
        connect(pals[i].Cr, pals[i+1].C)
        connect(pals[i+1].Ans, pals[i].Ansr)

    await run_all()

run(system(), with_monitor=True)

Just run python palindrome.py to execute it, which will give you the following output:

T:0: env.0 - a - True
T:200: env.0 - am - False
T:400: env.0 - ama - True
T:600: env.0 - aman - False
T:800: env.0 - amana - False
T:1000: env.0 - amanap - False
T:1200: env.0 - amanapl - False
T:1400: env.0 - amanapla - False
T:1600: env.0 - amanaplan - False
T:1800: env.0 - amanaplana - False
T:2000: env.0 - amanaplanac - False
T:2200: env.0 - amanaplanaca - False
T:2400: env.0 - amanaplanacat - False
T:2600: env.0 - amanaplanacata - False
T:2800: env.0 - amanaplanacatah - False
T:3000: env.0 - amanaplanacataha - False
T:3200: env.0 - amanaplanacataham - False
T:3400: env.0 - amanaplanacatahama - False
T:3600: env.0 - amanaplanacatahamay - False
T:3800: env.0 - amanaplanacatahamaya - False
T:4000: env.0 - amanaplanacatahamayak - False
T:4200: env.0 - amanaplanacatahamayaka - False
T:4400: env.0 - amanaplanacatahamayakay - False
T:4600: env.0 - amanaplanacatahamayakaya - False
T:4800: env.0 - amanaplanacatahamayakayam - False
T:5000: env.0 - amanaplanacatahamayakayama - False
T:5200: env.0 - amanaplanacatahamayakayamah - False
T:5400: env.0 - amanaplanacatahamayakayamaha - False
T:5600: env.0 - amanaplanacatahamayakayamahat - False
T:5800: env.0 - amanaplanacatahamayakayamahata - False
T:6000: env.0 - amanaplanacatahamayakayamahatac - False
T:6200: env.0 - amanaplanacatahamayakayamahataca - False
T:6400: env.0 - amanaplanacatahamayakayamahatacan - False
T:6600: env.0 - amanaplanacatahamayakayamahatacana - False
T:6800: env.0 - amanaplanacatahamayakayamahatacanal - False
T:7000: env.0 - amanaplanacatahamayakayamahatacanalp - False
T:7200: env.0 - amanaplanacatahamayakayamahatacanalpa - False
T:7400: env.0 - amanaplanacatahamayakayamahatacanalpan - False
T:7600: env.0 - amanaplanacatahamayakayamahatacanalpana - False
T:7800: env.0 - amanaplanacatahamayakayamahatacanalpanam - False
T:8000: env.0 - amanaplanacatahamayakayamahatacanalpanama - True

And success! It's remarkable how little code it took to accomplish this kind of simulation.

You can find the complete runnable code including the framework (Python 3.6 and up!) in this gist.

7   Summary

In this article, I've gone over an example of how to simulate a concurrent hardware system based on message passing between sequential processes using the framework we built in the first two articles (Part 1, Part 2) of this series. As you can see, it's really quite simple to set up and execute new processes that can implement non-trivial systems very quickly. Perhaps at some point I'll get around to porting the sensor network processor I designed in grad school into this framework, but as you can see, there really is no limit to the amount of complexity you could try to model with this type of simulator.

© Virantha Ekanayake. Built using Pelican. Modified svbhack theme, based on theme by Carey Metcalfe