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 9
POTENTIAL CONTRIBUTIONS OF THE MATHEMATICAL SCIENCES
TO HIGH-PERFORMANCE COMPUTING AND COMMUNICATIONS
The goals of the HPCC program cannot be met without the continued and substantial
involvement of mathematical sciences researchers, making advances such as those profiled
in Section 2. This section describes areas where mathematical involvement is crucial for
the success of the HPCC program or to longer-term progress in high-performance
computing and communications.
A. Hardware Advances
With circuit geometries becoming ever more complex, the importance of carefully designing
and modeling chips (including the modeling of the underlying materials) and their
manufacturing processes, and of identifying wafer and process flaws early, is steadily
increasing. Design and manufacturing faults contribute to limited yields in chin production.
and newer high-density circuits are especially fault-prone.
1 1
Optima] and robust engineering design for complex industrial processes is being addressed
with high-dimensional statistical modeling, which has the potential to contribute greatly.
Although these complex processes differ in many specific details, all share the features of
having a large number of process stages involving several hundred controllable variables,
and a set (often 10 or more) of final specifications that must be met. Actual production
data lead to in-line production measurements and final quality measurements as a function
of input and control variables. Potential progress is foreshadowed by some remarkable
successes [e.~.. Lorenzen. 19881 achieved bv using existing and modified techniques of
O. , ~,
. - . - . . · · . - . .- · . . . - ~ . ~ . . · · . . . - .
statistical design in nlgn-olmenslona1 settings. One class or techniques involves statlstlca
visualizations of the data, including methods in which the high-dimensional data are
reduced to a sequence of color pictures that can be viewed on a television. It also
includes the numerous high-dimension statistical methods of ACE, AVAS, CART, MARS,
projection pursuit regression, and so on [e.g., Efron and Tibshirani, 1991; HurIey and Buja,
19903. A second class of techniques creates a parametric mode] for each stage with a
prior distribution created for each of the unknown parameters. The data are then used
to sequentially estimate the posterior distribution of the parameters associated with each
stage of production.
Inevitably, defects are introduced during the production process. It is essential that these
be identified as early as possible during actual production so that process flaws can be
corrected and investment losses minimized. Most defects are visible only at high
9
OCR for page 10
magnification, which makes it infeasible for a process engineer to inspect all but a small
fraction of the total wafer. Current capabilities in automatic wafer inspection are limited,
largely because circuit patterns on wafers that have already undergone several stages of
processing appear in an unpredictable variety of colors' shadings' and textures. Whereas
humans easily accommodate these variations, machines "see" textures as collections of
micropatterns. The main challenge is to devise a machine-vision algorithm for collecting
these micropatterns into a textured whole, and thereby confirm the correctness of the
overall shape. A rather general theory, developed for stationary spatial stochastic
processes and involving Markov random fields, provides a possible tool for modeling the
textures that arise in, and confound, this and other inspection applications.
Control theory must be introduced into the chip-manufacturing process, in order both to
reduce start-up time and to produce quality products. In turn, these controls will call for
"smart" sensors incorporating signal processing and sophisticated decision-making
techniques. Finally, statistical quality control is critical to successful and timely
development and production of the necessary materials and components.
A closely related issue is that of on-line process diagnostics. In a production process, the
final product can fail to meet specifications if some stage of the production process is
performed abnormally, possibly because one of the machines used is deteriorating. In a
complex process, such deterioration may be very difficult to find. In VLSI fabrication,
where process cycle times can be as long as two months, early diagnosis of process
deterioration is vital. Models for the status of the input to each stage, in the form of
(perhaps very high dimensional) probability distributions, can lead to rapid process
diagnostics.
An additional approach for optimizing parameters in the engineering design of processes
in semiconductor manufacturing, as well as the design of circuits and devices, is to develop
statistical surrogates (fast prototypes) for high-dimensional simulators. Moderate-
dimensional response surface modeling has been successfully used to treat problems under
conditions where only a limited number of simulation runs are available. A single
optimization problem may require some 100,000 simulator runs. Doing many optimizations
to allow the designer to vale specifications and constraints would result in even more
prohibitive costs. The development of new hardware for high-performance systems will
inevitably lead to still greater demands.
B. Software and Algorithm Advances
Basic to achieving software and algorithmic advances are a number of specific needs
identified by the panel that will require substantial research progress in the mathematical
sciences.
10
OCR for page 11
I. The introduction of exotic architectures, especially massively parallel machines, has
resulted in an increase in the importance of numerical analysis and the trade-offs between
performance, stability, and accuracy of the basic numerical algorithms. Some issues that
must be dealt with are the building of random number generators that can run
concurrently on, say, 64,000 processors and produce uncorrelated streams. A less-stable
or less-common algorithm may become attractive for particular architectures because its
performance is better than that of an adaptation of the algorithm more commonly used
for serial machines; e.g., Gauss-Iordan elimination may be preferred to the standard LU
factorization when solving linear systems. There is also the question of the speed and
robustness of the actual floating-point arithmetic algorithms used on the individual
processors themselves; their numerical accuracy is also critical, since the very large
problems that are run on high-performance computers invite trouble from roundoff error.
These issues need serious mathematical investigation as more high-performance and highly
parallel computers emerge. The results of this work watt have to be incorporated into
whatever basic mathematical libraries are produced, and users will need to be educated
as to pitfalls and the trade-offs in performance, stability, and accuracy. Mathematical
scientists will have to do these analyses and provide material for the educational process.
The NSF-funded LAPACK project, an effort to design and implement the
LTNPACKlElSPACK suite on parallel architectures, has made a start in this direction, but
additional parallel libraries are needed.
2. A most useful advance would be the mathematical abstraction of the general structure
of algorithms to display their data flow requirements. Currently, each library routine for
a distributed memory computer has built-in assumptions about data flow and storage
layouts because the underlying mathematical algorithm does not carry information about
Hose cno~ces. nor example, tne Data resow or a rest courter transform (FFT) has been
altered in many ways over the years to fit hardware constraints. Recently, a mathematical
structure has been found to underlie this apparently ad hoc diversity, and so it is now
possible to systematically search the collection of such adaptations to find a form that wall
best fit any architecture. A technically modest, but practically significant, extension of this
result could generate Iibrarv routines from more general templates. based on specifications
~ 1 _ _ _ _ 1 _ · ~ _ ~ , 1 ~ , rat r ~ , ~ · ~
~ ~ ~ ~ ~ 1
· ~ ~ ~ - ~ ~ · · ~ ~ · ~ - ~ - - ~ - - ~ - ~ - -
prov~ueo by the user. In pnnc~ple, this could also be done for other basic library items
in addition to the FFT. In the simplest cases this automatic generation of routines would
involve no more than a decision at compile time about which of several mathematically
equivalent versions of a routine to use.
3. A more ambitious, but still practical, advance would be the creation of higher-level
libraries. Current software libraries are rich in low-level math routines (e.g., trigonometric
functions) and have a moderate number of middIe-leve] routines (e.g., linear algebra
subroutines), but there is almost no high-level software, which could perform many
procedures common to a variety of codes. For example, many computer models are based
essentially on the numerical solution of complicated systems of partial differential
equations. Rather than applications programmers writing each code from scratch,
11
OCR for page 12
incorporating some appropriate library subroutines (subject to the limitations of their
mathematical understanding), a higher-level library would provide these programmers with
larger blocks of code for major components of the modeling task--components such as
generating and rezoning grids, as appropriate; approximating derivatives numerically;
incorporating boundary conditions; and integrating the large, sparse systems of equations
as they evolve in time. These high-level blocks would internally adopt the data storage
and flow appropriate to the hardware and select mathematical algorithms and parameters
consistent with the reality being modeled.
4. The massive data sets now becoming available in many fields, from geosciences to
biology and medicine, call for more powerful and succinct statistical analysis techniques,
data storage and search algorithms, and visualization models. The central problem is how
to deal with high-dimensional (greater than 10 dimensions) and very high dimensional
(greater than 100 dimensions) state spaces.
5. It is very important to develop efficient algorithms for computational geometry. These
algorithms are important for grinding methods in partial differential equations and for
visualization. Also, simulations using three spatial dimensions are becoming commonplace,
increasing the geometrical complexity of simulation domains and contributing to the need
for computational geometry algorithms.
6. Symbolic computing has the potential to become a much more common tool, especially
as computing power develops isee Boyle and Caviness, 19904. It has already been of use
in calculating high-order perturbation expansions for problems from theoretical mechanics
and orbital dynamics. This technology can reveal the important mathematical structure
of problems and solutions. It enables efficient sensitivity analyses and allows one to avoid
numerical round-off until numbers are entered for a specific calculation.
C. Networks
The network technology goals of the HPCC program will require major contributions
from the mathematical sciences. The improvement of optical fiber technology requires
a deeper understanding of many basic problems in nonlinear optics, which can be acquired
by a combination of analytical and numerical methods. The effect of noise introduced
both by the signal repeaters and by imperfections in the fibers leads to difficult
mathematical problems in nonlinear partial differential equations with random coefficients.
A particularly interesting problem is the analysis of noise effects when the nonlinear pulse
is tuned to operate around the frequency for which the fiber has minimal dispersion. This
leads to mathematically degenerate equations that are even more difficult to analyze.
Carefully designed numerical simulations will be needed to help solve such equations.
Algorithmic advances in coding theory and data compression will be needed to handle a
12
OCR for page 13
wider range of multimedia traffic, including data, voice, and images. The wider range of
traffic characteristics and the increased scale of the network will necessitate advances in
queueing theory and network algorithms. Moreover, if any of the traffic has explicit timing
requirements, such as in the remote control of experiments, new theory will be needed to
handle this new dimension in communication queueing.
Given that new networks will result in high-volume and high-rate data transfers, recent
research in diffusion approximations of network queueing systems [e.g., Harrison, 1988]
will be of significance. At high levels of utilization, traffic flows can be approximated by
diffusion processes. This allows one to recast flow control, buffer sizing, and traffic routing
problems into the existing and well-studied framework of the stochastic control of diffusion
processes.
Another critical concern is the security of any national network. Issues of valid user
access to the network and the machine resources available on it, authentication, data file
encryption, and security of established communication links between collaborating users
or programs will all require a high level of security. This implies the necessity of robust
cryptographic systems and protocols. Since the original discovery of public-key
cryptosystems [Diffie and Hellman, 1976; Rivest et al., 1978], the mathematics community
has made great strides in the area of cryptography. Number theory and the theory of
computational complexity have made the key contributions to the underlying algorithms
and protocols that are the basis for existing schemes. For the future, there are two
requirements, one scientific and one administrative. The first is the need for the
development of a unified scheme to provide an appropriate, safe networking environment
for users and their programs. Mathematical work will be required to design the system
and to establish its robustness. The second and critical element is creating strong
incentives to rid such a network of well-known insecure software that compromises the
integrity of the entire system.
D. Basic Research and Human Resources
As exemplified under topics A, B. and C of this section, basic research for the HPCC
program must include research in a wide range of the mathematical sciences.
Mathematical researchers have much to contribute to this component of the HPCC
program.
Likewise, development of human resources for high-performance computing and
communications will continue to rely on contributions from mathematical scientists:
computational scientists must be well grounded in the mathematical sciences. More
particularly, the education and outreach programs at the nation's established
supercomputer centers will continue to reduce the barriers between applied and theoretical
scientists and will accelerate the impact of new mathematical models and algorithms on
13
OCR for page 14
large-scale computing. Such programs also can serve as catalysts to bring together
mathematical and physical (or biological) scientists into multidisciplinary groups, which can
be an extremely valuable research mode. The very nature of the HPOC program and the
grand challenges calls out for such an environment. By stimulating interactions among
different disciplines and engaging young researchers and students in these activities, an
exciting and appealing atmosphere is created that readily attracts new blood into these
areas.
Modes of research that create such an environment should be encouraged as part of the
HPCC initiative. Even though such educational, outreach, and student-mentor programs
are relatively low-cost and high-leverage means of educating and training people for
high-performance computing and communications, they are not nearly as numerous or
large as they should be, due to a lack of funding. There are many university research
groups that could increase the number of students trained in emerging areas of
high-performance computing and communications if more support were available.
14
Representative terms from entire chapter:
hpcc program
