Execution Model

RaftLib implements a data-flow/stream processing execution model. Each RaftLib application begins with the same main thread as the application executes from. RaftLib applications specify independent sections of code by containing the code within kernel constructs (each is a sub-class of raft::kernel). Each kernel can be thought of as a component connected to the outside world by ports or wires. Each port has directionality, for RaftLib either input or output. Complex applications can be built from composing kernel components into more complex graphs. A kernel has as its only link to outside data/state (aside from the constructor and specially denoted objects) is through these ports defined by the programmer via the constructor. This port-centric interface means that the application developer doesn't have to care about the substrate that provides the connection, only that each kernel is connected in a topology that implements the desired application. Each kernel can be executed sequentially or in parallel, completely asynchronously or synchronously depending on the runtime and hardware available.

Giving the programmer an interface that frees them from low level details of resource mapping/allocation/etc. lets them focus on the algorithm and not placement/optimization. The feedforward and explicit syntax (user specified ordering) enable lock free parallelism as well, which frees the programmer from having to think about how data is transferred, again, freeing them to focus on the algorithm. Execution order of any given raft::kernel sub-class cannot be guaranteed outside of the data-flow path defined by the programmer through links (i.e., given kernels a,b,c the order of execution of a then b then c can never be guaranteed, only that the data from a will always flow to b, and the data from b will always flow to c if that is the linkage specified by the programmer).

With RaftLib's model, the programmer creates objects that extend raft::kernel. These objects are added to a raft::map object. The runtime can choose to execute them in separate processes, threads, thread pools, or fibers (green threads/user-space threads). This execution can be multi-node (not currently implemented in GitHub version) or single node. Yet additional features that can be added include GPGPU and FPGA support (email @jonathan-beard if interested). Basically a RaftLib kernel can execute on any resource to which executable code is available (or can be compiled). In RaftLib, kernels can migrate from one resource to another on the fly (with a few exceptions, and of course locality of data is also a huge consideration).

The link type of RaftLib must be completely agnostic to the application topology specified, and only decided once execution resources have been chosen by the runtime. Links implement a generic FIFO interface which is flexible enough to be implementable for almost every possible link type. Buffer sizing is also guaranteed to be sufficient for the execution (i.e., no need to attempt to size links). The buffer is guaranteed to have at least two entries of the type size specified for the port (there are min/max limits set within the run-time at compile to prevent the off-chance of a run-away buffer allocation). The runtime itself optimizes the buffering capacity (dynamically sizing the allocation up/down using various optimization strategies).

The runtime should allow submap objects with multiple potential graph topologies for a specific task (e.g., multiple search kernels). These can be nested within other submap objects, or added to a larger raft::map object. The raft::map container is not designed to be nested, however there could be multiple raft::map containers defined within a given program and they can execute concurrently if the raft::map.barrier() function is used. The raft::map.exe() function should be used to block at the end of an application for each defined map so that the main thread waits until all child threads have executed and shut down.

Parallelism

• Modality Agnostic - RaftLib enables the programmer not to care how or where each compute kernel is run. The specification for compute kernels is designed to force the programmer to build tasks which encompass all the state necessary for execution. This means that the runtime is free to run the code that is the task in any schedule-able unit available. Currently RaftLib supports running kernels (sub-classes of raft::kernel) as standard POSIX threads, user-space fibers on multiple OS schedule-able thread pools, multi-process (separate virtual memory space), and (currently available by request only) both FPGA and GPGPU computation.
• Automatic/Explicit Parallelism Mix - Through building compute kernels and linking them via iostream-like operators the programmer tells the runtime data dependencies. Once these dependencies are known, the runtime chooses how best to parallelize the application (the runtime could choose any combination of threads/processes). It is designed to enable research into online modeling techniques (which are fed back into the open source version after validation/testing). Deciding when and where to run a particular kernel, is a complex task (the scope of which is outside this specification, however there is much relevant information in this thesis).
• Parallelism Model - RaftLib doesn't force the user into a single type of parallelism, all are implicitly or explicitly supported with the streaming/dataflow model.
  • fork-join - Compute graphs can be constructed that enable single line programming of fork-join applications using either the static split-join operator or the out-of-order stream modifier.
  • pipeline - Using the simple link operator and others, complex pipeline applications can be produced that enable job-shop or pipelining of operations. For example, given three "jobs" (a, b, c) that are dependent on their natural ordering: b can execute as soon as data is available from a, c can execute as soon as data is available from b. This execution can be done entirely in parallel by the runtime.
  • Map-Reduce - Map-Reduce style is really no different than fork-join except the name is different. Map-Reduce implies a temporary storage for each worker thread which is then reduced (written-to) to follow-on workers until a result is produced. The data-flow model embodied by RaftLib is a super set of Map-Reduce. Anything that can be written for Map-Reduce can be re-cast as a data-flow or RaftLib application. It should also be noted that the temporary storage, that is a hallmark of Map-Reduce, is embodied by the output streams rather than explicit copying of data.
  • data - Simple data parallelism is supported through many RaftLib operators, including efficient in-place usage of data where possible.
  • task - Multiple heterogeneous operations can take place in a RaftLib application graph that are either done in parallel across the same set of data or in a pipeline fashion across data as it is produced.