Abstract * Foil Index for this file
See also color IMAGE
Given by Geoffrey Fox at Trip to China on July 12-28,96. Foils prepared July 6 1996
Abstract * Foil Index for this file
See also color IMAGE
| This describes Our Approach focussing on Integration of Information and Computing and concentrating on coarse grain functionality |
| WebFlow : Dataflow (AVS) using Web with databases and numbercrunching |
| MetaWeb : Metacomputing or rather cluster management using Web |
| RSA Factoring was our first succesful example |
| Financial Modelling will be an obviously important commercial application |
| Java plays a critical role in high level user interfaces for visual programming, visualization of data and performance |
| Web Interfaces to HPF will be particularly useful initially in education -- programming laboratories on the Web |
| VRML is an interesting 3D datastructure |
This table of Contents
Abstract
Full HTML Index
| http://www.npac.syr.edu/users/gcf/hpcc96web/index.html |
| Presented during Trip to China July 12-28,1996 |
| Geoffrey Fox |
| NPAC |
| Syracuse University |
| 111 College Place |
| Syracuse NY 13244-4100 |
Full HTML Index
| This describes Our Approach focussing on Integration of Information and Computing and concentrating on coarse grain functionality |
| WebFlow : Dataflow (AVS) using Web with databases and numbercrunching |
| MetaWeb : Metacomputing or rather cluster management using Web |
| RSA Factoring was our first succesful example |
| Financial Modelling will be an obviously important commercial application |
| Java plays a critical role in high level user interfaces for visual programming, visualization of data and performance |
| Web Interfaces to HPF will be particularly useful initially in education -- programming laboratories on the Web |
| VRML is an interesting 3D datastructure |
Full HTML Index
| The Web Originated as an Information system but we can clearly use it as a base for distributed computing and as parallel computing is just a special case of this with low latency and tight synchronization, for parallel Computing as Well! |
| WebWork was our first Concept (with Boston University and Cooperating Systems) which concentrated on software engineering gotten by using information capabilities of Web linked to computing environments |
| DataFlow (for coarse grain software integration) and Embarassingly Parallel applications are natural first Web thrusts as not so sensitive to performance issues |
Full HTML Index
| Overview --- http://www.npac.syr.edu/projects/webbasedhpcc |
| WebTools --- http://king.syr.edu:2006/WebTools.html |
| RSA Factoring-by-Web -- http://www.npac.syr.edu/factoring |
| Distance Education / Virtual University -- -- http://www.npac.syr.edu/users/gcf/foilsbyarea.html |
| WebSpace/Labspace -- http://www.npac.syr.edu/projects/webspace |
| Web based Telemedicine -- http://www.npac.syr.edu/projects/careweb |
Full HTML Index
| Embarassingly Parallel: Succesful RSA130 Factorization |
| Linkage of Databases with MPP's: Financial Modelling on Demand |
| Java GUI for Distributed Computing and Performance Visualization |
| Java as WebFlow -- AVS done with the Web and applied to Image Processing |
| HPF on the Web -- General Principles and use in Education as a web programming laboratory |
Putting it together -- Java frontend to a domain specific problem solving environment -- WebAMR -- Adaptive Mesh Refinement
|
Full HTML Index
| This implies that we look at both Grand Challenges and National Challenges but we suggest this is not enough: |
| WebWork Builds HPCC technologies on a broad not niche base starting at bottom (Web,PC's) |
| not top (MPP's, Supercomputers) of computing pyramid |
Full HTML Index
| WebWork is an open, world-wide distributed computing environment based on computationally extended Web Technologies |
| The backend computation and information infrastructure is provided by the World-Wide Virtual Machine -- a mesh of computationally extended Web Servers (called Compute Servers) |
| These servers manage (via CGI mechanisms) a collection of standardized computational units called WebWork Modules. |
| Geographically distributed and Web-published WebWork modules interact by HTTP/MIME based message/object passing and form distributed computing surfaces called Compute-Webs |
| The front-end user/client interfaces are provided by evolving Web browsers with increasing support for two-way interactivity (e.g. Java, VRML) that facilitates client side control and authoring. |
| A natural user-level metaphor -- WebFlow -- is supported in terms of visual interactive compute-web authoring tools. |
Full HTML Index
| Collaboration with Arjen Lenstra and Boston/CSC. New NFS factoring algorithm successfully applied to RSA130 factoring on a tree of Web+CGI servers (FAFNER by Jim Cowie/CSC). |
| SC'95 Teraflop Challenge Award. |
| Next Challenge -- RSA155. |
Full HTML Index
RSA security systems based on numbers
|
| Bank of England and English Savings and Loan based on m=155 (512 binary digits) |
| RSA129 cracked by factoring with email team using sophisticated version of Quadratic Sieve. RSA155 will use better Number Field Sieve |
| Need x2 = y2 mod(RSAm) as then gcd(x+y,RSAm) likely to be interesting factor |
Find x and y by finding lots of interesting a's
|
| Given these a's factored into primes, multiply together so powers of primes are even. This gves desired x |
| This last step requires graph theory and solution (for Bank of England) of 5 million linear equations |
Full HTML Index
| RSA155 requires about 300 teraops hours to solve with NFS |
| RSA129 needed about an order of magnitude less time. Can be done today faster if use Number Field Sieve |
| We have roughly one to five million independent calculations which form the rows of matrix (after clever graph theory manipulates and combines) |
Set of master servers publish problem to solved with suitable demos, description of algorithm and full marketing attention.
|
| Clients return results -- not so easy except by email and cut and paste |
| Best done as a set of cooperating servers where server performing factorization publishs it solution as a file on the WWW. |
| Cooperating servers also better for computer administrators as can control set of clients at a given site |
| Initially use humans but replace by agents when software ready |
Full HTML Index
| Proposed Architecture of WWVM |
Full HTML Index
Illustrates implementation of WebWork message passing in terms of
|
| This diagram illustrates point-to-point communication between Web servers, used to implement a webflow channel between compute-web modules. Two extreme implementation modes are described: a) based on today's Web server technology, and b) based on thread memory mapped high performance implementation, expected in future Web compute-servers. Subsequent steps, represented by a sequence of labelled lines in the figure, are described below in both implementation modes. |
| a) Today's Web server mode: (1) -- M1 locks O1 on S1 disk. (2) -- M1 sends POST HTTP message to S2 with M2 URL in the header sector and with O1 URL in the body sector. (3) -- S2 activates M2 via CGI and passes O1 URL as a command-line argument. (4) -- M2 sends GET method to S1 with O1 URL in the header. (5) -- S1 fetches O1 from its document tree. (6) -- S1 sends the content of O1 to M2 which completes the GET exchange. (7) -- M2 saves O1 by overwriting current I2 on the S2 disk. If I2 is locked, M2 waits (blocks). (8) -- After O1 is saved on the S2 disk, M2 returns 'end-of-transfer' acknowledgment to M1 which completes the POST exchange. (9) -- M1 unlocks O1 and exists. |
| b) Compute-server (future Web server) mode: (1) - M1 locks its memory object O1. (2) - M1 checks if socket connection to M2 is in M1 connection table. If yes, go to (5) below. Otherwise, M1 connects to S2 and sends M2 creation script. (3) - S2 spawns M2 and acknowledges. (4) - M1 receives acknowledge message and saves new socket in connection table. (5) - M1 gets O1 handle. (6) - M1 writes O1 to M2 using socket lib calls. (7) - M2 reads O1 using socket lib calls. If I2 is free, O1 buffer is copied directly to I2 buffer. If I2 is locked, M2 creates O1 clone and blocks. (8) - M2 sends acknowledge to M1. (9) - M1 unlocks O1 and blocks. |
Full HTML Index
| http://cooperate.com/cgi-bin/FAFNER/factor.pl |
Features
|
| months of runtime, dozens of collaborators, |
| eight nations, four continents |
| hardware platforms from an i386 laptop to an IBM SP/2 (including HPs, Alphas, MIPS, Suns, SGI machines, RS6000s) |
| Most Heterogeneous and Geographically Dispersed Award, 3rd Annual HPC Challenge, Supercomputing '95. |
Full HTML Index
| Implemented as Perl scripts, invoked via CGI |
Hierarchy of cooperating World-Wide Web servers used for many functions in the collaboration:
|
Full HTML Index
General Number Field Sieve (GNFS)
|
GNFSD Wrapper Code
|
Full HTML Index
| http://www.npac.syr.edu/factoring/status.html |
| Web Sieving started in September 1995. |
| On April 10, 1996, we found that |
| RSA-130 = 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557 has the following factorization: RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243 * 45534498646735972188403686897274408864356301263205069600999044599 |
Full HTML Index
| Factoring on the Web Project |
Full HTML Index
| Can grab stock data from real-time services |
| Combine with historical data stored in databases (such as Oracle) |
| Use in Monte Carlo simulations of sophisticated financial instruments |
Full HTML Index
| Cooperative distributed (and parallel) computing will become mainstream in financial engineering due to a convergence of the following factors: |
| Increased volatility due to globalization of financial markets |
| Global distribution of data sources |
| Increase in complexity of derivatives and risk management vehicles |
| Increased demand for real-time asset allocation decision support |
| Increased volume of raw data and need to process large databases |
| Increased volume on the retail side of the spectrum in part due to on-line technologies (Internet and WWW) |
Full HTML Index
HPCC is becoming indispensable in the application domains such as:
|
| NPAC is engaged in development of new tools for quantitative financial modeling which take advantage of scalable computer architectures |
| The ultimate goal is to integrate various quantitative analysis transparently using Web technologies into a seamless cooperative computing environment, capable of supporting all aspects of enterprise-wide risk management. |
Full HTML Index
| We developed new algorithms for risk neutral valuation of derivative financial instruments |
| Theoretical prices of derivative instruments are obtained by discounting their expected payoffs under the equivalent martingale measure using money market interest rate. |
| The core algorithm is Path Integral Monte Carlo which used to generate arbitrary distributions of underlying risk factors (stocks, bonds, short interest rates, commodities, indices etc.) |
The advantage of the new algorithm is that sensitivities of derivative prices with respect to changes in all model parameters are computed in a single simulation.
|
| Parallel version of the algorithm is written in C and MPI and relies on task parallelism and functional decomposition (could also use HPF) |
| Monte Carlo samples are generated on multiple processors in embarrassingly parallel fashion |
Full HTML Index
| Pricing modules can either run in lock-step with the Monte Carlo module which generates histories of risk factors or asynchronously perform valuation functions on the histories which are broadcast as they are generated by the Monte Carlo module |
| We are linking this flexible algorithm with a novel scheme based on Maximum Entropy method which generates implied probability distributions from reported option prices. |
| The implied distributions can be used within the Path Integral Monte Carlo module to price exotic contracts consistently with exchange-traded contracts and they can also be used to search for arbitrage opportunities |
| Estimation of implied distributions requires large scale global optimizers. |
| We are developing two parallel stochastic optimizers based on mean field approximation (Laplace formula) and Langevin equation |
Full HTML Index
| Derivative valuation functions are integrated using Web technologies into a service which can be accessed from any platform which supports a graphical browser |
Using a combination of HTML forms or Java front-end, CGI mechanism, Perl scripts and modules written in C and MPI, which are executed on multiple NPAC RS 6000 and Sun workstations and the SP-2, the user can:
|
Full HTML Index
| In the next stage, flat files will be replaced with a parallel Oracle server |
| Ultimately, the graphical user interface will be supplemented with an agent-based middleware layer, implemented in Java, where derivative pricing and risk management services will be requested and dispatched to the parallel Monte Carlo engine and returned to the client using an EDI-like protocol encapsulated within the KQML envelope. |
| This will be a prototype of the new service economy that will flourish on the Web. |
Full HTML Index
Full HTML Index
Full HTML Index
Full HTML Index
Full HTML Index
| We can exploit the convenience of Java to build sophisticated user interfaces |
Further if computing (such as HPF programs) is linked in real-time to the web, we can get a rich window into execution using Web to process and display information produced by the programs
|
Full HTML Index
| New powerful Web'96 technologies from Netscape, JavaSoft, Oracle, NeXT etc. will result in a new generation of interactive services |
| A natural next step is to start Chaining (Integrating) such services to a distributed PSE by providing a server to server communication and dataflow support |
However Web'96 becomes also increasingly complex with its competing and overlapping multi-lingual standards
|
| Visual Programming for a multi-server Web (We call it WebVM) based dataflow (we call it WebFlow) is a natural next generation user-friendly programming environment |
| We view the area of distributed Web based computing for PSE as a promising niche for NPAC and academic R and D where we expect industry to continue their focus on client-server aspects of the Web where near term profits can be made |
Addon
Full HTML Index
| An example of Web-based Computing |
| It lets researchers author tools and leave them on the machine of choice on the web |
| It allows multiple data bases to intercommunicate with each other and the functional operators that the software tools represent and to make a web browser the window into this system. |
Full HTML Index
| From Gregor von Laszewski |
Full HTML Index
| From Gregor von Laszewski |
Full HTML Index
| From Gregor von Laszewski |
Full HTML Index
| From Gregor von Laszewski |
Full HTML Index
| From Gregor von Laszewski |
Full HTML Index
| http://www.npac.syr.edu/users/gcf/npacaddons -- see foil 105 |
| Java provides a convenient way to build flexible graphics interfaces |
| The screendump shows the message passing traffic and status of (36) parallel nodes used in a sorting algorithm |
| In the example, the 36 threads are running the explicit algorithm on the client |
| Alternatively and more generally, the threads are replaying a trace of the program which is or was running on a separate set of nodes |
If one uses Web Servers to control master parallel computation or more generally integrates Web into computing, these Web servers can naturally feed event traces into Java based display
|
Full HTML Index
| From Kemal Ispirli with 36 threads running client-side |
| Colors represent node status and links message-passing |
Addon
Full HTML Index
Full HTML Index
Full HTML Index
| Web front-end to HPF compiler and PVM-based distributed runtime. |
| Supports CASE tools for program development, process management and performance monitoring. |
| We have illustrated Java Pablo and Distributed Computing Interfaces already |
| This will be initially deployed as a Programming Lab Interface for Web Courses |
Full HTML Index
| PCRC embodies the Parallel Computing Synchronization and collective parallel algorithms and runtime that will enable efficient Web-based computing |
| Replace user interface of HPF or HPC++ with the Web(work) and use pervasive Web Technologies in infrastructure (World Wide Virtual Machine -- WWVM) |
Full HTML Index
| The compilation system is accessed through a Web Browser. The HPF program and requests are POSTed to the HTTP Server using HTTP Protocol. |
| HTTP Server analyzes the incoming request and activates the HPF Service Master which is a CGI module. |
| HPF Service Master starts the Compile module which translates a given HPF program into Fortran 77 with message passing calls (i.e.MPI), and produces an object file using a node compiler. |
Full HTML Index
| Link module links the generated object code with Common Runtime Support (CRS) and MPI libraries. |
| Run module forks copies of the executable code on the nodes of a workstation cluster. |
| After the request has been satisfied, HPF Service Master puts the results into HTML format and sends back to the HTTP Server. |
| HTTP Server sends the results to the Web Browser via the HTTP Protocol. |
Full HTML Index
| The WWVM is accessed through a Web Browser and requests are sent to the server through HTTP Protocol. |
| HTTP Server starts a service master which translates given HPF program to F90 with message passing calls and starts-up other client servers. |
| HTTP Servers at the client side get the requests through the HTTP protocol connection, and activates a Interpreter CGI module. |
| Interpreter makes calls to the Runtime Support and Communication Server that sends and receives messages using PVM daemons. |
Full HTML Index
Full HTML Index
Full HTML Index
| From Kivanc Dincer |
Full HTML Index
| From Kivanc Dincer |
Full HTML Index
| We illustrate here how the individual component technologies cooperate in a complete application, WebAMR (Adaptive Mesh Refinement) |
| A mesh of computationally extended Web servers, connected via HTTP based message passing, acts as WebVM that runs PDE solver modules for individual grids |
| In a simple static AMR topology (WebWork model), a tree of refined meshes is constructed by the user via the AVS like visual programming tools (WebFlow) |
| Dynamic AMR trees require interpreted programming support -- a pilot "little language" design towards WebHPL |
| WebAMR applications can be configured and run on heterogeneous clusters, including any WebWindows compliant platform |
| Example of WebTop System in this domain in a set of WebVM/WebFlow modules, packaged and customized as a PDE Toolkit for a given Grand Challenge community. |
Full HTML Index
| We need to use compilers on tightly coupled systems such as MPP's (shared and distributed memory) |
But for metacomputing, the hardware intrinsically has latencies that suggests increased flexibility of interpreters is more appropriate
|
| Maybe frontends should be built with interpreters such as object-oriented PERL5 so easier to link with Web. |
Note that interpreted environment will have best software engineering support and so suggestion is -- taking SP2 as example:
|
Full HTML Index
This implies that we should allow hybrid model not just for task (interpreted) versus data parallelism(compiled)
|
Current Web Interpreters include Java TCL and PERL(5) which are optimized for different application domains
|
This leads to WebScript Concept of interoperable interpreters optimized for different domains
|
Full HTML Index
| Java is a C++ subset which interestingly does not have pointers as these are unsafe in necessary secure metacomputing environment. |
| Thus Java has removed the part of C++ which is hardest to parallelize |
| Java may not "survive" but if it doesnt something better will! Thus it makes sense to study and experiment with it |
Natural first step is to use Java to build the interpreted "shell" which we called HPFCL for HPF coordination Language.
|
Java is partially compiled as you take basic Java high-level code and compile down to a universal Java machine language. This is very similar to concepts in ANDF (Architecture Neutral Distribution Format) but with a different goal
|
Full HTML Index
| VRML -- Virtual Reality Model Language -- is an object oriented database built as a subset of the SGI Inventor System |
| VRML can be considered as another script optimized for graphics but not many interesting processing (compute) capabilities are in current standard |
VRML can be considered as an example of a universal data structure allowing exchange of 3D objects over the Web.
|
| Thus useful to consider data parallel VRML and building CC++ or HPF(Fortran90) modules to support VRML |
| HPCC community should join with the Web to ensure that standards such as VRML can be implemented efficiently either in parallel (maybe a niche) but also in a distributed network (similar issues where HPCC can contribute and clearly very important) |
Full HTML Index
Features of the Java language and runtime
|
| Can build on existing work on HPF HPC++ -- especially latter |
Two basic types of opportunities:
|
Applet mechanism naturally incorporates task parallelism -- need to add "channel" class (as in Fortran-M, CC++) to augment "thread" and "socket" classes
|
| Java can be used both on Server and Client side as expect soon good Java based clients and servers |
| See the E language http://www.communities.com/e.html |
| or my class notes http://www.npac.syr.edu/users/gcf/cps616java96 or |
| http://www.npac.syr.edu/users/gcf/cps616tech96 |