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.
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
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
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
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
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
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
