path: root/doc/techreport.org

# meta information for org-mode
#+TITLE: RaSimu technical design document
#+AUTHOR: Jan Huwald
#+EMAIL: jh@sotun.de
#+OPTIONS: H:5 toc:2
#+LaTeX_CLASS: book

* General Data and Computation Structure
** Properties
   The simulation has an open number of properties. A properties value
   is derieved from it's own and other properties' values of the past
   using a fixed rule.
*** Ontological Association
    Each property has an ontological associated type. It is instanced
    for every object of the given type. The type determines further
    under wich circumstances the update rule of the property is called
    and when snapshots of the properties current values are
    stored. The available ontological types and their relations are:

#+ATTR_LaTeX: scale=0.25
#+begin_ditaa OntoTypeDeps.png -r -o -s 2.5
  +--------+     n +--------+     many +---------+
  | Global | ----- | Neuron | -------- | Synapse |
  +--------+ 1     +--------+ 2        +---------+
     1|             1|  1|                1|
      |              |   |                 |
      |many	     |   |many             |1 
 +-----------+       | +-------+  many +--------------+
 | GlobalMsg |       | | Spike |------ | SpikeArrival |  
 +-----------+       | +-------+ 1     +--------------+
                     |many 
                   +-------------+
		   | RandomSpike |
		   +-------------+
#+end_ditaa
 
*** Temporal nature
    All properties of above graphs first row types are continuous, all
    of second row types discrete.

    For discrete properties every single event is stored. Continuous
    properties are only stored at checkpoints. Checkpoints are roughly
    at regular intervals but fine-structured to exactly match the time
    of incoming events, so that a continuous property is only stored at
    moments of modification by an discrete property.

    The value of a continuous property instance (e.g. membrane
    potential of neuron 42) can be accessed for any time, whereas
    discrete properties can not be directly adressed. Instead one can
    only query them based on inequalities or ranges (e.g. get current
    value of oldest spike emitted from neuron 42 before 23s simulation
    time).
*** Dependencies
    A properties value may depend only on a strictly limited number of other values. These are
    determined by the properties type as follows. The dependency is explicitely stated as a
    (Type,Name)-Pair.

**** Discrete Properties
     Each discrete property may only depend on properties whose type is in the same column in the
     graph above. For continuous properties it may only depend on the value at the timepoint of the
     instance creation.

     An alternatve formulation is that discrete properties are events conditionally created by
     properties with common type column.

**** Continuous Properties
     A continuous property may depend on
     - global properties
     - properties of the same type (and instance)
     - discrete properties that are stated in the following table and associated to the instance
       via topology

       |---------------+-------------------------------|
       | Property Type | Available Discrete Properties |
       |---------------+-------------------------------|
       | Global        | GlobalEvent, Spike            |
       | Neuron        | SpikeArrival                  |
       | Synapse       | Spike                         |
       |---------------+-------------------------------|

     If a global type property depends on a spike type property it automatically depends on every
     spike. Contrary, synapse type properties depending on a spike type property will only receive
     the spikes corresponding the networks topology.

**** Circular Dependencies
     The dependency graph may have loops but must be circle free under ommission of all inter-type
     dependencies.

** Parallelization
   - coarse grained :: parallelization using property partitions without inter-partition dependency circle
   - fined grained :: usually single threaded; parallelization within a property partition might be
                      used if the property has no temporal dependency (e.g. mapping one spike value
                      to another)

*** Communiation Primitive
    - coarse grained :: client server with message passing
    - fine grained :: CREW shared memory with a per property heap split into three parts: read only,
                      write only and unused fulfilling the properties:
      1. 2*sizeof(addr_t) <= read barrier <= write barrier <= some constant (like 16G)
      2. barriers are stored in the beginning of the heap
      3. barriers are updated lockless and atomic (one barrier at a time)
      4. barriers may only increase

    The CREW shared memory is implemented using mmap'ed files.

*** Property Partitions
    The properties are partioned into minimal sets of circular dependent properties (idealy each of
    cardinality 1). For each set two interfaces and corresponding programs exist:
    - a reader interface, which reads discrete properties and replays / extrapolates continuous
      properties
    - a writer interface, wich generates (and stores to file) the values used by the reader
      interface

    Additional reader interfaces may exist for discrete properties of an larger than one cardinality
    property partition, if they do not require additional dependencies (wich is usually the case).

