%\documentstyle[options]{style}
%revision 2
\documentclass[12pt,titlepage]{report}
\usepackage{graphicx}
\begin{document}
\title{Parallel Particle Framework Project Proposal} 
\author{Martin Casado\\ 
  Northern Arizona University \\ 
  3515 N. Andes Dr.\\ 
  Flagstaff, AZ 86004 
  \and 
  Noel Keen\\ 
  Lawrence Livermore National Laboratory\\ 
  7000 East Ave.  L-39 \\ 
  Livermore, CA  94550 } 
\date{October 17, 1999}
\maketitle
\tableofcontents
\listoffigures
\listoftables
\begin{abstract}
  This document is a proposal to develop the Parallel Particle
  Framework (PPF).  The Parallel Particle Framework will be an API to
  ease the parallelization of Monte Carlo physics packages simulating
  radiation particles.  This document covers the problem statement,
  requirements, specifications, risk analysis, team standards,
  resource and schedule, design process and technical concepts to be
  used by the Parallel Particle Framework team.
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%Problem Statement%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{Problem Statement}

\section{Background}

Physical modeling of real world phenomena often demands significant
computer resources, such as speed and memory, that far exceed that
offered by even the largest single processor or shared memory systems.
The national laboratories including Lawrence Livermore, Sandia and Los
Alamos, are using large distributed computer networks to handle these
problems.  Parallelization of an algorithm across a distributed
network is not a mechanized process and the approach differs
drastically between problems.  Fortunately, some of these problems can
be classed, and generic solutions applied to them.  One class of these
problems is radiation transport problems.

Radiation transport using the Monte Carlo method is well-known and is
used extensively at Lawrence Livermore National Laboratory (LLNL).  To
accurately model a sophisticated three-dimensional problem including
detailed geometry specification it is common to represent the problem
with a {\it mesh}.  The resolution can be controlled by the number of
{\it zones} in the mesh which dictates the size of the problem, that
is the amount of memory needed to store the mesh.  As the mesh sizes
%  perhaps a better phrase than ``will not fit''  can be found...
become large it will not fit on even the largest single memory unit.
(Note that even if it could, we would still want to run an even larger
problem simply because we can -- i.e. distributed memory...)  Therefore,
in order for the Monte Carlo particle packages to handle problem
descriptions larger than conventional memory on a single shared memory
node, the problem must be distributed across multiple nodes.  A
distributed network computer must then {\it domain decompose} the mesh
such that it can be read into memory.  Using a distributed network
computer requires the application to communicate between nodes using
message passing techniques such as with the MPI library.  Learning the
details of distributed computing requires time and experience not
common to many developers of particle transport packages.  In order to
provide developers with an intuitive interface to efficiently handle
domain decomposition and particle passing, we propose development of
the Parallel Particle Framework.

\section{Business Issues}

%  some of what you say here is redundant.  you could prolly shorten this 
%  and list about 3 general points...  but i think you've covered everything...
Radiation particle packages are written largely by physicists without
formal backgrounds in computer science.  Learning the intricacies of
distributed computing and applying it to a project increases the time
of development and may compromise the correctness of that project.
More specifically, the business issues surrounding the parallelization
of radiation transport packages are as follows:

\begin{itemize}
\item Parallel training increases project times.
\item Parallel computation is not germain to many package developers
  fields and can be viewed as a waste of resources.
\item Efficiency and correctness of parallelization requires
  experience and knowledge of architectures that many radiation
  transport developers lack.
\item Currently, each developer is approaching the parallelization
  problem differently.  The absence of a common structure makes this
  class of code difficult to maintain.
\item Current parallelization techniques used are not conducive to
  future changes, such as:
  \begin{itemize}
  \item increased scalability
  \item load balancing
  \item optimization techniques
  \end{itemize} 
\item Current parallelizations are not abstracted from the code to
  support adaption to new parallelization technology.
\end{itemize}
        

\section{Product Statement}

The Parallel Particle Framework ({\bf PPF}) project involves designing
and developing an API which will be integrated into physics modules
within the KULL\footnote{KULL is a large physics modeling package
  currently in development at LLNL} framework.  The API will provide a
high level interface for the parallelization of particles over large
meshes\footnote{a mesh is a collection of geometric components which
  represent a physical problem} for radiation transport physics packages
developed within KULL.  The PPF will decompose the problem mesh over
large distributed super computers and handle all communication of
particles moving between nodes.  The API must be constructed to
integrate into existing physics packages without changing the original
programs' paradigms.

\section{Projected Value}

The goals of the PPF are to save time in developing particle Monte
Carlo packages and to provide a standard method of parallelization.
Benefits of a technological solution are:
\begin{itemize}
\item Reduction of development and training hours in order to reduce
  the time and cost of a project.
\item Maximization of resources by enabling physicists to concentrate
  on work applicable to their areas of study.
\item Ensured correctness in parallelization.
\item Increased maintainability of code, due to standardization.
\item Ensured robust, efficient parallelization over distributed
  systems, improving the end product.
\item Preparation for future changes to distributed mechanisms by
  abstracting parallelization methods.
\end{itemize}

\section{Business Environment}

