CMS is an advanced DIS system under development by the Night Vision Lab at Ft. 
Belvoir, VA. CMS simulates a broad spectrum of mines and minefields to interact with vehicles such as those provided by ModSAF, on the virtual battlefield. 
Modern warfare can require millions of mines to be present on the battlefield, 
such as in the Korean Demilitarized Zone or the Gulf War.  The simulation of 
such battlefield arenas requires High Performance Computing support. Syracuse 
University is building Parallel and Metacomputing Support for CMS by porting 
the CMS module to Origin2000 and linking it with a collection of distributed 
simulators handling terrain, vehicles and visualization.  


Parallel programming on Origin2000
==================================

Parallelization is the process of analyzing sequential programs for parallelism and restructuring them to run efficiently on multiprocessor systems. The goal is to minimize the overall computation time by distributing the computational workload among the available processors.  

Origin systems support a variety of parallel programming tools. These
include:   
*Parallel Compilers as made available in such tools as the MIPSpro 7 Compilers and High-Performance Fortran - C/C++, supporting automatic and semi-automatic (directives) parallelization techniques   
*Message passing among CPUs as made available in such tools as MPI, PVM, and Cray SHMEM
*Scientific & Math Libraries as made available in the Silicon Graphics Cray Scientific Library (SCSL) and other third party libraries   
*Operating system-based inter-process and inter-thread communication via standards-based sockets, pthreads, and shared memory

The shared-memory programming model supported with the MIPSpro 7 Fortran
and C compilers provides an ideal combination of good performance and
ease-of-use, with a directive approach that maintains application
portability. These compilers include support data distribution across
non-uniform shared memory, including a set of directives for incrementally
optimizing data layout. Parallelization can be automatic or manual.  During automatic parallelization, the Auto-Parallelizing Option extension of the compiler analyzes and restructures the program with little or no intervention by you. The optimizer automatically generates code that splits the processing of loops among multiple processors. An alternative is manual parallelization, in which you perform the parallelization using compiler directives and other programming techniques.

Alternatively, MPI provides a vehicle to develop
scalable applications via a standards- based message-passing implementation
for a given algorithm. Using MPI generally adds some programming complexity
due to the requirement that the programmer explicity manage interaction
among compute resources. MPI is widely used in research, and, as a result,
many programs have been written using the standard, and the MPI standard is
supported across a wide variety of system architectures and suppliers.
Originally intended as a data-sharing mechanism amongst multiple computers,
the MPI implementation on Origin systems employs the underlying S2MP
architecture for high bandwidth, low latency message passing between CPUs
in an Origin system. The Origin MPI implementation is highly optimized and
provides superb message-passing performance. 

SCSL is a new, highly optimized scientific and math library, developed by Silicon Graphics and Cray scientists and engineers, initially to be made available on the Origin platform. Over time, SCSL will be made available on additional Silicon Graphics and Cray platforms. SCSL is a merged version of Silicon Graphics' CHALLENGEcomplib and Cray Research's LibSci, that will, over time, supercede the
functionality of both these libraries.   SCSL includes the implementation
of a variety of well-recognized scientific kernel and solver algorithms.
These routines are optimized and parallelized for the Origin system and
S2MP architecture, providing an effective strategy to quickly develop
parallel, optimized scientific programs without tuning efforts.

Inter-process and inter-thread communication mechanisms are the underlying
basis of these aforementioned programming models. In some cases in which
the above models don't apply (for example, database applications, some
real-time simulations), inter- process and inter-thread mechanisms are the
basis for parallel implementation of these applications.   Cooperating
processes or threads coordinate their activities using a  client-server  or
producer-consumer  model. The Origin architecture, coupled with the IRIX
kernel, has been optimally tuned to support inter-process and, in
particular, inter-thread communication.   Coupled with the scalable
shared-memory-based S2MP architecture, large numbers of CPUs (beyond
classic SMP limitations) are able to share and communicate data via a
single shared-memory address space. Developers can scale algorithms
developed for classic distributed memory computer architectures, with the
benefit of low latency data sharing, minimal kernel overhead, and a simple
shared- memory address space programming model.   These capabilities are
accessible through industry standard POSIX interfaces, classic Unix IPC
interfaces, and IRIX specific interfaces. 

The other parallel programming
models supported on Origin systems SHMEM, PVM, and HPF are of primary
interest to applications developers already using these models on other
systems. Each has its particular strengths. SHMEM is a simple, high-
performance form of message passing that originates from the Cray T3D and
Cray T3E development environment. PVM was once the de facto standard for
message passing and is still widely used. HPF has proven useful as an
easy-to-program language for explicit data parallel applications. Solid
implementations of these models will become available on Origin systems,
making it easy to migrate applications using these tools.

