diff options
Diffstat (limited to 'doc/techreport.org')
| -rw-r--r-- | doc/techreport.org | 525 |
1 files changed, 525 insertions, 0 deletions
diff --git a/doc/techreport.org b/doc/techreport.org new file mode 100644 index 0000000..9fc65fe --- /dev/null +++ b/doc/techreport.org @@ -0,0 +1,525 @@ +# 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. |