*** Rationale
    - maintain cache locality aside allowing an open number of properties
    - avoid the duplication of shared properties wihtin a single node
    - ensure that the shared memory can be emulated in a distributed memory environment with a
      common, lockable filesystem (e.g. NFS, OCFS).

* Implemenation Details
** Distribution Server
*** TODO define basic structure

** Slave
  The slave is a C++ programm wich calculates a (compile time) fixed
  set of properties. Several Slaves share a common database of
  property values using mmap'ed files.
*** mmap\_core
**** TODO test (logic, performance, nfs)

*** Properties
    - PropertyInstance :: Yields access to the value of a current property. Template logic is used
         to deduce the correct container type from the property. It may be instanced as write or
         read container. If writing, it will be backed by a mmap'ed container. If set to read and
         applied to a continuous property, it will only contain the last known value and will not be
         stored persistently.
    - property interaction classes :: Concentrate all methods which are applied on a property:
         evolution of the state, application of incoming and generation of outgoing events.
    - quantor types :: as described above
    - quantor class types :: indicating either discrete or continuous types
    - property lists :: store the the continuous (CPL) and discrete (DPL) properties  of a PropertyComposition
    - PropertyComposition :: hold the collection of properties of a simulation

#+ATTR_LaTeX: scale=0.4
#+begin_dot PropertiesMPLDeps.png -Tpng
digraph dsd {
  AP [ style=filled; label="actual\nproperties" ];
  XPtr [ label="pointer types:\nGlobalPtr\nNeuronPtr\nSynapsePtr\nGlobalMsgPtr\nSpikePtr\nSpikeArrivalPtr" ];
  PI [ label="property interaction:\nContinuousProperty<>\nDiscreteProperty<>" ];
  QUANT [ label="quantor types\nGlobal\nNeuron\nSynapse\nGlobalMsg\nSpike\nSpikeArrival" ];
  QCT [ label="quantor class types\nDiscreteProperty\nContinuousProperty" ];
  XPL [ label="property list:\nCPL<>, DPL<>" ];
  PA [ label="property list actions:\nPLA_Get, PLA_Evolve, ..." ];
  PropertyComposition [ label="PropertyComposition<>" ];

  PI -> { AP; PropertyInstance };
  AP -> { QUANT; PI; XPL };
  QUANT -> { XPtr; QCT };
  XPL -> { QUANT; AP; PA };
  PA -> XPL;
  PropertyComposition -> { XPL };
}
#+end_dot
**** Declaration of a Property
     1. use macro GEN_CP or GEN_DP to create a class for the property, containing it's name,
        storage type, quantor type, default value and (for continuous properties) it's evolution
        method.
     2. use macro GEN_CP_APPLY, ... to create actions depending on events.

You can than bundle the property using the PropertyList to a PropertyComposition which is then
used to execute or analyze the simulation.
**** Methods on Properties / Property List Actions
     All methods applied to properties are encapsulated into property list actions (PLA). Each PLA
     has a pre and a post method. Execution of a PLA instance means to apply it to the entire
     property list: first pre() from head to tail, then post() in the reverse direction. State can
     be stored per property and globally as illustrated below:

#+ATTR_LaTeX: scale=0.2
#+CAPTION: Control (solid) and data (dashed) flow of a property list action
#+begin_ditaa PLA_DataAndInstFlow.png -E -r -o -s 2.5
       +----------------+         other                           
       |  SomeProperty  |      properties                 
       |   +--------+   |      
   ------> | pre()  | -----------> ... ----+   
       |   +--------+   |                  |
       |                |                  |
       |    :           |                  |
       |    | local     |                  |
       |    | state     |                  |
       |    v           |                  |
       |                |                  |
       |   +--------+   |                  |
   <------ | post() | <----------- ... <---+
       |   |        |   |                     +----------------+
   <-=---- |        | <-------=--- ... <--=-- | NeutralElement |
       |   +--------+   |   fold              +----------------+
       +----------------+   state
#+end_ditaa

     It is noteworthy, that the type of the local state depends on the property visited. This allows
     for example to evolve an old value to a new one within pre(), store the new value as a local
     value and apply it in post() to the global data storage, thus not interfere with other
     properties, which depend on the value before evolution[fn::This two-phase update mechanism is
     neccessary to ensure determinism independent of the order and update rule of the
     properties]. It also allows to leave the local state empty for properties which are ignored by
     the PLA.
