This is a brief description of the main aspects of the SMN algorithm in the context of the SMN software methodology. For a general overview of the structure of SMN (with diagrams) see the SMN ontology. Mathematical details are avoided here wherever possible however a basic overview is given. Also see this chapter of a book that gives a tutorial on the subject. There are also details on the mathematics and you can download the source code for the full details on the algorithm. Also see what SMN is and what SMN does.
System matrix notation (SMN) is a mathematical formalism with which we can represent and animate general systems and general distributed computational processes. It does this using a generalised form of matrix multiplication.
A major benefit of this approach towards system simulation and software development arises because matrix multiplication processes are in essence a collection of parallel processes operating on a shared information space. Hence SMN is ideal for multi-threaded software development and operation on parallel processing machines.
If you are not familiar with matrix multiplication or need a reminder, please see this brief description. So long as you understand how to add and multiply you can understand matrix multiplication – it is easier than a Sudoku puzzle.
Conceptually, at the heart of the SMN algorithm is the iterative equation where v is a vector and M is a matrix. The matrix provides a massively parallel network of information channels that interconnects all of the vector elements. With each iteration the information within the vector flows through the matrix and back into the vector.
If the vector represents system state and the matrix represents system interactions, then when this equation is iterated over and over the system states encoded within the vector evolve according to the system interactions encoded within the matrix.
Depending on the type of the information within the matrix and vector, and the type of iterative equation used to combine them, different scenarios arise.
The scenario from which the SMN software methodology arises uses binary data and functions within the matrix and vector, and a generalised and highly efficient form of matrix multiplication to implement the iterative equation.
Let us consider a simple concrete example, first using standard matrix multiplication. Consider a model of two systems S0 and S1.
Using standard (mathematical) matrix multiplication we have:
However generalised matrix multiplication gives us:
Standard Matrix Multiplication
In the standard form of matrix multiplication, the inner/interaction functions are all multiplication:
and the row/response functions are all summation:
or in general
Generalised Matrix Multiplication
In the generalised form the interaction functions can be any data or function that models how one system interacts with another system.
The response functions can be any function that models how a particular system responds to the incident data and thereby changes its state.
These functions can be any arbitrary function and they can be different for each interaction channel and each system response.
For example above, the function represents S0's experience of itself, represents S0's experience of S1 andrepresents S0's response to its experiences, which results in a change of state represented by .
The SMN engine operates on void* pointers which are untyped pointers to arbitrary binary data, so it doesn't know or care what the data or functions are that it is coordinating, they are all just binary data to it.
It is only within the interaction and response functions that the data has a type and a meaning, perhaps as a character string or a bitmap image or a function that does such-and-such.
In this way SMN is a general simulation engine that can integrate any set of binary data and functions into a complex dynamical system.
The data in the matrix can be any binary data or pointer to an interaction function. It might be a simple attenuation function that causes a system to focus on some systems more than others, or it might be a function that processes the data stream in complex ways.
The response functions can be any function that implements how the system processes the data that is available to it and changes its state according. This includes the state of its input and output interfaces, which are represented within the matrix.
The data in the vector can be any binary data or pointer to any function. It may be a simple character string, or colour code, or segment of HTML or PHP code, or function that sends and receives information to an external process or device.
This latter case is referred to as a sysWrap function because it effectively wraps an external system thus allowing it to be represented within the simulation and to be influenced by the simulated dynamics.
The external system might be a button or dialogue box within a program's user interface, or it might be another whole program, or any electronically controllable device. In this way SMN can serve as the core (kernel) of a program, an operating system, a control system or an embedded system.
SMN is conceptually equivalent to a matrix multiplication process hence, matrices provide a good explanatory framework to illustrate how networks of systems can be modelled. But representing and computing matrices, although able to be done in parallel, is very computationally intensive. For example, 1000 systems would require a 1000 x 1000 matrix and with each iteration the algorithm would need to compute 1,000,000 interaction channels, most of which would result in null interactions because either the systems don't interact at all or even if they do sometimes, there is no information flowing between them in that particular moment. This would be very inefficient.
To efficiently represent the system interconnections the SMN algorithm uses sparse matrices, where only non-null elements are stored. Hence, for example, if the 1000 systems formed a simple loop or circular pipeline, only 1000 interaction channels would need to be represented instead of 1,000,000.
This alone would still be inefficient if all 1000 interactions channels needed to be processed with every iteration because typically, not all channels would be active in any given moment. For example, imagine that a single pulse of information travels around the loop so information flows from one system to another in a serial manner. In this case only one interaction channel would be active in any given moment.
The SMN algorithm uses what is referred to as energy flow processing, where only the interactions that need to be processed in any given moment are processed. Very simply, if a system's state changes the algorithm looks down that system's output interface (matrix column) to see which systems depend on that state, then the algorithm only re-computes those system's states.
Hence in the example of the loop of 1000 systems with a single impulse flowing around it, because SMN uses sparse matrices and energy flow processing the algorithm only processes 1 interaction channel per iteration.
The use of sparse matrices and energy flow processing introduces a little complexity into the algorithm but the computational savings can be immense. It allows the complexity of the SMN process to scale linearly with the complexity of the model.
Of course, if the 1000 systems really were all interconnected and all interacting in every moment then there would be no saving, indeed there would be an extra overhead from using sparse matrices and energy flow processing. In these case the direct approach is more efficient.
However in general most systems that we might care to model have a modular structure, their interconnections are quite sparse and in any given moment only a proportion of the interaction channels are active. For these applications the algorithm is optimal.
If full efficiency is required then even the small overhead can be avoided. Instead of using SMN to manage the system interactions during run-time, all the interaction paths are first modelled using SMN and this is then represented as fragments of binary data and executable code that is interconnected by direct function pointers. This is then directly animated by the CPU and behaves exactly like the SMN model behaves when it is animated by the SMN engine, but there is zero overhead.
This gives the benefits of SMN design and analysis, which allows us to create complex dynamical systems, and it also gives us zero computational overhead. In fact it may often run even faster than conventional code and also be guaranteed bug-proof and fault-tollerant because the entire complex system can be pre-optimised and mathematically analysed in the SMN design phase.
Also, because the approach is a parallel process, where we can even assign a thread to each virtual system. This allows SMN to take full advantage of multi-processor computers and computing clusters.
Whilst the virtual systems can function in parallel, they can also keep shared data in the state vector and private static data within their interaction and response functions, whilst having single threaded style open access to it within a multi-threaded program. All locking and synchronisation issues are handled by the SMN algorithm, hence the systems can be designed without needing to consider these issues but they still result in a multi-threaded program.
Because of these factors the SMN approach can give us greater reliability and efficiency when creating complex multi-threaded software. Hence the SMN algorithm provides a mathematical science and engineering methodology for massively parallel software development and general system design and modelling.
There is a further detail regarding the interaction functions not illustrated above in order to keep the equations simple. That is, the systems can control how they present themselves to other systems and how they observe other systems.
For example, consider people, person A might be very verbose when talking to person B but be very brief when talking to person C. Likewise, person C might listen very closely to person A but person B only catches a word here and there. Hence person A expresses a lot to person B but most of it is lost as entropy because person B isn't paying attention, whilst person A expresses very little to person C but every word makes a difference.
This example illustrates how systems present different interfaces to each other, both in how they encode and transmit information and how they receive and decode it. Hence, a direct interaction channel comprises one system's output interface and another system's input interface.
In SMN a matrix row represents a system's input interface and a matrix column represents it's output interface. The many system's rows and columns are overlapping, i.e. one system's column crosses all other system's rows and vice versa, hence each system can potentially interact with any/every other system.
Each element of the matrix contains both an input and an output function and a system has control over the input functions in its row and the output functions in its column and can dynamically change these.
Each matrix element's input and output functions belong to different systems, except along the diagonal of the matrix where systems interact with themselves.
Whenever a system experiences another system's state (vector element) this state is first processed by the observed system's output function and then processed by the observer's input function. Hence instead of havingas the equation for S0's experience of S1, we have. Here S1's state (v1) is first encoded and transmitted by S1's output interface and this is then received by S0's input interface, along with some data describing the channel itself.
www.Anandavala.info 14th Sept 2008