bbbb (b4) runtime

1. bbbb

The bbbb (b4) runtime is a virtual machine representing programs as an Interaction Net, utilizing OpenSHMEM and OpenMP to apply the inherent parallelism of interaction nets to a given program.

1.1. components

The toolchain consists of 3 parts:

1.1.1. the b4l compiler

The b4l compiler is a Racket program that takes a program in a LISP dialect and compiles it to a .b4ir file, a textual representation of a network. This is an example .b4l program.

lisp
(let xin '(1 2 3 4 5))
(let yin '(5 6 7 8 9))

(defun dot (xs ys) (fold 0
                         (\acc (\x (\y (+ acc (* x y)))))
                         (zip xs ys)))

(defun main () (Io.write (dot xin yin)))

1.1.2. the b4n assembler

The b4n assembler is a C program that shares headers with the runtime. This acts as an intermediary, compiling the textual intermediate representation (a .b4ir) into a .b4n. This way, changes to the internal representation of agents or the graph do not require changes to the b4l compiler.

1.1.3. the b4 runtime

The b4 runtime executes .b4n files, loading them into a net (potentially distributed across OpenSHMEM PEs) and running reductions on active pairs until no more reductions are possible.

1.2. agents

Agents in the b4 runtime are stored as such:

c
typedef struct {
    bool lock : 1;
    agent_type_t tag : 15;
    agent_payload_t payload : 48;
} agent_header_t;

Locks are used to prevent races. These are fine-grained locks, acquired non-blockingly using shmem_atomic_fetch_or.

The tag is an enum, agent_type_t.

c
typedef enum : uint8_t {
    AGENT_CON,
    AGENT_DUP,
    AGENT_ERA,

    AGENT_INT,
    AGENT_FLOAT,
    AGENT_CHAR,

    AGENT_BINARY_OP,
    AGENT_BINARY_OP_PARTIAL,
    AGENT_UNARY_OP,

    AGENT_LAMBDA,
    AGENT_APPLY,

    AGENT_VAR,
    AGENT_EXPAND,

    AGENT_CMP,
    AGENT_CMP_PARTIAL
} agent_type_t;

The payload is also an enum, albeit a fair bit more complex.

c
typedef union {
    int32_t i32;
    float f32;
    char utf8[4];
} agent_payload_32b_t;

typedef enum : uint8_t {
    PLUS,
    MINUS,
    MUL,
    DIV,
    EXP,
    ROOT,
    LOGX,
} agent_bop_type_t;

typedef enum : uint8_t {
    NEG,
    SQRT,
    RECIP,
    LOG2,
} agent_uop_type_t;

typedef union {
    uint64_t raw;

    struct {
        uint16_t _pad16;
        agent_payload_32b_t x;
    };

    struct {
        agent_bop_operand_t 
        agent_bop_type_t bop;
        agent_payload_32b_t op_lhs;
    };

    struct {
        uint32_t _pad32;
        agent_uop_type_t uop;
    };
} agent_payload_t;

1.3. runtime architecture

The runtime is meant to be run on several threads using OpenMP, and eventually support scaling to multiple networked PEs using OpenSHMEM.

1.3.1. the work stealing deque

Each PE has a work stealing deque, that may be remotely popped from or locally pushed to on either end. This deque contains active pairs, representing agents that are ready to interact. The deque must be double ended in order to prevent unbounded recursion: in a recursive template using VAR and EXPAND agents, adding every VAR/EXPAND to the front of the work queue would mean an immediate loop. Instead, VAR/EXPAND is a special case; we push VAR/EXPAND to the back of the queue, and all else to the front. In this sense, it is more akin to a work stealing stack, as interactions will be popped from the front and most interactions will be pushed to the front.

1.3.2. the work loop

Each thread on each PE will cycle through their work loop, defined as such:

  1. Attempt to pop an active pair off of the