The parallel particle framework is intended to be integrated into radiation 
transport packages within the KULL framework.  The KULL project environment
requires the PPF to adhere to the following constraints:

\begin{itemize}
\item It must conform to the C++ standard.
\item It must compile on Digital Unix and AIX using the KCC compiler.
\item It will follow the KULL documentation standards.
\item Builds should be easily integrated into the larger KULL make system.
\end{itemize}

Since the PPF is meant to be integrated not only into new projects but 
existing code, the interface must be conducive to the parallelization of 
serial code.  That is to say, PPF must not require the project architecture
to be built around it, but more so be easily integrated into existing 
architectures. 

In general, applications which use the PPF must accept following assumptions:\\

\begin{itemize}
\item Particles do not interact with each other.  They are absolutely independent.
\item Particles contain the following base information:\\
  \begin{itemize}
    \item position in the mesh({\it x,y,z})
    \item direction of travel({\it u,v,w})
    \item time({\it t}) since being sourced
    \item energy({\it E}) carried
    \item current zone in the mesh
  \end{itemize}
\item The mesh is rigid and particles move through the mesh. 
\item Particles are simulated and change mesh-based values such as
  energy deposited, material temperature, etc.) which are quantities
  of interest in the problem.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Requirements%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Requirements}


\section{Goals} 

The goal of the PPF is to be a robust, efficient, and correct library
to help in the parallelization of radiation particle transport
packages.  Specifically the goals of the PPF are to:

\begin{itemize}
 \item Distribute workload of radiation particle transport problems
  semi-efficiently between nodes of large distributed supercomputers.
 \item Provide scalability of a problem across arbitrary nodes.
 \item Decompose the problem mesh across across multiple nodes transparently
       to the developer.
 \item Provide transparent particle passing between nodes/mesh sections.
 \item Eliminate the need for developers to learn the intricacies of
      distributed parallel programming.
 \item Provide a standard for particle physics module architectures.
 \item Reduce development and training time for radiation particle transport packages.
 \item Create a tracking system to aid in particle visualization.
\end{itemize}
\section{Benefits}

The benefits of creating a unifying parallelization library are as follows:

\begin{itemize}
\item Timeliness: The PPF will perform much of the work of
  parallelization so the code does not have to be re-written for each
  package.
\item Efficiency: The PPF will ensure efficiency in message passing by
  limiting the amount of data that is passed, and only passing data
  when appropriate.
\item Consistency: Packages using PPF can be contrasted because a
  unifying parallel framework provides consistent performance in the
  parallel regions.
\item Accuracy: The PPF will ensure accuracy in parallelization so
  that particles are not lost, transported incorrectly or delayed.
\end{itemize}

\section{Software Requirements}

Since the parallel particle framework is a library to be used by
developers of large physics problems where correctness and efficiency
is crucial, the library must have the following attributes.

\begin{itemize}
\item Ease of Use: PPF must provide a simple interface that is
  intuitive to a developer with no experience in parallel computing.
  All code dealing with parallelization technology must be transparent
  to the developer.
\item Efficiency: Large scale problems running billions of iterations
  on thousands of nodes can continuously accumulate small efficiency
  problems eventually leading to a significant increase to the running
  time of the problem.  For this reason the PPF must be extremely
  efficient in message passing and performance.
\item Stability: Problems run by radiation transport particle packages
  may take days to complete. For this reason it is imperative that PPF
  be stable by ensuring no runtime errors nor memory leaks.  This is
  more important for PPF than other small scale applications because a
  faulty run can cost the developers days at a time. In the advent of
  a crash PPF should be able to resume operation at the last time step
  completed.
\item Scalability: The platforms used for large scale radiation
  transport problems are continuously growing in size, therefore in
  order for PPF to be of use in the future it must be scalable to an
  arbitrary number of nodes efficiently.
\item Longevity: PPF must ensure the integrity of all its requirements
  for the life of the package which implements it. The KULL framework
  is expected to be a 20 year code, the PPF should retain
  functionality for at least this time period.
\end{itemize}
\section{Functional Requirements}

The following two lists are details of the costumers needs and wants for the 
Parallel particle frameworks functions.

\subsection{Needs}

\begin{itemize}
\item The library must be able to handle split meshes by indexing
  matched faces between mesh partitions.
\item During runtime the PPF must be able to make the following
  decisions correctly:
 \begin{itemize}
 \item when to stop tracking particles on a partial mesh and send
   particles frozen on a split surface to another domain
 \item how many particles to buffer before sending
 \item how often to perform checks whether or not to send buffered particles
 \item when to ask if another domain is ready to send particles
 \item how to handle load balancing if possible
 \item what to do if one domain ends up with too many particles to fit in memory
 \end{itemize}
\item Particles must be sent as efficiently as possible.
 \begin{itemize}
  \item particles should not be packaged with extra information for sending
  \item data should only be sent to nodes which require it, no broadcasts
 \end{itemize}
\item Particle transfers between nodes must be accurate.

\item The library's interface must be intuitive and not dependent on a prior
knowledge in distributed computing.
\end{itemize}

\subsection{Wants}

\begin{itemize}
\item The library may handle large mesh sizes and adapt to changes in the
  mesh interface.
