\section{Introduction}

\textit{Editor's note}. After Egorov died, I composed \cite{Eg} from scrap papers he left to me; he intended to improve them, but his sudden death intervened. Egorov was almost blind, so it was sometimes difficult to decipher intersecting lines of the notes he wrote to himself. Being guided by what I recalled of our discussions, I composed the introduction and supplied with the bibliography, but was unable to recover some of the proofs, see \cite{Eg}, published in not easily accessible collection. To the current version of Egorov's paper I updated the references trying to provide with the latest sources with more correct and reasonable definitions of the basics (e.g., Cartan matrix, Dynkin-Kac diagram, double extension) than the first definitions and more convenient notation. Ivan Penkov considerably improved the draft I composed for this Special volume in memory of Arkady Onishchik, I am very thankful to him for help. I heartily thank Osmo Pekonen who sent me the pdf of \cite{Eg} so I could work on it trying to make Egorov's findings more available. In what follows, ``I" means ``Egorov''.~\textit{D.Leites.}

\smallskip

In this paper, the ground field is $\Cee$.

\subsection{Lie algebras} There are many contenders for the role of $\fgl (n)$ in the case where $n =\infty$. Lately, some of these contenders are distinguished thanks to their applications in the theory of differential equations such as KdV and KP hierarchies, see~\cite{R} and references therein. For other applications of $\fgl (\infty )$, see \cite{B,K,KL1, KL2,FF,Lq,V}. (The best, in my opinion, short review on KdV is an MPI-1987 preprint by Date.)

Let me list some of the Lie algebras of infinite matrices that enjoy everybody's recognition. It goes without saying that we identify a~linear transformation with its matrix having chosen a~basis in the space $V$ of the tautological representation of the Lie algebra $\fgl (V)$. Thus, we replace the Lie algebra of operators $\fgl (V)$ by the Lie algebra of matrices $\fgl (\dim V)$ and for infinite-dimensional (of countable dimension) $V$, so every element of $V$ is a finite sum of basis elements, we get:
\[
\begin{array}{ll}
\fgl (\infty ) &= \{X \mid X\text{~~ is a~linear endomorphism of $\Cee^\infty=\Cee^\Zee$} \}\\
&= \{X\text{~~ is a~matrix with finitely many non-zero entries in every column} \};\\
\fgl _c(\infty ) &= \{X \in \fgl (\infty ) \mid \text{~~ nonzero entries of $X$ belong to a~band}\\ &\text{which contains the main diagonal and whose boundaries are parallel to it}\};\\
\fgl _f(\infty ) &= \{X \in \fgl (\infty ) \mid X\text{~~ has finitely many nonzero entries}\}.\\
\end{array}
\]

Each of these three Lie algebras of infinite both ways matrices has a~subalgebra of matrices whose rows and columns are only labelled with positive integers. Denote the respective subalgebras by $\fgl ^{+} (\infty )$, $\fgl_c ^{+} (\infty )$, $\fgl_f ^{+} (\infty )$.

Let us explain what is so natural about these algebras. For the definition of Lie (super)algebras with Cartan matrix and the corresponding Dynkin--Kac diagrams, see \cite{CCLL}; for realizations of finite-dimensional Lie superalgebras, see \cite{BGLLS}. Now, look at the Dynkin diagram of $\fgl (n)$; more precisely, of $\fsl(n)$ as $n\tto \infty $. There are two ways to tend $n$ to $\infty $ and that is how these algebras are obtained: they are generated by countably many Chevalley generators subject to the relations governed by the Cartan matrix corresponding to one of the following infinite Dynkin diagrams:
\[
\begin{array}{lll}
\bigcirc -\ldots -\bigcirc &\tto \bigcirc -\ldots &\text{(corresponds to $\fgl _f^{+} (\infty )$)}\\
\bigcirc -\ldots -\bigcirc &\tto \ldots -\bigcirc -\ldots & \text{(corresponds to $\fgl _f (\infty )$)}
\end{array}
\]
Observe that although seemingly different, the limit algebras are isomorphic, as Penkov proved by a simple argument: they are transformations of the space whose basis vectors are labelled by all or only positive integers; the isomorphism of the sets of labels establishes isomorphism $\fgl _f^{+} (\infty )\simeq\fgl _f (\infty )$ which does not come from any analog of the Weyl group considered in what follows.

For applications, however, these algebras turn out to be too small and it is desirable to enlarge them so that the enlarged Lie algebra has a~nontrivial central extension of degree 0. (This central extension is needed in ``quantization'', cf.~\cite{Lq, LSh}.)

The above-defined intermediate Lie algebras $\fgl _c(\infty )$ and $\fgl _c^{+}(\infty )$ prove to be just fine, although no analog of Dynkin diagram corresponds to them. (We will show that they themselves have interesting enlargements. R.~Bullough has reported that he found a~need in an enlargement of the conventional $\fgl _c(\infty )$, see \cite{BT}. Hopefully, the even parts of the Lie superalgebras introduced in this paper will satisfy these needs.) The central extension we have mentioned is given by the cocycle
\[
X,Y \mapsto \tr (J[X,Y])\quad \text{for}\quad X,Y \in \fgl _c (\infty )
\]
where $J = \diag(\ldots ,1,{-}1,\ldots )$ with the 1's occupying the slots with negative indices and the $-1$'s occupying the slots with positive indices.

\subsection{The Lie algebras studied by Penkov with co-authors} See \cite{PS1, PS2, FPS, PP1, PP2, PP3, PP4, IP, IPW, PSZ, PZ, ChP1, ChP2, HPS, CouP, GP, Pe, CP1, CP2} summarized in \cite{HP}, and an amendment in \cite{HZ}.

\subsection{Bases of Lie superalgebras} As is known, some~simple finite-dimen\-sio\-nal Lie superalgebras $\fg$ can have several bases (a.k.a. systems of simple roots) not isomorphic with respect to the Weyl group of $\fg_{\overline 0}$. The simplest way to see the reason for this phenomenon is to consider $\fgl (V)$ for a~finite-dimensional superspace $V$.

The matrix expression of elements from $\fgl (V)$ now depends not only on the basis of $V$ (which is always supposed to consist of homogeneous elements) but also on the \textit{parities} of the elements of the basis. The general linear Lie superalgebra of $n \times n$ matrices is determined by a~ set of $\sdim V=(\dim V_\ev, \dim V\od)$ basis vectors and the set \text{Par} of their parities, of which there are $\dim V_\ev$ even and $\dim V_\od$ odd ones, so that $\dim V_\ev+\dim V_\od = n$.

V. Serganova suggested several generalizations of the Weyl group all of which act by permutations of all the bases of a~simple Lie algebra $\fg$ (either finite-dimensional or a~(twisted) loop one) with Cartan matrix~\cite{S1,S2,LSS}. Let us recall them.

\subsection{Super Weyl groups}

\subsubsection{The universal super Weyl group} For simplicity, consider the finite-dimen\-sional case.

Let $\fg$ be a~simple Lie superalgebra, $\fh$ its maximal torus, $B$ a~base (system of simple roots), $\fn_B$ the nilpotent subalgebra generated by root vectors corresponding to~$B$. A subalgebra of the form $\fb_B:=n_B \oplus \fh$ is called a~\textit{Borel subalgebra}. Observe that $\fb_B$ is not the maximal nilpotent Lie superalgebra, see \cite{Shch}; Penkov showed that in the study of irreducible $\fg$-modules the non-maximal subalgebra $\fb_B$ is more convenient than the maximal one.

Let $L(\lambda ,B)$ be the finite-dimensional irreducible $\fg$-module with $\fb_B$-highest weight $\lambda $; let $\Lambda =\Lambda _B$ be the set of $\fb_B$-highest weights of all the finite-dimensional irreducible $\fg$-modules and $\Gamma _\lambda $ the set of weights of $L(\lambda, B)$.

For any $\alpha \in R$ and $\gamma \in \Gamma _\lambda $, denote by $S_\alpha (\gamma )$ the \textit{$\alpha $-string through $\gamma $}, i.e., the set
\[
\gamma -q \alpha ,\ldots ,\gamma -\alpha ,\gamma ,\gamma +\alpha ,\ldots ,\gamma +p \alpha
\]
such that $\gamma -(q+1)\alpha $, $\gamma +(p+1)\alpha \notin \Gamma _\lambda $. The number $l_\alpha =p+q-1$ is called the \textit{length} of the $\alpha $-string.

Set $r_\alpha (\gamma )=\gamma + (p - q)\alpha $. Since the weight $r_\alpha (\gamma )$ is defined for any $\gamma \in \Gamma _\lambda $, there exists a~map $r_\alpha \colon \Gamma _\lambda \mapsto \Gamma _\lambda $. This map will be called the \textit{reflection in $\alpha $}.

Let $F_R$ be the free group with generators $f_\alpha $ for every $\alpha \in R$. Then, for any $\lambda \in \Lambda $, there is defined an $F_R$-action on $\Gamma _\lambda $ by the formula $f_\alpha (\gamma ) := r_\alpha (\gamma )$.

Let $I_{\lambda ,R}$ be the normal subgroup of $F_R$ singled out by the formula
\[
I_{\lambda ,R}=\{f\in F_R\mid f(\gamma )=\gamma \text{ for all }\gamma \in \Gamma _\lambda \}.
\]

The group $UW_R = F_R/I_R$, where $I_R =\cap _{\lambda \in \Lambda }I_{\lambda ,R}$, will be called the \textit{universal super Weyl group} or just the univesal Weyl group of the root system $R$ (or of $\fg$ and then we denote $UW_R$ by $UW_{\fg}$).

Denote by $r_\alpha $ the image of $f_\alpha $ under the natural projection. By construction, $UW_{\fg}$ acts on $\Gamma _\lambda $ for any $\lambda \in \Lambda $, in particular, it acts on~$R$.

\parbegin{Lemma}
\textup{a)} $r_\alpha ^2 = 1$.

\textup{b)} $r_{-\alpha } = r_\alpha $.

\textup{c)} The Weyl group $W_{\fg_{\overline 0}}$ of the Lie algebra $\fg_{\overline 0}$ is naturally embedded into $UW_{\fg}$.

\textup{d)} Let $w \in W_{\fg_{\overline 0}}$. Then, $r_{w(\alpha )}=wr_\alpha w^{-1}$.
\end{Lemma}

\begin{proof} The properties a) and b) directly follow from the definition of the~$r_\alpha $, the property c) is obvious.

