# 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.