\documentstyle[leqno,twoside,11pt,ltexproc]{article}
\input{psfig}
\begin{document}
\cleardoublepage
\pagestyle{myheadings}
\title{An Interactive Visualization Environment for\\ 
Financial Modeling
on Heterogeneous Computing Systems\thanks{This study is supported by the Office
of the Vice President for Research and Computing at Syracuse University,
and Corporate Partnership funding from Digital Equipment Corporation.}}
\author{Gang Cheng\thanks{School of Computer and Information Science,
Syracuse University, Syracuse, NY 13244} \footnotemark[3]
\and
Kim Mills\thanks{Northeast Parallel Architectures Center
Syracuse University,
Syracuse, NY 13244}
\and
Geoffrey Fox\footnotemark[2] \footnotemark[3]}

\date{}
\maketitle
\markboth{Gang Cheng et al.}{A Visualization Environment for Financial Modeling}

\pagenumbering{arabic}

\begin{abstract}Financial modeling represents a major computational 
challenge in industry.
Parallel stock option pricing models developed on the Connection 
Machine-2/5 and DECmpp-12000 run approximately 100 times faster than 
sequential models on a high-speed workstation.  
To further evaluate and optimize pricing models,
a portable, work-station, interactive visualization
environment was created, by using a highly portable 
commercial visualization system, Application Visualization 
System(AVS). 
Using option pricing as an example of a challenging application problem, 
we describe design issues and performance requirements for integrating visual 
and scientific computing in a heterogeneous computing environment in which high
performance computational modules running on massively parallel computers are
coupled with workstation and network-based visualization, interactive 
system control and distributed I/O modules. \end{abstract}

\section{Introduction}
Advances in parallel computing systems provide a feasible solution to
many computationally intensive applications which would otherwise be
impossible or impractical on conventional computers. High performance
compuiting is expected to play a leading role in 1990's. Many applications,
however, especially modeling and simulation related applictions, require
an interactive graphical users interface in real-life computing environement.
The GUI's are mostly event-driven thus serial in nature and it's
difficult to ultilize their parallelism. On the other hand, most visulization
tools on parallel systems either require special hardware support or are
implemented for those specific systems, thus are non-portable. Therefore, well
portable interactive graphical users interface tools, developed on sequential
computing systems, are also needed in a parallel computing environment.
Another observation is that currently there is no such a general-purpose
supercomputer that it is good to solve any class of problems. We need a
metacomputer consisting of networked computing resources of
various architectures and computational power, in which subproblems of 
a large application are distributed to architectures best suited to them.

In this study, we integrate an interactive visualization environment
into a heterogeneous computing system to run stock option price
modeling. In this distributed system,
high performance computational modules, running
on two parallel systems, CM5 and DECmpp-12000, and two high-end workstations
are coupled with network-based visualization, interactive 
system control and distributed I/O modules on other three workstations.  
A commercial available visualization system AVS is used both as
a data visualization tool and as a networking tool in this application.
Using stock option pricing as an example of a challenging 
application problem in this paper, we describe design issues and performance 
requirements for integrating visual and scientific computing in a 
heterogeneous computing environment. We break down our analysis of design 
issues and performance requirements into three components: system integration,
visualization functionality, and the ratio of system components.

\section{Option Price Modeling}Stock option pricing models are used to 
calculate a price for an option
contract based on a set of variables defined by the market, e.g. stock price,
exercise price, time to maturity, and a set of model 
parameters: volatility of stock price, variance of the volatility, and 
correlation between volatilty and stock price.  These model parameters 
are not directly observable, and must be estimated from market data.

We use a set of four option pricing models in this study. Simple pricing
models treat stock price volatility as a constant, and treat only European
(option exercised only at maturity of contract) options.  More sophisticated
models incorporate stochastic volatility processes, and allow American
contracts (option exercised at any time in life of contract)[1][2][3]. 
However, those stochastic volatility pricing models are computationally 
intensive and have significant communication requirements.

In previous studies [4][5],
following four pricing models are investigated :\\
BS model  --- European, constant volatilty, Black-Scholes\\
AMC model --- American, constant volatility, binomial model\\
EUS model --- European, stochastic volatility, binomial model\\
AMS model --- American, stochastic volatility, binomial model
 
We developed serial and data parallel versions of
these models on various sequential and parallel systems, conducted a 
comparison of model and market prices, and evaluated model performance 
and parallel software issues.