Since $r_\alpha $ is a~linear transformation of $\fh^*$ and maps $\Gamma _\lambda $ into itself, then
\[
S_{w(\alpha )}(w(\gamma )) = w(S_\alpha (\gamma ))\text{ for any }w\in UW_{\fg},\gamma \in \Gamma _\lambda
\]
implying d).
\end{proof}

\parbegin{Example} For $\fg = \fsl(m | n)$, select a~base $B =\{\alpha _1,\ldots ,\alpha _{m+n-1}\}$ corresponding to the Dynkin diagram of the form
\[
\bigcirc --\cdots--\bigcirc --\otimes --\bigcirc --\cdots--\bigcirc
\]
By heading d) of Lemma we can take $r_{\alpha _1},\ldots ,r_{\alpha _{m+n-1}}$ for the generators of $UW_{\fg}$. \end{Example}

\parbegin{Proposition}[\cite{S2}] $UW_{\fg}$ is a~Coxeter group for $\fg = \fsl(m | n)$ and $\fg = \fosp(2 | 2n)$ with relations indicated in Table $3.1$.
\end{Proposition}

\parbegin{Conjecture} $UW_{\fg}$ is a~Coxeter group for any simple Lie superalgebra with Cartan matrix with relations indicated in Table $3.1$. \end{Conjecture}

\subsubsection{The linear Weyl group}
Under the notations of the previous section, let $A$ be the Cartan matrix (see \cite{CCLL}) and define the reflections $r_\alpha $ by the formulas
\[
r_{\alpha _i}(\alpha _j)=\begin{cases}
-\alpha _j&\text{for }i = j\\
\alpha _j-a_{ij}\alpha _i&\text{for }i \ne j \text{ and }A_{ii} = 2\\
\alpha _j-2A_{ij}\alpha _i&\text{for }i \ne j \text{ and }A_{ii} = 1\\
\alpha _j+\alpha _i&\text{for }i \ne j \text{ and }A_{ii}=0,\ A_{ji}\ne 0\\
\alpha _j&\text{for }i \ne j \text{ and }A_{ii} = A_{ji} = 0
\end{cases}
\]
Let $LW_R$ be the group generated by such reflections when $\alpha $ runs over simple roots of \textit{all} bases of $\fg$. We will call $LW_R$ the \textit{linear Weyl group} of $R$ (or of $\fg$).

\subsection{Formulation of the Problem} M. Saveliev was, probably, the firt to observe that in applications of Lie superalgebras to integrable dynamical systems, the base of a~simple Lie superalgebra that consists of only odd elements plays a~distinguished role, see~\cite{LSS}. In Table~ 6 of~\cite{LSS}, there are listed Lie superalgebras with which there are associated by a~superization of a~method by Drinfeld and Sokolov, also described in~\cite{LSS}, super versions of KdV and (with infinite diagrams) KP, see a~pioneering paper~\cite{MR} and later works~\cite{KL1,KL2,R}. Note that only a~\textit{method} to recover an equation from a~superalgebra is written in~\cite{LSS}, the exceptional super KdVs themselves corresponding to exceptional diagrams from Table~ 6 of~\cite{LSS} were never written explicitly.

Not every Lie superalgebra has such a~basis. Serganova's result states that if the Lie superalgebra is finite-dimensional or loop one (perhaps, twisted, or is its double extension with Cartan matrix, see \cite{BLS}) it does not matter which base we start with as long as the superalgebra has a~distinguished base since we can reach any of the bases from any given one with the help of any of Serganova's super Weyl groups.

\textbf{Question: Is it true for $\fgl _c(\infty |\infty )$ that there is just one class of bases with respect to an analogue of the Weyl group? } Since only $\fgl _c(\infty |\infty )$ was chosen so far (\cite{R,KL1, KL2,B}) to study superized versions of KdV and KP, the answer is important for these interesting differential equations.

It turns out that the answer is ``NO''.

\subsection{Formulation of the answer} In what follows, I will give a~complete and explicit description of bases (systems of simple roots) for the so far conventional $\fgl(\infty |\infty)$; namely,
\[
\text{the bases are indexed by the points of $[a, b]\cup [c, d]$, where $0<a \leqslant b<c \leqslant d<1$.}
\]
I also define interesting enlargements of $\fgl _c(\infty |\infty )$. For the largest of these enlargments, there is just one class of bases \textit{and} for all of these types of Lie superalgebras, there exists a~ nontrivial cocycle of degree~0 which defines a nontrivial central extension.

I will also describe analogues of the Weyl group for these enlarged $\fgl (\infty |\infty )$'s.

I also give a~similar description for $\fgl_c(p|\infty )$ and $\fgl _c(\infty |q)$ with ${p,q < \infty }$.

In the last section, I describe various important subalgebras of $\fgl _c(\infty |\infty )$: its orthosymplectic, periplectic and queer versions; how to embed certain affine Kac-Moody (see \cite{BLS}) superalgebras into some of these Lie superalgebras of infinite matrices.

\section{Examples of infinite matrix Lie superalgebras and their ``Weyl groups''}\renewcommand\thesubsection{\arabic{section}.\arabic{subsection}}

In this section, we introduce several (super)spaces of infinite matrices. Let us start with the underlying spaces. Let ${\Mat: =\{a = (a_{i,j})_{i,j\in \Zee}\}}$ designate the space of all infinite matrices. Set
\begin{gather*}
\Mat_f := \{x \in \Mat \mid \card (\Supp x) <\infty \},\text{ where}\\
 \Supp (a_{i,j}) := \{(i,j) \in \Zee \times \Zee\mid a_{i,j}\ne 0\}.
\end{gather*}

In what follows, an arbitrary map $p \colon \Zee \tto \Zee/2$ will be called a~\textit{parity function}. The following two parity functions are very important for us:
\begin{gather*}
p_{+}(x)=\begin{cases}
\overline 1,&\text{if } x \geqslant 0\\
\overline 0,&\text{otherwise.}
\end{cases}\\
p_{\text{st}}=x \mod 2.
\end{gather*}

On $\Mat_f$, introduce a~Lie superalgebra structure by defining the supermatrices with the help of a~fixed parity function $p$ and by setting
\be\label{1}
[a,b]_{ij}=\sum\limits _k(a_{ik}b_{kj}-(-1)^{(p(i)+p(k))(p(j)+p(k))}b_{ik}a_{kj});
\ee
denote the obtained Lie superalgebra by $\fgl _{p,f}$. The Dynkin diagrams corresponding to $p_{+}$ and $p_{\text{st}}$, respectively, are:
\[
\cdots--\bigcirc --\cdots--\bigcirc --\otimes --\bigcirc --\cdots--\bigcirc --\cdots
\]
and
\[
\cdots--\otimes --\cdots--\otimes --\cdots
\]

\subsection{Several superized $\fgl (\infty )$s} We will consider the following four en\-lar\-ge\-ments of $\fgl_{p,f}$ with the bracket defined by the formula \eqref{1}:
\begin{gather*}
\fgl _{p,g}:=\{(a_{ij})_{i,j\in \Zee} \in \Mat\mid \text{for any $i_0$, $j_0$ there exists}\\
\text{some $c = c(i_0,j_0) > 0$ such that}\\
a_{ij}=a_{ji}=0 \text{ for all $i$, $j$ such that }(i - i_0)(j_0 - j) > c\}
\end{gather*}
It is an easy exercise for the reader to prove that there are finitely many entries in every row and every column as well as in the first and the  third quadrants of every matrix in~ $\fgl _{p,g}$.
\begin{gather*}
\fgl _{p,l}:=\{a=(a_{ij})_{i,j\in \Zee} \in \Mat\mid \text{ for some $\lambda =\lambda (a)>0$ the matrix $a$ satisfies}\\
\lim\limits _{\substack{(i,j) \in \Supp a\\
|i| \tto \infty }}\frac {|i-j|^\lambda }{|i+j|}=\lim\limits _{\substack{(i,j) \in \Supp a\\
|j| \tto \infty }}\frac {|i-j|^\lambda }{|i+j|}=0)\};\\
\fgl _{p,o}:=\{a=(a_{ij})_{i,j\in \Zee} \in \Mat\mid \lim\limits _{\substack{(i,j) \in \Supp a\\
|i| \tto \infty }}\frac {|i-j|^\lambda }{|i+j|}=\lim\limits _{\substack{(i,j) \in \Supp a\\
|j| \tto \infty }}\frac {|i-j|^\lambda }{|i+j|}=0 \\
 \text{for all}\quad \lambda >0\};\\
\fgl _{p,c}:=\{a=(a_{ij})_{i,j\in \Zee}\in \Mat\mid a_{ij}=0 \text{ for all $i$, $j$ such that}\\
\text{$|i -j| > c$ for some constant $c = c(a)$}\}.
\end{gather*}

\sssbegin{Proposition} $\fgl _{p,*}$, where $* = g,l,o,c$, are Lie superalgebras, i.e., for any $a,b\in \fgl _{p,*}$ we have $[a,b] \in \fgl _{p,*}$.
\end{Proposition}

\begin{proof} Every row and column of any $(a_{ij})_{i,j\in \Zee} \in \fgl _{p,g}$ is finite, so the bracket is well defined. Let $c = [a, b]$, where $a, b \in \fgl _{p,*}$; we have to find $\Suppp c$, having given $\Suppp a$ and $\Suppp b$. We have to prove that the supercommutator does not lead out of $\fgl _{p,g}$.

If $(i,j) \in \Suppp c$, then $(i, k), (k, j) \in \Suppp a~\cup \Suppp b$ for some $k \in \Zee$. For any $i_0$ and $j_0$, there exist $c_1$ and $c_2$ such that $(i - i_0)(j_0 -k) < c_1$ and $(k - i_0)(j_0 - j) < c_2$. The details are left to the reader.
\end{proof}

\sssbegin{Lemma} \textup{1)} The superalgebra $\fgl _{p,g}$ has a~unique nontrivial central extension $\widetilde {\fgl }_{p,g}$
given by the cocycle:
\[
a,b\tto\str([a,b]J)z,
\]
where $J\in \Mat$ is such that $J_{ik}=\delta _{ik}\sign(i)$.

\textup{2)} The restrictions of this cocycle to $\fgl _{p,l}$, $\fgl _{p,c}$ and $\fgl _{p,o}$ are nontrivial.
\end{Lemma}

We will denote the central extensions corresponding to heading 2 of Lemma by $\widetilde {\fgl }_{p,l}$, $\widetilde {\fgl }_{p,c}$ and $\widetilde {\fgl }_{p,o}$, respectively.