\item The PPF may provide support for general domain decomposition and
  work sharing between nodes.
 \begin{itemize}
 \item The mesh may be re-decomposed dynamically to handle load balancing.
 \item The PPF may use a domain replication scheme to fairly distribute work loads.
 \end{itemize}
\item The PPF may include shared memory parallelization within each
  node using pthreads or OpenMP.
\item The library may include extensions for particle visualizations.
\item The library may decompose any given mesh using a graph cutting
  package such as Parmetis.
\end{itemize}

\section{Non-Functional Requirements}

\begin{itemize}
 \item All code written for PPF must be compatible with both the egcs and KCC compilers
 \item Programming must conform to sound object oriented design, and make use of MPI2
       if a reliable implementation is found for the IBM SP2 architecture.
 \item PPF code must have general compliance with POSIX standards.
 \item There must be readable and comprehensive documentation in all stages of
       the development process.
 \item The library must compile and run on AIX 4.3 and DEC Unix.
\item The library must be easily integrated into the make system of existing
      projects. 
\end{itemize}

\section{Additional Constraints, Concerns or Requirements}
\begin{itemize}
 \item KULL is an export controlled technology and the PPF could fall under
       this category so open source may be impossible.
\end{itemize}

\section{Appendix: API Functionality Overview}
\begin{center}
{\small (For interface description and function specifics, refer to chapter 7)}
\end{center}

%create a temporary box where the picture will be
\makebox[4.563in]{\rule{0in}{3.813in}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%Risks Analysis%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Risk Assessment}

The following section provides an overview of potential risks in
developing the PPF, risks will be divided into the following categories:

\begin{itemize}
\item{Product Size Risk}
\item{Business Impact Risks}
\item{Process Risks}
\item{Technology Risks}
\item{Development Environment Risks}
\end{itemize}

\section{Product Size Risks}

\begin{tabular}{||l||}\hline
\cr{\bf{\LARGE{Risks}}}\\ \hline
Addition of extraneous code not directly pertinent to a project.\\ \hline
Limited number of users may limit PPF's benefits.\\ \hline
The library may unnecessarily complicate the project using it.\\ \hline
Attempts to save a problems progress in the advent of failure may\\ use
large amounts of system resources including drive space.\\ \hline
The PPF may add a disproportionate amount of overhead to small\\ problems.\\
\hline
\cr{\bf{\LARGE{MITIGATION}}}\\ \hline
Development efforts should focus on limiting the code for\\ PPF to
only handle particle passing and mesh decomposition\\ which is
common to all projects.\\ \hline
During requirements capture, PPF's usefulness should be\\ evaluated in
light of the number of foreseeable clients.\\ \hline
Efforts should be made during development to make the library\\ linkage and
interface as simple as possible.\\ \hline
PPF should only do large data dumps to hard disk if explicitly\\ sanctioned by
the user.\\ \hline
It should be agreed by developers to use PPF only if the problems\\ they run are
large enough to warrant it.\\ \hline
\end{tabular}

\section{Business Impact Risks}

\begin{tabular}{||l||}\hline
\cr{\bf{\LARGE{Risks}}}\\ \hline
Delivery deadlines may be unreasonable.\\ \hline
Late deliveries may result in additional costs to Livermore.\\ \hline
Defects in the PPF may have negative consequences.\\ \hline
Governmental constraints may inhibit development of PPF.\\ \hline
Integration into larger systems may be problematic.\\ \hline
The PPF interface may be too difficult to use by developers.\\ \hline
The the developers needs may not remain consistent over time.\\ \hline
Senior management at Livermore may not approve of the PPF.\\ \hline
Documentation for developers may not adequately describe the PPF.\\ \hline
\cr{\bf{\LARGE{Mitigation}}}\\ \hline
Careful planning in the design phase will help provide\\ reasonable
deadlines for deliverables.\\ \hline
Developers intending on using PPF will be updated as to its\\
progress during development so they will be able to plan around the projects
progress.\\ \hline
The PPF must be thoroughly tested to eliminate defects.\\ \hline
Full specification and design of project must be presented\\ and approved of by
senior LLNL management before development.\\ \hline
Packages which will include the PPF must be carefully studied\\ during design
to ensure that there will be no incompatibility issues.\\ \hline
Efforts must be directed towards keeping the PPF interface simple.\\ \hline
The PPF should provide a basic functionality that will be\\ useful
for the life of the KULL project.\\ \hline
As stated before, the proposal of the project must pass senior\\ management
approval.\\ \hline
Each stage of the design and the development process must be\\ fully documented.\\ \hline
\end{tabular}

\subsection{Process Risks}