Parallel models developed on the Connection 
Machine-2/5 and DECmpp-12000 run approximately 100 times faster than 
sequential models on a high-speed workstation.  Extremely fast model 
run-times are important for trading purpose, pricing large portfolios, and
incorporating optimization techniques for model parameter estimation.

To further evaluate and optimize pricing models to run on massively parallel,
along with high performance computing modules for real-time pricing, 
real-time visualization of model results 
and market conditions and a graphical user interface allowing expert 
interaction with pricing models are needed. 
Comprehensive visualization functionality is required for
the dynamic visualization of market and model prices fluctuations and
the graphical model interface.  

We now incorporate dynamic visualization and system control
in a heterogeneous computing environment to further develop use of
optimization techniques for model parameter estimation and improved
model accuracy, and develop a graphical interface to our model system
so that a market expert can start and stop the model, adjust model
parameters, and call optimization routines according to dynamically
changing market conditions. Analytic models are useful tools in the 
financial market, but require expert interpretation. 

\section{System Configuration}
The overall system configuration is shown in Figure 1. 
7 machines of 5 different architectures are used in this application.
All workstations in the system, including the front-end workstations of
DECmpp-12000 and CM5, are connected by a 10MB/sec local network Ethernet.
UNIX-based software environment are running all the workstations.

Introduction of AVS as a visualization tool and a networking tool: 
(to be added)
. comprehensive visualization functionalities(graphical programming style, 
  high-level object-oriented design or modular design)
. networking capability(integrator), transparant networking, 
  fault-tolerent, etc.
. highly portability over different vendors (industry standard), XDR
. support data flow programming model

The computing modules for the four option pricing models are running
on 4 different remote machines: BS model on a DEC5000, AMC model on
a SUN4, EUS model on a CM5 and AMS on a DECmpp-12000. Each model can
allow its own I/O on that local machine, synchronized by the interface.

The DECmpp-12000 is a massively parallel SIMD machine with 8192 processor.
Each RISC-like processor has a 1.8-MIPS control processor, forty 32-bit
registers, and 16 KBytes of RAM. The peak performance is 650 Mflops DP.
The front-end of DECmpp-12000 is
a DEC5000 workstation.

The Connection Machine 5 is a parallel SIMD/MIMD machine with 32 processing
node.
Each PN consists of a SPARC processor for control, four proprietary 
vector units for numerical computation and 32 MBytes of RAM. The control
node(front-end) of CM5 is a SUN4 workstation.  

Our home machine is a IBM RS/6000 graphical workstation 
which has a GTO Graphics Adapter with 24-bit color. This machine is devoted 
to displaying graphical user interface, rendering graphical output, monitoring user's runtime interaction. 
windows(the ideal machine is a SGI workstation or a X terminal). As the home machine the user is logging in, it is also the 
physical interface through which user set up the system at start and 
interacts with the system by using mouse, keyboard and other peripheral I/O
devices. AVS kernel and system modules are running on this machine.     
	
The user interface is actually running on a remote SUN4. This machine is 
mainly as a file server, devoted to bulk data input of the system from
databases on disk. It also performs other functions like overall system 
synchronization, broadcast of collected input data to the remote 
computing machines. In our application, the input sources are 
historical market data on disk files and user runtime input from
GUI on home machine. Future improvements in our modeling environment 
include a real-time market data service.

Another IBM RS/6000 is used as a file server for non-graphical 
output of system bulk data. Based on results produced from 
all remote computing modules, it can also perform 
other non-graphical functions like data synthesis, statistical analysis.
In our application, the output distination are databases created for 
later analysis.

In this system, we make following requirements/resoures 
distributed for a large application :\\
(1) Distributed Computing (2) Distributed Memory (3) Distributed Input/Output
 
\begin{figure}
\centerline{\psfig{figure=fig1.eps}}
%BoundingBox: 0 0 612 725
%\caption{The network of AVS modules for the option price modeling}
\end{figure}

\section{System Integration and Implementation}
Issues invloved in the integration of modules written in C, Fortran, 
Fortran90, MPL and implemented on SUN4, DEC5000, IBM6000 and DECmpp, 
CM5(CM2).

AVS framework

AVS provides us with both a visualization tool and a high-level networking
tool. Using the AVS library routines, we imlemented portable user input/output
interfaces on SUN, DEC and IBM workstations. Using the remote modules and
network editor, we distributed the interfaces and computing modules on
different machines over Eithernet and integrated them in a single workstation-based visulaization environment. This Section decribes the implementation 
details of this remote visualization environemnt on a hertergenous system.