**** Property Update
     Discrete properties are created once and then remain constant. Contrary, continuous properties
     may be updated by advancing time or incoming events. Both situations are handled by PLAs:
     - PLA\_Evolve :: advance the time of an instance without incoming events
     - PLA\_Apply :: apply an incoming event to an instance and return if an event would be generated
     - PLA\_Generate :: generate the announced event and set the instance the to post-event state

     Because during the simulation an evolve is only called before application of an external event
     and events are only created at the time of an incoming event, these three PLAs are usually
     called together and in the above order.
*** Interfaces
**** Reading
     A Reader interface allows several ways to access the property values.

***** TODO Replay
      - Scope :: property partitions
      - Parameters :: {begin, end, delta} time, callback functions, initial folding pointer

      For each property of the associated partition a callback routine as given. The reader replays
      all properties in temporal ascending order (and without violating causality for coincident
      events). Every time a discrete property instance is generated the corresponding callback is
      executed. For continuous properties' callback this happens at begin time, end time and exactly
      every time delta.

      The callback is given the time, current value of the corresponding property and an additional
      pointer wich might be used to store a state during a folding operation. This pointer's value
      is returned by the previous callback function or set to the initial folding pointer for the
      first execution.

      Instead of a callback function a compile time function (object) might be used, if I have the
      time to implement it.
***** Range
      - Scope :: single properties
      - Parameters :: {begin, end} time

      Let you iterate over all property values within [begin time, end time]. In case of a discrete
      property this gives all instances. In case of a continuous property this gives all values at
      the exact times when it was influenced by an discrete property.

      For continuous properties only forward iteration is possible. For discrete properties backward
      iterating is allowed, too.
****** Extrapolating Range
       - Scope :: single continuous properties
       - Parameters :: {begin, end, delta} time

       Let you iterate over all property values at { begin + k * delta, end : k in {0,...} }. Forward
       only.
****** Structural Constraints
       Depending on the properties quantity type the following structural constraints are available
       to determine wich subsets of the quantity instances are of interest:

      |---------------+----------------------------------|
      | Quantity Type | Constraints                      |
      |---------------+----------------------------------|
      | Global        | all                              |
      | Neuron        | all                              |
      |               | group {X}                        |
      | Synapse       | all                              |
      |               | from neurons {X}                 |
      |               | to neurons {Y}                   |
      |               | from neurons {X}, to neurons {Y} |
      |---------------+----------------------------------|
      | GlobalEvent   | all                              |
      | Spike         | all                              |
      |               | from neurons {X}                 |
      |               | to neurons {Y}                   |
      |               | from neurons {X}, to neurons {Y} |
      | SpikeArrival  | all                              |
      |               | to neurons {Y}                   |
      |---------------+----------------------------------|
****** Associated Ranges
       Ranges may allow "navigation" within the data set by offering to return (thereby newly
       created) associated ranges of the current element of the range. For example when iterating
       over all spikes received by neuron A one may ask for a range giving all spikes sent by the
       sender B of the spike currently in focus.

       Consider the sources for availability.
***** Query
      - Scope :: single properties
      - Parameters :: time

      Return the properties' value at time (continuous property) or at the maximal available
      timepoint before time (discrete property). Using this more often than O(1) within a programm
      should be avoided for efficiency reasons.
**** Writing

*** Memory Mapped Data Structures
    The following figure gives an overview of the structures described in this section and their dependencies.
#+ATTR_LaTeX: scale=0.3
#+CAPTION: Dependencies of data structures. Memory mapped containers are denoted as rectangles, composed data structures as hexagons and indexed data structures as ellipses
#+begin_dot DataStructDeps.png -Tpng
digraph dsd {
  Scalar [ shape="box" ];
  Vector [ shape="box" ];
  Heap [ shape="box" ];
  Checkpoint [ shape="box" ];
  Array [ shape="hexagon" ];
  PriorityQueue [ shape="hexagon" ];
  NeuronProperties [ label="Neuron\nProperties" ];
  SynapseProperties [ label="Synapse\nProperties" ];
  GlobalProperties [ label="Global\nProperties" ];
  SpikeProperties [ label="Spike\nProperties" ];
  SpikeArrivalProperties [ label="SpikeArrival\nProperties" ];

  Scalar ->{ Heap; Vector; SpikeProperties };
  Vector -> { Heap; Checkpoint; SpikeProperties };
  Array -> { NeuronProperties; Checkpoint; SpikeArrivalProperties };
  Checkpoint -> { NeuronProperties; SynapseProperties; GlobalProperties };
  SpikeProperties -> SpikeArrivalProperties;
  PriorityQueue -> PendingEvents;
  Heap -> PendingEvents;
}
#+end_dot
**** MMapped Containers
     The following entities have a corresponding memory mapped file for each of their instances.
