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 minefield 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.  

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:   
1- 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   
2- Message passing among CPUs as made available in such tools as MPI, PVM, and Cray SHMEM
3- Scientific & Math Libraries as made available in the Silicon Graphics Cray Scientific 
   Library (SCSL) and other third party libraries   
4- Operating system-based inter-process and inter-thread communication via standards-based 
   sockets, pthreads, and shared memory

We have chosen the semi-automatic parallelization technique, because the C++ compiler 
on Origin fails to provide efficient parallelization and optimization for event based 
object oriented code such as CMS. The manual parallelization, in which you perform the
 parallelization using compiler directives and other programming techniques.

The first step is single-processor tuning since it 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. Then, the process 
continues 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 parallelization process, code modifications are 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.

The code given here is taken from CMS shows how to distribute loop on minefields
over the available processors, using the parallel compiler directives. This loop runs 
thorugh all minefields simulated by CMS and all their components and mines.
  
    start_t = clock();
    #pragma parallel shared(pField,id, proc_count, proc_simcount)
    #pragma local(i,count,simcount,totalmines) byvalue(n)
    { count =0; simcount=0; totalmines =0;
      #pragma pfor iterate(i=1;n;1)
       for(i=1;i<n;i++)
       { count ++;
         pField = GetField(i);
          if ( pField->IsSimulating() ) {
             simcount++;
             pField->UpdateMfield();
             totalmines = totalmines+pField->GetTotalMines();
          }
        }
        #pragma critical
        { proc_count[id] = count;
          proc_simcount[id] = simcount;
          proc_totalmines[id] = totalmines;
          id++;
        }
     }
     stop_t = clock();

The directives like 'pragma parallel' and 'pragma pfor' lets you partition
the workload without any worry about where the data lives and about the inter-
processor communication. By distibuting workload over processors, we achieved 
a moderate speedup.

        83 minefields with total 30196 mines
           on O2 - 180 MHZ IP32 Processor
                one loop over all minefields -> 290-420 msec
           on Origin 195 MHZ IP27 16 processors
                with 1 processor  190-210 msec
                using 4 processors 70-90 msec

But, 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. 
Since Origin is NUMA architecture, the cache behavior of the program
has a significant impact on the performance. The next step is to have data distributed over 
the processors maching the workload distribution meaning each processor owning the 
data which it is going to process. In CMS case, the data is the minefield. Currently, we are working on improvements on parallel CMS related to data (minefield) distribution to achieve better performance and  scalability to run parallel CMS on more then 4 processors.
 
CMS_HLA
=======

We have chosen to use the DIS-HLA bridge approach to HLA integration for CMS code.
 This technique provides a mechanism for legacy applications such as CMS to utilize
 RTI services without requiring too much  modifications to existing software. Similar
 to DIS communication layer in the CMS, HLA port abstraction layer is introduced to handle
 RTI based communication. The objective is to create a version of CMS which can be used
 both in DIS or in HLA simulations. 

Since the aim is to keep development as simple and as automated as possible, we adapted
 DIS PDU as common our data structure and buried them into HLA interaction. In HLA, CMS
 becomes a federate and sends/receives informations through the RTI which its job to
 distributes the information to the appropriate(interested) parties. Federate ambassador
 for CMS receives interactions through RTI and HLA port translates them into DIS PDUs,
 the same mechanism for sending PDUs, HLA port translates them into HLA interactions and
 delivers them through RTI ambassador.

JDIS is another NPAC software we use during this process. It provides link between DIS
 applications such as ModSAF and CMS running as HLA application. We use JDIS to test our
 HLA implementation of CMS. JDIS receives DIS PDUs produced by ModSAF and translates into
 HLA interactions and let RTI forward to CMS.     


-------------------------------------------------------------------------
Parallel Programming on Origin (Review)

1. 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.

2. 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 explicitly 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. 

3. 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.

4. 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. 

5. 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.

6. 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.

6.1 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.
-----------------------------------------------------------------------