All modules on different machines are compiled and linked like stand-alone
programs at operating system level. The only requirement is that input
and output ports must be defined in modules by the programmer, using 
specific library routines provided by AVS. 

System issues include integration of diverse functions running
on hardware best suited for high performance.  Our present problem
includes two computationally intensive models running on two massively
parallel machines, with visualization and system control functions
implemented on network connected workstations.  Larger, more
complex application problems will likely require
us to construct a network of machines to integrate functions such 
vas scientific  computing, visualization, database services, and 
using large memory distributed over
a network, while providing system integration and synchronization.

We require a high-level framework that is portable across systems rather than
architecture-specific computation and visualization libraries and tools.

We use multiple languages, and especially need calls between
sequential and data parallel versions of C and Fortran.

A mix of programming languages 
on the various compute nodes--Fortran77 on the DECstation 5000, C on
the SUN4, CMFortran on the CM-5, and MPL (data parallel C) on the
DECmpp-12000.

current research issue: integrating program environment--compiler,
OS, debuggers from sequential environment (front-end of parallel
machines is a sequential environment)

In AVS, message passing among different processes on the same machine is done by shared memory, while message passing from one machine to another is through TCP/IP in XDR format.


Data Flow:

As shown in Figure 1, input data of this system come from two sources: 
(the data brocasted from input file server to each computing machine)

(1) Historical market data on disk files of file server machine.\\
model primitive input \\
 . initial stock price . exercise (striking) price . risk-free rate\\
 . time to maturity    . time to dividend (early exercise time)\\
 . dividend amount     . call price\\

initial (default) model pramater\\
 . variance of stock volatility\\
 . correlation between stock price and its volatility\\

(2) user runtime input from the GUI on home machine. 
(the data from home machine to input file server machine) \\
 . variance of stock volatility\\
 . correlation between stock price and its volatility\\
 . each model's initial volatility 
   (if they are not defined, default values are calculated 
    by a function in user interface module)

Output data of this system go to three distincations:\\
 . each new model price(a scalar value), with certain number of previously 
   generated values, is rendering graphically in a graphic window on 
   home machine. (the data from each computing machine to home machine)\\
 . each new model price is also displayed numerically in a shell window
   on home machine \\
 . all 4 new models prices, with other model input data, are stored
   to databases on the file server machine in binary(or ASCII) format.
   (the data from each computing machine to the file server machine)\\
 . (optional) each new model price, with other data, is stored to a 
   file on the computing machine.\\

Control flow 

This is an event-driven system in which following events from
different machines are involved in:\\
. user runtime interaction through GUI on home machine\\
. model input from disk file on (input) file server machine\\
. send/receive data to/from other machine(s)\\
. computing module on each model computing machine\\
. model output to disk file on (output) file server machine\\
. model graphical output on home machine\\
. system synchronization on (input) file server machine

Figure 2 shows control flows of the overal network and thosse 
on home machine and (input) file server machine.
We use a simple overall system synchronization method: to start a new
cycle of modeling(started by broadcasting new input data to each computing
machine) if and only if the interface module on the file 
server machine checks that the previous cycle of modeling is finished
(ended by all model output rendered on home machine). 

\begin{figure}
\centerline{\psfig{figure=control_flow.eps}}
%BoundingBox: 0 0 612 728
%\caption{The network of AVS modules for the option price modeling}
\end{figure}

GRAPHICAL INTERFACE

The graphical interface is the component where the stock market expert 
is meant to interact with the modeling environment.  The graphical 
interface manages user runtime input and output, and the system 
configuration.  

As discussed in data flow, runtime input includes user defined model 
parameters and system execution styles, and the output are 
2-dimensional displays of model and market prices calculated in 
the compute nodes.  

The system configuration includes choice of pricing models, network 
configurartions and interface layouts.  Plans for future improvements 
include integrating a real-time decision support system for traders 
to improve expert use of modeling system.

GUI -- Input interface on home machine

Why we design buttons for optimzation, sleep, single:
Before reading from the model parameters from a file, a control 
module (right name??) 
checks for user input. 
Each compute node checks
the input market data, and in cases of flagged market observations,
the pricing model is inverted to estimate a value of sigma, termed
implied volatility, that is used to price options until the next
flagged option is observed.   We flag options at half-hour intervals
and apply the estimate of implied volatility through the remainder
of the half-hour.  
Depending on the approach to estimating xi and
rho, these values are read in data files, entered at run time by
the user, or estimated using optimization techniques.

