%Title: Current status of FORM parallelization
%Author: M.Tentyukov and J.A.M.Vermaseren
%Published:     <EM> Proceedings of the ACAT08</EM>, 3-7 November 2008, Erice, Italy. Published as <a href="http://pos.sissa.it/archive/conferences/070/119/ACAT08_119.pdf">PoS(ACAT08)119</a> 

\documentclass{PoS}
\usepackage{url}
\title{
       Current status of FORM parallelization
}

\ShortTitle{
       FORM parallelization
}

\author{
  \speaker{
     M.~Tentyukov
  }\thanks{
    Supported by SFB-TR9
  }\\  Institut   f\"ur Theoretische   Teilchenphysik,  Universit\"at
     Karlsruhe, Germany
}
\author{
J.A.M.~Vermaseren \\ Nikhef \\
Science Park 105 \\
1098 XG, Amsterdam
}

\abstract{ We report on the status of the current development in
parallelization of the symbolic manipulation system FORM. There are
two parallel versions available, one is based on POSIX threads and is
optimal for modern multicore computers while another one uses MPI and
can be used to parallelize FORM on clusters and Massive Parallel
Processing systems.

Most of existing FORM programs will be able to take advantage of the
parallel execution, without the need for modifications.  In some cases
some minor additions may be needed.

More information about FORM can be found on the 
FORM web page\\ \url{http://www.nikhef.nl/~form/}
}

\FullConference{XII Advanced Computing and Analysis Techniques in Physics Research\\
		 November 3-7 2008\\
		 Erice, Italy}

\begin{document}

\section{Introduction}

The symbolic manipulation system FORM~\cite{Vermaseren:2000nd} has been
available for more than 20 years. It is specialized to handle very
large algebraic expressions of billions of terms in an efficient and
reliable way. That is why it is widely used, in particular in the
framework of perturbative Quantum Field Theory, where sometimes hundreds of
thousands of Feynman diagrams have to be computed. None of the more
spectacular calculations of refs~\cite{FORMused,parFORMused}, would
have been possible with other available systems.  However, the
abilities of FORM are also quite useful in other fields of science
where the manipulation of huge expressions is necessary.

Some internal specifics \cite{CASC04ACAT05,recentFORM} allow FORM to
deal with expression which are much large than the memory (RAM)
available. The only restriction for the size of the expressions is the
disk space which is rather cheap now. This means, the complexity
of the problem solvable by FORM is restricted practically only by the
time.  In this context an improvement of efficiency is very important.

Parallelization is one of the most efficient ways to
increase performance, so the idea to parallelize FORM is quite natural.

In the late nineties a joint project was started with the University
of Karlsruhe for adapting FORM to run on parallel computers and
clusters.  This has led to the program ParFORM which uses most of the
FORM sources with some extra code in addition. It has been described
in the literature~\cite{CASC04ACAT05,ParFORM} and several calculations
have greatly benefited from it~\cite{parFORMused}.

Last few years most leading
vendors switch to dual- and multicore processors. Hence it was judged
important to create a version of FORM that can make efficient use of
such systems. The above considerations have led to the creation of
TFORM~\cite{TFORM}, the multithreaded version of FORM.

\section{General concepts}

FORM provides a special programming language adapted for the manipulating
of large sequences of algebraic terms and the user supplies programs
written in this language.  The FORM program contains several parts called {\em modules}.
The programs are executed module by module, see e.g. \cite{CASC04ACAT05}.

Mostly FORM allows local operations on single terms, like replacing
parts of a term or multiplying something to it; non-local operations
like replacing a sum of two terms by another term are not allowed.  We
refer to this property as the {\em locality principle}: all {\em
explicit} algebraic operations are local.  Non-local operations are
allowed only implicitly in the sorting procedure at the end of the
modules, when equivalent terms are summed up, and in some special
references to the contents of brackets in the input
expression.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=.7\textwidth]{pformstr}
\end{center}
\begin{center}\Large
{\tt Local expr = }$\underbrace{\tt a\ \hat{}\ 2 + a*x\ }_{To\ Worker\ I}$
$\ $
$\underbrace{\tt+\ x\ \hat{}\ 3 - b*2 }_{To\ Worker\ II}$ 
${\tt\ +}\ \underbrace{\tt .\quad .\quad .\quad }_{To\ next\ workers}$
\end{center}
\caption{
   \label{concepts}  General parallelization concept }
\end{figure}

All the existing approaches to the FORM parallelization consist of a
``Master'' which splits the incoming expression into chunks and
distributes these chunks among ``Workers'', see Fig.~\ref{concepts}.
The workers generate terms, sort them and send sorted terms back to
the master. The master performs final sorting \cite{CASC04ACAT05}.

This is done absolutely ``transparently'' for the FORM programmer, no
special efforts for parallel programming are required. The same FORM
program runs in parallel.

\section{Models in use}

There are two implementation of the above mentioned concept, ParFORM
and TFORM, see Fig.~\ref{models}. The workers are started only once at
the startup.

