\chapter{Internal Data Structures}
\label{KernelStruct}
\index{Internal Data Structure}
\thispagestyle{empty}

The kernel needs numerous data structures to administer and display
the network. The kernel has to display the units, links and sites (the
{\em static} component), and to save the functions and
connection weights of the units (the {\em dynamic} component). A
symbol table is used to handle all the names and types associated with
the units which are defined by the user. The allocation of data
structures is done in large blocks of several hundred or even
thousands of single structure components. This chapter describes all
the relevant data types in detail.


\section{Unit Array}
\index{Internal Data Structure!Unit Array}
\index{Unit!Array}

The units and all their components are stored in the unit array. The
data type `array' was selected for storing the units, because of its
short access time. When the array is filled up by requests from the
user interface, the memory management automatically requests a new,
bigger array from the operating system. The pointers to the structure
components are reallocated, and the old empty array is returned
to the operating system.


\begin{figure}[htbp]
  \begin{center}
      \begin{minipage}{\textwidth}
          \screendump{0.8}{kernel_figs/NetStruct.ps}
      \end{minipage}
\caption{Internal network data structures (simplified)}
\label{NetStruct}
  \end{center}
\end{figure}


Each element of the unit array has the following components:

\begin{itemize}
\item {\em Out} stores the output value of the unit

\item {\em flags} contains information for the memory management and
the topological type of the unit (see chapter\ref{UnitFlags})

\item {\em lun} the logical unit number

\item {\em lln} the logical number of the layer the unit belongs to

\item {\em *ftype\_entry} points to the internal representation of the
unit type, if a prototype exists for this unit

\item {\em Aux} saves temporary values needed by internal kernel
functions (e.g.\ backpropagation and topological sort)

\item {\em TD} saves values needed for time delay networks

\item {\em act} contains the activation of the unit

\item {\em i\_act} saves the initial activation, used to reset the
net

\item {\em bias} contains the threshold of the unit

\item {\em value\_a, value\_b, value\_c} general purpose elements for the
                                      learning functions 

\item {\em olddelta, newdelta} error values in recurrent networks

\item {\em actbuf} an array for storage of 10 miscellaneous values

\item {\em *out\_func} points to the output function

\item {\em *act\_func} points to the activation function

\item {\em *act\_deriv\_func} points to the derivation function of the
                              activation function

\item {\em *act\_2\_deriv\_func} points to the second derivation
                                 function of the activation function

\item {\em *unit\_name} points to the unit name, a string in the
symbol table

\item {\em subnet\_no} contains subnet membership information

\item {\em layer\_no} contains the location of the unit in a
multilayer network

\item {\em unit\_pos} stores the position of the unit in the network

\item {\em *sites} points to a linked structure of input functions or
connections
\end{itemize}

The internal representation of the network is displayed in figure
\ref{NetStruct}.
\index{Internal Data Structure!Figure}

\section{Sites}
\index{Internal Data Structure!Site}

\begin{figure}[hbt]
  \begin{center}
      \begin{minipage}{\textwidth}
%          \screendump{0.8}{kernel_figs/SiteList.ps}
          \epsfbox{kernel_figs/SiteList.ps}
       \end{minipage}
\caption{Site list}
\label{SiteList}
  \end{center}
\end{figure}
\index{Site!List (Figure)}

\index{Site!Data Structure}
The site data structure was designed to handle the input functions of
the unit. The sites are constructed as a linear linked list. Several sites
\index{Site!Array}
are grouped in an array (site array), each containing several hundred
sites. The site arrays are also connected by a linked list. Thereby,
empty, no longer needed, arrays can be freed.

The internal representation of a site has three components:

\begin{itemize}
\item {\em *links} is a pointer to the input connections (links) of
the site.
  
\index{Site!Table}
\item {\em *site\_table} is a pointer to the so called {\em site
table}. The site table contains information about the input function
and the name of the site.
  
\item {\em *next} points to the next site of the unit. The list is
terminated by NIL.
\end{itemize}


\section{Links}
\index{Internal Data Structure!Link}

\begin{figure}[htb]
  \begin{center}
      \begin{minipage}{\textwidth} 
%         \screendump{1.0}{kernel_figs/LinkList.ps}
          \epsfbox{kernel_figs/LinkList.ps}
      \end{minipage}
    \caption{Link list}
    \label{LinkList}
  \end{center}
\end{figure}
\index{Link!List (Figure)}


\index{Link!Data Structure}
The links make up the connections of the units. The direction of the
internal pointers of the link data structure is from the target unit
(destination unit) to the source unit (origin unit). Note that this is
reversed from the direction of the links in the neural network (which
run from source to target unit). This approach allows the efficient
storage of the network structure with a minimum of memory. However,
the memory needed to store big nets is still the limiting factor. For
a net with 10.000 units with a connectivity of 20\%, 20 million
connections have to be stored, requiring 230 megabyte of memory. In
comparison, the fraction of the memory used to store all other
components is negligible.

The structure of a link is quite similar to that of a site:
\begin{itemize}
\item {\em *to} points to the source unit of the link.

\item {\em weight} contains the connection weight.

\item {\em value\_a, value\_b, value\_c} general purpose elements for the
                                      learning functions 

\item {\em *next} points to the next connection of the same target
unit (terminated by NIL).
\end{itemize}

Like sites, the links are grouped in linked arrays which are
handled by the SNNS memory management routines.



\section{Network Memory Management}

When a network is loaded or constructed interactively, the memory
management always has to supply enough units. As already mentioned,
the user doesn't have to care about memory allocation and
deallocation. During the interactive manipulation of the net, the user
can change or delete whole parts of the net. The empty components are
grouped in a linked free storage list for later reuse. This is also
true for tables like the symbol table. There, identical names
(identifiers) are stored only once. A reference counter decides
whether an entry can be freed on a delete operation or not. An
exhaustive garbage collection is performed when the whole net is
deleted.


\subsection{Link/Site Arrays} 
\index{Network!Memory Management!Link Array}
\index{Network!Memory Management!Site Array}
\index{Link!Array!Data Structure (Figure)}
\index{Site!Array!Data Structure (Figure)}

The memory management is presented in figure~\ref{LinkArrays} with the
example of link arrays. Each first entry is used for backward links.
The data structure of site arrays is similar.


\begin{figure}[htbp]
  \begin{center}
      \begin{minipage}{\textwidth}
          \screendump{1.0}{kernel_figs/LinkArrays.ps}
      \end{minipage}
    \caption{Link arrays}
    \label{LinkArrays}
  \end{center}
\end{figure}
\index{Link!Array}

\subsection{Symbol Table}
\index{Network!Memory Management!Symbol Table}
\index{Symbol Table (Figure)}

The symbol table administers the identifiers of the units, sites and
unit prototypes. An entry in the table is deleted when the reference
counter is zero. Figure~\ref{SymbolTable} shows the symbol table with
linked empty entries.


\begin{figure}[htbp]
  \begin{center}
      \begin{minipage}{\textwidth}
          \screendump{0.9}{kernel_figs/SymbolTable.ps}
      \end{minipage}
    \caption{Symbol table}
    \label{SymbolTable}
  \end{center}
\end{figure}


\section{Unit Flags}
\index{Network!Memory Management!Unit Flag}
\index{Unit!Flag}

The simulator computes the topological position (topological type) and
the current state of the unit with the help of the unit flags. The
topological type is important for the teaching and propagation
algorithms. With certain status bits, the state of the unit in the
network is checked. The flags are stored as bit patterns in the unit
array.  Figure~\ref{UnitFlags} shows the correspondence between bits and
flags of the unit entry.

\begin{figure}[htbp]
  \begin{center}
      \begin{minipage}{\textwidth}
          \screendump{1.0}{kernel_figs/UnitFlags.ps}
      \end{minipage}
    \caption{Unit flags}
    \label{UnitFlags}
  \end{center}
\end{figure}


\section{Function Table}
\index{Network!Memory Management!Function Table}
\index{Function Table (Figure)}

The various site and unit functions are stored in the function table.
The user can define his own functions in form of a C program. Information
about these functions (name, type) is stored in a table, to give
the kernel access to and use of these functions.

\begin{figure}[htbp]
  \begin{center}
      \begin{minipage}{\textwidth}
          \screendump{0.7}{kernel_figs/functionTable.ps}
      \end{minipage}
    \caption{Function table}
  \end{center}
\end{figure}
\clearpage
