Super Computing Simulation Sure is Simple

A few years ago I had this idea about computing.  I thought, what is the smallest unit of compute power?  Then I thought about trying to define exactly what I meant by this, and how it might be rendered in reality.  Thus was coined the phrase “Computicle”.  Basically, a particle of computation.

A computicle is a basic unit of computation, not defined by NAND gates and transistors, but by pure definition of words and mechanisms.  I have come to believe the essential attributes of a computicle are the following:

  • Ability to receive input
  • Ability to perform some operations
  • Ability to communicate with other computicles

That’s it, and after reading it, it doesn’t sound like it’s worth much of anything. But, it’s amazing how hard it is to clearly define a small group of words precisely enough that they can be used to express a large variety of outcomes. Look at DNA for instance. There are the 4 base pairs, very simple. And there are rules for which combine with which, again very simple. Given those simple rules, and the soup that life stuff is made of and you can express everything from an ant to a zebra, and everything else in between, including plants.

So, do these computicle attributes buy me anything? Well, I’ll take a step back, and look at why I’d even bother pondering such things in the first place.

Increasingly, putting together a program with any level of complexity is getting harder and harder.  I used to be able to program in assembly, way back when it was 6502, or 8088.  I am completely bewildered by today’s machines, and would much rather rely on a compiler to do it for me.  Putting together a hard core web service is a very challenging task.  There are tons of little pieces, and lots of ways to do it.  Even so, it is at that 6502 assembly stage.  The only problem is, the machine has not been completely defined as yet.  We have bits and pieces such as TCP, JSON, HTTP, storage, and compute.  But, they don’t all flow into a coherent “machine” that can be reasoned about and easily programmed.  As such, there are no ways to really express a web service, such that a compiler could come along and optimize the heck out of it.  We’re all programming in assembly.  Even worse, the assembly is specific to the particular platform and service being deployed.  This is back to the cores and tubes days of early computing.

So, rolling forward, I’d like to use the constraints of the computicles to help me define what it is to create a massively parallel thing.  I’d first like to be able to express the “machine” that I am programming, and then use computicles to express that machine in real terms, and then apply a program to that machine.

Well, that’s kind of lofty stuff.  So, I’d better start much smaller.  I have previously played with running Lua instances in separate threads.  One of the things that I left as an exercise for the reader was the ability to communicate between those threads.  Recently I’ve baked thread support into HeadsUp, and gone the next couple of steps to be able to easily create a thread that runs some lua script.  And, the next step is showing how to actually talk to such a running thread.

First of all, within HeadsUp, there is some code to run a lua script.  It is in fact the same code that HeadsUp itself uses to run a script.  It’s just exposed, and has a signature such that it can be used as a startup routine for the CreateThread call.  The signature looks like this:

DllExport int RunLuaScript(void *s);

Great. Now, I already had this object, LuaScriptThread. This object takes a script, in the form of a lua string, and creates a thread, and sends the script to RunLuaScript() to be executed. This is the easiest way of running a bit of Lua script in a separate thread from whatever thread you so happen to be calling from.

Here is an instance of doing such a thing:

local ffi = require "ffi";

require "LuaScriptThread"


local user32 = ffi.load("user32");
local kernel32 = ffi.load("kernel32");

local path = ffi.new("char["..(string.len(package.path)+1).."]");
ffi.copy(path, ffi.cast("char *",package.path), string.len(package.path));

function testLooper()
    local looper = LuaScriptThread(simplechunk, path);

    -- Give the thread a chance to start
    kernel32.Sleep(1000);

    local maxIterations = 0xffff;
    local counter = 1;
    local bRet;
    cmd = C.WM_COMMAND;

    while (true) do
        if counter > maxIterations then
            looper:Quit();
            return ;
        end

        bRet = user32.PostThreadMessageA(looper.ThreadId,cmd,counter,0);
        if bRet == 0 then
            local err = C.GetLastError();
            print(string.format("Error: 0x%x", err));
            kernel32.Sleep(1000);
        end
        counter = counter + 1;
    end
end

testLooper();