\begin{tabular}{||l||}\hline
\cr{\bf{\LARGE{Risks}}}\\ \hline
There is no process standard for development.\\ \hline
The lack of a write-up on the process may result in\\ design and
development in an ad-hoc fashion.\\ \hline
Communication barriers between Livermore and Northern Arizona\\ 
University can result in discrepancies in the process design.\\ \hline
There has not been any full projects similar to PPF to base\\ the
process on.\\ \hline
Both members of the project are relatively inexperienced in\\ organized process
for design and development.\\ \hline
Time constraints will limit testing and code review.\\ \hline
The nature of the PPF limits test case design and use cases.\\ \hline
\cr{\bf{\LARGE{Mitigation}}}\\ \hline
The PPF should follow a commonly used process that has\\ proven
to be effective on other projects.\\ \hline
An effort should be made to document all aspects of the\\ process
to aid in a structured development stage.\\ \hline
Planned weekly meetings and regular email exchanges will\\ help
ensure both parties are on the same page.\\ \hline
Attention of the process selection based on the nature of\\ the
project will provide a basis for design in the absence of\\ experience.\\ \hline
Reviewing process decisions with professors/managers will\\ help correct
mistakes made from inexperience.\\ \hline
The project scope must be limited in light of time constraints\\
to guarantee a functional and stable product.\\ \hline
Interface issues can be resolved by approaching developers\\ who intend
to use the PPF library.\\ \hline
\end{tabular}

\subsection{Technology Risks}

\begin{tabular}{||l||}\hline
\cr{\bf{\LARGE{Risks}}}\\ \hline
Parallelization techniques may become outdated within a few years.\\ \hline
Load balancing is difficult and ensuring optimality is\\ virtually impossible.\\ \hline
The PPF will be interfacing with BLUE's hardware which\\ is experimental and unproven
in stability.\\ \hline
Misuse of the PPF will compromise its performance.\\ \hline
Simplifying the interface may compromise the library's\\ functionality.\\ \hline
The nature of the project requires facing problems which\\ have not
been dealt with or mitigated in the past.\\ \hline
There is an uncertainty that the requirements requested\\ are doable.\\ \hline
\cr{\bf{\LARGE{Mitigation}}}\\ \hline
The parallelization mechanism should be abstracted from\\ the functionality
of the PPF so changes to a new technology will not be\\ difficult.\\ \hline
It should be understood by the developers who use PPF\\ that the load
balancing may not be optimal.\\ \hline
Frequent comparison between builds on a proven system\\ such as the
TERA cluster will help isolate errors caused by anomalous\\ behavior
by BLUE.  These problems can be brought to the attention\\ of Livermore
Computing and/or IBM.\\ \hline
Careful and comprehensive documentation will help prevent\\ product misuse.\\ \hline
The priorities within the project must be analyzed prior\\ to design. If one decision
compromises another the one with higher priority is chosen.\\ \hline
If a perfect algorithm cannot be developed to handle all\\ cases, a heuristic
will have to do, and all shortcomings of the algorithm used\\ must be documented.\\ \hline
If the requirements prove to be to difficult a review of the\\ requirements
must be brought before the clients and an acceptable compromise\\ must be
reached.\\ \hline
\end{tabular}


\subsection{Development Environment Risks}

\begin{tabular}{||l||}\hline
\cr{\bf{\LARGE{Risks}}}\\ \hline
The project team does not have access to a process management tool.\\ \hline
The project team has little access to design and analysis tools.\\ \hline
Popular design and analysis tools are not appropriate\\ for development of
the PPF.\\ \hline
Compatibility between the KCC and egcs compilers may be problematic.\\ \hline
Cross platform compatibility may prove problematic.\\ \hline
The project members have no experience debugging threads\\ on the sp2 or
Digital Unix platform.\\ \hline
Thread debuggers for all platforms may not be available.\\ \hline
\cr{\bf{\LARGE{Mitigation}}}\\ \hline
Process management can be accomplished by use of programs\\ such as
Microsoft Project run on a separate machine than that used\\ for the
project.\\ \hline
The PPF project does not warrant any special tools for design\\ or development,
design should be rather straightforward as the library\\ has relatively
few use cases.\\ \hline
Again the nature of the PPF project does not require\\ the use of 
extravagant design and development tools.\\ \hline
All code for the PPF must follow the C++ standard.\\ \hline
Continuous builds on all target platforms will ensure\\ compatibility at
every step of the development process.\\ \hline
Project members must research debugging methods for threads\\ on the sp2 and
Digital Unix platform.\\ \hline
In the case that an adequate debugger is not found, the\\ threads can be
debugged separately from the running code using a traditional\\ debugger.\\ \hline
\end{tabular}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Team Standards%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{Team Standards}
\section{Roles}
\subsection{Leader} Martin Casado
\subsection{Communicator} Martin Casado
\subsection{Recorder} Martin Casado
\subsection{Project Design} Martin Casado, Noel Keen
\subsection{Programmers}Martin Casado, Noel Keen
\section{Meetings}
\subsection{Weekly Time for Outside Meetings}
Weekly meetings will be held Wednesdays between 11:30am and 12:30pm
over the phone, unless conflicting with Noel's schedule at LLNL. If a
meeting is missed it will be held at a later time or by discussion via
email.
\subsection{Standard agenda}
The following items will be discussed in each meetings if applicable.
\begin{itemize}
\item Review of last meeting
\item Review of previous weeks goals for current week
\item Discussion of current status of the project
\item Discussion of how we succeeded or fell short of goals set at previous
meeting
\item Discussion of problems in development and design
\item Set goals for the next week
\item Conclude
\end{itemize}