***** Scalar
      A scalar is a mmaped integer of arbitrary (compile time determined) size. For parallelisation
      purposes it's value must not decrease. It is used to store bounds for arrays.
***** Vector
      An Vector is the core data structure of rasimu. It is a memory mapped file, containing a
      regular data structure of equally sized elements. The elements have a compile time fixed width
      of $2^n$ bits. An element is retrieved by a nonnegative integer.

      Each array has a potentially unlimited size, but is constrained by the compile time determined
      number of pages allocated via the mmap call[fn:2]. Each array is accompanied by to Scalars:
      the current read and write barrier.

      As syntactic sugar each array has an associated pointer object which could be used for read
      access in any case and for write access if the width of the array elements is equal or greater
      $8b$.
***** Checkpoint
      A checkpoint stores the latest perfect value of a property at regular (compile time fixed)
      time interval. A perfect value is one, which is obtained immideatly after appying a discrete
      event to a continuous property. Compared to storing the properties value exactly at regular
      intervals, that way no superficious time evolution of the value and thus no numerical
      deviation of the stored value from the one used for further computation is possible. This
      allows deterministically stopping and restarting the simulation and is thus core of the used
      replay techniques.

      A checkpoint is implemented as two Vectors, each storing one Array per time slice. The Arrays
      width is compile time fixed. One vector stores the last perfect value of each time slice, the
      other the time at which it occured.
      occured. 
***** Heap
      A checkpointed heap of variable length[fn:3]. It stores the latest state of the heap for each
      time slice. Write access is only allowed to the latest heap - or corresponding to a time
      greater or equal to the last access time. In contrast to a Checkpoint the time point of the
      last modification is not stored.

      When crossing the boundaries between two time slices the Heap copies it's payload to a new
      location. To densely pack all payload instances the payload class has to offer a
      size()-method.
**** Composed data structures
     The following entities can be used as element of the above container data structures. This
     demands that they are copy and default constructable, self-contained and position independent.
***** Array
      A vector is continuous patch of memory containg a fixed number of equal sized elements. Both -
      vector width and element width - are compile time fixed. Array and element width must be of
      the form $2^n$.
***** PriorityQueue
      As seen on TV! A priority queue based on binary heaps.
**** Indexed data structures
     The following entities store the aforementioned properties using the containers above. The
     general principle is that for each ontological type a single index exists, wich allows
     navigating in multiple bodies of the same ontological type - one body per property. The index
     itself may consist of several mmaped containers. Each index offers a specialised allocator to
     allow creation of new elements.
***** Continuous properties
      Storage of continuous properties is implemented using a
      Checkpoint object. For *Global properties* the Vector's element
      is a time scalar. For *Neuron* and *Synapse properties* it is an
      Array of time scalars - for each neuron/synapse the last perfect
      value occured at a different time. The corresponding body of
      each property is structured the same way - Vector of scalar
      values for global properties, Vector of Arrays of scalar values
      for neuron and synapse properties.
***** Discrete Properties
      All discrete properties are stored using Vectors in temporally ascending order accompanied by
      an index which associates each property instance with the time of its occurence. Because each
      neurons frequency is roughly constant, binary searching an element in the index is possible in
      $O(n\log{n})$ time.

      *GlobalEvent properties* have a simple index: an Vector of ascendingly sorted timepoints of
      their occurence. The body is an Vector of the corresponding properties.

      *Spike properties* are stored in temporally ascending order. The index consists of an Vector of
      scalars for each of the following table's properties.

     |--------+-----------+------------------------------------|
     | Type   | Width [b] | Description                        |
     |--------+-----------+------------------------------------|
     | time   |        64 | time point when the spike happened |
     | neuron |        16 | id of the neuron firing the spike  |
     | prev   |        32 | id of last spike of that neuron    |
     | next   |        32 | id of next spike of that neuron    |
     |--------+-----------+------------------------------------|
      
      The spike property body is an Vector with the property values as elements.

      For *SpikeArrival properties* the Spike property index is reused. But the bodies are Arrays
      of SpikeArrival property values. The Array width is set to $2^{\lceil\log\max{fanout}\rceil}$
      so that all spike arrivals corresponding to one spike could be stored in one Array. They are
      thus stored sorted ascendingly in the time of the outgoing spike instead of the spike arrival
      time[fn:1].

