Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
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
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
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
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
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
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