robertmaynard/DaxScheduler.md

## DaxScheduler.md

      
    Raw
  

              DaxScheduler.md
            
          
    Understanding the Dax Scheduler

When Dax schedules a worklet it uses three signatures to determine how and what will be scheduled. The obvious two signatures are the required ControlSignature and ExecutionSignature that is contained in each worklet. The third signature is called the InvocationSignature and it is created when the user calls dax::cont::Scheduler.Invoke(Worklet, … ).
class CellAverage : public dax::exec::WorkletMapCell
{
public:
  typedef void ControlSignature(Topology, Field(Point), Field(Out)); //ControlSignature
  typedef _3 ExecutionSignature(_1,_2); //ExecutionSignature
};

...

dax::cont::Scheduler<> scheduler;
scheduler.Invoke(CellAverage(),geometry,in_field,out_field); //InvocationSignature
###Signatures###

ControlSignature describes the number of arguments the user will be allowed to pass to dax::cont::Scheduler.Invoke, what the type of each argument should be ( Field, Topology, Geometry, etc), what the access behavior is ( In, Out), and
what geometric domain the item maps too ( Point, Cell, etc ).
ExecutionSignature describes how the ControlSignature maps to the actual worklets
signature. Each _N represents that item in the ControlSignature and what position
it represents in the worklet operator() function signature. For Example

  typedef _3 ExecutionSignature(_1,_2); //ExecutionSignature
  float operator()(dax::Vector3 a, dax::Vector4 b) {}
The _3 means the that the third control signature object is going to bind to
the return value for this worklet which is a float value
The ExecutionSignature is also used to represent transformations of the user data that
should happen during in the execution environment while the worklet is running in parallel.
A perfect example is that of Vertices(_N) an execution signature that transforms
the Topology ControlSignature from just being the cell type, to being the actual
vertices of the cell. These transformations are done by dax::exec::arg classes.
It should be noted that a ControlSignature value such as _3 can be used multiple
times in the ExecutionSignature without issue.

InvocationSignature is used to confirm that that the call to dax::cont::Scheduler.Invoke
was passed the same number of arguments as the ControlSignature expects. It
is also used to determine if an argument that is passed in has a valid
mapping to the required type ( Field, Topology, etc ).

Scheduler

Now I am going to go over how the dax::cont::Scheduler uses these signatures
to determine what is going to be executed.
The dax::cont::Scheduler job is to prepare all the required data that is
going to be needed in the execution environment to be ready for transfer. It can
create new Fields, or determine that we should only execute on a subset of the
passed in data. Once the worklet is running the scheduler has no control over
what happens. It is merely pre and post worklet execution work.
First thing that happens is that the Scheduler looks at the worklet types
and uses dax::cont::scheduling::DetermineScheduler to determine the specific
Scheduler implementation to run. These custom schedulers handle the more complicated
worklet types like dax::exec::WorkletGenerateTopology and dax::exec::WorkletInterpolatedCell.
For now I am just going to cover the default implementation that handles
dax::exec::WorkletMapField and dax::exec::WorkletMapCell.


We take the InvocationSignature and confirm that it has the same length
as the ControlSignature. If the lengths don't match we throw a nice
error message.


We construct a dax::cont::internal::binding<InvocationSignature> object
around all the user arguments that have been passed in. The bindings will iterate
over each argument and try to find a valid concept that match the user type
with the ControlSignature requested type (Field, Topology, etc). At this
point we have only constructed the required dax::cont::arg::ConceptMap
specialization for each user argument. See the Control Binding section,
for more documentation on what happens during this process.


We use bindings.ForEachCont to iterate over all the ConcepMaps to
determine the scheduling length for the given worklet. We first match the domains
of the arguments being passed in too the domain of the worklet. So for a Cell
based worklet we only look at Fields that have a Cell Domain Tag in the ControlSignature;
when determining the number of iterations for the DeviceAdapter::Schedule call.
A detailed explanation of how this happens is covered in the Control Binding section.


We use bindings.ForEachCont and dax::cont::scheduling::CreateExecutionResources
functor to call each ConceptMap to allocate memory into the execution environment.
We look at the ControlSignature to determine if we are reading or writing memory
so that we call the proper methods on the user argument.
This doesn't create any of the dax::exec::arg classes, but just allocates
the memory that they will in the future use.


We construct a dax::exec::internal::Functor object that will do all
the execution side binding before we execute the worklet in parallel.
See the Execution Binding section, for more documentation on what happens during this process.


We pass this Functor object to DeviceAdapter::Schedule to actual
be run in parallel on the proper backend.
See the Functor Running section, for more documentation on what happens during this process.


Control Binding

How dax::cont::internal::binding<InvocationSignature> from the user supplied
types to the correct execution items in short is magic. Not a sufficiently advanced technology
which is indistinguishable from magic, it is high grade magic pixie bytes.
Okay in all seriousness here is the high level overview on how we take
the user supplied arguments and create the right execution objects:


MAGIC PIXIE BYTES


