\documentclass[final]{parallel} %\usepackage{epsfig} %\usepackage{graphicx} \usepackage{makeidx} \usepackage{multicol} \usepackage{subeqn} \usepackage{crop} \crop \makeindex % definitions used by included articles, reproduced here for % educational benefit, and to minimize alterations needed to be made % in developing this sample file. \newcommand{\pe}{\psi} \def\d{\delta} \def\ds{\displaystyle} \def\e{{\epsilon}} \def\eb{\bar{\eta}} \def\enorm#1{\|#1\|_2} \def\Fp{F^\prime} \def\fishpack{{FISHPACK}} \def\fortran{{FORTRAN}} \def\gmres{{GMRES}} \def\gmresm{{\rm GMRES($m$)}} \def\Kc{{\cal K}} \def\norm#1{\|#1\|} \def\wb{{\bar w}} \def\zb{{\bar z}} % some definitions of bold math italics to make typing easier. % They are used in the corollary. \def\bfE{\mbox{\boldmath$E$}} \def\bfG{\mbox{\boldmath$G$}} \input{psfig} \begin{document} \bibliographystyle{plain} \chapter[Implementation of a Biologically Realistic Parallel Neocortical-Neural Network Simulator]% {Implementation of a Biologically Realistic Parallel Neocortical-Neural Network Simulator\thanks{Funding for this paper furnished by the Office of Naval Research under multiple contracts.}} \index{Sample!file} \begin{authorline} E. Courtenay Wilson\thanks{Department of Computer Science, University of Nevada, Reno, ecwilson@cs.unr.edu}, Philip H. Goodman\thanks{Department of Internal Medicine, University of Nevada School of Medicine, Reno, goodman@unr.edu}, and Frederick C. Harris, Jr.\thanks{Department of Computer Science, University of Nevada, Reno, fredh@cs.unr.edu} \end{authorline} \section{Introduction} The primary goal of this simulator is to create a novel classifier based on a biologically realistic neocortical-neural network. Parallel processing of this very large-scale, object-oriented simulator is key for approaching real-time simulation of synaptic and neocortical network dynamics. Clustering algorithms applied to the dense cell-connection matrix enable load-balancing and data parallelism by organizing highly connected groups of cells onto a particular node, thus reducing the performance cost of inter-nodal communication. The simulation is accomplished by modeling a whole community of cells within a brain structure and observing the emergent behavior of this system. This modeling is done using fine grain parallelization, as opposed to very small scale cellular networks and coarse grain parallelism, such as that found in NEURON or GENESIS\cite{Neuronal}. The structure of the rest of this paper is as follows: in Section 2 we begin with an overview of the connectivity within the brain and its relevance to our simulation. In Section 3 we present the Object-Oriented design of this simulation. Section 4 follows with an overview and a discussion of how the control flow is implemented, including MPI's role in internodal communication Section 5 wraps up this paper with our Results, Conclusions, and a brief discussion of some Future Work. \section{Biological and Computational Motivations} \subsection{Biological Topology} The computational topology of the cortical simulator is based on a biological model of a mammalian neocortex. The neocortex is organized into functional units called columns, which are made up of multiple layers. Each column and each layer perform given tasks and contain highly connected groups of various cell types. The cell types that make up the columns and layers of the neocortex are heterogeneous and perform various functions. For example, some cell types contain excitatory synapses, which means that their synaptic outputs will stimulate the connected cell to raise its voltage level, thus bringing it closer to firing an action potential. Other cell types, called {\it interneurons}\cite{gwm:opfadogiasitn}, contain inhibitory synapses, and their outputs typically have a dampening effect on connected cells, lowering the voltage of the connected cells, and making it harder for the connected cell to fire an action potential. Each cell type consists of compartments\cite{biophysics}, such as dendrites, a soma, an axon, channels\cite{hmcj:kcrospidohpn}, and synapses. The functions of each are roughly described as follows: The dendrites are responsible for bringing inputs into the soma, these inputs typically come from other cells that have reached threshold and are firing an action potential. The soma is where the integrate-and-fire process takes place--a process which entails the aggregation of all inputs, calculation of membrane voltage, and the decision of whether or not to fire an action potential. The axon is responsible for carrying the output signal to the cells that will receive this signal. The synapses are the contextual filters whose effectiveness is modified based on the timing of the input to each cell. They are also responsible for converting the binary action potential input signal to a resulting analog {\it post synaptic current} (PSC). The synapses are classified as either excitatory or inhibitory. The excitatory PSC is a positive waveform, and the inhibitory PSC is a negative waveform. The channels are responsible for affecting the membrane voltage by accepting or rejecting certain ions. These ion fluxes are triggered by the release of neurotransmitters from the connecting synapse. Certain types of channels will help a cell reach threshold and fire, and other types of channels will dampen this response. The mechanics of the integrate-and-fire process are such that a given compartment within a cell aggregates all of its inputs, calculates the resulting membrane voltage, and, if it is equal to or greater than the threshold for that compartment, outputs a resulting spike shape as the action potential. The spike\cite{mb:pnn} shape is a short burst of voltage, on the order of only seven to ten milliseconds, and ranging from the threshold value to somewhere above positive 40 millivolts. This spike shape triggers the synapses on the connecting cells to release neurotransmitters. This release results in a PSC waveform on the connecting compartment's membrane, thereby beginning anew the cycle of a binary event (the spiking action potential) triggering an analog event (the PSC), which triggers a binary event, and so on. \subsection{Computational Topology} The computational topology is closely modeled after the biological principles mentioned above. The user specifies a template for each segment of the model, with biological principles specified. The segments are labeled as follows: Anatomical Elements (column and layer shell); Physiological Elements (stimulus, channel, synapse, spike shapes); Physiological Constructs (compartment, cell type); Anatomical Constructs (layer, column, brain); and Reports. Certain biomechanics are mimicked through templates rather than an intricate modeling process. For example, the spike shape and PSC waveforms are two such templates that are specified by the user. The choice for making some processes into templates was done to expedite the modeling of very large scale networks. Conversely, other neuron modeling tools, such as NEURON and GENESIS, model these processes explicitly in single neuron models. Thus one has the trade off between network size and computational complexity. The cell/compartment to cell/compartment connectivity is specified by the user as a probabilistic function, where only the compartments within a given cell are connected absolutely. For example, within layer 4, cell\_type1 is connected to cell\_type2 by synapse\_type1 and probability 0.5. Connectivity on all levels of the brain can be specified, or left blank. If no connectivity is specified, the program will run, but no communication between cells will take place. \section{Object-Oriented Design} Because the brain itself is segmented into compartments and individual objects such as synapses, dendrites, and channels, the choice of the object-oriented design matches the biological model. Each object utilizes the Standard Template Library as containers for other objects, and each object encapsulates functionality that is specific to that object only. In this way, the synapse object handles synaptic learning, outputting of PSC waveforms, and Redistribution of Synaptic Efficacy calculations\cite{smt:aafmnrpbopapsst}. Likewise the channel object encapsulates the calculations of channel currents and outputs those currents to the parent compartment. The object-oriented model allows the simulator to model objects generically, changing their results through the input parameters without affecting the underlying object functionality. In this way, we can model other areas of the brain with little computational changes, changing primarily the input parameters. On a computational level, there are several basic forms of objects. Some are containers for other objects and maintainers of administrative data, while others are both containers and state machines. Other objects perform specific functions that are important to the computational side but do not directly effect the biological system. The fundamental types consist of the following objects: synapses, channels, and spike shapes. These are owned by another object, perform specific biological or data-collection functions, and receive input from and output data to their owning object. The spike shape is responsible for giving to its owner object the values for a given indexed timestep. These values mimic the spike shape that a certain compartment may output after reaching threshold and firing. The container objects are ones that are holders for other objects and, in some cases, for administrative data. These objects are responsible for ensuring that each owned object is visited and updated. One of the container objects is the cell object, which is a container for the compartment objects. It is responsible for ensuring that the messages are delivered to the appropriate compartment, whether that message comes from outside the cell or within the cell (from another compartment). Of these contained compartments, only the soma is the minimum required to mimic a point to point model. Another container object is the brain itself. The brain is a container for the virtual global cells list, the stimulus objects, and the report objects. The brain is responsible for ensuring that the stimulus objects are visited (to send data to the cells), that the report objects are visited (to collect data on the cells), that the MessageBus object is visited (to ensure message passing), and that each constituent cell/compartment is visited. The brain object is also responsible for such administrative duties as calculating for how many time ticks the program runs and incrementing the counter on each time tick. The object that is both a container and a state machine is the compartment object. It is a container of such objects as synapses, channels, and spike shapes. It is a state machine in that its membrane voltage is calculated and updated at each time step. This is where the heart of the cortical simulator is located. All the integrate-and-fire routines exist here, and all action potentials are fired from compartment objects to other compartment objects (within cell or outside cell). If there is no input from the contained objects or external sources, the compartment still changes state--it's membrane voltage degrades by a pre-set amount towards resting potential. The compartment is a generic object that switches based on given input parameters. For example, only one compartment object is used to model all of the compartments within the cell--that is the basal dendrites, the apical dendrites, an axon, and the soma. Everything is based on the variables that were specified in the user input file, including whether or not this particular compartment will fire an action potential, and, if so, which spike shape it will utilize. The compartment also contains a list of cell/compartment data, to which cell/compartment it is sending action potentials, and from which cell/compartment it is receiving action potentials. This connection matrix forms the heart of the inter-cell/compartment connectivity and message passing. The other types of objects are those that perform specific functional tasks. The stimulus object calculates a given voltage or current stimulus based on the user-defined choice of types ranging from a linear function, to a pulsed (staircase or constant) function, to a sine function. These functions are designed to mimic signals that are coming in from other parts of the brain as well as to mimic external stimuli (like a voltage clamp). The report object handles the data processing of what to report on, which cell/compartment to receive this report, and at what frequency the report is to be received. The most detailed reporting is done every single timestep, although this is computationally expensive. The FileIO object handles the file input/output in a threaded manner. It outputs the data from a cell/compartment to a given file. This output file is later processed and reformatted into a more user friendly display. The message object is a collection of data that is used in communication between all objects within the simulator. The ownership of the message object (once instantiated), passes from the sender to the receiver. It is the responsibility of the sender to allocate the memory for the message and for the receiver to de-allocate the memory once used. One of the most important functional objects is the MessageBus object. Its detailed model will be discussed in a later section; however, it is responsible for all of the message passing between cells, stimulus and cells, and reports and cells. It encapsulates all of the MPI calls, and, through MPI, it is responsible for all inter-nodal communication. It is utilized at all stages of the simulator, from initialization to simulation end. It is also responsible for synchronizing the globally distributed set of brains, so as to prevent race conditions, deadlock, and starvation. \section{Simulator Implementation} \subsection{Overview} In the brain, there is a high degree of connectivity within columns of highly clustered cells and much less connectivity across column boundaries. The input data file mimics the biological realism of the brain as much as possible by stipulating connectivity on several levels: intra-cell (inter-compartment), intra-layer (inter-cell), intra-column (inter-layer), and intra-brain (inter-column)\cite{ieee:dsl}. The connectivity of cells within a layer, column, or brain is specified by the user as a probabilistic function. Only the intra-cell connectivity is non-probabilistic: a cell either has a specific compartment or it doesn't. The parallel algorithm for the cortical network simulator consists of several steps. The first step is the reading and parsing of the input data file. Once all of the data templates are input and error-checked for biological accuracy, the distribution begins. The distribution algorithm makes a connection matrix based on the connectivity specified in the input data file. A deterministic clustering algorithm is then employed to aggregate groups of high connectivity. If a cell is considered ``empty'' (meaning it is not connected to other cells) and the user has specified the ignoring of empty cells, then it is deleted, and the connectivity matrix is modified to reflect this change. This modification improves the load of computation by ignoring those cells that do not contribute to the overall network of cells within the brain, while mimicking the biological realism of the phase of cell die-off. The cell data are then partitioned so that each node in the cluster has its own portion. This reduces the performance cost of inter-nodal communication by grouping together highly connected cells onto one node. Once the cell distribution map is established, each node instantiates the objects according to the global connection matrix if that object has been designated for that node. The individual cell's connection matrix is created and owned by that cell. Now the program is ready to begin the actual neocortical simulation. The main simulation consists of a brain loop in which all the cell-to-cell communication is handled via a MessageBus object\cite{ieee:petri}, which functions as a router for packing and delivering of the messages. This structure allows us to encapsulate the message-passing paradigm, thus allowing us to swap out our current MPI-based implementation with other communication paradigms. This is a critical issue in porting of this simulator to other hardware platforms. The message that is sent between cells contains two things (1) a static set of data that is consistent for each message and (2) a dynamic set of data that changes depending on the message type. The static data set contains the message type, sending address, the receiving address, and time step (i.e., the message envelope). The dynamic data set contains such information as the membrane voltage values, external stimuli values (current or voltage), or reporting information. When a cell fires an action potential it communicates this event through the MessageBus to all the cells in its connection matrix. The MessageBus then relays these messages to the cells specified. If the receiving cell is off-node, it is the responsibility of the MessageBus to package this in an appropriate way and communicate it to the proper node, at which point the MessageBus on that node forwards it to the local recipient cell. The sending and receiving of messages is done in such a way as to prevent node starvation or deadlock. These new messages are then buffered to be read by the MessageBus on that local node. This whole process occurs for each simulated time tick and is synchronized to prevent a race condition whereby certain nodes can become many time ticks ahead of other nodes in the simulation. The synchronization is important for maintaining biological realism as it allows each cell to aggregate all inputs for each time tick in order to perform its integrate and fire calculations. \subsection{Control Flow Implementation} The control flow of the cortical simulator consists of three major stages: initialization, brain computations, and finally post-processing of the data. Each stage and its constituent parts are discussed in some detail within this section. The initialization stage is handled by the InitializationManager object and consists of multiple functional units. This stage occurs on all nodes within the cluster concurrently with switches for computation that should occur on particular nodes. The first step of initialization is the reading and parsing of the input file. This file contains templates for biological data structures (i.e., cells, channels, synapses, columns, layers, etc.), functional units (such as reports, stimulus), and connectivity. The data from the input file is stored in temporary variables which utilize the dynamic memory allocation of the Standard Template Library vectors. The second step of initialization is the displaying of values to the user. The DisplayObjects object, if requested by the user, will prompt the user to accept/reject the configuration that has just been read in. The third step of initialization is the error checking of the temporary variables. The ErrorCheck object is responsible for examining the data for consistency and biological accuracy. In case of errors in the input, it will display the incorrect variable along with the correct range of values for that variable. The fourth step in initialization is groundwork for parallelization of the simulation. This step is handled by the CreateConnectMatrix object, which is responsible for filling in the global connectivity matrix. CreateConnectMatrix utilizes the connection schemes that were specified by the user and stores this information in the CellManager object. This object holds the groups of cell types, their location in the brain (column \& layer), and their global cell id values. The CreateConnectMatrix object updates each cell list in the CellManager with the constituent cells connections. The fifth step creates the DistributionManager object which uses the connection information now stored in the CellManager to compute the distribution of the cell groups onto the nodes within the cluster. During this process the DistributionManager updates the CellManager with the node number for each cell group. The CellManager can then be used when instantiating the cell objects. The sixth step in initialization is the instantiating of each object from the biological template provided by the user. The MakeObjects object handles this task. Each node in the cluster has a MakeObjects object which is responsible for checking the current machine number, and only making those cells which are situated on that particular machine. The CellManager object is utilized heavily for this task as it stores the machine location for each cell being instantiated. This step creates the data parallelization of the cortical simulator. The global cell list is now a virtual global list, in which its constituent parts are spread out among the different nodes within the cluster. The last step in initialization is the connecting of the cell/compartments. This is handled on each node, where each node fills in the connection matrix for the given cell/compartment based on whether or not it exists on this node. The Synapse objects are then instantiated on the receiving node, and they are then owned by the receiving cell/compartment. The MessageBus is employed at this point to send data to each cell/compartment with the synapse ID values. After the initialization stage is complete, each constituent helper object is deleted. The brain objects on each machine are synchronized before beginning the next stage of the simulation, which is the brain computation. This computation is the same on each node. On each timestep, the brain visits the objects that it contains. These include the stimulus objects (which may or may not send values to cell/compartments), the reports objects (which may or may not send report requests to cell/compartments), the MessageBus (to send and receive messages and pass them along to cell/compartments on this node and on external nodes), and each cell within its local list. These cells then visit each compartment contained within them, which process the integrate-and-fire routines mentioned above. The third and final stage of the simulator takes place once the Brain object has completed its pre-determined number of cycles. This stage consists of using the PostProcessing object to reformat the output data files into a more user friendly context. This process inputs each output file and reformats it into a specified display which could be either a text file or a web-based PHP file. Once this post processing is completed, the simulation deletes all allocated memory and the program terminates. \subsection{MPI and Communication} The MessageBus object is an important object for facilitating communications between objects within each brain. Through the use of MPI\cite{mpi:book,mpi:pacheco,mpi:ref}, our current implementation handles communication with external nodes. The communication scheme of the cortical simulator is best described by the diagram in Figure~\ref{fig:comm-model}. \begin{figure}[h] \centerline{\psfig{figure=com-model.ps,height=2.5in}} \caption{Communication Model} \label{fig:comm-model} \end{figure} The algorithm for preventing deadlock and starvation is based on a simple All-to-all personalized message exchange Each node sends a message at each time step; the MPI element TAG is utilized to distinguish between data messages, empty messages, and multi-part messages. The MessageBus exits this stage only when the sign off has been given for each node within the cluster. In this way, the MessageBus prevents a situation whereby one node in the cluster has not finished sending its messages but the other MessageBuses have finished receiving. The MessageBus uses blocking sends (MPI\_Send) and blocking receives (MPI\_Recv). In order to send a message to an off-node cell, the MessageBus processes the outgoing message queue and formats each message to a particular node into a user defined MPI data type, stores it onto a user defined MPI buffer, and sends this buffer to the designated destination node. Once the message has been sent, the memory allocated by that message object is deleted. On a local level, the MessageBus checks the destination of each message, and if it is the same as the current node, no MPI communication operations are used for the message object to be passed to the particular cell/compartment addressed in the message. The MessageBus also uses a synchronization to create a lock step barrier, so that the brains on different nodes reach the MessageBus at the same time, to process messages in the same order. This barrier prevents a deadlock condition (one MessageBus is sending but no other MessageBus is receiving), as well as preventing a starvation situation (one MessageBus is receiving, but no other nodes are sending). \section{Results, Conclusions, and Future Work} The sequential implementation was finished at the end of the summer of 2000. Once this implementation was completed, it was evaluated and tested for biological realism and accuracy. This was accomplished by comparing our results with published and accepted results for channels\cite{hmcj:kcrospidohpn}, compartments\cite{Neuronal}, and synapses\cite{gwm:opfadogiasitn,smt:aafmnrpbopapsst}. The sequential implementation was then changed into a parallel implementation as described previously, and we are in the process of evaluating this implementation. At this point in our research, we have tested our implementation on two architecture platforms. The first platform is a dual processor Sun Enterprise server with 2GB of shared memory, and the second platform is a Beowulf cluster of 8 Pentium II 400 machines with dual 100 Mbs Ethernet connections to a Bay network switch. On the shared-memory architecture, we have run the simulation with one and two processors and have scaled the number of cells per processor from 40 to 200. On the Cluster we have run the simulation with one, two, and four processors and have also scaled the number of cells from 40 to 200 per node. Connectivity in each of these cases was set at such a level that would stress the implementation and help us determine the architectural limits of each hardware platform. For our tests we chose a cell connectivity of approximately $n^{2}$. Seventy-five percent of the cells were receiving external voltage from the Stimulus object which was set at such a level so as to force an action potential to occur. This stimulus arrived at regular intervals for 60\% of the total simulation time. When the cell receives this stimulus and fires an action potential it then sends a message to each cell to which it is connected which, in turn, causes a cascade of communication. In Figure~\ref{fig:ponderosa} we show the results of our simulation running on the dual processor Sun shared-memory machine, and in Figure~\ref{fig:cluster} we show the results from the Beowulf cluster using the same number of CPUs and cells. \begin{figure} %\centerline{\psfig{figure=ponderosa.ps,height=2.0in}} \begin{center} \input{ponderosa.tex} \end{center} \caption{Brain Time (in seconds) on a dual processor shared memory machine} \label{fig:ponderosa} \end{figure} \begin{figure} %\centerline{\psfig{figure=cluster.ps,height=2.0in}} \begin{center} \input{cluster.tex} \end{center} \caption{Brain Time (in seconds) on our Beowulf Cluster} \label{fig:cluster} \end{figure} It is clear from comparing these results that communication latency is a major factor in performance of our simulation. We have shown an improvement in the performance on a well-connected machine but a decrease on a loosely coupled machine. Therefore, in order to achieve the results we desire, we will need to continue evaluation on an architecture that can support massive communication between the cells. In conclusion, once this simulator is operating with hundreds of thousands to millions of cells, it will allow us to address the following types of questions: What minimal micro-circuit must be replicated to create a functional cortical column? How many such columns must interact to demonstrate emergent behavior, such as the remarkable generalization ability of mammalian brain ``classifiers''? We will also be able to compare brain-like computation to existing artificial neural network and traditional non-neural classifiers in order to address several other challenging problems such as pattern recognition, real-time human gesture recognition, and navigation. %\baselineskip=12pt %\parindent=0pt \bibliography{/staff/fredh/papers/bibdir/parallel,paper} \end{document}