***** Pending Events
      implemented as heap of priority queues, wich gives a regular
      snapshot of the pending events
** Properties Definition
   Properties can be defined via the CPP macros explained below, or
   using a model definition DSL, which is translated into these
   macros. The later way is preferred.
*** Available variables
    * td :: time difference since to gapped (only with evolution of
            continuous variables)
    * id :: the id of the thing to calculate
    * all properties of the same quantor class and associated quantor
      classes which are unique
*** Continuous Properties
    A continuous property is defined using the macros GEN_CP,
    GEN_CP_EVOLVE and GEN_CP_APPLY. GEN_CP defines the type and its
    static properties. It takes the quantor type (parameter 1), the
    properties name as C++ type (2) and string (3), the backing C++
    type (4) and its initial value (5). The backing type usually is
    int, float or bool.

    The time evolution of the property is defined using GEN_CP_EVOLVE
    which takes the property name (1) and assigns a RHS expression (2)
    to it. This expression has to calculate the new value of a given
    instance of itself at time $t + td$ using the time delta between
    last update $td$, absolute time of last update $t$ and the
    previous value $self$ of the given $instance$ at time $t$. To get
    values of other properties the macro _CP can be used with a
    property name (1). It can however only be used to get properties
    of the same instance of the property under evolution. If access to
    properties of a different quantor type is neccessary the
    Property_Get template function has to be used. Note that this is
    only allowed for associated quantor types (e.g. accessing a Neuron
    property during the evolution of a Spike property). Properties of
    non-associated instances of any quantor type is prohibited.

    The behaviour under incoming events may be defined using the macro
    GEN_CP_APPLY. It is given the quantor type of continuous property
    (1) receiving the discrete property of the given quantor type (2).
    continuous (2) property. .. TODO (generation of events via 3 bool
    flags, update of value)
    
*** Discrete Properties
    Discrete Properties are more complex in their data dependency. At
    the same time they are fewer in numbers and have a smaller
    implementation burden regarding the range accessors. Thus no
    macros arre given to ease their implementation and the have to be
    defined as template specialisations of .. TODO
** Adding new quantor
   There is no central list of quantors admissible for compile time
   programming, yet. To add a new quantor one has to call several
   macros and create some custom structures:
   * quant_types.hpp: declare quantor via GEN_QUANT_PROP (respectively
     GEN_DQ_PROP) and add to appropriate quantor list
   * add to account in report_spacereq and report_names
   * pointers.hpp: add specialization for Ptr<>

   Depending on the temporal nature of the quantor, additional
   definitions are neccessary:
*** Continuous quants
    * context.hpp: specialization of ContinuousContext
    * to be continued
*** Discrete quants
    * event.hpp: add specialization of Event<>
    * sim_loop.hpp:
      * SimLoop(): add to ctor  of queues, indices
      * run(): add to type switch (macro HT)
      * handleEvent(): add to event creation (macro MGE)
    * context.hpp: spezialisation of DelieveryContext
** Tools
*** simulate
    Run the simulation until a given timepoint. May be terminated with
    C-c without causing data corruption.
*** convert_topology
    Read a plain text topology file and convert it into the rasimu
    storage format.
*** bootstrap
    Bootstrap the simulation by initializing all values (except those
    touched by convert_topology). A global message is created as well
    as a random spike for each neuron.
*** replay
    Replay a given property of given instance for the given interval
    at the given time delta.
*** coarse_replay
    Like replay, but instead of rerunning a part of the simulation
    only the values stored in the regular snapshots are displayed.
*** spike_out
    List all outgoing spikes of a given neuron in a given timespan.
*** report_names
    Lists all properties defined wihtin the current model and gives
    their quantor class.
*** report_spacereq
    The programm report_spacereq calculates the space requirements for
    typical simulation scenarios and the attribution of different
    quantity types to these numbers. It is also an example on how to
    (ab)use metaprogramming to implement compile-time reflection on
    the property definitions.
*** tests
    Named core/test_bla a number of illustrative test cases and
    performance benchmarks for almost all components can be found. The
    tests are successful if their exit status is zero. Beyond
    regression testing these files are useful entry points for
    studying the source code as they stress isolated issues.
* Footnotes

[fn:1] This is a space optimisation, because typical SpikeArrival properties are 1 or 2 bit wide and
thus far smaller than a complete index of spike arrival events.

[fn:2] However this value can be increased during a simulation using recompilation of the simulator.

[fn:3] The length has to be a multiple of one machine word for alignment reasons.