Why buttons for psi, rho, 4 v's:
Pricing models are extremely sensitive to sigma, 
xi, and rho, yet these variables cannot be directly observed.  
We use a variety of methods including expert opinion, historical values, 
and optimization to estimate sigma, xi, and rho.  These parameters may 
be read from data files (historical estimates), calculated just prior 
to running the pricing model (optimization), or defined at run time 
(expert user). 
Figure 3 is a overlook of the interface on screen.

\begin{figure}
\centerline{\psfig{figure=all.new.bw,width=6.0in}}
%BoundingBox: 0 0 612 728
\caption{A screen look of the graphical user interface for the option modeling on a distributed high performance computing system}
\end{figure}

\section{ A Preliminary Analysis of Performance Requirements and Experimental Results}
Figure 4 shows a generalized performance model of our networked system.
 In completing a synchronized cycle of this framework, let $t_{\rm calc}$
 be the summed calculation time on all machines and $t_{\rm comm}$ be the 
summed communication time in the system; $T_d, T_s$ be the total time to 
complete such a cycle in the distributed system and in a single-machine 
system, respectively. 

In a single-machine system $M_I = M_h = M_1 = M_2 = \cdots = M_n, 
 t_{\rm comm} = 0$ and $T_s = t'_{\rm calc} = \displaystyle{\sum^n_{k=1}}\
(m'_k+r_k)$, because message passing among different processes on a single 
machine is by shared memory. 

In the distributed system in which message passing between different
machines
 is through TCP/IP protocol, we observed that:
\begin{enumerate}
\item  sending messages from $M_I$ to $M_k$'s is done sequentially
 (i.e., one by one), while the sending order can be scheduled;
\item the execution of the computing process on each $M_k$ is 
solely activated upon receiving new message from $M_I$;
\item because $P_k$'s are running on a single-processor machine $M_h$ in the 
manner of time-sharing, we can assume each $P_k$ is activated if and only if 
after receiving new message from $M_k$ and no other $P_j (j\ne  k)$ is running. 
\end{enumerate}

Calculation and communication among different machines in the system 
are in a pipelined way. We can have possible overlapped time segments: 
for $j, k = 1,2, \ldots, n$  and $j\ne k$, (1) $c_k$ with $m_j, d_j$, 
and $r_j$; (2) $m_k$ with $d_j$ and $r_j$; and (3) $d_k$ with $r_j$.
 Figure 5 gives examples of different cases in a simplified system $(n = 2)$.

As shown in Figure 5, for each machine $M_k$, we have
 $T_d=c_k+m_k+d_k+r_k+i_k$ , where $i_k$ is the idle time of $M_k$ in the 
whole cycle, excluding the waiting time $r_k$ for the rendering on $M_h$.
 Thus, 
$nT_d = t_{\rm comm} + t_{\rm calc} + t_{\rm idle}$, where
 $t_{\rm comm}=\displaystyle{\sum^n_{k=1}}(c_k+d_k)$,
 $t_{\rm calc} = \displaystyle{\sum^n_{k=1}}(m_k+r_k)$,
 $t_{\rm idle} = \displaystyle{\sum^n_{k=1}}i_k$,
 is the total idle time of all $M_k$'s.

