Skip to content

Kernel Linkage Modifiers

Jump to bottom Edit New page
Jonathan Beard edited this page Jan 2, 2017 · 38 revisions

Still really rough, start by just filling in operators that will exist or do currently exist and what they should do. Will add descriptions and formal specs shortly. Starting with the C++ section.

Definitions

  • Link - Connection between two compute kernels, can be through any type of medium (e.g., shared memory, heap, TCP, PCIe, RDMA, etc.). By definition it doesn't matter. There are however modifiers (manipulators in C++ streams) to modify this behavior and force certain things to happen.
  • Kernel - An object defined by the user or from a library that extends raft::kernel or one of its sub-classes.

C++

We'll assume that the left hand side that isn't always shown, contains a map operator like this:

raft::map m;
m += /** something that returns a kpair or compatible struct for the map to consume **/

the map operator takes in a pair of kernels (kpair) which can be a linked list internally that is a list of compatible compute kernels strung together with one of the operators that we list below. All compute kernels are of course expected to be able to be executed independently, and all state must be passed into the kernel either by value or the kernel must have enough knowledge within its constructor to make a copy (RaftLib kernels must contain all the state, see kernel interface spec).

All the compute kernel link operators listed below will use compute kernels a, b, and c as examples without instantiating them. The specific operations, along with functionality expected and pre-post conditions are given.

Basic Link Operator

a >> b

This operator links two compute kernels. a and b can operate synchronously, asynchronously, or any combination thereof.

Conditions:

  • a and b extend raft::kernel or one of its sub-classes.
  • a is assumed to have a single output port. b is assumed to have a single input port. If either breaks this condition than an exception of AmbiguousPortAssignmentException.
  • a and b are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Chain Link Operator

a >> b >> c

The basic link operator can be extended to N kernels in a chain, provided they meet some conditions (listed below). The overall chain returns a kpair object which is then fed to the raft::map container object.