There are three parts to this piece of code. The first part is simply concerned with getting the right modules loaded, and creating a copy of the current inclusion path, so it can be passed along to the thread when it starts.

The second part of the program is the creation of the thread of execution:

    local looper = LuaScriptThread(simplechunk, path);

As soon as this line is executed, the OS is creating a separate thread to execute whatever Lua script code is indicated by “simplechunk”. The ‘path’ parameter is being passed along as the single argument to the code. Really, this could be anything at all, including a whole large Lua program in and of itself. This thread startup, and the parameter being passed go hand in hand. Usually, whomever creeates the threads, knows what parameter to pass to the thread on startup. It’s generally a good idea to at least pass the current path, but it completely depends on the code that is to run in the thread.

The last part of this code snippet is concerned with sending messages to the newly created thread. In this case, using PostThreadMessage() will do the trick. On Windows, any thread the starts calling “GetMessage()”, will have a message queue associated with it. This is typically done with apps that have Windows associated with them, but that’s not strictly required. it used to be that you had to create this fake window to get this queue, but these days, it seems to work without having to create that fake window.

PostThreadMessage() is a non-blocking call. You just call it, and you’re done. Whatever you sent will be pulled out of the queue by the thread routine, and they’ll do whatever they want with it.

So, how about that thread routine?

local simplechunk = [[
local ffi = require("ffi");

local path = ffi.string(ffi.cast("char *",tonumber(_ThreadParam)))
package.path = path;

require("win_user32");
local user32 = ffi.load("User32")

require("MessagePrinter")
printer = MessagePrinter();


local msg = ffi.new("MSG")

local bRet = user32.GetMessageA(msg,nil,0,0);

while (bRet ~= 0) do
    printer:Receive(msg);

    bRet = user32.GetMessageA(msg,nil,0,0);
end
]];

Again, represented by a couple of parts. The first part deals with getting the path, which was passed as a parameter (which shows up as _ThreadParam). That parameter is passed as a string representation of a pointer to the data which represents the argument. It has to be turned back into a number, and then cast to a char *, which can then be converted to a string, and then we can set the package.path. This allows us to then load scripts, just like the original program did.

There is one thing to note about this thread instance of the Lua environment. Unlike the HeadsUp Lua environment, this environment does not have anything but the standard libraries loaded into it, not even the core stuff like class, and the like. So, anything you want to use, you have to “require” or ‘ffi.load’ to get.

But, this is a beach head. From this stub, you can do anything, including recursively creating even more threads. In fact, this is a good way for a “service” to make instances of stuff. But, I digress.

The second half of the program contains the GetMessageA() loop. In this case, I’m doing something very simple. Just get the message, and print it out. The message printer is implemented in a class in a separate file, which is ‘require(d)’ to get it in:

require "BanateCore"

class.MessagePrinter()

function MessagePrinter:_init()
end

function MessagePrinter:Receive(msg)
    print(string.format("Message: 0x%x  wParam: 0x%x  lParam: 0x%x",
        msg.message, msg.wParam, msg.lParam));
end

Again, fairly brain dead simple. And here, I start to see the constraints of computicles expressing themselves. The MessagePrinter might be a computicle. It receives data, and does something.

The thread routine is the same, it receives data, and it does something.

One thing that would help here is to standardize the “receives data” part of things. In this example, I’m using two different mechanisms. In one, I’m using PostThreadMessage() to send data to a computicle. In another, I’m calling the “Receive()” method on an object. In both cases, I’m essentially communicating the same information, just using different communications mechanisms.

Well, that’s easily standarizable. Let’s first encapsulate the data in some payload, which could be defined as:

typedef struct {
    int size;
    char *data[1];
}payload;

Or something like that. The idea being, whatever data you’ve got, you can pack into a data structure, which tells how big the data is.

After you’ve stuffed the buffer using whatever means available, you’re ready to send the payload off to somewhere. Well, “To Somewhere” could mean many different things. It could be a routine running on a thread, in a process, on an OS, on a machine, in a vault, in the US, or it could be something across the internet. Clearly, some form of addressing needs to occur. The internet has IPV4, but that only gets you halfway there, depending, and that’s the wrong kind of address when I’m communicating with threads within the same process.