\begin{figure}[ht]
\begin{center}
\hfill\includegraphics[width=.45\textwidth]{mpi_big} \hfill
\includegraphics[width=.45\textwidth]{threads} \hfill
\end{center}
\caption{
   \label{models} Structures of ParFORM and TFORM }
\end{figure}

ParFORM uses independent processes communicating via a message
passing protocol named MPI\footnote{More about it can be found at
  \url{http://www.mpi-forum.org/}} which makes it suitable to parallelize
the FORM program not only on Symmetric Multi Processor (SMP) computers
but also on clusters and Massively Parallel Processors\footnote{See,
  e.g.,\tiny \url{http://sawaal.ibibo.com/computers-and-technology/what-massively-parallel-processing-mpp-516077.html}.
}

TFORM starts a pool of POSIX\footnote{POSIX, ``a Portable Operating
System Interface for uniX'' is the collective name for a family of
related standards.} threads. A thread is a semi-process, that has
its own stack, and executes a given piece of code. Unlike a real
process, the thread normally shares its memory with other threads.
If the computer is an SMP computer, i.e., it has several CPU cores, each
worker can run on its own core thus speedup the process.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=.8\textwidth]{pAndT}
\end{center}
\caption{
   \label{pAndT}
   Computing time and speedup for the test program BAICER on the
SGI Altix 3700 SMP server with 32x Itanium2 processors (1.3 GHz).
}
\end{figure}

Both models work well and give a speedup of more than 10 on a 32-core
computer, see Fig.~\ref{pAndT}. The speedup is almost linear up to 16
CPU cores.

\section{Features and problems}

One of the main ParFORM disadvantage is its dependence on MPI. Despite
MPI being the industrial standard, various implementations are not binary
compatible so ParFORM should be compiled with exactly the same MPI
version which is installed on the computer. In contrast, TFORM
requires no installation since it is just an executable file.

TFORM shares all resources of a single computer which sometimes leads
to a competition between threads. Common bottlenecks are various
buses, especially the front-side bus, and the local disk storage. In
contrast, ParFORM is able to run independent processes on individual
%computational  % taken out because we have problems with space (JV)
nodes which (theoretically) increases its scalability.
On the other hand, shared address space allows TFORM to implement some
features which are hardly possible for ParFORM. In the future we are
planning to join these concepts in order to obtain the advantages of both
of them, see Section \ref{Outlooks}.

Both ParFORM and TFORM have efficient techniques for load balancing: the
Master immediately sends the next chunk to a ready worker. The smaller chunk
the better load balancing but the worse overhead.  With big chunks,
it is easy to run into clusters of ``bad'' terms. 
A ``bad'' term produces a lot of new terms,
many more than other terms. This means that in the end all other workers will 
be waiting for this worker to finish this or these term(s).

TFORM solves this problem by ``stealing'' the tail of the chunk which is
processed by this ``last'' worker and re-distributing it among free workers.
This is on by default; it can be switched on or off with the
statements\ ``\verb|on ThreadLoadBalancing;|''\ and \hfill \\
``\verb|off ThreadLoadBalancing;|''. 
For ParFORM such kind of load balancing is impossible.

There are some variables in FORM that are an intermediate between
local and global variables, so-called dollar-variables. Since they
might be re-defined during processing of each term, their value can be
nondeterministic in a parallel environment. Indeed, one worker could
define such a variable and then the next one could overwrite this
value before the first worker has used it. Hence their administration
needs special attention.

By default, both ParFORM and TFORM switch into the sequential mode
for each module which gives dollar variables a value during execution. 
But there are common cases 
when some dollar variables obtained from each term in each chunk
natively can be processed in order to get a minimum value, a
maximum, or a sum of results. Also, sometimes at the end of the processing
of a term the value of the dollar variable is not important at all. Hence
new module options have been implemented to help FORM to process these
variables in parallel: \verb|minimum|, \verb|maximum|, \verb|sum| and
\verb|local|. Since TFORM is able to perform centralized
administration of the shared objects the implementation of these
options is rather efficient while ParFORM has to broadcast all dollar
variables to all the workers and then collect them at the end of the
module.

The next problem is Right-Hand Side (RHS) expressions, e.g.
\begin{verbatim}
L   F = a + b;
L   G = x + F;
\end{verbatim}

This is not a problem for TFORM since all threads work with the same
file system while it is a big problem for ParFORM since the expression
may be situated in a scratch file but different nodes may have
independent scratch file systems. For a long time ParFORM forced
evaluation of modules with RHS expressions in sequential mode and now
it is able to treat them in parallel but less efficient then TFORM.

\section{Outlooks and conclusion}
\label{Outlooks}

TFORM is optimal on a relatively small number of CPUs since it
does not suffer from a MPI overhead and can administrate various
shared objects rather easily. But it is restricted to a single SMP computer.
In the future we are planning to join the ParFORM independent-processes concept 
as a ``coarse-grained'' structure for
parallelization on a cluster and the TFORM thread-based approach as a
``fine-grained'' parallelization on multi-core cluster nodes, see
Fig.~\ref{TandPOutlook}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=.6\textwidth]{TandPOutlook}
\end{center}
\caption{
   \label{TandPOutlook} Combination of ParFORM and TFORM }
\end{figure}

At the present moment,
\begin{itemize}
\item
Both ParFORM and TFORM are able to execute almost all FORM programs in
parallel.
\item
ParFORM supports more hardware architectures. TFORM supports
parallelization of more FORM features.
\item
ParFORM requires MPI, TFORM doesn't, which makes it much easy to deploy.
\item
TFORM is optimal for parallelization on a small ($\leq 8$) number of
CPUs.
ParFORM is optimal for parallelization on a large ($\geq 6$) number of
CPUs.
\end{itemize}

In order to get benefits from a parallel version of FORM, some specific 
hardware is required. 

ParFORM can be used on clusters with Gigabit Ethernet interconnection
but it is better to have a faster network, like InfiniBand with
non-blocking topology. Both the parallel FORM versions need a huge and fast
parallel disk storage system. For example, it is not enough for
ParFORM to have a cluster with a Fast Ethernet NFS disk system. It is
important to have huge fast local disk storages on each of the nodes
(hundreds GB per CPU core).

\begin{thebibliography}{9}

\bibitem{Vermaseren:2000nd}
J.~A.~M.~Vermaseren,
arXiv:math-ph/0010025.

\bibitem{FORMused}
S.~Moch, J.~A.~M.~Vermaseren and A.~Vogt,
Nucl. Phys. B {\bf 688} (2004) 101;\\
A.~Vogt, S.~Moch and J.~A.~M.~Vermaseren,
Nucl. Phys. B {\bf 691} (2004) 129;\\
J.~Blumlein and J.~A.~M.~Vermaseren,
Phys. Lett. B {\bf 606} (2005) 130;\\
Y.~Schr\"oder and A.~Vuorinen,
JHEP {\bf 0506} (2005) 051;\\
J.~A.~M.~Vermaseren, A.~Vogt and S.~Moch,
Nucl. Phys. B {\bf 724} (2005) 3;\\
R.~Bonciani and A.~Ferroglia,
Phys. Rev. D {\bf 72} (2005) 056004;\\
Y.~Schr\"oder and M.~Steinhauser,
JHEP {\bf 0601} (2006) 051;\\
K.~G.~Chetyrkin, J.~H.~Kuhn and C.~Sturm,
Nucl. Phys. B {\bf 744} (2006) 121;\\
T.~Aoyama, M.~Hayakawa, T.~Kinoshita and M.~Nio,
Nucl.Phys. B {\bf 740} (2006) 138.
\bibitem{parFORMused}
A.~Retey and J.A.M.~Vermaseren,
Nucl. Phys. {\bf B604} (2001) 281;\\
P.A.~Baikov, K.G.~Chetyrkin and  J.H.~Kuhn,
Phys. Rev. Lett. {\bf 88} (2002) 012001;\\
P.A.~Baikov, K.G.~Chetyrkin and  J.H.~Kuhn,
Phys. Lett. {\bf B559} (2003) 245;\\
P.A.~Baikov, K.G.~Chetyrkin and  J.H.~Kuhn,
Phys. Rev. {\bf D67} (2003) 074026;\\
P.A.~Baikov, K.G.~Chetyrkin and  J.H.~Kuhn,
Eur. Phys. J. {\bf C33} (2004) 650;\\
S.~Bekavac, hep-ph/0505174;\\
P.~A.~Baikov, K.~G.~Chetyrkin and J.~H.~Kuhn,
Phys. Rev. Lett.  {\bf 95} (2005) 012003;\\
P.~A.~Baikov, K.~G.~Chetyrkin and J.~H.~Kuhn,
Phys. Rev. Lett.  {\bf 96} (2006) 012003;\\
P.~A.~Baikov, K.~G.~Chetyrkin and J.~H.~Kuhn,
Phys. Rev. Lett. {\bf 101} (2008) 012002;\\
A.~Kotikov, J.H.~Kuhn and O.~Veretin, 
Nucl. Phys. {\bf B788} (2008) 47;\\
\bibitem{CASC04ACAT05}
M.~Tentyukov {\em et al}, ``Parallel Version of the Symbolic
Manipulation Program FORM'', in: V.G.~Ganzha {\em et al} (Eds.),
Proceedings of the CASC 2004, Technische Universit\"at M\"unchen,
Garching, Germany; arXiv:cs.SC/0407066;\\
M.~Tentyukov {\em et al},
Nucl. Instrum. Meth. A {\bf 559} (2006) 2248.

\bibitem{recentFORM}
M.~Tentyukov, J.A.M.~Vermaseren,
Comput. Phys. Commun. {\bf 176} (2007) 385.

\bibitem{ParFORM}
D.~Fliegner {\em et al}, arXiv:hep-ph/9906426;\\
D.~Fliegner {\em et al}, arXiv:hep-ph/0007221.

\bibitem{TFORM}
M. Tentyukov and J.A.M.~Vermaseren arXiv:hep-ph/0702279

\end{thebibliography}
\end{document}