On a distributed shared memory architecture such as Origin, the latency 
for a CPU to access main memory is function of the distance to the 
physical memory accessed and contention on the internal network. This 
dependence of latency on distance leads to new resource for OS to 
manage - memory locality. The OS supports memory locality management 
through a set of low-level systems calls. These are not interest to the 
general user as the capabilities required to fine-tune performance have 
been made available in a high level tool, dplace and through compiler 
directives. The memory locality management automatically performed by 
IRIX means that most Origin users could achieve good performance and 
enhanced scalability without having to change the program. 

Single Processor Optimization:
------------------------------

Even though Origin is a highly parallel system, the vast majority of 
programs run on it use only a single processor. Single-processor tuning 
accounts for most of the performance work done on Origin; using the 
proper compiler flags and coding practices can yield big improvements 
in program performance. 

Since Origin is NUMA architecture, the cache behavior of the program 
has a significant impact on the performance. Cache-friendly programs 
have very few cache misses. However, not all programs can be made cache 
friendly, and it just means they will spend more time accessing memory 
than their cache-friendly brethren, and in general will run at lower 
performance. perfex and speedshop tools can be used to determine if a 
program is cache-friendly. perfex and speedshop can be used together to 
identify cache problems.

To tune a program's performance, you need to determine its consumption 
of machine resources. 

*perfex: simple profiling tool to do performance analysis

*speedshop: The SpeedShop tools allow you to run experiments and to 
generate reports to track down the sources of performance problems. 
utilities to find out exactly where a program is spending its time 
precisely which procedures or lines of code.

*ssusage : Collects information about your program's use of 
machine resources. Output from ssusage can be used to 
determine where the most resources are being spent.

*Ssrun   : Allows you to run experiments (Statistical PC sampling, 
Basic block counting) on a program to collect 
performance data. 

Once the amount of code to be tuned has been narrowed down, it is time 
to do actual work of tuning. The most important tool for accomplishing 
this is the compiler. 
 
        Recommended Flags 
        -------------------
        -n32 -mips -Ofast=ip27 -OPT:IEEE_arithmetic=3 -lfastm -lm

This will enable all key sequential optimizations include :

  * Statement level optimizations   
    - array expansion   
    - common subexpression elimination   
    - global constant propagation   
    - dead code elimination
  * Architecture-specific optimizations   
    - software pipelining   
    - instruction scheduling   
    - automatic blocking   
    - register blocking   
    - array padding global 
    - instruction distribution   
  * Loop-level optimizations, including combinations of:   
    - loop unrolling   
    - loop interchange   
    - unroll-and-jam 
    - loop distribution
    - loop fusion   
    - loop invariant code motion   
    - sum reduction
  * Procedure-level optimizations   
    - procedure inlining   
    - interprocedural analysis (IPA)

By using this set of flags, compiler will accomplish the major categories of optimization automatically. The aggressive optimizations will be tried. This affects compilation time.

Parallelization  
----------------

The process starts with identifying of the loops, which consume the 
most CPU time, and then parallelizing these loops. This can be 
implemented incrementally, one loop at a time. A lot of loops have to 
be parallelized to achieve a decent speedup. During to implementation 
no need to worry about where the data lives and about the inter-
processor communication, it is implicit in the shared memory.  

During parallelization process, code modifications may be needed to 
remove data dependencies or add compiler SGI compiler directives like 
'#pragma parallel' and compile the code using -mp flags. It is 
important to parallelize largest possible loops, not to go after small 
loops. Conditional modifiers can be used. 

Example :
#pragma parallel if(max>100)
        #pragma parallel shared(a, b, sum) local(I)
        #pragma by value(n)
        { #pragma pfor iterative (i=0; n; 1)
                a[I] = 2.0*3.1415*b[i];
                #pragma critical
                { sum = sum + a[i]; }
}


OpenMP
======
The OpenMP Application Program Interface (API) supports multi-platform shared-memory parallel programming in C/C++ and Fortran on all architectures, including Unix platforms and Windows NT platforms. Jointly defined by a group of major computer hardware and software vendors, OpenMP is a portable, scalable model that gives shared-memory parallel programmers a simple and flexible interface for developing parallel applications for platforms ranging from the desktop to the supercomputer.

In essence, OpenMP is a specification for a set of compiler directives, library routines, and environment variables that can be used to specify shared memory parallelism in Fortran and C/C++ programs.

How does OpenMP compare with MPI? 
--------------------------------
Message-passing has become accepted as a portable style of parallel programming, but has several significant weaknesses that limit its effectiveness and scalability. Message-passing in general is difficult to program and doesn't support incremental parallelization of an existing sequential program. Message-passing was initially defined for client/server applications running across a network, and so includes costly semantics (including message queuing and selection and the assumption of wholly separate memories) that are often not required by tightly-coded scientific applications running on modern scalable systems with globally addressable and cache coherent distributed memories.


CMS 
====

83 minefields with total 30196 mines

on joker (180 MHZ IP32 Processor)
        one loop over all minefields -> 290-420 msec
on origin (cewes)       (195 MHZ IP27 16 processors)
   with 1 processor 190-210 msec
   using 4 processors 70-90 msec 