The binding class iterates over each user argument and the ControlSignature
at the same time. For each argument it constructs a ConceptMap whose
first template argument is the ControlSignature type ( Field, Topology, Geometry, etc)
and the second argument is the type that the user passed in ( dax::cont::ArrayHandle, int, etc ).
For example here is the specific definition of a ConcepMap implementation
for binding a dax::cont::ArrayHandle to a Field:
namespace dax { namespace cont { namespace arg {
template <typename Tags, typename T, typename ContainerTag, typename Device>
class ConceptMap< Field(Tags), dax::cont::ArrayHandle<T, ContainerTag, Device> >
{
  typedef dax::cont::ArrayHandle<T,ContainerTag, Device > HandleType;
  //Use mpl_if to determine if we are storing a const or non const portal
  typedef typename boost::mpl::if_<
      typename Tags::template Has<dax::cont::sig::Out>,
      typename HandleType::PortalExecution,
      typename HandleType::PortalConstExecution>::type  PortalType;
public:
  typedef dax::exec::arg::FieldPortal<T,Tags,PortalType> ExecArg;
...
};
} } }
Lets look at the template signature of ConcepMap. The goal of the ConceptMap
is to define how to convert the second argument ( ArrayHandle ) to the
Field Concept that will be used in the execution environment. The
typedef dax::exec::arg::FieldPortal<T,Tags,PortalType> ExecArg;
Tells us what object that the Field binding for an ArrayHandle will produce. In
this case it is a FieldPortal. If we look at the ConceptMap for a primitive
type like a float we would see that we are going to create a FieldConstant
object in the execution side.
It is important to remember that ConceptMap goal is to determine the type
of object that will be used in the execution side, and to transfer
any required information from the control side to the execution side.
The execution objects that a ConceptMap has to produce just need to
match the required exec::arg object interface to be used. The
dax::exec::arg::ArgBase is a CRTP class that can be inherited to make
class that obey the required interface. More information can be found
in the Writing Exec Arg section.
Execution Binding

Execution binding is composed of two parts. The execution argument class like
FieldPortal or FieldConstant which I will call ExecArg, and the binding class
like BindDirect or BindCellPoints which describes how the ExecArg will be
used by the worklet.
The most basic binding is BindDirect which means that for each iteration
of the functor we will query the ExecArg with the index we are currently on.
For a more complicated binding like BindCellPoints we have have to query
the ExecArg for each point of the given cell and return a container class
( dax::exec::CellField ) that holds all the field values for the points.
The issue with BindCellPoints is that it was only given the point field and has
no information on the topology that we are currently iterating. This is okay
since for each Binding we pass in the entire signature for all the worklets
parameters as a template signature, and when we construct the Binding object
we pass in a dax::cont::internal::binding<InvocationSignature> that
contains all the ConceptMaps so any Binding can extract a copy of another
arguments ExecArg, which for BindCellPoints would be the Topology argument.
Functor Iteration

At the heart of the scheduling algorithm is the actual iteration of the worklet
over a given range of 0 to N. For each of these values we call dax::exec::internal::Functor
which holds onto the binding object that the '''dax::cont::Scheduler''' created.
What happens is the following:


We are given a value from 0 to N as the parameter to the operator() method.


We create a temporary instance of each ExecArg instead an object call
the argumentsInstance. This currently is required because on shared memory
backends the instance of Functor is shared and we don't want two threads
writing to the same ExecArg. When we create these temporary instances
of each ExecArg it will go through all the ConceptMaps that we have created
and call the GetExecArg() method of each storing the created object.


We call each ExecArg operator() with the given value we had been passed.
the resulting values from this are passed directly to the worklet.


We finally execute the worklet with the values that had been returned by Step 3


We iterate over the ExecArgs calling the SaveExecutionResult() method
on each. This is done so that ExecArgs that return reference objects during Step3
can now save them back properly into the correct memory location.


Writing New ControlSignature Type

Each control structure type ( Field, Geometry, Topology ) has two required
components  that need to be constructed in the dax::cont namespace. After
that is finished you will most likely need to add a new Exec Argument which is covered
in the Writing Exec Arg section.
A ControlSignature Type has two sections, the first being the actual class
that is used as a label used when writing the ControlSignature, and the
ConceptMap that converts user classes to that type.
For Example Say we wanted to create a new Type called Foo. The first step
would be to construct a file called Foo.h in dax/cont/arg/ which had the
contents:
namespace dax{ namespace cont{ namespace arg {

class Foo {};

} } }
The class Foo will only be used in the signature so it should have no implementation
so that compilers have an easier time from removing it entirely when compiling.
Next we have to define the specializations of dax::cont::arg::ConceptMap
that covers the user supported types. In this case we are going only handle
dax::cont::ArrayHandles as the supported type for the Foo signature type.
namespace dax { namespace cont { namespace arg {
template <typename Tags, typename T, typename ContainerTag, typename Device>
class ConceptMap< Foo(Tags), dax::cont::ArrayHandle<T, ContainerTag, Device> >
{
  typedef dax::cont::ArrayHandle<T,ContainerTag, Device > HandleType;
  //Use mpl_if to determine if we are storing a const or non const portal
  typedef typename boost::mpl::if_<
      typename Tags::template Has<dax::cont::sig::Out>,
      typename HandleType::PortalExecution,
      typename HandleType::PortalConstExecution>::type  PortalType;
public:
  typedef dax::exec::arg::FieldFoo<T,Tags,PortalType> ExecArg;
...
};
} } }
Careful observation of the above example shows that we have defined the Exec
Arg object to be FieldFoo, which you can learn how to implement by reading
the Writing Exec Arg section.
This implementation would go into the file FooArrayHandle.h as it is the
implementation for binding Foo to an ArrayHandle.
Lastly you will need to add FooArrayHandle.h to the dax/cont/arg/ImplementedConceptMaps.h
so that all schedulers know about the Foo control type and how to create a ConceptMap
for it.
Writing Exec Arg