Conditions:

  • a, b, and c extend raft::kernel or one of its sub-classes.
  • a is assumed to have a single output port (note, no condition is placed on its input port). b is assumed to have a single input and output port. c is assumed to have a single input port (note, no condition is placed on the output ports). If any kernel in the chain breaks this condition than an exception of AmbiguousPortAssignmentException.
  • a and b are assumed to have compatible output and input ports respectively, as are b and c (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Named Port Link Operator

a[ "out" ] >> b[ "in" ]

When kernels have more than one output and input port, the basic operator won't quite do (see conditions). To fix this we must use the brackets operator (which is an overload on the kernel class). The bracket operator is context dependent in that its meaning changes depending on the direction of data flow. Given the example above, the first bracket operator references the output port structure of kernel a to specify the port out. The bracket operator on the second compute kernel b references the input port structure of the kernel b to specify the input port in.

Conditions:

  • a and b extend raft::kernel or one of its sub-classes.
  • a is assumed to have an output port named out, otherwise a PortNotFoundException is thrown.
  • b is assumed to have an input port named in, otherwise a PortNotFoundException is thrown.
  • a and b are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Dual Named Link Operator Chain

a[ "out" ] >> b[ "in" ][ "out" ] >> c[ "in" ]

When kernels have more than one output and input port, the basic operator won't quite do (see conditions). As with the previous named link operator, we must use brackets (which is an overload on the kernel class). The bracket operator is context dependent in that its meaning changes depending on the direction of data flow. The named link operator chain extends this to input and output ports using two sets of brackets. Given the example above, the first bracket operator references the output port structure of kernel a to specify the port out. Moving to kernel b, the first bracket operator with the string in references the port by that name from the input port container of kernel b. The second bracket operator of kernel b references a port with the name out of from kernel b which is linked with the following link operator to the port named in from the kernel c.

Conditions:

  • a and b extend raft::kernel or one of its sub-classes.
  • a is assumed to have an output port named out, otherwise a PortNotFoundException is thrown.
  • b is assumed to have an input port named in, otherwise a PortNotFoundException is thrown.
  • a and b are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Static Split-Join Operator

a <= b >= c

This operator is a convenience operator designed to make building larger topologies faster and easier. The split operator or <= maps N output ports from kernel a to N duplicates of kernel b which are created by the runtime dynamically. Within the user-supplied input, after kernel b there is a join operator or >=. This join operator specifies that the duplicates of kernel b are to be linked to a single kernel c. The precondition is that the number of output ports on kernel a matches the number of input ports on kernel c. For example, if a has five output ports and c has five input ports then the runtime will duplicate b four additional times to have 5 copies of b to link between a and c.

Conditions:

  • a, b, and c extend raft::kernel or one of its sub-classes.
  • b further implements the CLONE() function by placing the macro in its header file.
  • a is assumed to have N output ports of the same type (note, no condition is placed on its input port). b is assumed to have a single input and output port. c is assumed to have N input ports (note, no condition is placed on the output ports). If any kernel in the chain breaks this condition than an exception of AmbiguousPortAssignmentException.
  • the out-edge count of a must match the in-edge count of c
  • a, b, and c are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Static Split/Fork Operator

a <= b

Similar to the full split-join syntax above, this naked split operator or <= specifies that the output ports of a are to be distributed to duplicate copies of kernel b. The conditions are similar to the full split-join as well.

Conditions:

  • a and b extend raft::kernel or one of its sub-classes.
  • b further implements the CLONE() function by placing the macro in its header file.
  • a is assumed to have N output ports of the same type (note, no condition is placed on its input port). b is assumed to have a single input port (note, no conditions are place on the output port of b). If any kernel in the chain breaks this condition than an exception of AmbiguousPortAssignmentException.
  • a and b are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Static Join/Reduce Operator

a >= b

Similar to the full split-join syntax above, this naked join operator or >= specifies that the input ports of b are to be distributed to duplicate copies of kernel a. Said another way, this means that N a kernels are to be linked to a single b with N input ports. The conditions are similar to the full split-join as well.

Conditions:

  • a and b extend raft::kernel or one of its sub-classes.
  • a further implements the CLONE() function by placing the macro in its header file.
  • a is assumed to have a single output port (note, no conditions are placed on the input port of a). b is assumed to have N input ports of the same type (note, no condition is placed on its output port). If any kernel in the chain breaks this condition than an exception of AmbiguousPortAssignmentException.
  • a and b are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented

Static Split-Join to Kernel Set

a <= raft::kset( b, c ) >= d

The previous split join modifiers have specified a single type of compute kernel to split and join to. The kernel set enables extending that to the more generic case where kernel a has N output ports, not all of the same type (previous examples required that). In the example above kernel a is required to have two output ports that match the type for b and c, in order of declaration (within the kernel, this order is also the order of assignment, e.g. is assigned to b, is assigned to c. The same order of assignment applies to the inputs to kernel d.

Conditions:

  • a, b, c, and d extend raft::kernel or one of its sub-classes.
  • a is assumed to have N output port (note, no conditions are placed on the input port of a). d is assumed to have N input ports (note, no condition is placed on its output port). If any kernel in the chain breaks this condition than an exception of AmbiguousPortAssignmentException.
  • The kernel set container (raft::kset) is expected to have N kernels that extend raft::kernel, as shown in the example the kernel set contains kernels b and c.
  • Each linked kernel, including those implicitly linked via the split-join operators to the kernel set, are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.
  • Kernels from kernel a are linked to kernels within the kernel set (raft::kset) in order of declaration, e.g., if out-1 is defined first in kernel a and kernel b is the first kernel (from left to right) given as a parameter to the kernel set (raft::kset) then a link is created between out-1 of kernel a and the single input port of kernel b.

Status:

  • Implemented in dev branch, not yet complete.

Out-of-Order Stream Modifier

a >> raft::order::out >> b;

The raft::order::out stream modifier (manipulator) is added in-line with the stream to tell the runtime that the order of the items arriving to b from a doesn't matter. In this case the runtime is free to duplicate a and b. There are however limitations/conditions:

Conditions:

  • a and b extend raft::kernel or one of its sub-classes.
  • a is assumed to have a single output port. b is assumed to have a single input port. If either breaks this condition than an exception of AmbiguousPortAssignmentException. NOTE: you can add the bracket operator to specify a specific port to meet this condition.
  • a and b are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.
  • for the raft::order::out specifier to enable duplication of kernel a, then kernel a must have an input port that also is specified by the user to be out-of-order, or the user must input a kernel that extends raft::reduce between the raft::order::out as in:
a >> raft::order::out >> raft::reduce >> b;
  • for the raft::order::out specifier to enable duplication of kernel b, then kernel b must have an output port that also is specified by the user to be out-of-order, or the user must input a kernel that extends raft::split between kernel a and the raft::order::out as in:
a  >> raft::split >> raft::order::out >> b;

Status:

  • Implemented

Out-of-Order Stream Modifier Chain

a >> raft::order::out >> b >> raft::order::out >>  c

Conditions:

  • a, b, and c extend raft::kernel or one of its sub-classes.
  • This example assumes a single output port on kernel a, a single input and output port on kernel b, and a single input port on kernel c. It makes no assumptions about the number of input ports for kernel a or the number of output ports for kernel c. This example can be extended with the brackets syntax shown in previous examples to name specific ports to link which enables usage of kernels for a that have more than one output port, likewise for c.
  • b can be parallelized or not, at the discretion of the runtime.
  • a and c will not be parallelized in this example, however they could be if the incoming and outgoing links are specified as raft::order::out.
  • b must not access file IO directly, only via provided RaftLib kernels or via designated accessor functions, otherwise IO cannot be guaranteed to be free of race condition.
  • a, b, and c are assumed to have compatible types on all linked ports (see previous condition), otherwise a PortTypeMismatchException is thrown.

Status:

  • Implemented, only single kernel in between two raft::order::out stream manipulation operators. TODO, implement better single entry single exit (SESE) so we can put more kernels in between the two raft::order::out operators.

Modify System Stream Manipulation

Note: the case below is but one way to set the type of process...you can set the virtual memory space or the other details...TODO, add in the enum specifies as well and the template requirements.

a >> raft::manip< raft::parallel::thread, raft::vm::partition >::value >> b

This construct an also be used in combination with other operators like this:

a >> raft::manip< raft::vm::partition >::value <= b

which specifies a split from N output ports of kernel a to multiple clones of kernel b that each have their own virtual memory space.

Conversely the other static operator also applies here

a >> raft::manip< raft::vm::partition >::value >= b

where the virtual memory space is now unique to clones of a which are connected to N input ports of kernel b.

There are two ways to modify the way raft::kernel objects run. The first is mentioned within the kernel interface section. The second is the inline stream modifier/manipulation objects. These are handy, but sometimes get more complicated than simply using the wrapper object method.

The modifiers that can be used as parameters to the raft::manip struct are as follows:

/**
 * NOTE: sizeof( manip_vec_t ) * CHAR_BIT == 64 for most systems, so 64 states total
 */
/** raft::parallel **/
namespace parallel
{
    enum type : manip_vec_t { system = 0  /** do whatever the runtime wants, I don't care  **/,
                              thread      /** specify a thread for each kernel **/, 
                              pool        /** thread pool, one kernel thread per core, many kernels in each **/, 
                              process     /** open a new process from this point **/,
                              NPARALLEL };
    
}
/** raft::vm **/
namespace vm
{
    enum type { flat = NPARALLEL        /** not yet implemented, likely using segment  **/, 
                standard                /** threads share VM space, processes have sep **/, 
                partition               /** partition graph at this point into a new VM space, platform dependent **/ }; 
}
} /** end namespace raft **/

Conditions

  • Exceptions will be thrown for multiple raw manipulators in succession within a stream. The correct way to use multiple manipulators is using the raft::manip struct by accessing the value of multiple modifiers combined.

Status:

  • Partially implemented in dev branch. TODO, finish, finalize needed options.
Add a custom footer
Add a custom sidebar
Clone this wiki locally