
\section{A Computational Chemistry Application}

\subsection{Introduction and Problem Description}

MOPAC is a general-purpose semi-empirical molecular orbital 
package for the study of chemical structures and reactions. 
Semi-empirical Hamiltonians are used in the electronic part 
of the calculation to obtain molecular orbitals, the heat of
formation and its derivative with respect to molecular geometry. 
Using these results MOPAC calculates the vibrational spectra, 
thermodynamic quantities, isotopic substitution effects and 
force constrains for molecules, radicals, ions, and polymers. 
For case studies in chemical reactions, we examined 
a transition-state location 
routine and two transition state optimization routines.

Although MOPAC has been very successfully used in many research 
projects, its application is limited to small molecules, 
typically consisting of no more than 60 atoms. The limitation 
comes from the CPU demand that increases with the number of
atoms $n$ roughly as $O(n^2)$. A possible solution is to port 
the code to parallel or distributed computers. 

Within this project\cite{lin95a}, the computational structure 
of the program is examined in order to identify opportunities for 
parallelization and to select appropriate hardware 
configurations for implementation. A model implementation of 
selected MOPAC routines on architectures of choice 
is conducted and an AVS based visualization front end is built 
to provide visual display and model parameter control of
specific applications based on those MOPAC routines.

The structure of the MOPAC is described in \cite{coolidge90am}.
The execution flow is that it reads in a set of keywords and a set of
atom geometry, checks keyword to decide which subroutine to call, and
goes back to begin of program if there are more sets of atom geometry
to work on. By selecting different keywords, the user may choose one 
of $nine$ basic paths of execution. 
% The main loop in main program is 
% controlled by the variable
% "ISOK". ISOK is set to TRUE in the beginning of main program and will 
% be set to FALSE in deriv.f and readmo.f. However, from the tracing results 
% of all test data sets, ISOK is never set to FALSE 
% thus execution flow never normally ends. Instead, it always reaches 
% a "STOP" statement in subroutine GETTXT called by READMO in normal
% cases.
% 
%\begin{figure}
%\centerline{\psfig{figure=section5/call_compfg.eps,width=1.5in}}
%\caption{General structure of execution flow}
%\label{call_compfg}
%\end{figure}
% 
Most execution flows of the $nine$ paths are similar. After setting 
up the required parameters from the input keywords, they call 
subroutine COMPFG directly or indirectly
and organize the results after calling COMPFG. COMPFG can be called several
times by giving different parameters to perform different functions.
%The general structure of execution flow is shown as Fig \ref{call_compfg}.
The codes of these MOPAC main subroutines are mostly 
preparing data for calling COMPFG and organizing results
generated by COMPFG. Subroutine COMPFG is the computation kernel 
of those subroutines.

\begin{table}
\begin{center}
\begin{tabular}{|l||r|r||r|} \hline
          & \multicolumn{1}{c|}{Total CPU time} & \multicolumn{1}{c|}{COMPFG time} &
            \multicolumn{1}{|c|}{Percentage} \\ \hline\hline
apsbtest  & 4817.16 & 4791.24 & 99.46 \\\hline
porphin   &  734.74 &  726.76 & 98.91 \\\hline
tetrabenz & 2905.28 & 2884.62 & 99.28 \\\hline
\end{tabular}
\end{center}
\caption{IBM SP2 single node timing of kernel subroutine COMPFG}
\label{compfg_all}
\end{table}

We choose three test data from the Bryan's test sets to analyze
the computation time used by COMPFG. Table \ref{compfg_all} shows
the time and the percentage that COMPFG spends in our test sets.
COMPFG takes almost everything in our test sets.

