
%12/23/92
\documentstyle[12pt]{article}
\renewcommand{\baselinestretch}{1.2}
\newcommand{\mc}{\multicolumn}
\begin{document}

\centerline{\Huge **** DRAFT  *****}
\vspace{.5 in}
\centerline{\Large not approved by Syracuse University}
\vspace{.5 in}
\centerline{\LARGE NPAC ACTION-New York State Proposal}
\centerline{\LARGE to NYNEX Science \& Technology Inc}

\vspace{1 in}
\centerline{\large Northeast Parallel Architectures Center}
\centerline{\large Syracuse University}
\vspace{.5 in}
\centerline{\large December, 23, 1992}


\section{Introduction}
NPAC proposes a partnership with NYNEX Science \& Technology
Inc to apply parallel computing technologies in the industry research
and development program of NYNEX.  To initiate this partnership, we
invite NYNEX to join our ACTION-New York State corporate program.
To further develop our partnership, we propose a short term application
research project, with a goal of developing a broad set of applications
over the longer term.

\section{Proposed Approach}
As a corporate member of NPAC's ACTION program, NYNEX will have access
to NPAC's parallel computing systems and research staff.  This interaction
is intended to lead to application research projects and high performance
computing and communication applications on the proposed supercomputing
corridor.  Elements of this program include assigned NPAC staff contact,
100 hours of time on NPAC parallel systems, and parallelization of a
significant application.

Voice recognition, and network simulation are immediate examples of 
application projects at NYNEX that may benefit from parallel computing.
The voice recognition research team could trial test
parallel software/hardware systems, and run the training portion of their 
neural net code.  The network optimization model could be 
initially implemented as an embarrassingly parallel computing application on 
a network of workstations.  This first step could expand the
analysis of network configurations, and allow a more thorough investigation 
of parameter space.

Parallelizing a significant application should serve to demonstrate the 
potential of parallel computing in NYNEX's research and development program.
A candidate demonstration application is the network simulation and 
optimization project of Flikop.  As a short term (2-3 month) project, 
NPAC could analyze the components of the application code (e.g. data 
structures, algorithms, computational model) and implement the code on an 
appropriate parallel computing systems.  NPAC will be responsible for 
evaluating model performance, the effort required to implement the code, 
relevant software issues such as language, SIMD/MIMD compatibility, and
providing source code and documentation.  NYNEX would provide the application 
expertise needed to define the requirements of an improved network model.

The network optimization approach currently investigated by Flikop at
NYNEX seems to lend itself to efficient parallelization. A preliminary
analysis of the algorithm suggests at least two different methods of
parallelization. The cost function describing the network behavior is
additive by its very nature, and, as such, distributable. The
contributing entities are the conceivable routing paths and, on a lower
level, the physical network components. Parallel algorithm can either
assign a path or a network component (or, for a large problem, a number
of each of these entities) to a processor. 
Both approaches should be investigated since it is not clear which of
them will be more efficient. Since a single network element belongs, as a
rule, to multiple routing paths, assignment of the routing paths to a
processor may request synchronization measures and significant
communication between the processors dealing with the same network
component in different paths. The approach assigning a physical network
component to a processor is conceptually much simpler, but it seems to
be susceptible to possible load imbalance. Also, for smaller networks,
it might be difficult to take full advantage from the available CPU
power of the massively parallel platform. A careful study of both
strategies should enable us to identify the most efficient approach to
parallelization.  A longer term goal in this project should include the 
research needed to produce a commercial network analysis software package 
combining a parallel optimization model with an expert system.


\section{Related Application Projects}
During the December 10, 1992 visit to NYNEX Science \& Technology Inc
by NPAC and New York Telephone staff, we visited a number of project
teams and discussed the potential of application research projects in
Geographic Information Systems, database applications, medical applications,
and in the longer term, virtual reality.  In each application area, NPAC
has an ongoing development project, and we are interested in developing future 
projects with NYNEX and New York Telephone in these areas.  In a fuller 
proposal, we will describe NPAC activities in each area.


\section{Schedule of Work}
NYNEX membership in NPAC's ACTION program could begin at any time, and
with this step, NPAC could begin a 2-3 month project to parallelize
an application of NYNEX's choosing.

Longer term projects, such as extending the network simulation project
to include alternative methods and algorithms, or interfacing the
parallel code to an expert system must be negotiated, but an approximate
time period for this work is 6-9 months.

Longer term project development and coordination with the installation
of the supercomputing corridor could occur over the next 12 months.


\section{Budget}
The project budget contains an ACTION membership component, and a budget
for additional application research that must be negotiated for the
specific project.

Membership in the ACTION program begins at \$25K per year, and includes
access to NPAC's parallel systems, staff collaboration, and parallelization
of a significant application.  Extending the research collaboration
to a longer term project, or a broader set of applications is possible
through an extended corporate ACTION membership of \$40K per year.
Additional projects may be negotiated 


\section{Personnel}
Depending on the application project, an NPAC Project Leader will be
identified, and an appropriate number of Graduate Research Assistants assigned.
For example, Paul Coddington would serve as the project leader for Flikop's
network optimization application.  Other NPAC researchers who could
contribute to a NYNEX ACTION project include:
Paul Coddington, Research Scientist, Geoffrey Fox, Chief Scientist and 
Director NPAC, Kim Mills, Research Scientist, and Marek Podgorny, Research 
Scientist.


\end{document}