Hmmm, what to do… Well, there needs to be an addressing mechanism, so I’ll just wish it into existance. Now, I need a message dispatch mechanism. The message dispatcher will take the address, and the payload, and ensure the payload gets to the address. So, the generalized communications flow looks like:

construct payload
get address of recipient
deliver payload to recipient
[rinse repeat]

Pretty simple in theory, and actually, pretty simple in implementation as well I think.

Now, an interesting thing begins to happen to my program. Payloads can represent protocols. There’s no reason the protocol has to be connected to the transport mechanism… I can talk TCP/IP between threads in a process, without involving the networking stack in any way. As long as I have a payload packer that knows how to pack TCP/IP packets, and a transport that knows how to talk TCP/IP, it can work.

Hmmm, that’s interesting. I can easily implement “Ping” between two threads. Just as easily, or perhaps easier, than I can do it between internet nodes. Well, isn’t that cheerful! And if I can implement these low level protocols, then I can implement higher level protocols as well, because they simply layer atop these lower ones.

OK. Now to the sweet Jesus moment. If I’ve got these simple computicles, which can communicate using a variety of mechanisms, then I can simulate my distributed cloud based service? Why yes, and why not? It’s a royal pain to try and simulate a distributed services that is based in 8 different countries around the world, without actually deploying it for real. I’d like to be able to simulate the latencies, redundant packets, packet loss, down links, and all the rest. Well, with my little computicles, I might begin to have a chance.

Similarly, I want to simulate a deployment of a large scale services. Let’s say 100 nodes, even spread accross 8 data centers. Then I want to do a live update, and take some nodes down in the process.

Oh, and while I’m at it, of course I want to be able to visualize what the heck is going on without much fuss.

Is this total fantasy? Well, at least I’ve nailed down the running of Lua script in a thread, and communicating with it thing. Now it’s a matter of implementing some more intelligent computicles to string together a grammar which can express some machine configurations. Then I’ll be cooking with gas.

Advertisements

4 Comments on “Super Computing Simulation Sure is Simple”

  1. Levi Pearson says:

    I’ve been reading through your entire thread of luajit development with great interest. I have grand dreams of doing stuff like this, but I end up spending more time reading about things than doing them. 🙂

    Anyway, thanks to that fault of mine, I recognized your “computicle” idea as a form of the Actor Model of computation which was first published by Carl Hewitt and others in 1973. It was developed into a foundational model of computation, much like lambda calculus and the Turing machine. It’s also similar to Alan Kay’s original vision of ‘object oriented’ programming, except messages are asynchronous and computation of actors takes place concurrently rather than the way synchronous message sends sequentialize computation in object systems.

    The Actor Model was also one of the inspirations for the Scheme programming language (specifically its notion of first-class continuations, which can be used to implement something like an asynchronous message send via a synchronous call) and also later and more literally implemented by Joe Armstrong’s Erlang language, which was used to great effect in some of Ericsson’s heavy-duty multi-processing telecom switches. Erlang has a lot of cool infrastructure built on top of the actor idea that you might want to take a look at. You might also be interested in looking at the Wings3D CAD program, which is implemented in Erlang.

    • I’m glad this is proving to be of some use to you.
      Yes, the Actor model is what I’m headed towards. I think we’re at an interesting juncture in computing these days. Nowadays, a ‘computicle’ as encapsulated in the $24 nano router I just purchased from TP-Link, is not only the software, but the actual hardware as well. This thing is smaller than your traveling laptop mouse, and yet it has 32Mb of RAM, and enough of a CPU and communications hardware to act as a router. surely that little box is an Actor if I ever did see one!

  2. […] have written about the “computicle” concept a couple of times in the past: Super Computing Simulation Sure is Simple The […]

  3. Islandia says:

    When I originally commented I clicked the “Notify me when new comments are added” checkbox
    and now each time a comment is added I get three
    emails with the same comment. Is there any way
    you can remove people from that service? Appreciate it!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s