% \begin{table}
% \begin{center}
% \begin{tabular}{|l||r|r||r|r||r|r|} \hline
%         & \multicolumn{2}{c||}{apsbtest} & \multicolumn{2}{c||}{porphin} &
%           \multicolumn{2}{c|}{tetrabenz} \\ \cline{2-7}
%         & Total\% & Times & Total\% & Times & Total\% & Times \\ \hline\hline
% DCART   &  6.51 &    56 & 11.56 &    48 &  8.22 &    36 \\ \hline
% DENSIT  & 16.18 &  1590 & 14.14 &   437 & 15.83 &   298 \\ \hline
% DIAG    & 63.17 &  1516 & 63.98 &   432 & 68.69 &   295 \\ \hline \hline
% Sum     & 85.86 &       & 89.68 &       & 92.74 &       \\ \hline
% \end{tabular}
% \end{center}
% \caption{Timing of the four most time-consuming subroutines}
% \label{all4}
% \end{table}
% 
% We break down and analyze the subroutine COMPFG by our test sets.
% Three subroutines of COMPFG are found taking most computation.
% Table \ref{all4} shows the timing of the three kernel subroutines,
% DCART, DENSIT, and DIAG. They take more than $85\%$ of 
% CPU time in our test sets.
% 

\subsection{System Configuration and Integration}

\begin{figure}
\centerline{\psfig{figure=section5/config.eps,width=6in}}
\caption{System configuration of MOPAC}
\label{configuration}
\end{figure}

The system can be divided into 4 parts. Fig \ref{configuration}
shows the system configuration of MOPAC system.
\begin{itemize}
\item {\bf PCH (Parallel Computation Host)} a parallel computer which 
    handles the computation of time consuming modules.
% For
%    portability reason, we use PVM communication library. Using
%    PVM, we can connect heterogeneous architectures to form a 
%    meta parallel computer in which SUN's, RS6000's, SP2 nodes, 
%    and Alpha's become individual nodes.
\item {\bf SCH (Sequential Computation Host)} a sequential computer 
    which handles file I/O, data distribution, and other sequential 
    modules. It also acts as the coordinator of all computation
    nodes.
\item {\bf AVSH (AVS server)} an AVS server which handles graphic 
    output and controls the execution of modules. 
\item {\bf XDH (X-windows Display Host)} a color workstation or 
    X-terminal with at least 8-bits pseudo color to display
    the graphic output. 
\end{itemize}

The PCH is a meta parallel computer consists of any combination
of SUN4 workstations, IBM RS6000 workstations, DEC Alpha workstations,
IBM SP2, and DEC Alpha Farm. The inter-connection among those computation
nodes is a heterogeneous network consists of 10-base2 Ethernet, IBM 
SP2 High Performance Switch, FDDI, and DEC Giga Switch. The 
PVM based communication program runs over the heterogeneous network
to connect all heterogeneous computation nodes into a meta parallel 
computer. The MOPAC kernel module is initiated remotely by the SCH
and runs on the PCH meta computer. Although the PCH consists many
kind of machines, the real configuration and number of running
nodes can be changed from AVS user interface at run time to 
avoid using busy node and fit the requirements of input data.

The SCH runs an AVS remote module, {\it mopacavs}. The AVS module
{\it mopacavs} is essentially the host program of MOPAC kernel 
module. It takes the parameters from the AVS control panel.
Via PVM based heterogeneous network, it configure the
PCH, initiate computation nodes, and distribute jobs to the 
computation nodes. It also organizes the results and translates
the results into AVS graphic calls. The SCH is a high performance
workstation in our implementation.

\begin{figure}[t]
\centerline{\psfig{figure=section5/avsall.ps,width=6in}}
\caption{The MOPAC graphic interface}
\label{avsall}
\end{figure}

The AVSH in our implementation can be either a SUN4 or an IBM 
RS6000. It runs AVS kernel and handles the communications 
among remote and local modules. The AVS network connections 
of MOPAC modules is shown in the right-lower corner of 
Fig \ref{avsall}. 
% The remote module {\it mopacavs} 
% is the MOPAC host program running on SCH. 
The input parameters
and the configuration of PCH 
are fetched through the control panel of module {\it mopacavs}.
Module {\it atomcntl} controls the display of atom structures.
%As shown in Fig \ref{avscntl}, 
Users can move, zoom, or rotate 
the atom structures by clicking the bottoms on control panel
to get the best view angle of atom structures.
The connection between remote and local modules are handled by AVS.