\subsection{Weyl groups for $\fgl _{p,g}$ and its subalgebras} Let $p_1$ and $p_2$ be two different parity functions. What are the conditions for these two functions to determine isomorphic Lie superalgebras of type $\widetilde {\fgl }_{p,c}$ (resp. $\widetilde {\fgl }_{p,o}$, $\widetilde {\fgl }_{p,l}$ and $\widetilde {\fgl }_{p,g}$)? To answer this question we need the following infinite permutations groups that will serve as analogues of the Weyl group of $\fgl (n)$.

\ssbegin{Convention} In what follows we will only consider isomorphisms of these superalgebras which transfer their common Lie subsuperalgebra of finite matrices $\Mat_f$ into itself.
\end{Convention}

Let $S_{\Zee}$ be the group of all permutations of $\Zee$, i.e., the group of all one-to-one maps $\sigma: \Zee \tto \Zee$. We define the groups
\begin{gather*}
S_g:=\{\sigma \in S_{\Zee} \mid \text{ for some $c_\sigma >0$ we have $\frac {\sigma (i)}i>0$}\\
\text{for all $i$ such that: $|i| >c_\sigma $}\};\\
S_l:=\{\sigma \in S_g\mid \lim\limits _{|i| \tto \infty }\frac {|\sigma (i)-i|^\lambda }{|i|}=0 \text{ for some }\lambda _\sigma =\lambda >0\};\\
S_m:=\{\sigma \in S_g\mid \limsup\limits _{|i| \tto \infty }\frac {|\sigma (i)-i|}{|i|}<\infty ,\text{ and } \liminf\limits _{|i| \tto \infty }\frac {|\sigma (i)-i|}{|i|}>0\};\\
S_n:=\{\sigma \in S_{\Zee} \mid \lim\limits _{|i| \tto \infty }\frac {|\sigma (i)-i|}{|i|}=0\};\\
S_o:=\{\sigma \in S_{\Zee} \mid \lim\limits _{|i| \tto \infty }\frac {|\sigma (i)-i|^\lambda }{|i|}=0 \text{ for all }\lambda >0\};\\
S_c:=\{\sigma \in S_{\Zee} \mid |\sigma (i)-i|<c_\sigma \text{ for some }c_\sigma >0 \text{ and }i\in \Zee\}.
\end{gather*}

It is clear that
\[
S_c \subseteq S_o \subseteq S_n \subseteq S_m \subseteq S_l \subseteq S_g \subseteq S_{\Zee}.
\]
Define the action of $S_{\Zee}$ on parity functions by setting $(\sigma p)(i)=p(\sigma (i))$.