\subsection{Decision Strategy} All decisions will be made upon agreement
by both Martin Casado, and Noel Keen.  If opinions result in a deadlock
Dr. Pat Miller's opinion on the matter will serve as the final decision.
\subsection{Minutes}  Minutes will be kept for each meeting by Martin Casado
and distributed via email to Noel Keen and Stu Wecker by the end of the day
Wednesday.
In the advent that the meeting did not take place at its scheduled time
on Wednesday, minutes will be distributed via email at the end of the day
in which the meeting took place.
\section{Documentation}
\subsection{Typesetting Language} All documents produced during the
parallel particle framework project will be done using the \LaTeX\
$2\varepsilon$.  
\subsection{Coordination} All documentation will be written by Martin
Casado and submitted to Noel Keen for editing and revision.  If time
constraints restrict Noel from going over the paper, Martin will submit
the papers directly.
\subsection{Version Control}
Documentation revision numbers will be maintained in the comments
at the top of each \LaTeX\ file.  All changes should be added to the
comments, as well who made the changes and the date.  Official copies of all 
documents will be kept by the document coordinator. 
\subsection{Format}
All documents will adhere to \LaTeX\ file templates and document classes
which will be created and revised as the project progresses. Each document
will use the standard \LaTeX\ styles, and set the following options
\begin{itemize}
\item 12pt font
\item oddside margin 2.54 centimeters
\item evenside margin 2.54 centimeter
\item Roman style font
\end{itemize}
\subsection{Review Process}
Documents will be written by Martin Casado and submitted to Noel Keen for 
review.  All drafts must be finished by a pre-determined deadline and
submitted for review before the final paper is written.  
\section{Development Standards}
\subsection{Version Control}
All code versioning will be done through Perforce on the LC machines and
CVS in Linux.
\subsection{Commenting and Documentation}
All comments and documentation of development will follow KULL documentation
standards defined by the KULL team.
\subsection{Compilers and Platforms}
All program development will be on the UNIX operating system and support
the following platforms.
\begin{itemize}
\item IBM AIX 4.3
\item Digital Unix
\item Linux
\end{itemize}
All code developed will compatible with the KCC and ecgs compilers.
\section{Self Evaluation Methods}
\subsection{Weekly Evaluations}
Each week, Noel Keen will submit a quick email memo evaluating Martin's
performance on the project.  Each evaluation will be printed and saved
in the project notebook, and submitted to Stu Wecker upon request.
Martin will as well, submit a personal evaluation into the project folder
weekly.
\subsection{Evaluation Contents}
Each evaluation will discuss positive aspects of Martin's performance as
well as negative, and provide a final statement on whether the performance was
low, average or well done.
\section{Standards for Behavior/Cooperation}
\subsection{Design Changes}
All design changes must be approved by Noel Keen.  Both Noel Keen and Martin
Casado can propose design changes.
\chapter{The Design/Development Process}
\section{Methodology}

We propose to use the iterative design process for construction of the
Parallel Particle framework. Preliminary steps for development are as follows:\\
\begin{itemize}
\item Create workspace with working PolyMesh code.
\item Develop a fake physics package to randomly move particles around the mesh.
\item Write a driver file to model a use of the PPF
\item Create the skeleton of the PPF. All methods should be defined, however to begin
      with they will have no functionality.
\item Incrementally add functionality to the methods.
\end{itemize}

\section{Deliverables}

During the course of the PPF project, deliverables demonstrating the teams progress
will be submitted to Livermore for review.  The deliverables will include:

\begin{itemize}
\item PPF interface description documentation
\item PPF OO architecture write-up
\item PPF skeleton mock-up
\item PPF demonstrating basic functionality on a false physics package
\item Test results for runs of PPF on:
\begin{itemize}
        \item large particle sets, few nodes
        \item large particle sets, many nodes
        \item large particle sets, serial run
        \item small particles sets, few nodes
        \item small particles sets, many nodes
        \item small particle sets, serial run
\end{itemize}
\item Final product
\end{itemize} 

\chapter{Resources}


\section{Tools and Environment}

The following is a list of software and hardware resources available to the PPF
project team:\\

\subsection{Compilers}

The compilers which will be used for PPF development are as follows:

\begin{itemize}
\item egcs 2.95.1
\item KCC 3.4d
\end{itemize}

Compilers may be updated during development.
\subsection{Platforms}

All targeted platforms are large-scale distributed supercomputers at Livermore.  If
time is available during development, PPF will be ported to Linux as well.

Need:
\begin{itemize}
\item TERA Cluster
  \begin{itemize}
  \item 24 DEC AlphaServer 4100 Model 5/533 SMP systems
  \item Each system has 4 CPU's and 1 GB memory
  \item Processor speed of 533 MHZ
  \item Currently available with 23 nodes
  \item All nodes run Digital UNIX 4.0
  \end{itemize}
\item ASCI Blue-Pacific
\end{itemize}
Want:
\begin{itemize}
\item Linux
\end{itemize}

\subsection{Version Control}

\begin{itemize}
\item Both Blue and the Tera cluster share an NFS drive.  One both of these platforms
{\bf Perforce} will be the revision control system.
\item If time constraints permit the development of PPF on Linux, CVS will be used
for revision control.
\end{itemize}

\subsection{Debuggers}

\begin{itemize}
\item TotalView
\item gdb on Linux?
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Technical Concept%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Technical Concept}

\section{Discussion of Views}

