Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter.
Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.
OCR for page 3
RECENT CONTRIBUTIONS OF THE MATHEMATICAL SCIENCES
TO HIGH-PERFORMANCE COMPUTING AND COMMUNICATIONS
The federal initiative in High Performance Computing and Communications (HPCC),
proposed in February 1990 by the President to the Congress, consists of four main
components:
A. Development of hardware that will increase computer and communications
performance a thousandfold;
B. Development of advanced software and algorithms to complement the hardware
advances;
C. Development of a National Research and Education Network capable of
transmitting data at a speed of a gigabit per second; and
D. Increases in basic research and development in computational science and
technology so as to produce the knowledge and trained personnel to use the above
products effectively.
The symbiosis between the mathematical sciences2 and high-performance computing and
communications is far-reaching. On the one hand, the mathematical sciences are the
beneficiaries of advances in computing and communications, since these are basic tools for
many mathematical scientists. On the other hand, advances in high-performance
computing and communications rely on the ongoing work of a wide range of mathematical
sciences researchers. This report focuses on the latter half of this interplay. Work on the
four components of the HPCC program must exploit the full range of existing ideas and
techniques from the mathematical sciences, and also develop new mathematical ideas and
methods in the immediate future.
In addition to their work on algorithms and numerical analysis, mathematical scientists
contribute to the fundamental modeling of phenomena, which is the first step in posing
computable questions, to the analysis of those models and their necessary approximations,
2The mathematical sciences include core and applied mathematics, probability,
statistics, operations research, and some areas of theoretical computer science. This report
focuses on the past and potential contributions of researchers who specialize primarily in
the mathematical sciences, although mathematical advances can be made by people with
other specialties.
3
OCR for page 4
and to the collection, analysis, and interpretation of data. The purview of mathematical
scientists also includes the design of chips and communications channels, queueing models
and optimization problems of communications, and other problems underlying the
construction of the hardware for high-performance computing and communications. Other
scientists and engineers may aisc attend to such mathematical issues, sometimes with great
creativity. This is good; it is critical that the design and use of high-performance
computers be done with mathematical sophistication. ideally though, such work is
performed by multidisciplinary teams or informal collaborations bringing together
specialists, including someone who specializes in the mathematical science aspects.
This section surveys some of the ways in which the mathematical sciences have been
contributing in recent years to high-performance computing and communications. These
past contributions are related to the four components of the HPCC program, A through
D listed above.
A. Hardware Advances
Computer simulation and design tools play a critical role in the creation of
high-performance hardware and communications networks. For example, process, device,
and circuit simulators are now routinely used in the early stages of development to
evaluate alternative designs, instead of relying on actual wafer fabrication, resulting in
enormous savings of time and money.
Mathematical scientists, working as part of multidisciplinary teams, have had a substantial
impact on the current array of simulation tools. Many innovative numerical techniques--
including multigrid methods, novel finite-element discretizations, adaptive local mesh
refinement, a postenon error estimation, homotopy continuation techniques, and
differential-algebraic equation solvers--have been introduced from mathematics and
specialized for very large scale integration (VES]:) applications. These have resulted in
substantial increases in the efficiency and reliability of simulators, which have in turn made
practical the current degree of chip sophistication, facilitated the introduction of more
complicated physical models, and enabled some three-dimensional problems to be solved.
Methods of statistical quality control have been brought to bear to achieve still more
efficiency in design development and also to assure the quality of products.
Designing the actual layout of a microprocessor chip is also aided by mathematical
methods--particularly those from discrete mathematics. For instance, a common task in
manufacturing and testing circuit boards is moving a too] to hundreds or thousands of
points and performing some action, such as drilling or probing, at each. Minimizing the
time this takes is frequently a version of the traveling salesman problem, in which one has
to visit all the vertices of a graph with a path of minimal length, where the graph is
embedded in Euclidean space. Advances in graph theory and computational complexity
4
OCR for page 5
have produced simple ways to evaluate the quality of approximation algorithms. Recently,
algorithms have been devised that quickly give solutions within I% of optimal to problems
involving tens of thousands of nodes.
In addition to aiding in the design of efficient circuits and the simulation of the physics
and operation of those designs, the mathematical sciences also contribute to
microelectronics R&D in circuit testing, fault location, and protocol validation. These
areas depend critically on mathematical techniques for logically partitioning large circuits
so as to avoid insupportable exhaustive searches.
B. Software and Algorithm Advances
It is well known that algorithm developments and hardware developments have contributed
equally to the remarkable increase in scientific computing capabilities over recent decades.
The search for more efficient algorithms has been guided by a wide range of mathematical
ideas.
An example of a recent advance is the multigrid algorithm, the fastest known numerical
method for solving elliptic partial differential equations. Recently, a general-purpose
multigrid program--BOXMG [Dendy, 1982i, originally developed to solve neutron transport
calculations--was easily incorporated into an oil-reservoir simulation-production code in use
at Chevron Corporation. The new multigrid software operated five times as fast as the
previous algorithm, cutting hours off the time for each run of the overall simulation
program. This multigrid package is now being redesigned for scalable hypercube
computers and will allow applications programmers ready access to high-powered
algorithms. Future research into multigrid algorithms for systems of linear and mildly
nonlinear equations holds the promise of similar improvements in computational fluid
dynamics simulations in many other contexts.
The technology for using parallel and `distributed architectures is maturing quickly and will
be essential to the future of high-performance computing. While profiting from the use
of these new architectures, the mathematical sciences have also contributed much to the
development of this necessary technology. Areas such as graph theory, combinatorics, and
probability and statistics have become basic to the analysis of interprocessor networks and
the complexity of algorithms, to the prediction of fault tolerance, and to the mapping of
parallel algorithms. For example, graph theory has played an important role in the design
of networks whose small diameter and high local connectivity minimize internal
communications, and in the mapping of algorithms to the architecture so as to make
optimal use of the available bandwidth [see, e.g., Johnsson, 19873.
Mathematical advances always have the potential for far-reaching ramifications. Consider
the case of the problem of simulating the trajectories of N mutually interacting bodies, the
5
OCR for page 6
N-body problem. This is a basic algorithmic kernel in a number of scientific codes
including celestial mechanics, molecular dynamics, and fluid dynamics. Directly computing
the N2-pairwise interactions on a conventional computer can take an unacceptably long
amount of time for values of N in the range of interest for applications, but recent work
has given rise to two fruitful approaches to this problem. The first seeks alternative
methods that solve an approximation to the problem but reduce the computational
complexity. These include the particle/mesh [Hockney and Eastwood, 1981], local
correction [Anderson, 1986], hierarchical [Appel, 1985; Barnes and Hut, 1986], and
multipole [Greengard and Rokhlin, 1987] methods. The second approach led to new
algorithms for the direct method that take advantage of parallel hypercube architectures
to enable one to obtain results for large values of N in a reasonable amount of time
[Brunet et al., 1990~.
Other advances are stemming from the burst of mathematical activity in recent years in
the creation of new bases for L2(R), such as Meyer and Daubechies waveless [e.g.,
Daubechies, 1988] or Colfman and Meyer windowed transforms [Colfman and Meyer,
1990; Coifman, 19914. These tools have already led to exciting results in data compression
for speech and images. Wavelets have also had an impact on spread-spectrum
communication. Related work on solving integral equations [Beylkin et al., 1991] is also
of potential value to the HPCC program, because it shows great promise for solving the
cross-chatter problem on the next generation of chips.
Another example of the role of the mathematical sciences is in human-machine
communication. Complex machines (especially communication systems and computers)
serve society better if they are easy and natural to use. Spoken language communication
with machines is now becoming practical through combined advances in microelectronics
and algorithmic understanding for digitally processing information signals (speech, image,
and, to some extent, touch). Fundamental mathematics research has led to advances such
as dynamic programming, which allows efficient comparisons of information patterns.
This technique for pattern recognition has found wide application in areas as diverse as
biology (see Section 4) and communications. In word-based automatic speech recognition,
it is crucial to the reliability and high performance that are now being achieved. In the
same field, hidden Markov models have proved remarkably effective in characterizing
sequences of distinctive signal spectra, for phonemes or for whole words. Voice
interaction with machines is now being commercially deployed in preliminary forms, such
as voice repertory dialers for mobile cellular telephones, automated voice information
services (in the financial and telecommunications sectors), and in consumer products such
as voice-controlled toys and home systems. These societal applications' moving in the
direction of easy use of complex systems, depend directly on mathematical advances, and
continued improvements in human-machine communication will likewise depend on
continued advances in mathematical understanding [Flanagan et aL, 1990; Flanagan, 1991].
6
OCR for page 7
C. Networks
The National Research and Education Network (NREN) component of the HPCC
program has as its goal to dramatically enhance and expand the worldwide infrastructure
of high-performance computing. This initiative will provide network access to research and
educational institutions at all levels. The NREN must provide enormous bandwidth and
a set of capabilities going far beyond currently available networking technology. These
capabilities include fast database access and retrieval, teleconferencing, real-time
visualization, and remote control of experiments.
The networks and communication protocols must be capable of simultaneously handling
traffic types with many different characteristics, including bulk file transfer, bursty
interactions from voice or image transmissions, and messages with timing requirements,
used to control remote experimentation.
The mathematical sciences have played an important role in the development of theories
that led to today's communication technology. Coding theory and data compression
algorithms are routinely used to achieve both the efficient use of available bandwidth and
high reliability in data transmissions. Queueing theory, especially network queueing theory,
and large-scale optimization methods have been used to successfully model, predict, and
control effects of congestion. These theories have also been instrumental in achieving
efficient network flows and rerouting of traffic when network failures occur.
Optical fiber transmission technology, as an example, has been significantly influenced by
the mathematical theory of solitons [e.g., Newell, 19853. High-capacity data transmission
over long distances became possible with the advent of light-transmission technology in
optical fibers in the 1970s. Light pulses broaden as they propagate because of dispersion.
This limits the capacity of optical fibers to transmit error-free information at high speeds.
The need for frequent reconstruction and amplification of the pulses to compensate for
dispersion introduces noise and substantially increases the cost of the network. The
mathematical theory of solitons, which are nonlinear waves that retain their shape in the
presence of dispersion, introduced the possibility of nonlinear pulse transmission in optical
fibers tHasegawa and Tappert, 19733. In 1990, Mollenauer demonstrated in a series of
definitive experiments that nonlinear optical pulses allow for very efficient high-capacity
transmission over long distances [Mollenauer et al., 1990~. As a result, a transpacific
optical fiber cable from the United States to Japan is now under development and is
expected to be functional by 1995.
D. Basic Research and Human Resources
The development to date of high-performance computing and communications has relied
heavily on basic research, and a substantial portion of that work has been in the
7
OCR for page 8
mathematical sciences. For example, graph theory and control theory developed over
the past few decades have been translated into techniques for chip design and production;
numerical analysis underlies the software libraries now appearing in serial, vector, and
parallel form; and queueing theory and statistics have enabled prediction of the behavior
of networks. The mathematical sciences and computational science are so closely entwined
that research in the former has inevitably benefited the latter.
As high-performance computing equipment has become increasingly available, universities
and federal funding agencies have also stepped up their efforts to develop users for that
machinery. Mathematical scientists have played a significant role in building up a base of
computational scientists, in particular by helping to found new undergraduate and graduate
programs in computational science. On the national level, the so-called "David I" report
[National Research Council, 1984] called for additional federal funding specifically to
prepare enough new mathematical scientists to support the then-emerging field of
supercomputing, and a more recent report [National Research Council, 1990] focused
substantial attention on human resources issues in the mathematical sciences.
8
Representative terms from entire chapter:
mathematical scientists