\ssbegin{Proposition} Let $p$ and $p'$ be parity functions, $\sigma \in S_g$ and $p'=\sigma p$. Let
\[
(J_\phi )_{ij} := J_{\sigma ^{-1}i,\sigma ^{-1}j}-J_{ij}.
\]
Then, the formulas
\[
\phi _\sigma (z)=z,\phi _\sigma (a_{ij})=(a_{\sigma (i),\sigma (j)}+\str(J_\phi a)z,
\]
determine an isomorphism ${\phi _\sigma \colon \widetilde {\fgl }_{p,g} \tto \widetilde {\fgl }_{p',g}}$.

If $\sigma \in S^l$ \textup{(}or $S^o$, or $S^c$\textup{)}, then $\phi _\sigma $ induces the isomorphism of $\widetilde {\fgl }_{p,l}$ and $\widetilde {\fgl }_{p',l}$ \textup{(}of $\widetilde {\fgl }_{p,o}$ and $\widetilde {\fgl }_{p',o}$, or $\widetilde {\fgl }_{p,c}$ and $\widetilde {\fgl }_{p',c}$, respectively\textup{)}.
\end{Proposition}

\begin{proof} Let $pr \colon \widetilde {\fgl }_{p,g} \tto \fgl _{p,g}$ be the natural projection. Let us first prove that $\phi _\sigma $ is an isomorphism. It is clear that
\[
pr \phi _\sigma pr([a,b])=pr([\phi _\sigma (a),\phi _\sigma (b)]).
\]
Then,
\begin{gather*}
\phi _\sigma ([a,b])=\phi _\sigma (pr([a,b])+\str(pr([a,b])J)z)\\{}=
pr \phi _\sigma pr([a,b])+\str(pr([a,b])J_\sigma )z+\str(pr([a,b])J)z\\{}=
pr([\phi _\sigma (a),\phi _\sigma (b)])+\sum\limits (-1)^{p(i)}[a,b]_{ii}(J_{\sigma ^{-1}i,\sigma ^{-1}i}-J_{ii}+J_{ii})z\\{}=
{}[\phi _\sigma (a),\phi _\sigma (b)].
\end{gather*}

Let $*$ be $c$, $o$ or $l$. We should prove that $\phi _\sigma (a) \in \fgl _{p,*}$ for any $a\in \fgl _{p,*}$ and $\sigma \in S_*$.

Let $*$ be $c$. Then, $a_{ij}=0$ for any $i$, $j$ such that $|i - j| > c_a $. For any $i$, $j$ such that $|i - j| >c_a+2c_\sigma $, we have
\[
(\phi _\sigma a)_{ij}=a_{\sigma ^{-1}(i),\sigma ^{-1}(j)}=0,
\]
because
\[
|\sigma ^{-1}i-\sigma ^{-1}j|>>|i-j|-|\sigma ^{-1}i-i|-|\sigma ^{-1}j-j|>c_a.
\]
Let $*$ be $o$. Then,
\[
\lim\limits _{\substack{i,j\tto \infty \\
(i,j) \in \Supp \phi _\sigma (a)}}\frac {|i-j|^\lambda }{|i+j|}=\lim\limits _{\substack{i,j\tto \infty \\
(i,j)\Supp(a)}}\frac {|\sigma ^{-1}(i)-\sigma ^{-1}(j)|^\lambda }{|\sigma ^{-1}(i)+\sigma ^{-1}(j)|}=0
\]
by definition of $S_o$.

For $* = l$, the proof is quite similar.
\end{proof}

\section{Main Reduction}

The following theorem shows that the isomorphism problem for Lie superalgebras $\widetilde {\fgl }_{p,g}$, $\widetilde {\fgl }_{p,l}$, $\widetilde {\fgl }_{p,o}$, $\widetilde {\fgl }_{p,c}$ can be reduced to the equivalence problem for the parity functions on $\Zee$ with respect to permutations groups $S_g$, $S_l$, $S_o$ and $S_c$, respectively.

\ssbegin{Theorem} Let $\tau \in S_{\Zee}$ be given by the formula $\tau (i)=-i-1$. The Lie superalgebras $\widetilde {\fgl }_{p_1,g}$ and $\widetilde {\fgl }_{p_2,g}$ \textup{(}$\widetilde {\fgl }_{p_1,l}$ and $\widetilde {\fgl }_{p_2,l}$, $\widetilde {\fgl }_{p_1,o}$ and $\widetilde {\fgl }_{p_2,o}$, $\widetilde {\fgl }_{p_1,c}$ and $\widetilde {\fgl }_{p_2,c}$\textup{)} are isomorphic if and only if there exists $\sigma \in S_g$ (resp. $S_l$, $S_o$, $S_c$) such that $p_2=\sigma (p_1)$ \textup{(}respectively $p_2 =\tau \sigma (p_1)$\textup{)}.
\end{Theorem}

First, let us prove the following lemma.

\sssbegin{Lemma}\label{l2.1} If $\sigma \in S_g$ and for any $i,j\in \Zee$ we have
\[
|\sigma (i)-\sigma (j)|<c|i-j|\quad \text{and}\quad |\sigma ^{-1}(i)-\sigma ^{-1}(j)|<c|i-j| ,
\]
then there exists $C$ such that $|\sigma (i)-i|<C$ for any $i\in \Zee$.
\end{Lemma}

\begin{proof} We will find such a~constant $C$ for $i \geqslant 0$ and apply the same arguments to $i < 0$.

Let $C_0 = 1+\max\nolimits _{i \leqslant 0}\sigma (i)$. The maximum exists because the definition of $S_g$ implies that $\sigma (i)<0$ for almost all $i < 0$.

Consider the permutation $\sigma '(i)=\sigma (i)-C_0$. Since $\sigma '(i)<0$ for $i \leqslant 0$, we see that for any $k\in \Nee$, there exist $i$, $j$ such that $j > k > i$ and such that $0 <\sigma '(j)\leqslant k$, $\sigma '(i)\leqslant k$. Then, if $\sigma '(k)>k$, there exist $m$, $n$ such that
\[
m<k<n,\quad \sigma '(m)<k,\quad \sigma '(n)\leqslant k,\quad \sigma '(m+1)\geqslant k,\quad \sigma '(n+1)\geqslant k.
\]

Since
\[
\sigma '(a)-\sigma '(b)=\sigma (a)-\sigma (b)\quad \text{and}\quad |\sigma (i+1)-\sigma (i)|<c,
\]
we get
\[
|\sigma '(m+1)-\sigma '(m)|<c,\quad |\sigma '(n-1)-\sigma '(n)|<c.
\]
Thus,
\[
|\sigma '(m)-k|<c,\quad |\sigma '(n)-k|<c,
\]
and therefore
\[
|\sigma '(m)-\sigma '(n)|<2c \quad \text{and }|m-n|<2c^2.
\]
Since $m > k > n$, then $|m - k|<2c^2$ and $|\sigma '(m)-\sigma '(k)|<2c^3$.

Finally,
\begin{gather}\label{3}
|\sigma (k)-k|<|\sigma '(k)-k|+C_0 \leqslant{}\notag\\
 |\sigma '(m)-k|+|\sigma '(m)-\sigma '(k)|<C_1=2c^3+c+C_0. \label{3.1}
\end{gather}
If $\sigma '(k)<k<\sigma (k)$, the inequality \eqref{3.1} still holds because $\sigma (i)-\sigma '(i)=C_0$.

If $0 <\sigma (k)<k$, then we can obtain a~similar inequality for $\sigma ^{-1}$:
\[
|k-\sigma (k)|=|\sigma ^{-1}(\sigma (k))-\sigma (k)|<C_2.
\]

Since the estimate is done for all $i\in \Nee$ but a~finite set, we have:
\[
\card B < \infty ,\quad \text{where}\quad B = \{i \mid i\in \Nee,\sigma (i) \notin \Nee\}.
\]

Finally, set
\[
C := \max\{C_1 , C_2, \max\limits _{i\in B}|\sigma (i) - i|\}.\qed
\]
\noqed \end{proof}

\sssbegin{Lemma}\label{l2.2} Let $\phi \colon \fgl _{p,*} \tto \fgl _{p',*}$ be an isomorphism. Then, there exist $\gamma \in \Aut \fgl _{p',*}$ and $\sigma \in S_{\Zee}$ such that $\gamma \phi =\phi _\sigma $.
\end{Lemma}

\begin{proof} Let $(e_{ij})$ be an elementary matrix; $H$ and $H'$ the diagonal subalgebras in $\fgl _{p,*}$ and $\fgl _{p',*}$, respectively;
\[
\text{$L_r := \{(a_{ij})_{i,j\in \Zee} \in \Mat_f$ such that $a_{ij}=0$ if $|i| > r$ or $|j| > r\}$.}
\]
 (Clearly, $L_r$ is a~subsuperalgebra.)

For any $k\in \Nee$, there exists $m\in \Nee$ such that $\phi (L_k)\subseteq L_m$, because $\phi (\fgl _{p,f})\subseteq \fgl _{p',f}$. It is possible to show that there exists $X_k\in L_m$ such that $1+X_k$ is invertible and
\[
\text{$\Ad_{1 + X_k}\phi (e_{ii}) =e_{\sigma (i),\sigma (i)}$ for some function $\sigma \colon [-k,k] \tto \Zee$.}
\]

When $X_k$ is constructed, we can choose $X_{k+1}$ so that $\Ad_{1+X_{k+1}} (e_{\sigma (i),\sigma (i)})=e_{\sigma (i),\sigma (i)}$ for $|i| < k$. Then, we can set $\gamma :=\prod\nolimits _{k=1}^\infty \Ad_{1+X_{k}}$ and take the corresponding $\sigma \in S_{\Zee}$. It is easy to prove that $\gamma $ is extendable to an automorphism of $\fgl _{p',*}$ and satisfies Lemma's conditions.
\end{proof}

\begin{proof}[Proof of Theorem] By Lemma~\ref{l2.2} we can only consider the isomorphism $\phi _\sigma $ for some ${\sigma \in S_{\Zee}}$. Moreover, $\sigma \in S_g$ because $\phi _\sigma (\fgl _{p,c})\subseteq \fgl _{p',g}$.

We have to prove that if $\phi _\sigma (\fgl _{p,*})\subseteq \fgl _{p',*}$, then $\sigma \in S_*$. For $* = o$, this follows from Lemma~\ref{l2.1}. For the other classes, it is not difficult to suitably adjust the formulation of Lemma~\ref{l2.1}.
\end{proof}

\section{Description of equivalence classes of parity functions}

For an arbitrary parity function $p$ and $-\infty \leqslant a<b \leqslant +\infty $, set:
\begin{gather*}
\Odd (p;a,b) := \card \{i\in \Zee\mid a~\leqslant i \leqslant b,p(i)=1\},\\
\Even (p; a, b):= \card \{i \in \Zee\mid a~\leqslant i \leqslant b,p(i) = 0\},\\
d(p;a,b)=d(p,b,a):=\frac {\Odd(p;a,b)}{(b-a)}.
\end{gather*}

We will call a~parity function $p$ \textit{finite} if
\[
\Odd(p; - \infty , +\infty ) < \infty \quad \text{or}\quad \Even(p; -\infty , +\infty ) < \infty .
\]
It is clear that both $\Odd(p; -\infty , +\infty )$ and $\Even(p; -\infty ,{+}\infty )$ are invariant under any of the permutation groups defined above. On the other hand, two finite parity functions $p$, $p'$ are $S_c$-equivalent if and only if
\[
\Odd(p; -\infty , +\infty ) = \Odd(p'; -\infty , +\infty )
\]
and
\[
\Even(p; -\infty , +\infty ) = \Even(p'; -\infty , +\infty ).
\]

We will denote the superalgebras corresponding to a~finite parity function $p$ by:
\[
\fgl _{p,*}(m|\infty ),\quad \text{where}\quad m = \card(\Even(p; -\infty , \infty ))
\]
or by
\[
\fgl _{p,*}(\infty |n),\quad \text{where}\quad n = \card(\Odd(p;-\infty ,\infty )) .
\]
\ssbegin{Proposition}\label{p3.1} For any finite parity function $p$, the cardinalities
 $\Odd(p; -\infty, +\infty )$ and $\Even(p; -\infty ,{+}\infty )$ constitute the complete system of invariants with respect to $S_c$, $S_o$, $S_l$, and~ $S_g$.
\end{Proposition}

\begin{proof} It is obvious that both the cardinalities are $S_{\Zee}$-invariant. Therefore, we have to show that there exists a~belonging to $S_c$ isomorphism between two such parity functions. So take a~one-to-one map
\[
\sigma \colon \begin{cases}\Zee_{p'}^{+} \tto \Zee_{p'}^{-}=\Zee_p^{+}&\\
\Zee_p^{-} \tto \Zee_p^{+}=\Zee_{p'}^{-}&\\
\end{cases}
\]
arbitrary on two finite sets, where $p \ne p'$ and such that $\sigma (x) = x$ if $p(x) = p'(x)$.
\end{proof}

Non-finite parity functions are subdivided into five $S_g$-invariant classes according to how many infinite values (0 to 4) there are among
\[
\Odd(p;-\infty ,0),\ \Even(p;-\infty ,0),\ \Odd(p; 0,{+}\infty ) \text{ and } \Even(p; 0,{+}\infty ).
\]
Denote by $\text{Inf}$ the set of parity functions for which all the four values are infinite.

\subsection{Continuous invariants of certain parity functions} Let $\{a_i\}_{i\in\Zee}$, $\{b_i\}_{i\in\Zee}$ be two arbitrary series such that
\be\label{4}
\lim\limits_{i\to\infty} a_i=\lim\limits_{i\to\infty} b_i=\pm \infty ,\quad \lim\limits_{i\to\infty} (a_i-b_i)=\infty .
\ee

We will say that $\alpha $ is a~\textit{left \textup{(}right\textup{)} density point} for $p$ if there is a~$-$ (respectively, $+$) sign in eq.~\eqref{4} and $\alpha $ is a~limit point of the $d_i = d(p; a_i,b_i)$. We will call the set of all left (right) density points for all such series the \textit{left \textup{(}right\textup{)} density spectrum} and denote it by $D_l(p)$ and $D_r(p)$, respectively.

\sssbegin{Proposition} Both $D_l$ and $D_r$ are subsegments of $[\hspace*{.9pt}0, 1]$.
\end{Proposition}

\begin{proof} This follows from the fact that these two sets are closed and convex.

Let $d$ be a~limit point of $D_r$, i.e., $\lim_{i\to\infty} d_i = d$ for some $d_i\in D_r$. For each $d_i$, select
\[
\{(a_{ij},b_{ij}) \mid \lim\limits _{j\tto \infty }d(p,a_{ij},b_{ij})=d_i\}
\]
as in definition of $D_r$. Then, $d$ is a~density point for the set $\{a_{ii},b_{ii}\}_{i\in\Zee}$.

Let $d, d' \in D_r$ and $\{(a_i,b_i)\}_{i\in\Zee}$, $\{(a_i',b_i')\}_{i\in\Zee}$ be some series converging to them, respectively. Then, for any $\alpha$ such that $0 < a~< 1$, we can select $(a'', b'')$ such that $a_i< a''< a'$ and $b_i<b''<b'$.
\end{proof}

\sssbegin{Theorem}\label{Th} \textup{1)} The sets $D_l$ and $D_r$ are $S_c$- and $S_o$-invariant; i.e., if $D_l=[\alpha ^l,\beta ^l]$, $D_r=[\alpha ^r,\beta ^r]$ and parity functions $p$ and $p'$ are $S_o$-equivalent, then $\alpha _p^l=\alpha _{p'}^l$, $\alpha _p^r=\alpha _{p'}^r$, $\beta _p^l=\beta _{p'}^l$, $\beta _p^r=\beta _{p'}^r$.

\textup{2)} If $0<\alpha ^l=\beta ^l<1$ and $0 <\alpha ^r=\beta ^r<1$ for both $p$ and $p'$, then these two functions are $S_m$-equivalent if and only if they have the same density spectrum.

\textup{3)} If $0<\alpha ^l \leqslant \beta ^l<1$ and $0<\alpha ^r \leqslant \beta ^r<1$ for both $p$ and $p'$, then these two functions are $S_m$-equivalent.

\textup{4)} Any two non-finite parity functions that belong to the same invariance class are $S_g$-equivalent.
\end{Theorem}

\begin{proof} First, let us examine the case of $S_g$. Let us fix some invariance class of non-finite parity functions, say $\Inf$. For any parity function $p\in \Inf$, we can define $\sigma _p\colon \Zee\tto \Zee$ by the following formulas:
\[
\begin{array}{l}
\sigma _p(x)
\footnotesize
:=\begin{cases}2(1-p(x))\Even(p;1,x)+p(x)(2 \Odd(p; 0, x) - 1)&\text{for }x \geqslant 0,\\
-2(1-p(x) )(\Even(p; x, 0) - 1) - p(x)
(2\Odd(p; x, -1) - 1)&\text{for }x < 0.\qed
\end{cases}
\end{array}
\]
\noqed \end{proof}

\sssbegin{Lemma} For some $\sigma _p\in S_g$, we have $\sigma _p(p)=p_{st}$
\end{Lemma}

\begin{proof} Observe that
\[
\sigma _p(-\infty ,0) = \begin{cases}(-\infty ,0)&\text{if $p(0) = 0$,}\\
(-\infty ,0)&\text{if $p(0) = 1$},\\
\end{cases}
\]
and $\sigma _p(0,\infty ) = (0,\infty )$.

The function $p_{st}$ is therefore $S_g$-equivalent to any other parity function from Inf. So any two parity functions $p,p' \in \Inf$ are $S_g$-equivalent: $p' =\sigma _{p'}^{-1}\sigma _p(p)$.

It is easy to see that four parity functions, which are equal to $p_{st}$ either on $(-\infty ,0)$ or on $(0, +\infty )$ and are constant elsewhere, are representatives of the four other classes. The required isomorphisms are obtained in a~similar way.
\end{proof}

\subsubsection{}
Now, let us consider the smallest of our permutation groups, $S_c$. The main reason to investigate it is that for $p \equiv 0$, the Lie algebra $\widetilde {\fgl }_{p,c}$ has various nice properties, studied in~\cite{V}, and our $\widetilde {\fgl }_{p,c}$ for $p$ not identically equal to zero is its straightforward generalization.

For $\sigma \in S_c$, we have $|\sigma (a)-a|\leqslant c_\sigma $, and therefore we obviously have
\[
|d(\sigma (p);a,b)-d(p;a,b)|\leqslant \frac {2c_\sigma }{|a-b|}\text{ for any }p.
\]
Thus, for any two series $a_i$, $b_i$ such that $|a_i-b_i| \tto \infty $ as $i\tto \infty $, all density limit points are $\sigma $-invariant.

There exist continuous $S_c$-invariants other than just upper/lower left/right density limits, which describe the behavior of the density (for example, logarithmic density) in more detail, as well as involve other $S_c$-invariant characteristics (for example, $\limsup \ln \Odd(p; - x,x)$). The proof holds not only for $S_c$, but for $S_a$ as well. Still, I can only guarantee that two parity functions are non-$S_o$-equivalent if some of these invariants differ.

One can hope to describe parity functions from \text{Inf} in terms of density spectrum only for non-finite functions with the property that for some $c_p > 0$ there is no interval $(a, b)$ of more than $c_p$ units long on which $p$ is constant. In other words, the density spectrum should be separated from 0 and 1. Let us call such parity functions \textit{tight}.

A larger group, $S_n$, enables us to progress further. Namely, we have

\sssbegin{Proposition} If two parity functions have coinciding one-point left and right density spectra and are tight, then they are $S_n$-equivalent.
\end{Proposition}

\begin{proof}[Proof\nopoint] uses the construction of $\sigma _p$ described above. Although neither $\sigma _p$ nor $\sigma _{p'}$ belong to $S_n$, if $D^l_p =D_{p'}^l$ and $D_p^r=D_{p'}^r$, then $\sigma _{p'}^{-1}\sigma _p\in S_n$.
\end{proof}

\section{Miscellanea}

For complete list of simple (twisted) loop superalgebras see~\cite{S3}. The list of all their central extensions (not all of which are affine Kac-Moody superalgebras a.k.a. double extensions with Cartan matrix, see \cite{BLS}) is given in~\cite{FLS}. For the definition of Lie superalgebras with Cartan matrix, in particular, of affine Kac-Moody superalgebras, see \cite{CCLL}.

\subsection{Embeddings of affine Kac-Moody superalgebras into $\widetilde {\fgl }_{p,c}$} Recall the definition of the double extension of the loop (super)algebra $\fg^{\ell(1)}$ or of its twisted version $\fg^{\ell(k)}$, see \cite{BLS}. Let $p$ be a~parity function such that $p(i) = p(i + k)$ and set
\[
A^k:=\{(a_{ij})_{i,j\in \Zee} \in \widetilde {\fgl }_{p,c} \mid a_{ij}=a_{i+k,j+k}\}.
\]
Let $p$ be a~parity function such that $p(i) = p(i + k) + 1$, and set
\[
B^k := \{(a_{ij})_{i,j\in \Zee} \in \widetilde {\fgl }_{p,c} \mid a_{ij}=a_{i+k,j+k}\}.
\]

\sssbegin{Proposition} \textup{1)} $A^k \cong \fgl (m|n)^{\ell(1)}$, where $m=\Even(p; 1,k)$, $n =\Odd(p; 1,k)$.

\textup{2)} $B^k \cong \fq(k)^{\ell(2)}$.
\end{Proposition}

\subsection{Analogues of classical subalgebras for $\widetilde {\fgl }_{p,*}$}
Provided the parity function meets the requirements in curly brackets below, set
\begin{gather*}
B_{p,*}:=\{(a_{ij})_{i,j\in \Zee} \in \widetilde {\fgl }_{p,*} \mid a_{ij}=-(-1)^{p(i)}a_{-j,{-}i}\text{ for }p(i)=p(-i),p(0)=0\}.\\
D_{p,*}:=\{(a_{ij})_{i,j\in \Zee}\in \widetilde {\fgl }_{p,*} \mid a_{ij}=-(-1)^{p(i)}a_{1-j,1-i}\text{ for }p(i)=p(1-i)\}.\\
\fq_{p;*}:=\{a\in \widetilde {\fgl }_{p,*} \mid [a,P]=0 \text{ for an odd matrix $P$ such that }P^2 = \lambda \pmb1\}.
\end{gather*}

The Dynkin diagrams corresponding to $B_{p_{st},*}$ are of the form:
\[
\raisebox{-.25em}[0pt][0pt]{\text{\huge $\bullet $}}-\otimes -\cdots-\otimes -\cdots
\]
The Dynkin diagrams corresponding to $D_{p_{st},*}$ are of the form:
\[
\begin{array}{@{}r@{}c@{}l@{}}
\otimes \\[-.3em]
&\diagdown \\[-.16em]
\raisebox{0pt}[0pt][0pt]{\rule[-1em]{0.05em}{2.5em}\,\rule[-1em]{.05em}{2.5em}}\hspace*{.2em}\mbox{}&&\otimes -\cdots-\otimes -\cdots\\[-.16em]
&\diagup\\[-.3em]
\otimes
\end{array}
\]
The Dynkin diagram corresponding to $\fq_{p_{st},*}$ is of the form (for a definition of the base described by a~square circle, see~\cite{LSe2}:
\[
-\ldots -\lozenge-\ldots
\]
There is also the periplectic superalgebra without a Dynkin diagram:
\[
\mathfrak {pe}_{p,*}:=\{(a_{ij})_{i,j\in \Zee} \in \widetilde {\fgl }_{p,*} \mid a_{ij}=-(-1)^{p(i)}a_{1-j,1-i}\text{ for }p(i)= p(1-i)+1\}.
\]

\subsection*{Acknowledgements} I am thankful to D. Leites, who raised the problem, and to V. Serganova, who defined $\fgl_{p,g}$, for help.

\begin{landscape}
\begin{table}
\caption{Coxeter diagrams of universal super Weyl groups}

Notation: $\otimes $ stands for an odd reflection.

\medskip

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$\fg$&$\fsl(m | n)$&$\fosp(3 | 2)$&$\fosp(3 | 2n)$; $n> 1$\\
\hline
$UW_{\fg}$&$\underbrace {\bigcirc -\cdots-\bigcirc }_{m-1}\overset \infty {-}\otimes \overset \infty {-}\underbrace {\bigcirc -\cdots-\bigcirc }_{n-1}$&$\bigcirc \overset \infty {-}\otimes \overset \infty {-}\bigcirc $&$\bigcirc \overset \infty {-}\otimes \overset \infty {-}\underbrace {\bigcirc -\cdots-\bigcirc \overset 4{-}\bigcirc }_n$\\
\hline
\end{tabular}

\vspace{5pt}

\begin{tabular}{|c|c|c|c|}
\hline
$\fg$&$\fosp(2m+1 | 2)$, $m>1$&$\fd(\alpha )$&$\fosp(2 | 2n)$, $n>1$\\
\hline
$UW_{\fg}$&$\underbrace {\bigcirc \overset 4{-}\bigcirc -\cdots-\bigcirc }_m \overset \infty {-}\otimes \overset \infty {-}\bigcirc $&$\underset {\displaystyle \overset {\displaystyle \hphantom {\scriptstyle \infty }|{\scriptstyle \infty }}{\displaystyle \bigcirc }}{\bigcirc \overset \infty {-}\otimes \overset \infty {-}\bigcirc }$&$\otimes -\otimes \overset \infty {-}\underbrace {\bigcirc -\cdots-\bigcirc \overset 4{-}\bigcirc }_n$\\
\hline
\end{tabular}

\vspace{5pt}

\begin{tabular}{|c|c|c|c|}
\hline
$\fg$&$\fosp(2m+1 | 2n)$; $m,n>1$&$\fosp(4 | 2n)$, $n>1$&$\fosp(2m|2)$, $m>2$\\
\hline
$UW_{\fg}$&$\underbrace {\bigcirc \overset 4{-}\bigcirc -\cdots-\bigcirc }_m \overset \infty {-}\otimes \overset \infty {-}\underbrace {\bigcirc -\cdots-\bigcirc \overset 4{-}\bigcirc }_n$&
$\begin{array}{@{}r@{}l@{}l@{}}
\bigcirc \\[-.16em]
&\hspace*{-.145em}\diagdown \hspace*{-.3em}\raisebox{.3em}[0pt][0pt]{$\scriptstyle \infty $}\\[-.7em]
&&\hspace*{-.4em}\otimes\overset \infty {-}\underbrace {\bigcirc -\cdots-\bigcirc \overset 4{-}\bigcirc }_n \\[-1.3em]
&\hspace*{-.145em}\diagup \hspace*{-.3em}\raisebox{-.3em}[0pt][0pt]{$\scriptstyle \infty $}\\[-.16em]
\bigcirc
\end{array}
$&$\underbrace {\bigcirc -\cdots-\bigcirc }_{m-2}\overset \infty {-}\otimes \overset \infty {-}\bigcirc $\\
\hline
\end{tabular}

\vspace{5pt}

\begin{tabular}{|c|c|c|c|}
\hline
$\fg$&$\fosp(2m|2n)$; $m>2$, $n>1$&$\fag(2)$&$\fab(3)$\\
\hline
$UW_{\fg}$&$\begin{array}{@{}r@{}c@{}l@{}}
\bigcirc \\[-.16em]
&\hspace*{-.145em}\diagdown \\[-1em]
&&\underbrace {\bigcirc -\cdots-\bigcirc }_{m-2}\overset \infty {-}\otimes \overset \infty {-}\underbrace {\bigcirc -\cdots-\bigcirc \overset 4{-}\bigcirc }_n\\[-1.65em]
&\hspace*{-.145em}\diagup\\[-.16em]
\bigcirc
\end{array}
$&$\bigcirc \overset \infty {-}\otimes \overset \infty {-}\bigcirc \overset 6{-}\bigcirc $&$\bigcirc \overset \infty {-}\otimes \overset \infty {-}\bigcirc \overset 4{-}\bigcirc -\bigcirc $\\
\hline
\end{tabular}
\end{center}
\end{table}
\end{landscape}


\section{Introduction}

Motivated by the grand challenge of understanding how information is represented and processed in brains, brain simulations that create and run computational models of a brain have become an important inter-disciplinary research topic~\cite{6750072}. Since human brain represents the peak of biological intelligence, brain simulations not only reflect the most advanced artificial intelligence but also inspire new developments in artificial intelligence technologies.

A human brain comprises about 86 billion neurons interconnected via around 86 $\times$ $10^{3}$ billion synapses. Simulation of the inter-neuron information exchange demands a total throughput over one terabit per second. Low-latency communication is particularly crucial to brain simulations. Human cerebral cortex takes fraction of a second to complete a sequence of tasks for information exchange and process~\cite{laughlin2003communication} thus requiring millisecond-level latency for inter-neuron communications in brain simulations.
Therefore, brain simulations are only possible upon high-performance computing platforms, which typically leverage parallel processing technologies and graphical processing units (GPUs)~\cite{van2020exploring}.

Figure~\ref{system-structure} illustrates the structure for a brain simulation system. The simulation model is a large-scale spiking neural network whose structure is inspired by the connectivity characteristics of the human brain. The model runs on a supercomputer that consists of a group of computer nodes interconnected through a network of Infiniband switches. Each computer node comprises multiple GPUs and a CPU comprising multiple NUMA (Non-Uniform Memory Access) nodes, each utilizes the NUMA architecture to better match with the multiple GPUs. Simulation is setup through two stages -- first generate a simulation model (e.g., a spiking neural network) and then disperse the model across the GPUs in computer nodes. The simulation process comprises two main aspects -- computation on GPUs for data processing and communications among GPUs for data exchange.

In order to support large-scale brain simulations with increasing number of neurons and complex models, state-of-the-art simulators leverage the multiple GPUs available in a supercomputer for performing neuron data processing in parallel to accelerate computing speed~\cite{xu2019meurep,knight2021larger}. However, when the number of simulated neurons increases to a super-large-scale, information exchange among neurons generates a huge volume of data traffic that must be transmitted between GPUs with low latency~\cite{merolla2014million,9284088}. Therefore, communications among GPUs in a supercomputer play a crucial role in a brain simulation system and low-latency communication design becomes a significant research topic for meeting the performance requirements of brain simulations.

Various research efforts have been made for reducing communication latency in brain simulations, including topology design, cross-layer optimization, and parallel computing technologies~\cite{roy2019towards}. However, experiment results have shown that the communication bottleneck issue in super-large scale simulations with more than 4 billion neurons have not been solved by the current methods. In this article, we attempt to address the problem of low-latency communications in brain simulations from a design perspective with focus on partitioning neurons across GPUs and routing traffic among GPUs. To our best knowledge, we are the first team to study the low-latency communication problem on a scale level of 10 billion neurons for human brain simulation.

The rest of the article is organized as follows. We first briefly review the current brain simulators and related parallel technologies in Section \ref{Review}. Then in Section \ref{Guidelines}, we analyze the characteristics of communications for brain simulations and provide a list of guidelines for low-latency communication design in such a special environment. Following the guidelines we propose a partitioning algorithm for mapping neurons to GPUs and a two-level routing scheme for inter-GPU communications in Section \ref{Design}. Experiment results are presented in Section \ref{Experiment} to show the proposed partition and routing methods may improve delay performance of large-scale brain simulations. We also discuss several challenges and identify some research directions for low-latency communication design in Section \ref{Directions} before we draw conclusions at the end of the paper.

\section{Parallel Technologies for Brain Simulations} \label{Review}

\begin{table*}[!t]
	\begin{threeparttable}
		\centering
		\fontsize{10}{16}\selectfont

		\caption{Main features of available brain simulators}
		\label{tab:performance_comparison}
		\begin{tabular}{p{2.5cm}cc|cc|ccccc|ccc}

			\hline

			\multirow{1}{*}{\bf{Simulator}}&
			\multicolumn{2}{c}{\bf{mGPU}}&
			\multicolumn{2}{c}{\bf{Status}}&
			\multicolumn{5}{c}{\bf{Programming paradigm}}&

			\multicolumn{2}{c}{\bf{SNN Models}}\cr\cline{2-13}
			&Yes&No&Open&Active&MPI&C/C++&OpenACC&Cuda&OpenCL&LIF&LZH&HH

			\cr
			\hline
			Brian2Cuda~\cite{goodman2008brian}
			&
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{\bf{\checkmark}}
			& {\bf{\checkmark}}
			\cr\hline
			GeNN~\cite{stimberg2013brian}
			&{}
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			& {\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{\bf{\checkmark}}
			& {\bf{\checkmark}}
			\cr\hline
			Neuron~\cite{kumbhar2019coreneuron}
			&{\bf{\checkmark}}
			&
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			& {\bf{\checkmark}}
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			&{}
			& {\bf{\checkmark}}
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			\cr\hline
			HRLSim~\cite{6579754}
			&{\bf{\checkmark}}
			&
			&
			&
			&{\bf{\checkmark}}
			&
			&
			&
			&
			&{\bf{\checkmark}}
			& {\bf{\checkmark}}
			&
			\cr\hline
			{ NCS6 ~\cite{hoang2013novel}}	&{\bf{\checkmark}}
			&
			&{\bf{\checkmark}}
			&
			&
			& {\bf{\checkmark}}
			&
			&
			&{\bf{\checkmark}}
			&{\bf{\checkmark}}
			& {\bf{\checkmark}}
			&
			\cr\hline

		\end{tabular}
		\begin{tablenotes}
			\footnotesize
			\item[*] There are three main categories of SNN models: Leaky Integrate and Fire (LIF), Izhikevich (IZH), and conductance-based models of which the Hodgkin-Huxley (HH).

		\end{tablenotes}
	\end{threeparttable}
\end{table*}

A variety of simulation applications have been developed to employ parallel technologies for better utilization of the multi-GPU architecture in supercomputers~\cite{chatzikonstantis2019multinode}.
The simulator Brian2CUDA~\cite{goodman2008brian} generates C++/CUDA code to run on NVIDIA GPUs. GeNN~\cite{stimberg2013brian} is a code generator that can generate CUDA kernels and runtime code to be executed on multiple GPUs. Similar to GeNN, ANNarchy is a Python parallelizing interface used to create neural networks implementing neurons and synapses in the same manner as a brain. GeNN, Brian2CUDA, and ANNarchy are used to generate an entire C++ library optimized for parallel frameworks, such as OpenMP or CUDA, in a single GPU. However, simulations of large-scale brain models that contain over 1 billion neurons usually leverage a supercomputer as the computing platform to reduce simulation time and memory footprint. CoreNEURON~\cite{kumbhar2019coreneuron} is a compute engine for the NEURON simulator that is optimized for architecture with multiple CPUs and GPUs. Another high-performance simulator, HRLSim~\cite{6579754}, achieves a cognitive model in a supercomputer with a form and architecture similar to mammal brains. Message Passing Interface (MPI) is employed by HRLSim for both intra-node and inter-node communications. The neural cortical simulator (NCS6)~\cite{hoang2013novel} has been developed as a real-time neural simulator that may better utilize the heterogeneous clusters of CPUs and CUDA-capable GPUs in supercomputers.
Table I gives a summary of the main features of the parallel technologies employed by the reviewed brain simulators in the multi-GPU architecture. CarlSim, CoreNeuron, HRLSim, and NCS6 are some of the representative brain simulators that support multi-GPU implementations.

Although encouraging progress has been made for brain simulations, the existing works focus on simulating mammal brains that have much simpler brain structures and fewer neurons compared to human brain. Although the latest work reported in~\cite{yamazaki2021human} simulates an entire human brain, all the simulated neurons are copies of a single neuron without considering physiology features of the real human brain. Communications do not form a performance bottleneck in the aforementioned simulation with a relatively small scale (for mammal brains) or a highly simplified human brain model. In order to reflect the communication models in real brains, which tend to have peer-to-peer data exchange between any pair of neurons, current brain simulators typically employ random assignment of neurons onto to GPUs and provide direct peer-to-peer connections between GPUs for the logical data flows between all neurons assigned on different GPUs. For example, the state-of-the-art brain simulators presented in~\cite{van2020exploring} and~\cite{yamazaki2021human} assign neurons to multi-GPUs randomly.

However, in a large-scale simulation for human brain data communications based on random neuron-GPU mapping and direct inter-GPU connections may cause network congestion inside a supercomputer thus introducing significant simulation latency. Therefore, more sophisticated schemes are needed for partitioning the simulated neurons to GPUs and controlling data transmissions between GPUs (which is referred to as routing in this paper). Low-latency communication design for brain simulations faces unique challenges -- the partitioning and routing methods need to minimize the number of connections between GPUs and balance the traffic across the connections on the one hand while maintaining the communication mode in the real brain as much as possible.

There are a few algorithms that could be applied for partitioning neurons and grouping GPUs in brain simulations for low-latency communications. The minimum $k$-cut algorithm that finds the minimum-weight $k$-cut in a weighted graph may be applied to assign neurons to GPUs. However, analysis on the communication features of brain simulations in a multi-GPU environment indicates that minimizing the total traffic on the inter-GPU connections (which can be achieved by a $k$-cut algorithm) is not as effective as balancing traffic across these connections for latency reduction. Furthermore, the time complexity of the k-cut algorithm in a large-scale neural network with 10 billions of nodes make it not practical for real-time simulations~\cite{k-cut-approximation-2020}. Some meta-heuristic algorithms, including the genetic algorithm, simulated annealing algorithm, ant colony optimization, and swarm particle optimization, may be employed for addressing the partitioning problem. We evaluated these algorithms in our project and found that although a certain degree of traffic balance may be achieved the effectiveness of these algorithms for latency reduction is very limited in large-scale brain simulations, mainly due to the huge solution spaces that these kind of algorithms have to search through. The limitation of the existing methods motivated our development of new algorithms for neuron partitioning and traffic routing for achieving low-latency communications in large-scale brain simulations.

\section{Guidelines for Low-latency Communication Design in Brain Simulations} \label{Guidelines}

The huge volume of floating-point operations for simulating a brain model makes brain simulation a computing-intensive application whose performance may be improved by allocating more computing resources, which is typically realized by utilizing more GPUs in a supercomputer. This implies that the neurons of the brain model must be dispersed across GPUs thus requiring data to be exchanged among GPUs. Although using more GPUs may acquire more computing capacity and larger memory space, distributing neurons across a large number of GPUs introduces overheads of inter-GPU communications. Therefore, communications may become a performance bottleneck in a supercomputer with a massive cluster of GPUs for brain simulations.

Our analysis found that communications in brain simulations have the following characteristics.

\begin{enumerate}[1)]
	\item The volume of data generated in brain simulations for information exchange among neurons is considerable, often in the magnitude of petabytes per second, which is very challenging to even the most advanced supercomputers.

	\item The data transmissions in brain simulations usually require extremely low latency that might not be guaranteed by the conventional network control mechanisms. A main reason for latency in brain simulations is network congestion caused by the huge amount of traffic for inter-neuron communications.

	\item The communications among neurons for simulating a certain brain function are not evenly distributed. For example, some neurons mainly communicate with a few neurons while other neurons exchange information with a large number of neurons. The uneven distribution of inter-neuron traffic is a main factor that causes network congestion in brain simulations.

\end{enumerate}

Based on the above analysis, we suggest the following guidelines of communication design for brain simulations.
\begin{enumerate}[1)]
	\item Network congestion is a main reason for the delay of multi-GPU communications in supercomputers. Considering the uneven traffic generated by bain simulations, the two key aspects of communication design -- partitioning for assigning neurons to GPUs and routing for steering data traffic among GPUs -- both should consider balancing inter-GPU traffic in order to avoid network congestion.

	\item The communication design should attempt to cluster the neurons and GPUs in such a way that minimizes the traffic among GPUs for reducing communication latency. To achieve this objective, the partitioning algorithm should assign the neurons that have strong information exchange relationship onto the same GPU and the routing scheme should cluster the GPUs that have stronger communication demands among each other into the same group.

	\item The number of connections among GPUs for inter-neuron data transmissions is also a key factor impacting simulation delay. A large number of inter-GPU connections cause significant overheads that may slow down or even halt the simulation process. Therefore, communication design for brain simulations should reduce the number of connections between each pair of GPUs as much as possible.

	\item Communication design for brain simulations has to enhance simulation performance by leveraging the current supercomputer architecture, which is difficult to be revised. Also, the design should strive to balance between adding control mechanisms (partitioning and routing) and maintaining the communication modes of brain models (peer-to-peer communications between neurons).

\end{enumerate}

\section{A low-latency communication design} \label{Design}

Following the design guidelines given in the previous section, we propose in this section a low-latency communication design, which consists of a partitioning algorithm for assigning neurons to GPUs and a two-level routing method for controlling inter-GPU data transmissions.

\subsection{Partitioning Algorithm}

The proposed partitioning scheme assigns neurons to GPUs in order to minimize the traffic between different GPUs. Since communications between neurons on the same GPU are much faster than that between neurons across GPUs, this algorithm reduces communication latency by assigning a set of neurons that have strong communication demand between each other on the same GPU. Furthermore, this algorithm makes the traffic between each pair of GPUs in the system as balanced as possible to avoid network congestion thus improving delay performance.

\begin{algorithm}[!ht]
 	\caption{The partitioning algorithm}
 	\label{alg:A}
 	\begin{algorithmic}[1]
 		\REQUIRE~~\\ $P[M,M]$(the probability matrix of neurons connections), $W[M,1]$(the weight of neurons), $N$(the number of GPU in the system)

 		\ENSURE~~\\ $PM$ (the neuron-GPU mapping)

 		\STATE Set parameters $T$(itermax) , $t$(current iteration) and Initialize all these parameters;

 		\WHILE{$t$ $<=$ $T$ }
 		{  \STATE \bf	If}  $\sum_{i=1}^{N} w_{i} < avg \sum{W/N}$
 		{  \STATE \bf \hspace*{0.1in}	for}  $i = 1$ to $N$ {\bf do}
 		{\STATE \hspace*{0.3in} Greedy neurons assignment for every GPU by the probability matrix of neurons connections; }

 		{\STATE \hspace*{0.3in} Select $x_{i,t}$ as  $w_{i} \in W_{i}$}
 		{\STATE \bf \hspace*{0.1in} end for}
 		{\STATE  $t= t+1$}
 		\ENDWHILE
 		{ \STATE Update the best optimal solution of the neuron-gpu mapping}
 		{\STATE  \bf  Output $PM$}
 	\end{algorithmic}
 \end{algorithm}

Algorithm 1 gives the pseudocode of the proposed partitioning scheme.
While maintaining the balance of the volume of each GPU, the algorithm uses a greedy strategy to assign neurons to every GPU to ensure high cohesion among neurons within a GPU and low coupling between neurons on different GPUs. The inputs for the algorithm include a matrix $P[M,M]$ and a vector $W[M,1]$ for a simulation model with $M$ neurons running on $N$ GPUs. The matrix $P[M,M]$ gives inter-neuron connection probability; i.e., each element $P[i,j]$ ($i, j \in [1, 2, \cdots, M]$) has a value in $[0, 1]$ representing the connection probability between the neurons $i$ and $j$. The $W[M,1]$ gives the weight of each neuron that describes the data volume generated by the neuron for communications with all other neurons. $x_{i,t}$ represents the output of Algorithm 1 in each iteration, which is the neuron that needs to be placed in each GPU. The goal of the algorithm may be formulated as $min \ \Sigma_{i,j} (P[i,j]*W[i]*W[j])$ for all $i$ and $j$ that are not assigned to the same GPU; that is, minimizing the total amount of traffic across different GPUs for inter-neuron communications. During each iteration, the algorithm first balances the total weight of all the neurons assigned to each GPU and then selects the best optimal solution of the neuron-GPU mapping using a greedy assignment for each GPU based on the probability matrix. Finally, the algorithm updates the solution and outputs a table for neuron-GPU mapping.

\subsection{Two-Level Routing Method}

 \begin{algorithm}[!t]
	\caption{The two-level routing method}
	\label{alg:b}
	\begin{algorithmic}[1]
		\REQUIRE~~\\  $PG[N,N]$ (the probability matrix of GPUs connections),  $WG[N,1]$ (the sum weight of neurons in each GPU)

		\ENSURE~~\\  $TB$ (the routing table)

		\STATE Set parameters $T$(itermax), $t$(current iteration), $G$(cluster groups) and Initialize all these parameters;
		\STATE Set $PG[N,N]$ and $WG[N,1]$ according to the partitioning algorithm;

		\WHILE{$t$ $<=$ $T$ }
		{  \STATE \bf	while}  $\sum_{i=1}^{N} w_{i} < avg \sum{WG/N}$
		{  \STATE \bf \hspace*{0.1in}	for}  $i = 1$ to $N$ {\bf do}
		{\STATE \hspace*{0.3in} Greedy GPUs assignment for every group $G_{i}$ by the probability matrix $PG[N,N]$; }
		{\STATE \hspace*{0.3in} GPU connections in $G_{i}$ are the level-1 routing; }
		{\STATE \hspace*{0.3in} Select GPUs to connect other groups $G_{j}$ as the level-2 routing; }

		{\STATE \bf \hspace*{0.1in} end for}
		{\STATE \hspace*{0.1in} $t= t+1$}
		{\STATE \bf \hspace*{0.05in} end while}
		\ENDWHILE
		{ \STATE Update the best optimal solution of the routing method}
		{\STATE  \bf  Output $TB$}
	\end{algorithmic}
\end{algorithm}

Although the partitioning algorithm reduces traffic between GPUs, the large number of inter-neuron connections across GPUs with uneven traffic distribution is still a challenge that must be addressed for achieving low-latency communications. In a large scale brain simulation, thousands of GPUs attempt to communicate with each other simultaneously thus may cause network congestion that degrades delay performance.
For example as illustrated in Figure 2(a), at a time instant GPUs No. 1 to No. 8 all need to communicate with GPU No. 12. If the total traffic amount is greater than the link capacity to GPU No. 12, then the inevitable congestion on the link will introduce extra latency to the simulation functions running on these GPUs. Please note that the connections that we are referring to here are for logical data flows (shown as red lines in Figure 2) while the physical data flows (shown as green lines in Figure 2) follow the network structure, e.g., an Infiniband network, in the supercomputer.

For addressing this challenge to low-latency communications, we propose a control scheme with a two-level routing structure for reducing the number of connections between GPUs while balancing the traffic distribution across the connections. This scheme clusters GPUs in the system into groups with an objective of minimizing the amount of traffic between GPUs in different groups. GPUs in the same group communicate with each other through direct connections. When a GPU wants to communicate with another GPU in a different group, it first transmits data to a bridge GPU in the same group and then the bridge GPU forwards data to the destined GPU. As illustrated in Figure 2(b), the two-level routing scheme with GPU clusters reduces the number of direct connections between GPUs. Please note that although the physical data flow structure stays the same (as shown by the green lines in Figure 2 (a) and (b)) the amounts of traffic on these flows are reduced by the two-level routing scheme. It is worth noting that the proposed two-level routing is an application layer function for steering the traffic of logical data flows, which is different from the network routing in the underlying supercomputer architecture that controls the forwarding of physical data flows through switches. A brain simulator runs as an application on top of the supercomputer architecture; therefore, the communication control mechanism in the simulator leverages the supercomputer infrastructure including its routing protocol.

While maintaining the balance of the
traffic of each group and the number of direct connections between GPUs, the proposed method also uses a greedy strategy to assign GPUs to every groups to ensure high cohesion among neurons within a group and low coupling between neurons on different groups. The reason is GPUs in the same group communicate with each other through direct connections, and GPUs in different groups need to identify the corresponding GPU node in their group to forward data traffic. Moreover, a group of GPUs on the same switch in the physical structure, which speed of the information interaction is faster. In addition, because each connection requires a thread to be started, the time taken to start the thread in the whole system can be reduced by reducing the number of connections.
Algorithm 2 describes the proposed routing method. Inputs to the algorithm include the matrix $PG[N,N]$ and vector $WG[N,1]$, where $N$ denotes the number of GPUs in the system. Each element $PG[i,j]$ of the matrix $PG[N,N]$ represents the connection probability between GPUs $i$ and $j$ ($i, j \in [1, N]$). The $WG[N,1]$ gives the total weight of all the neurons assigned on each GPU, which describes the data volume generated by the GPU. The goal of the algorithm is to minimize the number of inter-GPU connections and reduce the traffic across GPU groups, which can be formulated as $min \ Conn[i,j]$, where $i,j \in [1,N]$ and $Conn[i,j]$ denotes the number of connections between GPUs $i$ and $j$, and $min \ (\Sigma_{i,j}PG[i,j]*WG[i]*WG[j])$ for all pairs of GPUs $i$ and $j$ that are not in the same group.
In each iteration of the loop (lines 3-12) the algorithm updates the best optimal solution of the routing by adapting the greedy assignment for every GPU group $G_{i}$ to cluster the most connected GPUs in the same group. GPUs in the same group are connected to each other via the level-1 routing (i.e. direct peer-to-peer connections). If a GPU wants to connect to a GPU in another group and itself is not a bridge node on behalf of its own group, then it needs to find another GPU as the bridge node for data forwarding. In the end, the algorithm obtains a routing table that defines the connection relationship for each GPU as the output.

\section{Experiment Results} \label{Experiment}

In this section, we evaluate the performance of the proposed partitioning and the routing methods for brain simulations. In the experiments, we used 2,000 GPUs on the supercomputer Kunlun to simulate a brain model with 10 billion neurons. The model was created according to the biological structure of a real human brain scanned using medical instruments. The simulation involves memory transfer and communications between GPUs via PCIE and InfiniBand. We used OpenMPI, which combines two parallel programming methods MPI and CUDA to achieve the highest data transmission efficiency. For performance evaluation, we compared the data traffic and number of connections between GPUs with and without the proposed design. We also evaluated the simulation time to verify the effectiveness of the proposed design for low-latency communication.
  \begin{table*}[!t]

 	\centering
 	\fontsize{8}{16}\selectfont

 	\caption{Latency performance comparison of different simulation scales}
 	\label{tab:performance_comparison}
 	\begin{tabular}{p{1.2cm}c|c|c|c|c|c|c|c|c}

 		\hline

 		\multicolumn{9}{c}{\bf{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad The channel noises in brain simulations }}\cr\cline{2-10}

 		\multirow{1}{*}{\bf{Scales}}&
 		\multirow{1}{*}{\bf{Neurons}}&
 		\multirow{1}{*}{\bf{Partition }}&
 		\multirow{1}{*}{\bf{Routing }}&
 		\multicolumn{1}{c}{\bf{0.1}}&
 		\multicolumn{1}{c}{\bf{0.2}}&
 		\multicolumn{1}{c}{\bf{0.3}}&
 		\multicolumn{1}{c}{\bf{0.4}}&
 		\multicolumn{1}{c}{\bf{0.5}}&
 		\multicolumn{1}{c}{\bf{0.6}}\cr\cline{2-10}

 		\hline
 			{\bf {2000GPUs}}&{10 billion}&{Random}&{P2P}&{4h30min+}&{4h30min+}&{4h30min+}&{4h30min+}&{4h30min+}&{4h30min+}\cr\hline

 			{\bf {2000GPUs}}&{10 billion}&{GA}&{GA}&{4h20min+}&{4h20min+}&{4h20min+}&{4h20min+}&{4h20min+}&{4h20min+}\cr\hline

 		{\bf {2000GPUs}}&{10 billion}&{proposed}&{proposed}&{0.179s}&{0.27s}&{0.319s}&{0.339s}&{0.357s}&{0.367s}\cr\hline

 		{\bf{4000GPUs}}&{20 billion}&{proposed}&{proposed}&{0.323s}&{0.377s}&{0.413s}&{0.499s}&{0.467s}&{0.491s}\cr\hline
 	\end{tabular}
 \end{table*}

Comparison of inter-GPU traffic generated by simulations with different neuron partitioning methods is presented in Figure 3(a). In this figure, the red, blue, and green lines give the amounts of traffic generated by each of the 2000 GPUs in the simulation system when the system uses random mapping, a genetic algorithm, and the proposed algorithm respectively for partitioning. It can be seen from the red line that random partition causes significant fluctuation in the amounts of traffic from different GPUs, which may easily cause congestion on some network links in the supercomputer. The blue line indicates partition using a genetic algorithm may obtain a certain degree of balance for inter-GPU traffic but not sufficient yet to avoid network congestion for reducing simulation latency (as shown by the results reported in Table II). The green line shows that the proposed partitioning algorithm may greatly reduce the difference in traffic volumes across GPUs. The peak value of the green line is 31.2\% lower than that of the red line and 13.4\% lower than  that of the blue line. Therefore, the proposed algorithm is more effective in balancing traffic and avoiding congestion compared to current methods. We also evaluated other heuristic algorithms, including simulated annealing, ant colony optimization, and swarm particle optimization, for neuron partitioning in our experiments and found they achieved similar performance as the genetic algorithm, which is used in Figure 3(a) as a representative.

Figure 3(b) shows the effectiveness of the proposed two-level routing method for controlling the amount traffic for inter-GPU communications. In this figure, the red line gives the amount of traffic generated from each of the 2000 GPUs when the two-level routing method is not employed. The blue line and green line in this figure respectively give the amounts of level-2 traffic when the two-level routing scheme is employed and the GPUs are clustered using a genetic algorithm and the proposed algorithm. Level-2 traffic, i.e., traffic destined to GPUs in other groups, is used in this figure because it has a larger impact on communication delay compared to level-1 traffic within each GPU group.
This figure shows that the proposed algorithm may achieve better balanced level-2 traffic across different GPUs than what a genetic algorithm does (The peak value of the blue line is $39.2\%$ lower than that of the green line). Moreover, the peak value of the green line is $51.1\%$ lower than that of the red line, it shows the effectiveness of the two-level routing method.
  Because simulation latency is determined by the communication between the pair of GPUs that has the largest traffic volume, balancing inter-GPU traffic may greatly improve delay performance for brain simulations.

Our analysis indicates that a key aspect of achieving low-latency communication in brain simulations is to reduce the total number of connections between GPUs. In order to evaluate the performance of the proposed method in this aspect, we present the histograms of frequency distribution for the total number of inter-GPU connections generated in the simulation system using direct peer-to-peer routing and the proposed two-level routing respectively in sub-figures (a) and (b) of Figure 4. This figure shows that the two-level routing method proposed in this paper is able to reduce the number of connections between each GPU and all its destined GPUs. Our experiments found that the average number of connections departing from each GPU is reduced from 1,552 to 88 by using the proposed routing method.

In order to evaluate the delay performance and scalability of the proposed communication design, we tested the simulation time for the brain model with various levels of computational complexity and system scales. The obtained results are reported in Table II. The channel noise in the simulation is a parameter that reflects the complexity of simulating brain functions. As this parameter increases from 0.1 to 0.6, the computational complexity for brain simulation increases significantly.

We first run the simulation on 2000 GPUs using random neuron-to-GPU partition and peer-to-peer routing between GPUs. The obtained latency results are listed in the first row of Table II, which give very long latency (more than four and half hours) that makes the simulation infeasible in practice. We tested the simulation time when we explored heuristic algorithms, such as the genetic algorithm (GA), simulated annealing algorithm, ant colony optimization, and swarm particle optimization, for partitioning neurons and clustering GPUs and found they all achieved the same level of performance. The results obtained using GA are presented in the second row of Table II, which indicates that basically no improvement in simulation latency is achieved by applying such algorithms in communication control.

Our experiments show that the simulation time is reduced significantly when the proposed partitioning and routing algorithms are employed in the simulation system. The obtained results for a model with 10 billion neurons running on 2000 GPUs are given in the third row of Table II. The data show that the simulation latency achieved for all complexity levels are less than one second, which satisfy the requirement of real-time inter-neuron communications in human brain. We also run the simulations for 20 billion neurons using 4000 GPUs on the same supercomputer and the measured results of simulation time are shown in the forth row of Table II. This row of data shows that the proposed partitioning and routing schemes are able to ensure low-latency communications even in a super-large simulation scale. The last two rows in Table II also verify that our communication design is scalable with respect to the brain model (from 10 billion neurons to 20 billion neurons), the simulation system (from 2000 GPUs to 4000 GPUs), and the simulation complexity (channel noise parameter from 0.1 to 0.6). We also noticed that the latency increment with respect to channel noise is smaller in the model with 20 billion neurons than that in the model with 10 billion neurons. That is mainly caused by the biological features of the simulated brain -- the synapses among the 20 billion neurons are sparser compared to those among the 10 billion neurons. Therefore, when the model with 20 billion neurons is simulated on 4000 GPUs it generates less intensive traffic for inter-GPU communications than what 10 billion neurons generate on 2000 GPUs, which leads to less latency increment as the channel noise increases.

\section{Challenges and future directions}  \label{Directions}

In this section, we shed light on several challenges to communication design in large-scale simulations of low-latency applications such as brain modeling.

\subsection{Modifications to MPI Library }

Communications in low-latency applications such as brain simulations require appropriate assignment of (virtual) destination LIDs for MPI~\cite{kang2020improving}, which cannot be satsified by existing MPI libraries used in supercomputers. Although we used OpenMPI to support IB’s multi-LID addressing, this is achieved in the form of a static topology table, which cause extra communication latency when it is used for mapping datasets to GPU devices and managing topology. Additionally, existing communication scheduling algorithms of MPI are relatively simple, which directly determine the calls of communication functions such as MPI-Send and MPI-Recive.

The communication kernel for redistributing requests in MPI development provides a many-to-many communication mode for applications with numerous discontinuous requests, which plays a crucial role in the overall system performance. Thus, we can further improve the communication performance of asynchronous MPI implementations, and adopt the communication throttling method to reduce the number of communication contentions to reduce inter-GPU communication delay.

\subsection{Parallelization of algorithms}

Parallel algorithm design plays a crucial role in enhancing performance of simulation applications in supercomputers with multi-GPUs. These algorithms include analog computing functions (such as SNN) and the algorithms studied in this paper~\cite{9748023}. An effective algorithm parallel design divides the models and algorithms into different layers and distributes them to different hardware, while achieving load balance and reducing communication overheads. Both parallelism and scalability should be considered during the algorithm design process. Different designs will directly affect the algorithm running speed on a supercomputer. A preliminary test on our algorithm indicates that a parallel design may speed up the algorithm by more than 10 times.

\subsection{Larger scale simulations of human brain}

Simulation of human brain is a large-scale research project. Although we have designed a low-latency communication framework in the simulation of 10 billion neurons spread across 2,000 GPUs, the simulation realizes part of human brain functions. The secrets of human brain are far beyond our present capabilities. The human brain has 86 billion neurons and the simulation complexity increases exponentially with the number of simulated neurons. We estimate that tens of thousands of GPUs are needed to simulate the entire human brain. An even bigger challenge is that the connections among neurons in the brain do not form a regular network. If a matrix were used to represent the inter-neuron connections in the brain, the matrix would be extremely sparse, which brings in unique challenges to communication design in the simulation system for effectively simulate the rapid information exchange among neurons during the thinking process of human brain.

\section{Conclusion}

In this paper, we investigated the problem of low-latency communications for supporting simulations of large-scale brain models. We first summarized a list of design guidelines for achieving low-latency communications based on our analysis on the communication characteristics in brain simulations. Then we proposed a communication design, including a partitioning algorithm for assigning neurons to GPUs and a two-level routing method for controlling data transmissions among the GPUs, for achieving low-late communications required by brain simulations. Experiment results reported in this paper show that the proposed partitioning algorithm and routing method together may significantly improve the delay performance of inter-GPU communications in brain simulations. We also discussed open issues and identify some research directions in design of a low-latency communication framework in supercomputers.
In our future work, we will continue to conduct large-scale human brain simulations to solve the problem of algorithm parallelization and MPI modification to further enhance the performance of brain simulations.

\bibliographystyle{IEEEtran}