The simplest way to create a new Exec Arg is to write a class that inherits
from dax::exec::arg::ArgBase. ArgBase uses the CRTP to make sure that
all derived classes specify all the correct methods to be a valid ExecArg.
Inheriting from ArgBase also makes sure that your class doesn't read in, when
it is marked only as write, and vice versa.
For dax::exec::arg::ArgBase to understand how your class behaves you also
need to write an dax::exec::arg::ArgBaseTraits that lists he following:

If you are writing out (HasOutTag)
If you are reading in (HasInTag)
What is your value type (ValueType)
What are you passing to the worklet (ReturnType)
What are you saving from the worklet (SaveType)

Generally SaveType is equal to ValueType, and ReturnType is ValueType& when
we are writing out and const ValueType when we are reading.
The best way to show how to write a class that inherits from ArgBase is to show
an example, so lets show some code:
template <typename Tags, typename T>
class ExampleExecArg : public dax::exec::arg::ArgBase< ExampleExecArg<Tags, T> >
{
public:
  typedef dax::exec::arg::ArgBaseTraits< ExampleExecArg< Tags, T > > Traits;

  typedef typename Traits::ValueType ValueType;
  typedef typename Traits::ReturnType ReturnType;
  typedef typename Traits::SaveType SaveType;

  DAX_CONT_EXPORT ExampleExecArg(const T& t):MyT(t)
    {
    }

  template<typename IndexType>
  DAX_EXEC_EXPORT ReturnType GetValueForWriting(const IndexType&,
                            const dax::exec::internal::WorkletBase&)
    {
      return MyT;
    }

  template<typename IndexType>
  DAX_EXEC_EXPORT ReturnType GetValueForReading(
                            const IndexType& index,
                            const dax::exec::internal::WorkletBase& work) const
    {
    return MyT;
    }

  DAX_EXEC_EXPORT void SaveValue(int index,
                       const dax::exec::internal::WorkletBase& work) const
    {
    }

  DAX_EXEC_EXPORT void SaveValue(int index, const SaveType& values,
                       const dax::exec::internal::WorkletBase& work) const
    {
    }

  T MyT;
};

//the traits for ExampleExecArg
template <typename Tags, typename T>
struct ArgBaseTraits< dax::exec::arg::ExampleExecArg< Tags, T > >
{
  typedef typename ::boost::mpl::if_<typename Tags::template Has<dax::cont::sig::Out>,
                                   ::boost::true_type,
                                   ::boost::false_type>::type HasOutTag;

  typedef typename ::boost::mpl::if_<typename Tags::template Has<dax::cont::sig::In>,
                                   ::boost::true_type,
                                   ::boost::false_type>::type HasInTag;

  typedef T ValueType;
  typedef typename boost::mpl::if_<typename HasOutTag::type,
                                   ValueType&,
                                   ValueType const>::type ReturnType;
  typedef ValueType SaveType;
};

Writing New ExecutionSignature Type

As stated before the ExecutionSignature is used to represent a transformation of the user data that
should happen during in the execution environment while the worklet is running in parallel.
For an new ExecutionSignature Type to be added we have to add a class that is the
label to use inside the signature, and the binding finding rules to describe what new binding
class should wrap around the Execution Arg instead of the default dax::exec::arg::BindDirect.
First we add a header named after our new ExecutionSignature type to dax/cont/sig/ (yes cont) which
looks like this:
namespace dax{ namespace cont{ namespace sig {

class FooArg {};

} } }
Now we can use the FooArg as part of the execution signature. Now lets presume that
FooArg is like the Vertices tag and but you pass two control postions to it, like
this:
  typedef void ControlSignature( Field(Out), Field(In), Field(In) )
  typedef void ExecutionSignature( _1, FooArg(_2,_3) )
What we have to do is extend dax::exec::arg::FindBinding to handle
this use case. We do so by adding the following:
//specialize on FooArg(_N,_M) binding
template<typename WorkletType, int N, int M, typename Invocation>
class FindBinding<WorkletType,
                  dax::cont::arg::FooArg(*)(dax::cont::sig::Arg<N>,dax::cont::sig::Arg<M>),
                  Invocation>
{
public:
  typedef BindFoo<Invocation,N,M> type;
};