This section describes the PPF with respect to its function, 
data flow, and interaction with the current environment. 

\subsection{Functional View}

Functionally, the PPF is a library which is compiled or linked with the physics
package using it.  All methods available to the user from the PPF are public
methods in the PPF\_Interface class.  The PPF is
intended to mask the programmer from the intricacies of parallel programming
as well as distributed domains.  Figure 7.1 diagrams the users perspective
when using PPF with a physics package.
 
\begin{figure}[ht]
\begin{center}
\includegraphics{functional.eps}
\end{center}
\caption{Programmers view of physics package with PPF.  PPF hides issues of multiple
domains and all MPI programming.} 
\end{figure}

\subsection{Data Flow}

The major component of data within a package using the PPF is the particle.  The
particle is passed between the physics code and the PPF throughout program execution.
The figure 7.2 illustrates the particles interactions with the package and
the PPF during runtime:

\begin{figure}[ht]
\begin{center}
\includegraphics{DataFlowDiagram.eps}
\end{center}
\caption{Flow of particle interactions in a package using PPF} 
\end{figure}

\subsection{Physical View}

Packages using the PPF will be run as MPI programs.  At the start of execution
the program binary will be distributed to all participating nodes.  During program
execution, the PPF will use MPI as a medium of communication between nodes.  All
buffering issues will be handled by the PPF.   

\section{Preliminary Design}

\subsection{Block Diagram}

An abstracted view of high-level object interactions can be seen in figure 7.3.

\begin{figure}[ht]
\begin{center}
\includegraphics{BlockDiagram.eps}
\end{center}
\caption{Block diagram of component interactions of a package PPF in a 
using PPF in parallel environment.}
\end{figure}

\subsection{Interface Option 1}

The following preliminary design option gives the PPF more control over the
particles. The added control enables the PPF to force the programmers to
correctly implement domain decomposition of their code and cuts down on
the amount of code the developer using the PPF must write.  The drawbacks
of implementing the PPF with more control is that it makes it more difficult
to integrate the PPF into existing code and packages using the PPF will contain
large amounts of proprietary code that is PPF specific.\\

\begin{itemize}
\item {\bf PPF.submitParticles} pass the PPF a pointer to the list of particles
\item {\bf PPF.reset} set the current position in the particle list to the first particle
\item {\bf PPF.nextParticle} return a pointer to current particle in the list, advance
current particle to the next particle in the list
\item {\bf PPF.moveTo} move current particle to x position, y position in mesh (Note:
message passing must be considered in this method)
\item {\bf PPF.getParticle} return the current particle
\item {\bf PPF.addParticle} add a single particle to the current position
\item {\bf PPF.distributeParticleList} add the particles within a linked list to
the current list of particles by randomly distributing them throughout the current list.
\item {\bf PPF.deleteParticle} delete current particle, or particle at a given index
\end{itemize}

\subsection{Interface Option 2}

A minimalist approach to the design of the PPF give the developers more freedom
to apply PPF to various problems and code structures.  However, the PPF will not
be able to guaranty load balancing and development under these loose guidelines may
be detrimental to the integrity of the architecture of the package.  A minimal 
interface for the PPF package must include the following methods.\\

\begin{itemize}
\item {\bf PPF.moveTo} Move a particle to a different node
\item {\bf PPF.sendParticles}  Send all of the particles frozen on a nodes edge to the 
neighboring node.
\item {\bf PPF.recieveParticles} Receive particle list being sent from a different node.
\end{itemize}

This model assumes that all other concerns of particles positions are handled
by the package developer.  

\subsection{Appendix I: Example Driver File Pseudo-Code}

The following code snippet is an example of how the PPF may be used in a project.
Particle packages as not limited to a single design however, a method's logical position
within the codes execution structure must remain the same.

\begin{verbatim}