The XDH in our implementation has been tested on DEC 
X-terminals, SUN4's with 8-bits pseudo color display, and 
IBM RS6000's with 24-bits true color display. The connection 
between XDH and AVSH is based on X-windows.

% \subsection{Performance Analysis}
% 
% \begin{table}
% \begin{center}
% \begin{tabular}{|l|r|r|r|} \hline
%         &  apsbtest   &   porphin   &  tetrabenz  \\ \hline\hline
%  $Tp$   &   85.86\%   &   89.68\%   &   92.74\%   \\ \hline\hline
%  $P=2$  &     1.75    &     1.81    &     1.86    \\ \hline
%  $P=4$  &     2.81    &     3.05    &     3.28    \\ \hline
%  $P=8$  &     4.02    &     4.64    &     5.30    \\ \hline
% % $P=16$ &     5.13    &     6.28    &     7.66    \\ \hline
% \end{tabular}
% \end{center}
% \caption{The maximum speed-up of the test set}
% \label{max_sp_up}
% \end{table}
% 
% The maximum speed-up we can achieve depends on the portion of 
% parallelized code. The more the portion of parallelized code, 
% the higher the speed-up. Suppose the time needed for parallelized 
% code before parallelization is $Tp$, the time needed for sequential 
% code before parallelization is $(1 - Tp)$, the number of computation 
% nodes is $P$. The maximum speed-up is:
% 
% \[ Speed_up = \frac{1}{(1-Tp)+\frac{Tp}{P}} \]
% 
% Table \ref{max_sp_up} shows the maximum possible speed-up of MOPAC 
% if all three kernel subroutines are well parallelized and no 
% communication involved.
% 
% From Table \ref{max_sp_up}, the efficiency of CPU drops sharply
% when the number of processing node is increased. The CPU efficiency
% drops to about $50\%$ when using 8 nodes. The CPU efficiency will
% be even lower in real implementation since communication will take
% time also. There is no reason to use a large number of computation
% nodes in such case. Instead, we should use fewer, but faster nodes.
% 
% \begin{table}
% \begin{center}
% \begin{tabular}{|l|r|r||rr|r|r|} \hline
%  & \multicolumn{2}{|c|}{apsbtest} & \multicolumn{2}{|c|}{porphin}
%  & \multicolumn{2}{|c|}{tetrabenz} \\ \cline{2-7}
%  & \multicolumn{1}{c|}{Time} & \multicolumn{1}{c|}{Speed-up}
%  & \multicolumn{1}{c|}{Time} & \multicolumn{1}{c|}{Speed-up}
%  & \multicolumn{1}{c|}{Time} & \multicolumn{1}{c|}{Speed-up}\\ \hline\hline
%  $P=1$  & 31672 & 1.00 & 4869 & 1.00 & 19007 & 1.00 \\ \hline\hline
%  $P=2$  & 20125 & 1.57 & 3123 & 1.56 & 10804 & 1.76 \\ \hline
%  $P=4$  & 17204 & 1.84 & 2533 & 1.93 &  8588 & 2.21 \\ \hline
%  $P=8$  & 16320 & 1.94 & 2339 & 2.09 &  7848 & 2.42 \\ \hline
% \end{tabular}
% \end{center}
% \caption{The speed-up of the test set on SUN4}
% \label{sunresult}
% \end{table}
% 
% To measure the performance, we need to get exclusive access of a
% both computation nodes and networks. We run our test sets on a 
% SUN4 cluster connected by Ethernet. The results is shown in Table 
% \ref{sunresult}. Due to the slow networking, the SUN4 cluster
% performs only about half of maximum speed-up. The results should
% be close to the maximum speed-up if using machines with high
% performance networks such as SP2 or Alpha Farm.
% 