It follows that the speed-up $S$ of the distributed system over the 
single-machine system is:
$$S= {T_s\over T_d} ={n\over{t_{\rm calc}\over t'_{\rm calc}}+
{t_{\rm comm}\over t'_{\rm calc}}+{t_{\rm idle}\over t'_{\rm calc}}},$$
 where $t'_{\rm calc}$ 
is the total calculation time on a single-machine system.

Thus, the speedup depends on: (1) $n$, the number of machines for distributed 
computing modules; (2) $t_{\rm calc}/t'_{\rm calc}$, the ratio of total 
calculation time on the distributed system over that on a single-machine
 system; (3) $t_{\rm comm}/t'_{calc}$, the ratio of total communication time 
over total calculation time on a single-machine system; and (4)
 $t_{\rm idle}/t'_{\rm calc}$, the ratio of total idle time over total 
calculation time on a single-machine system. As  can be seen in Figure 5,
 for a given application problem on given systems, $t_{\rm idle}$
 depends only on the scheduled order to send messages from $M_I$ to $M_k$'s.
 This is essentially a scheduling problem. 
 
            
Further analysis  is beyond the scope of this paper. It can be shown that there is a best case in which:
$$t_{\rm idle}=\displaystyle{\sum^{n-1}_{k=1}}c_k(n-k)+ 
\displaystyle{\sum^n_{k=1}} a_k,r_k, $$
 where $\{a_1, a2, \ldots, a_n\}$ is a permutation on set $\{0,1, 
\ldots, n-1\}$.

Table 1 shows the measured approximate timings of the AVS framework on 
the configuration in Figure 1. According to our analysis, expected
$T_d = c_1 + m_1 + d_1 + r_1 + r_2 + r_3 + r_2  = 0.017 \, +\, 0.015\, +\, 
0.1\, + \, 4^*0.9 = 3.642$ seconds (assuming the scheduled order is
 $c_1\Rightarrow c_2\Rightarrow c_3\Rightarrow  c_4$).
 Assuming the framework runs on a single parallel machine with its
 front-end workstation, e.g.,      DECmpp-12000 and $m_4 = 0.025$ seconds,
 i.e., $t_{\rm calc} = t'_{\rm calc}$, we have
 $T_s = 0.015\, +\, 0.085\, +\, 0.075\, +\, 0.025\, +\, 4^*0.9 = 3.8$. 
Thus, the expected
 speedup $S = 3.8/3.642 = 1.043$, which is quite small due to the high ratio
$t_{\rm idle}/t'_{\rm calc}  = 10.3/3.8 = 2.71$ in the system. If a
 workstation, e.g., SUN4, is assumed in the single-machine system, a much 
larger speed-up $S = 16.0/3.642 = 4.34$ can be expected. Because the system 
is running under a completely resource-and-time-sharing environment, the best 
$T_d$ we measured in various situations is $T_d = 4.1$ seconds, which is 
slightly larger than the expected one.

The performance bottleneck of this system lies on the rendering time for
the four graphical output windows on home machines.  

\begin{figure}
\centerline{\psfig{figure=performance.eps}}
%BoundingBox: 0 0 612 728
\end{figure}

\section{Discussion and Conclusion}
outline functionality required for our application
what are key integration issues and how we achieved this
Interactive control, real-time visualization of model output and market 
data, and system integration make this an attractive software environment 
for future research in financial modeling.  This highly portable software 
environment running on massively parallel computers can be implemented with 
relatively small programming effort, and allows for rapid prototyping.

In the future, we will take advantage of
on-going research (Hariri citation) in performance prediction tools meant 
to analyze application and system input parameters, and predict performance
of the application on a specified hardware system.  This will allow users to 
examine alternative system configurations for the given application,
and examine predicted execution time, communication time, computation
time, idle time for each node and system as a whole.

application code implemented on hardware/software system
hardware--compute nodes, network connection, I/O devices include visualization
run-time system loads on compute nodes and network

emergence of high performance distributed computing systems
based on availability of high speed networks and advances in
computational power

need software to integrate, support heterogeneous, network based
computing environment... must combine computation with dynamic visualization
and system control

Ethernet network provides 10 Mbit/sec but only 1 -2 Mbit/sec available
for application
host/sytem interface must be improved

current software implemented as stack of software layers, consuming
much of system capacity, leaving little bandwidth for application

research needed in high speed communication protocols, ... we focus here
on functionality required for industry applications on het distributed
systems.
performance prediction remains a research issue

\begin{thebibliography}{99}
\bibitem{}
F. Black, and M. Scholes. ``The Pricing of Options and Corporate
Liabilities,'' {\it Journal of Political Economy}, 81, 1973, 637-59. 1973.

\bibitem{}
J. Cox,S. Ross, and M. Rubinstein. ``Option Pricing: A Simplified Approach,''
{\it Journal of Financial Economics}, Vol. 7, pp. 229-63, 1979.

\bibitem{}
K. Mills, M. Vinson, and G. Cheng, ``A Large Scale Comparison
    of Option Pricing Models with Historical Market Data,'' in 
    {\it The 4th Symposium on the Frontiers of Massively Parallel 
    Computation}, Oct. 19-21, 1992, McLean, Virginia.


\bibitem{} 
K. Mills, G. Cheng, M. Vinson, S. Ranka, and G. Fox.  ``Software Issues 
    and Performance of a Parallel Model for Stock Option Pricing"
    in {\it The Fifth Australian Supercomputing Conference.}  Dec. 6-7, 1992,
    Melbourne, Australia.
\end{thebibliography}

\end{document}