(1) Compute One Time Step {
(2)   generateSources()
(3)   Loop over Particles{
(4)       Advance Particle {
(5)          Do Work
             if Frozen {
(6)             PPF_Submit(particle)
(7)             Erase particle from current node             }
(8)          PPF_SendFrozenParticles()
(9)          PPF_RecvFrozenParticles()
          }
       }
(10) PPF_DoneAdvancing()
(11) if(PPF_NumRemainginPsarticles == 0){
(12)     we are done with this time step
     }
(13) PPF_Repartition()
     Replicate Mesh()
\end{verbatim}

\subsection{Appendix II: Driver Description}
\begin{enumerate}
\item Each time step is an independent parallel problem.  All particles
      must be run to completion in each time step before continuing.
\item This line generates the source particles which are coming from
      outside, sources within the mesh, or are ``census particles'' which
      are particles left over from the last time step.  Source particles
      also include any previous ``combining'' of particles.
\item The important item here is that the particles do not need to be
      computed in any particular order (Note: there is a potential for
      cache optimization here).
\item Move the particle within the mesh
\item Each particle's work can be computationally intensive, this is where
      the runtime code spends most of its time.
\item The application code using PPF decides which particles have hit the mesh
      boundaries and at what times, these particles are then submitted to the
      PPF. 
\item Application removes particle from list of particles still advancing.
\item Ask PPF to send all particles to the correct nodes.
\item Ask PPF to receive particles sent from other nodes
\item Let PPF know that the the advancing particles loop is finished.
\item If there are particles that are jumping back and forth between 
      meshes, keep iterating until they have all terminated, otherwise
      the time step is finished.
\item If PPF handles general domain decomposition it must be done between
      time steps, here we can re-partition and replicate.
\end{enumerate}

\section{Feasibility}

The issues that have not been resolved are as follows:

\begin{itemize}
\item If a node's memory is completely used by the particles within that
      mesh partition, how can PPF stop particles being sent to that node?
   \begin{itemize}
   \item If particles are stalled within the MPI\_Send of the sending
         nodes then we risk buffer overflows on the sending sides system
         buffer.
   \item If we require programmers to check whether a node's memory is
         saturated we compromise ease of use and PPF becomes more difficult
         to integrate into existing code.
   \item If we manage to stop sends to that node there are a number of timing 
         issues we must deal with.
   \end{itemize}
\end{itemize}

\chapter{Architecture}
 
We have decided to begin by implementing the second option mentioned in the design section.
This method allows the package programmer more flexibility since the PPF is only responsible for
send and receives of lists of particles.  Secondly, this method allows the PPF to be more easily
integrated into existing code because it demands less PPF specific sections.  In the advent that
the PPF should need more control, it can be implemented on top of the current method which is a
logical stepping stone.
 
\section{Class Descriptions and Interactions}
 
The PPF will be designed using a minimum of five classes distinguished by responsibility.\\
 
\begin{itemize}
\item {\bf PPF\_Interface} Facade class \footnote{  \underline{Design Patterns}, Gamma, Helm,
Johnson, Vlissides. Addison Wesly, 1995. Pg 185-193} whose responsibilities are as follows:
 \begin{itemize}
   \item knows which subsystems' classes are responsible for a request
   \item delegates client requests to appropriate subsystem objects
  \end{itemize}
 
\item {\bf PPF\_Statistics} Keeps track of statistics for each run including:
 \begin{itemize}
   \item number of particles sent from current node
   \item number of particles received from each neighbor
   \item average time for send and receives
   \item average time between send and receives
   \item time it took for the run from initialization to conclusion
  \end{itemize}
 
\item {\bf PPF\_Timer} Simple utility timer accurate to milliseconds
 
\item {\bf PPF\_Logic} Handles all logic for particle passing, including:
 \begin{itemize}                                                      
  \item which domains to pass particles too
   \item which domains to receive particles from
   \item if not enough particles are in a list don't send it (unless the send is forced)
   \item if the current node is out of memory, write particles to disk
  \end{itemize}
 
\item {\bf PPF\_Parallel\_Wrapper} Wrapper class to abstract all parallel calls to MPI
\end{itemize}
 
Figure 8.1 shows a general block diagram of class interactions in the PPF.
 
\begin{figure}[ht]
\begin{center}
\includegraphics{GenClassDiagram.eps}
\end{center}
\caption{Flow of particle interactions in a package using PPF}
\end{figure}
 
\section{Data Structures}
 
The architectural approach we choose in creating the PPF does not require
an extensive use of data structures.  Rather, the majority of the code
will involve the technicality of sending particles between nodes and
keeping track of statistics. However, the PPF will include the following
data structures:
 
\begin{itemize}
\item Particles will be stored and passed between functions in linked lists or
vectors from the Standard Template Library.              
\item Each node will contain a lookup array defining the neighbors.  An enumerated
type will represent each of the nodes sides and the neighbor's ID will be placed
in the index represented by the value of the enumerated type of that side.
\end{itemize}
 
This list is by no means inclusive, for example disk writes of particles
in saturated nodes may require the use of buffers and lookup tables.
 
\chapter{Schedule}
 
\section{Project Table}
 
The following project table is a planned schedule for spring semester, 2000.
 
\begin{tabular}{|l|l|l|}
\hline
\bf Work Tasks & \bf Planned Start & \bf Planned Complete \\
\hline
1. Finish Proposal & & \\
   Specs & finished & finished\\
   Research & finished & finished\\
   Schedule & wk1, d2 & wk1, d4\\
   Architecture & wk1,d2 & wk1, d5\\
2. Validate with Sponsor: & & \\
   Meet with Sponsor & wk2,d3 & wk2,d3\\
   Validate Web-site & wk2,d1 & wk2,d3\\
3. Do Detailed Software Design & &\\
   Data & wk2,d4 & wk2 d6\\
   Processes & wk3,d1 & wk3,d3\\
   Objects   & wk3,d3 & wk3,d5\\
4. Coding and Implementation & &\\
   Interface Class and Headers & wk4,d1&wk4,d3\\
   PPF\_Logic Prototype & wk4,d3 & wk5,d3\\
   Parallel\_Wrapper & wk5,d1 & wk6,d1\\
   PPF\_Logic with Wrapper & wk6,d1 & wk7,d3\\
   Statistics and Timer & wk7,d3 & wk8,d1\\
5. Finish Code & &\\                                  


   Testing & wk8,d1 & wk10,d5\\
   Revision & wk8,d1 & wk10,d5\\
   Review & wk8,d1 & wk10,d5\\
6. Finish documentation & &\\
   Code Documentation & wk11,d1 & wk11,d5\\
   Project Usage Documentation & wk11,d1 & wk11,d5\\
\hline
\end{tabular}
 
\section{Gantt Chart}
 
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\bf Work Tasks & Wk1 & Wk2 & Wk3 & Wk4 & Wk5 & Wk6
\\ \hline
1. Finish Proposal & & & & & & \\
   Specs & & & & & &\\
   Research & & & & & &\\
   Schedule &xxxx& & & & & \\
   Architecture &\_xxxxx&&&&&\\
2. Validate with Sponsor: & & & & & &\\
   Meet with Sponsor &  &\_\_\_x& & & &\\
   Validate Website &  &xxx& & & &\\
3. Do Detailed Software Design & & & & & &\\
   Data &  & \_\_\_xx& & & &\\
   Processes & & &xxx& & &\\
   Objects   & & &\_\_\_xx& & &\\
4. Coding and Implementation & & & & & &\\
   Interface Class and Headers & & & &xxx & &\\
   PPF\_Logic Prototype &  & & &\_\_xxx&xxx&\\
   Parallel\_Wrapper &  & & & &xxxxxx&x\\
   PPF\_Logic with Wrapper & & & & & &xxxxx\\
\hline
\hline
\bf Work Tasks & Wk7 & Wk8 & Wk9 & wk10 & Wk11 & \\
\hline
   PPF\_Logic with Wrapper &xxx& & & & & \\               
   Statistics and Timer &\_\_xx&x & & & & \\
5. Finish Code & & & & & &\\
   Testing & &xxxxx&xxxxx&xxxxx& & \\
   Revision & &xxxxx&xxxxx&xxxxx& & \\
   Review & &xxxxx&xxxxx&xxxxx& & \\
6. Finish documentation & & & & & &\\
   Code Documentation &  & & & &xxxxx&\\
   Project Usage Documentation & & & & &xxxxx& \\
\hline
 
\end{tabular}                     

\chapter{Testing}

\section{Philosophy of Testing}

Modules of the PPF will be tested at every step of the development process.  Our design
will begin with skeleton code for the entire PPF.  As each module or subcomponent of the
system is enhanced, the same black and white box tests and integration tests will be done
to ensure that the project has maintained its integrity.  During early stages
of development,
a oversimplified pseudo physics package will be used to test the correctness of the PPF code.
As the project progresses actual physics problems with known results will be used as a basis for
integrated black box testing. 

\section{Testing by Subcomponent}

\begin{itemize}

\item {\bf PPF\_Interface} Testing for the interface will happen mainly during integration testing.
The purpose of the PPF\_Interface is to call the correct subcomponent when an interface method is
called.  After each of the subcomponents is tested for correctness, each of the interface methods
will be tested to ensure the correct subcomponent is called in all preconceived scenarios.

\item {\bf PPF\_Statistics} The PPF\_Statistics class will be tested as an individual component and
when integrated with the timer.  White box testing will consists of creating debug files
of all computations during trial runs from a driver program.  A debug file dump will allow
us to trace through the computations and verify correctness.  Each statistical computation will
be tested on data sets with known answers to ensure correctness.  Illegal number usage (such as 
negatives) must be caught and filtered by the software and hence these numbers and other bounds
conditions will be tested.  Black box testing will consist of the PPF\_Statistics package integrated
with PPF\_Timer.  During these tests it will be assumed that PPF\_Timer has already been tested.
Tests will check final results after exhaustive runs from a driver file.

\item {\bf PPF\_Logic}  PPF\_Logic may be the most difficult component to test.  It must be tested
individually and integrated with the PPF\_Parrallel\_Wrapper class.  Testing should
include the following:

\begin {enumerate}
 \item Ensure that domains and neighbor array lookup tables are loaded correctly.  Testing
       should include loading a mesh and physically plotting out the neighbors to ensure 
       correctness.
 \item Ensure that particles are being sent to the correct domain.  Each particle tested
       must be identifiable by a unique ID so as to be traceable.  Each test should be
       from a contrived driver file, where each particle destination is known before hand.
       This is one of the most critical portions of the PPF and correctness must be ensured
       to the best ability of the developers.
 \item Ensure that the PPF\_Logic only sends particles when enough particles are present
       to justify the message passing overhead.  This limit must be tested and may be
       a variable parameter within the code.  White box testing of particle numbers in
       each particle send should be adequate for this.
 \item During times when a node is saturated particles must be written to disk to free up
       RAM. This can be tested by creating readable ASCII files for each particle written
       and read to disk.  After a run from a driver file, each file should be checked to ensure
       that all particles which were written to disk were read and moved correctly.  Obviously
       if the node crashes during a test, the PPF\_Logic did not handle the freeing of memory correctly.
\end {enumerate}

\item {\bf PPF\_Parallel\_Wrapper} Send and receive pairs must be tested for correctness.  Currently
the PPF is planned to be run only on homogeneous distributed systems, however if it is ported
to a heterogeneous system, like a Linux beowolf cluster, byte ordering may be a problem.  During
test runs, each send and receive should dump a debug file detailing the exact byte data sent and
received to ensure the data is not being corrupted.  This must be rigorously tested on all
architectures supported by the PPF. 

\end{itemize}


\end{document}
