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.
6 What Is Computer Science and Engineering? Chapter 1 provided a brief sketch of computer science and engi- neering as an intellectual discipline. This chapter elaborates on that discussion, discusses some key structural features of the field, and provides some history on some of the major intellectual accomplish- ments of the field in a few selected areas. For the reader's conve- nience, the Chapter 1 section "Computer Science and Engineering" is reproduced in its entirety here. COMPUTER SCIENCE AND ENGINEERING Computational power however measured- has increased dra- matically in the last several decades. What is the source of this in- crease? The contributions of solid-state physicists and materials scientists to the increase of computer power are undeniable; their efforts have made successive generations of electronic components ever smaller, faster, lighter, and cheaper. But the ability to organize these compo- nents into useful computer hardware (e.g., processors, storage de- vices, displays) and to write the software required (e.g., spreadsheets, electronic mail packages, databases) to exploit this hardware are pri- marily the fruits of CS&E. Further advances in computer power and usability will also depend in large part on pushing back the frontiers of CS&E. 163
164 COMPUTING THE FUTURE Intellectually, the "science" in "computer science and engineer- ing" connotes understanding of computing activities, through mathe- matical and engineering models and based on theory and abstrac- tion. The term "engineering" in "computer science and engineering" refers to the practical application, based on abstraction and design, of the scientific principles and methodologies to the development and maintenance of computer systems be they composed of hardware, software, or both.: Thus both science and engineering characterize the approach of CS&E professionals to their object of study. What is the object of study? For the physicist, the object of study may be an atom or a star. For the biologist, it may be a cell or a plant. But computer scientists and engineers focus on information, on the ways of representing and processing information, and on the machines and systems that perform these tasks. The key intellectual themes in CS&E are algorithmic thinking, the representation of information, and computer programs. An algo- rithm is an unambiguous sequence of steps for processing informa- tion, and computer scientists and engineers tend to believe in an algorithmic approach to solving problems. In the words of Donald Knuth, one of the leaders of CS&E: CS&E is a field that attracts a different kind of thinker. I believe that one who is a natural computer scientist thinks algorithmically. Such people are especially good at dealing with situations where different rules apply in different cases; they are individuals who can rapidly change levels of abstraction, simultaneously seeing things "in the large" arid "in the small."2 The second key theme is the selection of appropriate representa- tions of information; indeed, designing data structures is often the first step in designing an algorithm. Much as with physics, where picking the right frame of reference and right coordinate system is critical to a simple solution, picking one data structure or another can make a problem easy or hard, its solution slow or fast. The issues are twofold: (1) how should the abstraction be repre- sented, and (2) how should the representation be properly structured to allow efficient access for common operations? A classic example is the problem of representing parts, suppliers, and customers. Each of these entities is represented by its attributes (e.g., a customer has a name, an address, a billing number, and so on). Each supplier has a price list, and each customer has a set of outstanding orders to each supplier. Thus there are five record types: parts, suppliers, custom- ers, price, and orders. The problem is to organize the data so that it is easy to answer questions like: Which supplier has the lowest price
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 165 ore part P?, or, Who is the largest customer of supplier S? By cluster- ing related data together, and by constructing auxiliary indices on the data, it becomes possible to answer such questions quickly with- out having to search the ermine database. The two examples below also illustrate the importance of proper representation of information: · A "white pages" telephone directory is arranged by name: knowing the name, it is possible to look up a telephone number. But a "criss- cross" directory that is arranged by number is necessary when one needs to identify the caller associated with a given number. Each directory contains the same information, but the different structuring of the information makes each directory useful in its own way. · A circle can be represented by an equation or by a set of points. A circle to be drawn on a display screen may be more conveniently represented as a set of points, whereas an equation may be a better representation if a problem calls for determining if a given point lies inside or outside the circle. A computer program expresses algorithms and structures ir~for- mation using a programming language. Such languages provide a way to represent an algorithm precisely enough that a "high-level" description (i.e., one that is easily understood by humans) cart be mechanically translated ("compiled") into a "low-level" version that the computer can carry out (unexecuted; the execution of a program by a computer is what allows the algorithm to come alive, instructing the computer to perform the tasks the person has requested. Com- puter programs are thus the essential link between intellectual corr- structs such as algorithms and information representations arid the computers that enable the information revolution. Computer programs enable the computer scientist and engineer to feel the excitement of seeing something spring to life from the "mind's eye" and of creating information artifacts that have consid- erable practical utility for people in all walks of life. Fred Brooks has captured the excitement of programming: The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, creating by the exertion of the imagination.... Yet the program construct, unlike the poet's words, is real in the sense that it moves and works, pro ducing visible outputs separate from the construct itself. The magic of myth and legend has come true in our time. One types the correct incantation on a keyboard, and a display screen comes to life, showing things that never were nor could be.3
166 COMPUTING THE FUTURE Programmers are in equal portions playwright and puppeteer, working as a novelist would if he could make his characters come to life simply by touching the keys of his typewriter. As Ivan Suther- land, the father of computer graphics, has said, Through computer displays I have landed an airplane on the deck of a moving carrier, observed a nuclear particle hit a potential well, flown in a rocket at nearly the speed of light, and watched a com- puter reveal its innermost workings.4 Programming is an enormously challenging intellectual activity. Apart from deciding on appropriate algorithms and representations of information, perhaps the most fundamental issue in developing computer programs arises from the fact that the computer (unlike other similar devices such as non-programmable calculators) has the ability to take different courses of action based on the outcome of various decisions. Here are three examples of decisions that pro- grammers convey to a computer: · Find a particular name associated with it. 1] n a list and dial the telephone number · If this point lies within this circle then color it black; otherwise color it white. · While the input data are greater than zero, display them on the screen. When a program does not involve such decisions, the exact se- quence of steps (i.e., the ''execution path") is known in advance. But in a program that involves many such decisions, the sequence of steps cannot be known in advance. Thus the programmer must an- ticipate all possible execution paths. The problem is that the number of possible paths grows very rapidly with the number of decisions: a program with only 10 "yes" or "no" decisions can have over 1000 possible paths, and one with 20 such decisions can have over 1 mil- lion. Algorithmic thinking, information representation, and computer programs are themes central to all subfields of CS&E research. Box 6.1 illustrates a typical taxonomy of these subfields. Consider the subarea of computer architecture. Computer engineers must have a basic understanding of the algorithms that will be executed on the computers they design, as illustrated by today's designers of parallel and concurrent computers. Indeed, computer engineers are faced with many decisions that involve the selection of appropriate algo- rithms, since any programmable algorithm can be implemented in hardware. Through a better understanding of algorithms, computer
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 167 . . . . . . . . . ... .. . . . . .. ... . . . . . . . . . . . . ''"a.". 22"'^ i'" " " "~'''t21 "t' ' ' ' ' ' '" " ' ' '' ' ' " ' ' ' ' ' ' Programming I tngoages Computer architecture |~| :~41111 chili ' ~c=~,~..~.~.......... ~-~ ~ a~s:~:~n-ales: e~meat<>s? ~ Maya titohnermOantd) '..'''''c'l'.''"'3""'""''' ........ ..... . ... ........ .......... ................................... . · '""'I"""" I ~ to Cheer| (dentin jam re9~i~ii|S 8|| 5~( j3tC2|iQn$| tm3 . . . . . ~ ~ ~ ~ ~11~ engineers can better optimize the match between their hardware and the programs that will run on them. Those who design computer languages (item two in Box 6.1) with which people write programs also concern themselves with algorithms and information representation. Computer languages often differ in the ease with which various types of algorithms can be expressed and in their ability to represent different types of information. For example, a computer language such as Fortran is particularly conve- nient for implementing iterative algorithms for numerical calcula- tion, whereas Cobol may be much more convenient for problems that call for the manipulation and the input and output of large amounts of textual data. The language Lisp is useful for manipulating sym- bolic relations, while Ada is specifically designed for "embedded" computing problems (e.g., real-time flight control). The themes of algorithms, programs, and information representa- tion also provide material for intellectual study in and of themselves,
168 COMPUTING THE FUTURE often with important practical results. The study of algorithms with- in CS&E is as challenging as any area of mathematics; it has practical importance as well, since improperly chosen algorithms may solve problems in a highly inefficient manner, and problems can have in- trinsic limits on how many steps are needed to solve them (Box 6.2~. The study of programs is a broad area, ranging from the highly for- mal study of mathematically proving programs correct to very prac- tical considerations regarding tools with which to specify, write, de- bug, maintain, and modify very large software systems (otherwise called software engineering). Information representation is the cen- tral theme underlying the study of data structures (how information can best be represented for computer processing) and much of hu- man-computer interaction (how information can best be represented to maximize its utility for human beings). ABSTRACTIONS IN COMPUTER SYSTEMS While algorithmic thinking, computer programs, and information representation are the key intellectual themes in the study of CS&E, the design, construction, and operation of computer systems require talents from a wide range of fields, such as electrical engineering for hardware, logic and mathematical analysis for writing programs, and psychology for the design of better user interfaces, to name just a few. This breadth reflects the fact that computer systems are among
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 169 the most complicated objects ever created by human beings. For example, the fastest computers today have around 100 billion transis- tors, while the personal computer on one's desk may have "only" a few million. People routinely use computer programs that are hun- dreds of thousands of lines long, and the largest software systems involve tens of millions of lines; printed at 50 lines per paper page, such a system might weigh several tons. One of the most effective ways to cope with such complexity is to use abstractions. Abstraction is a generic technique that allows the human scientist or engineer to focus only on certain features of an object or artifact while hiding the others. However, while scientists in other disciplines typically use abstractions as a way to simplify calculations for purposes of analysis, those in CS&E are concerned with abstractions for purposes of synthesis: to build working com- puter systems. Other engineering disciplines also use abstractions as the basis of synthesis, but the "stuff" of these disciplines-engineered and created artifacts is ultimately governed by the tangible reality of nature, which itself imposes structure on these abstractions. Com- puter programs are not similarly limited; instead, they are built out of ideas and information whose structuring is constrained only by human imagination. This extraordinary flexibility in structuring in- formation has no analog in the material world. The focus of the computer scientist or engineer in creating an abstraction is to hide the complexity of operation "underneath the abstraction/' while offering a simple and useful set of services "on top of it." Using such abstractions is CS&E's principal technique for organizing and constructing very sophisticated computer systems. One particularly useful abstraction uses hardware, system software, and application software as successive layers on which useful com- puter systems can be built. At the center of all computer systems is hardware, i.e., the por- tion of a computer system that one can see and touch. Hardware is divided into three principal components: · Processors. Processors perform the arithmetic and logical oper- ations, much like the arithmetic operations available in a hand-held calculator. Processors also handle conditional behavior, executing one or another set of operations depending on the outcome of some . . c .eclslon. · Memory (short term and long termJ. Memory hardware is like the memory function of a calculator, since it can be used to save and later retrieve information. Such information may be lost in a calcula- tor when the power is turned off, as it is in the short-term memory of
170 most computer systems. COMPUTING THE FUTURE Computer systems also need a long-term memory that doesn't forget when the power is lost. · Communication (user-machine and machine-machined. For com puters to be useful, they must be able to communicate with people, and so display screens and keyboards are critical components of com- puter systems. For maximum usefulness, computers must be able to communicate with other computers, and so computers are often equipped with modems or other network connections that can transmit and receive data to and from other computers. Readers familiar with personal computers are likely to have en- countered the technical names or brand names for these three types of hardware. Personal computers might use an Intel 80486 processor as the processor hardware, dynamic random access memory (DRAM) as the short-term memory hardware, and disks as the long-term memory hardware. The user-computer communication hardware for personal computers is the keyboard, mouse, and video screen, while examples of machine-machine communication hardware are telephone modems and networks such as Appletalk and Ethernet. While the characteristics of the underlying hardware are what ultimately determine the computational power of a computer system, direct manipulation of hardware would be cumbersome, difficult, and error-prone, a lesson learned in the earliest days of computing when programmers literally connected wires to program a computer. Thus computer scientists and engineers construct a layer of "system soft- ware" around the hardware. System software hides the details of machine operation from the user, while providing services that most users will require, services such as displaying information on a screen, reading and writing in- formation to and from a disk drive, and so on. System software is commonly divided into three components: · Operating system software that controls the hardware and or- chestrates how other programs work together. The operating system may also include network software that allows computers to commu- nicate with one another. · Tools-the software (e.g., compilers, debuggers, linkers, data- base management systems) that allows programmers to write pro- grams that will perform a specific task. Compilers and linkers trans- late "high-level" languages into machine language, i.e., the ones and zeros that govern machine operation at the lowest level. Debuggers help programmers to find errors in their work. Database manage- ment systems store, organize, and retrieve data conveniently. · User interface-the software that enables the user to interact with the machine.
WHAT IS COMPUTER SCIENCE AND ENGINEERING ? 171 Once again, personal computer users are likely already familiar with the brand names of these pieces of system software. MS-DOS in IBM Personal Computers and the System in Macintoshes are exam- ples of operating system software; Novell is the brand name of one type of widely used networking software; Dbase IV is a popular da- tabase management system; Microsoft Basic and Borland C are exam- ples of compiler system software; and Microsoft Windows and the Macintosh Desktop are examples of user interface system software. While the services provided by system software are usually re- quired by all users, they are not in themselves sufficient to provide computing that is useful in solving the problems of the end user, such as the secretary or the accountant or the pilot. Software de- signed to solve specific problems is called applications software; ex- amples include word processors, spreadsheets, climate models, au- tomatic teller machines, electronic mail, airline reservation systems, engineering structural analysis programs, real-time aircraft control systems, and so on. Such software makes use of the services provid- ed by system software as fundamental building blocks linked togeth- er in such a way that useful computing can be done. Examples of applications software include WordPerfect and Word (word-process- ing applications) and Lotus 1-2-3 and Excel (spreadsheet applications), and there are as many varieties of applications software as there are different computing problems to solve. The frequent use of system software services by all varieties of applications software underscores an important economic point: pro- viding these services in system software means that developers of applications software need not spend their time and effort in devel- oping these services, but rather can concentrate on programming that is specifically related to solving the problem of interest to the end user. The result is that it becomes much easier to develop applica- tions, leading to more and higher-quality computing applications than might otherwise be expected. This description of layering a computer system into hardware, system software, and applications software is a simple example of abstraction.5 (Box 6.3 explains why abstraction is so powerful a tool for the computer scientist and engineer.) But it suffices to illustrate one very important use of abstraction in computer systems: each layer provides the capability to specify that certain tasks be carried out without specifying how they should be carried out. In general, computing artifacts embody many different abstractions that capture many different levels of detail. A good abstraction is one that captures the important features of an artifact and allows the user to ignore the irrelevant ones. (The features decided to be important collectively constitute the interface
172 COMPUTING THE FUTURE
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 173 of the artifact to the outside world.) By hiding details, an abstraction can make working with an artifact easier and less subject to error. But hiding details is not cost free in a particular programming problem, access to a hidden detail might in fact be quite useful to the person who will use that abstraction. Thus deciding how to construct an abstraction (i.e., deciding what is important and irrelevant) is one of the most challenging intellectual issues in CS&E. A simple example of this issue is the writing of a system program that displays data on a screen. The program may allow the user to specify the size of the screen, or it may assume that "one screen size fits all." In the first case, the user is given control over the screen size, at the cost of having to remember to specify it every time this program is used. In the second case, the user does not need to choose the screen size, but also loses the flexibility to use the program on screens of different size. A second challenging issue is how to manage all of the details that are hidden. The fact that they are hidden beneath the interface does not mean that they are irrelevant, but only that the computer scientist or engineer must design and implement approaches to han- dle these details "automatically," i.e., without external specification. Decisions about how best to handle these details are subject to nu- merous trade-offs. For example, a designer of computer systems may face the question of whether to implement a certain function in hard- ware or in software. By implementing the function in hardware, the designer gains speed of execution, but at the cost of making the func- tion very difficult to change. A function implemented in software executes more slowly, but is much easier to change. Abstractions enable computer scientists and engineers to deal with large differences of scale. At the highest level of abstraction, a per- son editing a document in a word-processing program needs only to mark the start and the end of the block of text and then press the DEL key to delete the block of text. But these few keystrokes can initiate the execution of thousands or tens of thousands of basic in- structions in the machine's hardware. Only by inserting abstractions intermediate between the user's keystrokes and the basic machine instructions can those keystrokes be predictably translated into the correct set of instructions. Thus the programmer who writes the word-processing program will provide one abstraction (in this case called a subroutine) that will delete the block from the screen, a sec- ond to reformat and redisplay the remaining text, and a third to save the changed document to disk. Within each of these abstractions will be lower-level abstractions that perform smaller tasks; each succes
174 COMPUTING THE FUTURE sive lower-level abstraction will control the execution of ever smaller numbers of basic machine instructions. Abstractions are also central to dealing with problems of differ- ent size (e.g., searching a database with a thousand or a billion records) or hardware of different capability (e.g., a computer that performs a million or 10 billion calculations per second). Ideally, the user ought to be presented with the same high-level abstraction in each of these cases, while the differences in problem size or hardware capability ought to be handled at lower levels of abstraction. In other words, the user ought not be obligated to change his or her approach simply because the problem changes in size or the hardware becomes more capable. However, in practice today, users must often pay logical and con- ceptual attention to differences in hardware capability and problem size. Querying a database of a billion records requires a strategy different from one for querying a database of a thousand records, since narrowing the search is much more difficult in the larger case; writing a program to run on a computer that performs 10 billion calculations per second most likely requires an approach different from one for a program written to run on a computer that performs one million calculations per second, since the former is likely to be a parallel computer and the latter a serial computer. Bridging the gap between today's practice and the ideal making the "ought-to-be's" come true is the goal of much CS&E research today. SELECTED ACCOMPLISHMENTS This section is intended to be partly tutorial (describing some of the intellectual issues in the field) and partly historical (describing accomplishments that have had some impact on computing practice). The committee also wishes to bring to the reader's attention a 1989 report of the NSF advisory committee for computer research, Com- puter Science: Achievements and Opportunities, that provides a good discussion of the accomplishments of CS&E from the perspective of the field's own internal logic and intellectual disciplined Further, the committee stresses that this sampling of intellectual accomplish- ments does not differentiate between those made by academia and those made by industry; as the discussion in Chapters 1 and 2 sug- gests, the determination of "credit" for any given accomplishment would be a difficult task indeed.
WHAT IS COMPUTER SCIENCE AND ENGINEERING? Systems and Architectures 175 Computing-system architects and building architects play similar roles: both design structures that satisfy human needs and that can be constructed economically from available materials. Buildings have many sizes, shapes, styles, and purposes; similarly, computing sys- tems range from the single microelectronic chips that animate calcu- lators, fuel-injection controls, cardiac pacemakers, and telephone-an- swering machines, to the geographically distributed networks of thousands of computers. Just as buildings are constructed from a variety of materials, so also do computing systems incorporate many different manufacturing processes and technologies, from microelec- tronic chips, circuit boards, and magnetic disks to the software that tailors the machine to an application or for general programming use. Standardization yields economies both in buildings and in com- puters; for example, pre-cut 8-foot studs and pre-made windows are commonly used in residential houses, whereas 8-bit bytes, commodi- ty processor and memory chips, and standardized programming no- tations and system conventions may be used in many different mod- els of computing systems. For both computing systems and buildings, the conceptual dis- tance from the available materials and technologies to the require- ments established by society and the marketplace is so great that a diversity of designs might satisfy a given requirement, and the task of producing any complete design is extremely complex. How, start- ing with a "blank slate" of silicon and access to computer-aided- design and programming tools, does someone create a system to play chess, to process radio-telescope signals into images, or to handle financial transactions in a bank? The complexity is managed by ap- plying the abstraction principles described above in "Abstractions in Computer Systems." The foundation of nearly all computing systems today is micro- electronics. Even within the design of a microelectronic chip, the task is organized around such specialties as circuit design, logic de- sign, system organization, testing, and verification, and each of these specialties must deal with physical design and layout together with logical behavior. Design techniques similar to those employed for chips are applied at higher levels to assemble aggregates of chips on circuit boards, and to provide interfaces to disks, displays, communi- cation networks, and other electronic or electromechanical systems. Microelectronics technology has blurred the boundary between hardware and software. Programs written in specialized notations are commonly built into chips. Systems designed for a single pur
176 COMPUTING THE FUTURE pose may, for example, incorporate application software that is com- piled into such circuit structures as programmed logic arrays or into microprograms that reside in read-only memories. Computing sys- tems also employ built-in programs to provide for maintenance, ini- tialization, and start-up. Ger~eral-purpose computing systems require additional layers of software to provide the standardized system services needed to exe- cute a variety of applications. The operating system allocates re- sources to run multiple programs, handles input and output devices, maintains the file system, and supports interprocess and network communications. Application programs may also require packages that provide standard interfaces for windows, graphics, databases, or computation, whether local or remote. The remarkable advances in the performance, performance-cost ratio, and programmability of computing systems have been the combined result of achievements of CS&E within each of these layers. Although these advances have built on improvements in the base technologies, computing scientists and engineers have exploited these improve- ments extremely rapidly. The following subsections describe achieve- ments within these layers: microelectronics; the organization of pro- cessors, memories, and communication; operating systems; computer networks; and database systems. rid ~ __ Microelectronics The history of microelectronics is one of increasing the density of circuitry on a chip; the smaller the transistors and wires within a chip, the faster they can work, and the less energy they require. The process by which a microelectronic chip is fabricated is independent of the particular circuitry that will ultimately reside on the chip. The chip designer creates information-processing, memory, and-commu- nication structures within the chip by defining geometric patterns on a set of 10 to 15 photomasks; these patterns define the transistors and wires that will be embedded in the chip. Some of these wires lead to connections external to the chip that allow it to be hooked up to other chips and components. In the 1960s, early integrated circuits (i.e., small-scale- and n:~edi- um-scale-integration (SSI and MSI) chips) implemented electronic gates, adders, selectors, decoders, register memories, and other modules that had previously required circuit boards of discrete transistors and other electronic components. Photomasks for SSI and MSI chips were simple enough that they could be cut by hand from large sheets of plastic film before being photographically reduced.
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 177 The large-scale-integration (LSI) chips of the 1970s contained thou- sands to tens of thousands of components and included the dynamic random-access memory (DRAM) chips that eventually displaced the magnetic-core memory, and the first single-chip processors. These LSI chips were too complex for their photomasks to be created with- out computer-aided-design (CAD) tools. However, the CAD tools of that era served principally as drawing aids, a computerized exten- sion of the drafting board. They did not otherwise assist designers in managing the complexity of their creations. By the late 1970s, it was widely recognized that continued ad- vances in microelectronics depended at least as much on streamlin- ing the design processes and on new system ideas as on improving the fabrication processes. The time required to design then-sophisti- cated chips had already grown from weeks to years. Few people were prepared to address the functions (other than memory) that more complex chips would serve. One of the great achievements of CS&E was to show how to design the now-current generation of very-large-scale-integration (VLSI) chips. Many advances in chip design resulted from the application of lessons learned from managing the complexity of large programs. Structured design disciplines based on a layout-cell hierarchy en- couraged designers to compose layouts flexibly and systematically, to focus on improvements at the high levels of algorithms and over- all organization, and to abstain from certain low-level optimizations (analogous to "goto" statements in programming) that are known to be more troublesome than useful. These structured design approaches achieved significant success- es even when applied using only computer-aided layout tools; these achievements might be compared with writing structured programs in assembly language. The next step was to incorporate these disci- plines into high-level tools called silicon compilers. A silicon com- piler includes a "front end" that translates a behavioral description for a chip into an intermediate structural representation, and a "back end" that translates the intermediate representation into layout that is tailored to the geometrical and electrical design rules of a particu- lar fabrication process. Designs produced in this way can according- ly be re-created easily for different fabrication processes. Today, many chips are designed entirely by silicon compilation; nearly all complex chips employ these procedural approaches for creating lay- outs of some of their major cells. Of course, chip designs may contain errors. To reduce the cost and effort required to debug chip designs, tools for simulation and verification are essential to the chip designer. The development of
178 COMPUTING THE FUTURE algorithms and programs for multilevel simulation, including where necessary simulation down to the transistor-switch level, is the prin- cipal reason that today's million-transistor chips more often than not function correctly the first time they are fabricated. Symbolic verifi- cation that a chips behavior will conform to its specification is not yet universal, but these techniques have been employed, for example, to demonstrate that a floating-point element within a chip will be- have identically to software routines previously used for the same functions, and to verify the logical design of processors of moderate complexity. The net result of these advances in design disciplines and tools is that today's state-of-the-art chips, although they approach being 100 times as complex as those of a decade ago, require a comparable design effort. Whereas a decade ago VLSI-design courses were of- fered in only a few universities, today they are offered in approxi- mately 200 colleges and universities and have supplied the increas- ing demand for chip designers. Students in these courses use modern design and simulation tools to produce projects in a single term that are substantially more complex than state-of-the-art chips of a de- cade ago. Processor and Memory Design In recent years, it has become clear on theoretical grounds that for computations performed in NILSI chips and other high-perfor- mance digital technologies that press against the physical limits of intrachip communication, it is less costly to perform many operations at once (in parallel or concurrently) than it is to perform an operation correspondingly faster; see Box 6.4. For example, performing a given operation 10 times faster on a chip of a given family of designs would require a chip 100 times larger. However, by replicating the original chip only 10 times and connecting the chips in parallel, the same speedup factor of 10 could be obtained.7 Much of high-speed com- puter architecture (both on the market now and to be available in the future) can be understood today as an endeavor to increase perfor- mance with parallelism and concurrency, which results in only a pro- portional increase in area, and to avoid brute-force attacks on serial speed, which leads into a realm of diminishing returns in perfor- mance for chip area. Based on this complexity model and theory, algorithms that ap- proach making optimal use of limited communication resources have been devised for such common operations as arithmetic, sorting, Fourier transforms, matrix computations, and digital signal processing. Analyses
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 179 of such algorithms account for the patterns of data movement, often in regular topologies such as hypercubes, meshes, and trees. These algorithms have been applied both to the internal design of VLSI chips and to the design of special-purpose systems such as digital signal processors, and to the programming of parallel and concurrent computers. The analyses of communication topologies hare, in addi- tion, been important to the design of the communication networks used in programmable parallel and concurrent computers. VLSI technologies led to a renaissance in many computer archi- tectures during the 1980s. An example is the emergence of reduced- instruction-set computers (RISCs), which provide a good illustration of why single-chip processor performance has advanced more rapid- ly than might have been expected simply from technology gains. As we have seen, VLSI technology favors concurrency. RISCs exploit concurrency by employing a pipeline structure that can overlap the execution of several instructions. Dependencies between sequential instructions can defeat this approach, but RISCs employ compilers to analyze dependencies and to generate object code (i.e., machine in- structions) to schedule the pipeline in advance.
180 COMPUTING THE FUTURE High-speed processors also place severe demands on the memory system. Again, the solutions include parallelism and concurrency: wider data paths to convey more bits in parallel, separate memories for instructions and data, and multiple banks of memories. These innovations were first applied to the supercomputers of the 1960s, and they are applicable to single-chip design issues as well. Fast memories require more area per bit than do slow memories; it is accordingly not economical to implement the primary memory of a computing system entirely from fast memories. A more sensible or- ganization employs a small, fast memory called a cache to store fre- quently accessed items. If the processor makes reference mostly to items that are stored in the cache, memory operations can be speeded up considerably. Of course, the cache memory must have a way of determining what items will be most frequently accessed. Analysis of cache sizes, organizations, and replacement strategies has been an active and productive area of research and development. Just as advances in processor design have depended on compiler technolo- gy, so also is cache design starting to benefit from compiler analysis and optimization of the patterns of memory accesses. ~1 ~1 . Operating Systems One of the important, practical ideas that led to modern operating systems was timesharing, invented in the early 1960s. Operating systems are part of the system software that provides frequently needed functions to the user. The earliest operating systems limited the computer to running one user program at a time: these systems could not start the next program until the preceding one had terminated. A time- sharing operating system interleaves execution over short intervals between several executable programs available in the machine. This interleaving is equivalent to executing a number of programs concur- rently on a number of somewhat slower machines. Before the inven- tion of timesharing, interactive tasks required a computer dedicated to that task, whereas with timesharing, a large number of users can tap into a single machine that provides bursts of computation on demand. The introduction of hardware address-translation, memory-pro- tection, and system-call mechanisms under the control of a multipro- gramming operating system made timesharing a good way to in- crease the efficiency of a machine's use by allowing multiple processes to reside in memory at the same time, and provided processes with virtual memory. A "process" is an instance of a program during its execution, including both the program's instructions and data. Pro- cesses are the basic schedulable units of activity or execution for
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 181 Execution of a user program, updating a graphics window, transferring data from or to an open file, and controlling the operation of an input-output device can be regarded as processes that execute concurrently. "Virtual memory" refers to the ability of a process to refer to a larger range of memory addresses than may be present in primary memory at any one time. In addition to their demand for execution cycles, processes re- quire memory resources. The physical memory of a computer is limited and contains layers of increasing size and access time: Ma- chine registers are few but very fast, primary memory is intermedi- ate, and disks store large volumes of data but with large access times. The greatest disparity in access time, hence, the most critical choice for memory allocation, occurs between the disks and the primary memory. Should programs explicitly manage the memory actually available by bringing data and subroutines from disk on demand, or can the operating system perform these functions? Theory and prac- tice have shown that programs do not need to be complicated with the extra task of memory management; indeed, operating systems that manage memory for many processes at once can do a better job overall than is possible when applications programs handle memory management individually. Paging is one technique operating systems use to provide virtual memory. In common with other caching strategies, paging is based on the likelihood that the instruction and data words accessed are the same as or located close to previously accessed words. A paging strategy partitions memory into frames of, for example, four kilo- bytes each. A frame can hold a page of information that can be moved between disk and primary memory. Put simply, the operat- ing system's goal is to make it likely that the pages involved in active computations are available in the primary memory, and that inactive pages remain on disk. Accessing a page that is not in the primary memory is called a page fault. The operating system must then inter- vene to move the needed page from disk to primary memory. What happens when the primary memory is full with active pages, and another page must be loaded? One algorithm is to replace the least recently used (LRU) page, or any page not used recently. The operating system decides on the replacement based only on its record of the page-access behavior of the processes whose pages it manages, and not on information about their internal structure. The LRU algo- rithm generally performs well in err environment of unrelated con- current processes for the same reason that paging works: programs tend to access memory locations that are local to recently accessed locations, a characteristic referred to as locality of reference. nearly everything an operating system does.
\ 182 COMPUTING THE FUTURE Processes may need to communicate with each other. That need existed 30 years ago when time-sharing was applied to single ma- chines but has become increasingly necessary now that processes that are parts of the same computation are commonly distributed across networks of computers. Applications that employ communicating concurrent processes may require certain actions to be performed by no more than one process at a time, or to be done in a particular order. Suppose, for example, that processes X and Y share the use of a file that contains a record of your bank balance, and that both processes attempt to record deposits. Processes X and Y can each have read the initial balance, added their own deposit, and written the new balance back into the file. If the processes are interleaved so that the two read operations precede the two write operations, one of the deposits will be lost when one process overwrites the result of the other. What is neces- sary to prevent this error is to lock the file against other accesses when the first process requests the balance, and to unlock the file after its deposit transaction is completed. Problems with the order of execution may arise in situations where one process cannot proceed because another process has not acted. For instance, if process X reserves airline seats and process Y records cancellations, X must wait for Y whenever all seats for a flight are booked. Computer scientists and engineers invented synchronization mech- anisms to deal with these problems long before they became common in practice. The first such mechanism employed operations that are analogous to the way semaphores protect railroad sections against conflicting train traffic. A critical section of program that must not be executed by more than one process can be entered only when the semaphore is green, and entering has the side-effect of turning the semaphore red. The semaphore is set back to green when the process that entered has completed the execution of the critical code. When the semaphore has been set back to green, which of several waiting processes will be allowed to enter the critical section? A priority queue that records the processes waiting for the critical sec- tion can ensure fairness, so that all waiting processes will eventually be served. Once these properties of logical correctness and fairness are assured, what is the performance of these solutions? Queuing models have been devised that lead to solutions that are optimal de- pending on the particular characteristics of the concurrent processes. A nasty problem not solved by synchronization mechanisms is deadlock. A deadlock arises due to mutual dependencies between processes, such as process X using resource A and requesting the use
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 183 of additional resource B without giving up A, and process Y using resource B and requesting the use of A without giving up B. When these processes fail to make progress, all services dependent on them cease to function, eventually halting the entire system. (This is one reason that the distributed systems used by banks and airlines some- times cease to function.) Proving that a system of concurrent pro- cesses will operate correctly and will not deadlock is generally harder than proving the correctness of a single sequential program. Reason- ing about concurrent processes has been aided by temporal logic, a first-order predicate logic with the addition of temporal notions such as "forever" and"eventually." In common with other system-building disciplines, the design of operating systems illustrates how progress has benefitted from theo- retical work, has been stimulated by practical ideas, and has been responsive to changes in technologies and needs. Data Communications and Networking Computer technology is becoming increasingly decentralized; the personal computers on office desks are an example of this trend. Similarly, centralized corporate control is passing down the hierar- chy, and in many cases the hierarchy itself is flattening. To provide connectivity among these distributed parts, computer networks have proliferated at an amazing speed in business, government, and aca- demia. In fact, perhaps the only remaining aspect of information technology that remains in the hands of central management is the network itself. The first successful large-scale computer network was the experi- mental ARPANET, first deployed in 1969 to provide terminal-to-computer and computer-to-computer connectivity to major CS&E departments in the nation. ARPANET was based on packet-switching technology (Box 6.5~. The network itself consisted of many switches, each con- nected to at least one and usually several others so that there were multiple paths between any two. The communication lines connect- ing the switches were not used exclusively for any particular end-to- end communication. Rather, each line was used by a particular mes- sage only when one of its packets happened to be transmitted over that line. Packet switching provided high-speed, cost-effective connectivity between attached devices across long distances by dynamically shar- ing the expensive bandwidth of high-speed lines among many users. A major benefit of packet switching is fault tolerance when a node or line fails, other nodes can simply bypass it.
184 COMPUTING THE FUTURE ARPANET had substantial impact on architectures for commer- cial networks such as SNA and DECnet. It also spurred a great deal of research on data communications and resulted in the TCP/IP net- work protocol, now widely used to connect heterogeneous computer networks. While nationwide packet networks such as the ARPANET met the needs of the 1970s, a new requirement arose from the prolifera- tion of personal computers in the 1980s. Personal computers pre- sented a rapidly rising demand for connectivity among themselves, peripherals, and servers in a local office environment. The CS&E research community anticipated this need in the 1970s and pioneered the hardware and software technologies for local area networks (LANs). Current LAN technologies grew out of small research investments at Xerox (Ethernet) and Cambridge (token ring). The growth of LANs paralleled that of personal computers in the 1980s. LANs provided
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 185 relatively inexpensive connectivity in an office environment, and did so at multi-megabit-per-second speeds. Today, LANs are being interconnected to form larger networks. Meanwhile, the bandwidths of wide area networks (WAN s) have evolved from 64 kilobits per second to the widespread availability of econom- ically tariffed T1 service at 1.5 megabits per second (mbps). Thus WAN speeds are approaching the speeds of many LANs deployed today, though LANs are getting much faster, too. Recent needs for faster metropolitan area network (MAN) speeds have been met with the acceptance of the Fiber Distributed Data Interface (FDDI) stan- dard for MANs. This is a 100-mbps offering based on fiber-optic media. LANs, MANs, and WANs were initially designed to meet data communications problems based on copper technology. The emer- gence of fiber-optic technology and its consequent 1000-fold increase in bandwidth completely changes the technology trade-offs and re- quires reconceptualization of network designs. This subject is the focus of effort currently under way in the National Research and Education Network component of the High Performance Computing and Communications Program, discussed in Chapter 1. Database Systems Modern database technology has been shaped from top to bottom by CS&E research. Computer science researchers in the 1960s created the relational data model to represent data in a simple way. Computer engineers worked through the 1970s on techniques to implement this model. By the mid-1980s these ideas were understood well enough to be standardized by the International Organization for Standardization (ISO) as the SQL language. Today, the SQL language has become the lingua franca of the database business, for reasons described below. Computerized databases began in the late 1950s, each built as a special application. By the late 1960s, the network data model had emerged as a generalization of the way these systems stored and accessed data. The network model is a low-level approach that rep- resents and manipulates data one record at a time. However, despite its undeniable utility at the time, the network data model was troubling, because it lacked a firm mathematical foun- dation. Indeed, database systems at the time were ad hoc and seemed to behave in random ways, especially in unusual cases. Database researchers needed a good theory with which to predict the behavior of databases and a data manipulation language with clear properties, reasoning that these tools would make it easier to program database
186 COMPUTING THE FUTURE applications that could be insulated from changes to the database as the database evolved over the decades. The relational data model grew out of this research effort. It is a high-level, set-oriented, automatic approach to representing data. The data are structured in tabular form, making them easier to visualize and display. Database queries and manipulations are based on pure mathematics (sets and relations) and the operators on them. As a result, the model is simpler to use, and gives applications greater independence from changes in technology and changes in the data- base schema. Early studies showed it to improve programmer pro- ductivity by large factors. The relational model was initially rejected by database imple- mentors and users because it was so inefficient. All agreed that it boosted productivity, but there was skepticism that the nonproce- dural language could ever be efficiently implemented. Research computer engineers in academia and industry took on the challenge of efficiently implementing the relational model. The goal was to provide the simplicity and nonprocedural access of the relational model and performance competitive with the best network database systems. This effort required the invention of many new concepts and algorithms. This research took about ten years. In the end, the relational system's performance began to meet and even exceed the perfor- mance of systems using the network data model. With this feasibili- ty demonstration, the slow transition from network to relational sys- tems began. First, computer vendors began offering database systems based on the research prototypes. Then the SQL international stan- dard was approved, and customers began to use the relational ap- proach. Today, 25 years after the first research papers appeared, the transition to SQL databases is in full swing. Without the early seed work by computer scientists, the relation- al model would not have been invented. Without the early seed work by computer engineers, the implementation feasibility would not have been demonstrated. And without these two advances, we would likely still be programming databases in low-level program- ming languages. Based on the relational model, the database community spent much of the 1980s investigating distributed and heterogeneous data- base systems. Those ideas are now well understood, and the ISO is about to approve a standard way for databases to interoperate the Remote Database Access standard. This standard promises to allow diverse computers to interchange information and to allow database queries and transactions to span multiple database systems; see Box 6.6 for more discussion.
IT ~ COMPUTER SCONCE ~D ENG6EER~G? ]67 1 1 1 1 11B O1X 1 14 1 1611111 1 1 11 1R1 E1L1I B161L 1E11 1 1 T I A 1~1S/< T111°11~11111 1 S Y ST1~) 11 Most current database research activity focuses on adding more semantics to the relational model and to the ~ansachon model This work, operating under the banner of object-oriented databases/ is stat in Us early stages. In addition/ consistent With the application-ore ented trend of computer science in general there is considershle in- terest in databases designed specifically for certain problems: geo- graphic databases, text databases/ image databases/ and scientific databases. Programming Languages/ Comp11er~ and Software Engineering brow [~as Advances in science often lead to the invention of notations to express new concepts or to Employ and unify old ones. The advent of computers spurred the invention of programming languages/ a
188 COMPUTING THE FUTURE new kind of notation for expressing algorithms in terms more appro- priate to human discourse, while nevertheless meeting the exacting mechanical needs of computers. The development of programming languages introduced new challenges. First, more formality and greater detail were required; because of processing by computer, nothing could be left for interpretation by humans. Second, new concepts
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 189 had to be developed to deal with execution of an algorithm; previ- ously, mathematics dealt primarily with a more static world. Third, a conflict between transparency of notation and efficiency of execu- tion was introduced; programs have to be reasonably efficient as well as perspicuous. Since the dawn of the computer age, many developments in the area of programming language design have emerged developments that are reflected in a succession of programming languages that make it easier to express algorithms precisely in various problem domains. Many are familiar with mainstream languages descended from For- tran via Algol and Cobol through countless variants such as Basic and Pascal. However, though the bulk of programming today is done in these languages, there are countless alternate styles, as noted in Box 6.7. Without the development of the concepts that have been embedded in these languages as well as the languages themselves, the information age would not be so advanced. Compilers Compilers provide the essential link between programming lan- guages (i.e., the readable, higher-level, problem-oriented text written by human beings) to the low-level machine encodings that actually govern the operation of a computer. Advancements in compiler tech- nology have been remarkable in the past few decades. For example, the first Fortran compiler took dozens of person-years to build with what were essentially ad hoc techniques. Today, the same effort is required to develop compilers that handle languages of much greater complexity and sophistication. This vast increase in productivity is due partly to better programming environments and more powerful computers, but most significantly to a sound theoretical understand- ing of compiler techniques that allow a high degree of automation for much of the compiler writing process. Several waves of theory have contributed to compiler technology: formal languages, semantic analysis, and code optimization and generation. Formal language theory provided the understanding of grammar upon which the mechanical parsing in every modern compiler is built, and that shaped the very form of programming languages. The theo- ry provides the mathematical basis for engineering the front ends of compilers, where the structure of a program is extracted from a pro- gram text. The subject of parsers is now so well understood that their construction has been highly automated. From a precise defini- tion of the syntax of a programming language a parser can be gener- ated in a very short time.
190 COMPUTING THE FUTURE Formal theories of semantic analysis gave accurate descriptions of the meaning of programming languages, which has led to more predictable languages and in some commercial instances to automat- ic generation of compilers from language specifications. In concert with type theory, formal semantics have enabled compiler writers to implement languages that support these advanced modes of expres- sion in a clean and rigorous manner. One result has been that poly- morphic programming systems-programming systems that can sup- port the design of algorithms that work independently of the type of input data- can now be transported from one computing environ- ment to another with a minimum of difficulty. Techniques for analyzing programs have been developed that en- able optimizing compilers to speed up the execution of programs substantially. An important approach is called data-flow analysis, a method for determining where values once computed in the program can possibly be used later in the program. This information is now routinely applied in optimizations such as register allocation, com- mon subexpression elimination, and strength reduction in loops. Regis- ter allocation attempts to keep the most frequently used quantities in the most accessible storage. Common subexpression elimination at- tempts to identify and obviate the need to recalculate equal quanti- ties at different points of a program. Strength reduction in loops amounts to identifying instances of repeated evaluation of polynomi- al expressions that can instead be updated by finite differences, thus simplifying the computation. More elaborate optimization is required to compile sequentially written programs to make effective use of parallel hardware architec- tures. Although good parallelizing Fortran compilers exist for par- ticular computers, this technology is still far from routine. Software Engineering Software engineering refers to the construction of software sys- tems. While there is some controversy in CS&E regarding the extent to which the "engineering" in software engineering is truly science- based engineering (as opposed to management), it is clear that large software systems (in excess of several million lines) can and have been built. Without many of the software engineering tools that have been developed in the last 30 years, the construction of large software systems would not be possible. These tools have been de- veloped in response to pragmatic needs, but they may well incorpo- rate some of the products of research. Two generic types of software engineering tools are described below. In addition, software reuse,
WHAT IS COMPUTER SCIENCE AND ENGINEERING ? 191 an issue of generic concern to software engineers, and real-time com- puting, a computing application of great engineering importance to society, are discussed. Project Control Systems The development of large-scale software sys- tems is particularly problematic. A large-scale software system may have millions of lines of code. Writing such a system is obviously a many-person enterprise, and the efforts of all of these programmers need to be coordinated efficiently. Project control systems enable the construction of large systems by automating coordination processes that would otherwise be subject to human error. For example, large systems are written in modular form, to facil- itate debugging. Modules must be relatively small (hundreds of lines of code), so that the programmer can understand the details of the module. Any given module may exist in several different versions, perhaps an early version that is known to work properly but imple- ments only basic functions and a later one in progress that is being enhanced. To assemble the large system (e.g., for system-level testing), it is necessary to gather together the working versions of each module, taking into account the fact that a change in module A may mean that an earlier version of module B must be included. Assembly can be performed manually, but with tens of thousands of modules to be gath- ered, it is inevitable that mistakes will be made. Automated configura- tion management systems keep track of a myriad of bookkeeping details, enabling such assembly to proceed with far fewer errors. Source Code Control Systems The source code of a software system is written by human programmers. When source code becomes volu- minous and involves a team effort of many programmers, manage- ment is often difficult. Source code control systems automate many management-related tasks. For example, such systems can ensure that only one person is making changes to any given module at any time, and that all changes are recorded (usually through an automat- ed comparison of the new file to the old version) so that there is a trail of implementation responsibility comparable to the change his- tory found on engineering drawings. "Discovery tools" are an important adjunct to source code con- trol. These tools provide for navigation within a large library of software so that developers and maintainers can efficiently answer questions such as, What modules touch this variable? What does that subroutine do? What is the data layout of that table? Do two selected actions always happen in order? By what routes through the program can control get to this point? Such tools help program- mers understand better the code on which they work.
192 COMPUTING THE FUTURE As an aside, it is interesting to note that the algorithm used to compare files in the source code control system of Unix came from research; the same is true for the flow analysis tools used in many discovery tools. Software Reuse An elusive grail of CS&E has been the reuse of soft- ware parts. Just as one constructs electrical appliances or houses largely from off-the-shelf parts, so would one also like to build soft- ware in a similar fashion. Because software is the dominant cost of most systems, developing ways to reuse software is a growing con- cern and is being tackled in a variety of ways. In some domains, useful libraries of software components have long existed. Particularly well known are the libraries that provide efficient implementations of common mathematical constructs, such as trigonometric functions or matrix operations. Major packages of routines for statistics and other fields of mathematics and engineer- ing are also available. Programming tools, as exemplified by Unix, foster the construction of systems out of many small and indepen- dent generic components coupled by a "shell" language. By generalizing from specific instances, the domain of applicabil- ity of code may be widened. For example, the notions of polymor- phism and modularity found in Ada and ML (and other languages) make it possible to write portions of programs that are applicable to more kinds of data, thus reducing the need to write highly similar portions of code that differ primarily with respect to the kind of data being processed. Object-oriented programming provides a different way to struc- ture programs to increase abstraction and reduce the need for rewrit- ing. In object-oriented programming, the basic procedures that oper- ate on an object are encapsulated with that object. For example, an object called POLYGON can have associated with it not only a de- scription of its sides but also a procedure for calculating its area. A second important feature of object-oriented programming is that an object can "inherit" procedures of a higher-level object but can also replace some of them with new procedures. For example, having already defined a POLYGON, one can then define a SQUARE as a special instance of POLYGON but with a more efficient procedure for calculating its area. A program that manipulates polygons or squares would not include code to calculate area, since the object itself would provide that code. Object-oriented programming pro- vides a new flexibility in structuring programs, leading to easier de- velopment and maintenance of large programs and programming systems. Despite such developments, reuse of software is not common, and much more remains to be done in this area.
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 193 Real-Time Computing Real-time computing refers to a mode of com- puting in which computing tasks must be accomplished within cer- tain time limits. For example, computers controlling the operation of an airplane's engines and flaps are computing in real time; failure to meet the relevant computing deadlines could easily lead to disaster. When a processor for a real-time computer system must handle several tasks simultaneously, how much time to give to each task and in what order they should be performed are crucial consider- ations for the real-time programmer: sometimes a lower-priority task must be preempted by a higher-priority one, even though both must be completed on time (because the higher-priority task may depend on a result computed by the lower-priority one). Such decisions are simple to make when the number of tasks is small and the amount of available computational power is large relative to the demands of the tasks taken in the aggregate. But as a matter of engineering practi- cality, the designer of an airplane or a missile does not have unlimit- ed freedom to choose processors that are greatly overmatched to the computing tasks involved. The traditional method of scheduling concurrent tasks is to lay out an execution time line manually.8 Although for simple cases it is relatively easy to determine task execution sequences, the resulting program structure is hard to change. For example, the specification of a task may be altered so that it demands more computational resources; accommodating such a change might well require redoing the entire time line. The scheduling must accommodate the differing deadlines, demands on resources, and priorities of the various tasks to ensure that all tasks are completed on time. However, by taking advantage of certain features of a relatively new programming language, Ada, it is possible, under certain cir- cumstances, to implement conveniently an algorithm ensuring that all tasks will be completed on time without knowing the precise de- tails of the execution sequence. This algorithm-the rate monotonic scheduling algorithm also enables the convenient accommodation of changes in task specification without re-doing the entire time line, and is starting to come into use in some real-time aerospace applica- tions. Algorithms and Computational Complexity As noted above in the section '~Computer Science and Engineer- ing," algorithms as an intellectual theme pervade all of CS&E. How- esrer, the formal study of algorithms is an important subarea of CS&E research in its own right (but see Box 6.8~. The design and analysis
194 COMPUTING THE FUTURE ..... .. .. .... ..... . . .... ... .. .. . .. .......... ..... .... ........ .. . . . . . ~.o,\.,6.,.,.,. ~, ~.~. ~.~. ~ ~ ~ ~ ~ ~ ~ ~ = ~1~117~11~ ~1114 15~} S~1111~_~1~: . ~ . tnertais of dat ba chanlcal theove lKll ;~' of algorithms combine intellectual and theoretical challenges with the satisfaction of computational experimentation and practical re- sults.9 Algorithms Everywhere One domain in which better algorithms are enormously impor- tant is science and engineering research. Chapter 1 noted that the solution of certain partial differential equations has been speeded up by a factor of about fell since 1945. A large part of this speedup is due to the development of faster algorithms, as outlined in Table 6.1.
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 195 TABLE 6.1 Algorithmic Improvements in Solving Elliptical Partial Differential Equations in Three Dimensions Method Year Run Timea Timeb Successive over-relaxation (suboptimal) 1954 8 N5 250 years Successive over-relaxation (optimal) 1960 8 N4 log2 N 2.5 years Cyclic reduction 1970 8 N3 loge N 22 hours Multigrid 1978 60 N3 17 hours aN is the number of grid points in one linear dimension. bTime required for solving an equation with N = 1000, assuming a time of 10-6 seconds for processing each of the 10003 points. SOURCE: Adapted from John Rice, Numerical Methods, Software, and Analysis, McGraw- Hill, 1983, p. 343. Box 6.9 describes an algorithmic advance that made feasible a com- putationally complex calculation for a member of the committee. In many problems faced by industry and commerce, other types of algorithms are often relevant, including linear programming (LP) algorithms and algorithms to solve the traveling salesman problem. An LP problem is one that requires the maximization or minimi- zation of some output subject to a set of constraints on the inputs. For example, a manufacturing firm makes two different products, widgets and gizmos. The sale of each product results in a different profit; the manufacture of each product requires a different combina- tion of engineering, inspection, and packaging attention as it moves through the shop. The total amount of attention that can be given every day is fixed by union regulation. What is the optimal combina- tion of widgets and gizmos for the firm to manufacture so that it can maximize its profits? Problems of this general form arise in all walks of life. Airlines use highly sophisticated LP algorithms to schedule equipment and flight crews.~° Equipment scheduling seeks to optimize the use of available aircraft and maintenance facilities by assigning aircraft to each route to meet the requirements of inspection and maintenance at the right ground facilities, with the needed personnel, and with the fewest delays. Crew scheduling seeks to optimize the use of personnel and layover facilities by matching the available crew qual- ifications and home bases with equipment demands, while respect- ing government and other work rules, such as those governing time between flights and travel time between assignments. Airline sched- uling problems may involve millions of variables. Until recently, the solutions could only be guessed at.
196 COMPUTING THE FUTURE ...... ~ . ~ . ~ ... ~ ~ .~ ~ .~ .... . .. . ~ . .. The chemical industry also uses sophisticated LP algorithms to compute, for example, the least expensive mix for blending various distillates of crude oil to make the desired products. Another scheduling problem that arises in many practical appli- cations is best understood in terms of the traveling salesman problem (TSP): given a set of cities and the distances between them, find the shortest tour for a salesman to visit all cites. The TSP arises in planning deliveries and service calls. Less ob- viously, it appears in many different contexts in science, engineering, and manufacturing. For example, in crystallography with high-ener- gy and high-density x rays, the irradiation time is small compared to the time needed for the motors to change the orientation of the sam- ple and/or the detector's position. For an experiment with some 14,000 readings, minimizing the repositioning time can cut the dura- tion of a week-long experiment by 30 percent to 50 percent. In man- ufacturing electronic components, the drilling of holes in circuit boards
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 197 with an expensive laser drill puts a premium on minimizing the total "travel time" of the drill head (or board) between successive holes. For a complex circuit board, the shortest total route among as many as 17,000 holes may be required. may call for solving an analogous problem with over a million sites. Faster algorithms can reduce significantly the time required to perform tasks on the computer, thus making industry more efficient, and can also increase dramatically the sizes of the problems that can be feasibly solved. An appropriate selection of algorithms can also have a profound effect on the conduct of science, again by reducing the time needed to solve certain problems from utterly unfeasible times to quite feasible times. The fabrication of a NILSI circuit The Study of Algorithms In the 1930s, before the advent of electronic computers, Church, Kleene, and Turing laid the foundations for the theory of computa- tion and algorithms. Their work showed that there was essentially only one basic concept of effective computability-aside from mat- ters of speed and capacity, a problem solvable on one computer is solvable on all. Particularly relevant to the study of algorithms is the Turing ma- chine, an abstract computational device that Turing used to investi- gate computability. The Turing machine is also a vehicle through which it can be shown that all computational problems have an in- trinsic difficulty that theoretical computer scientists call complexi- ty-an inescapable minimum degree of growth of solution time with problem size. The solution time for a problem with high complex- ity grows very rapidly with problem size, whereas the solution time for a problem with low complexity grows slowly with problem size. Switching to a faster computer may improve the computation time by a constant factor, but it cannot reduce the rate of increase of com- putation time with the growth of the problem size. Suppose we could prove that finding the optimal tour for TSPs with n cities requires on the order of 2n steps in the worst case. Then no computer could overcome the prohibitive exponential growth rate for the solution of the TSP. A factor-of-100 speedup over a machine that could barely solve 100-city problems would not increase the capacity enough to solve 110-city problems. (This would be true whether the faster computer were a parallel computer with 100 pro- cessors or a serial computer that operated 100 times as fast.) A particular algorithm that solves a given problem may result in solution times that grow with problem size at a faster rate than one
198 COMPUTING THE FUTURE would expect from the intrinsic complexity of the problem. Design- ing algorithms that run in times that are close to those implied by the intrinsic complexity of a problem becomes an important task, be- cause the need to solve ever larger practical problems grows much faster than our ability to buy larger or faster computers. Computational Complexity The study of the complexity of computations, referred to as com- putational complexity theory, has revealed remarkably rich connec- tions between problems. Good examples of complexity theory arise in the context of linear programming and traveling salesman sched- uling problems. If the solution time for a problem grows exponentially with prob- lem size, then there is no hope of solving large instances of the prob- lem, and it becomes necessary to look for approximate solutions or study more tractable subclasses of this problem. The question of minimal growth, or "lower bounds," requires a deep understanding of the problem, since all possible ways of computing a problem must be considered to determine the fastest one. 1 a ~ The study of LP algorithms provides an interesting illustration of how theory and practice interact. For many years, the simplex algo- rithm was the main way to solve LP problems. In 1972, it was shown that its worst-case running time grew exponentially with the size of the problem, although the algorithm worked well on practical problems. In 1979 came the startling announcement of a new polynomial- time algorithm. Although this algorithm did not compete well with the highly developed simplex algorithms, the proof that polynomial time was possible galvanized the research community to activity. The new research yielded "interior-point" algorithms that today compete successfully with the simplex algorithm. A major airline now uses an interior-point algorithm for scheduling equipment and crews. Although LP problems can be solved in polynomial time, it is widely believed that there is no polynomial-time algorithm for the TSP. However, in spite of at least 20 years of hard effort, there is no proof of the conjecture that the problems in the class denoted by NP are not computable in polynomial time. The class of NP problems, which contains many important combinatorial problems, is widely believed to be not computable in polynomial time. The TSP and hundreds of other problems are known to be "NP-complete," which means that a polynomial-time algorithm for any one of them will guarantee a polynomial-time algorithm for all. For example, from a polynomial-time algorithm for determining whether a set of jigsaw
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 199 pieces will tile a rectangle, it is possible to derive a polynomial-time algorithm for the TSP, and vice versa. The question of determining whether NP-complete problems have polynomial-time algorithms, the "P = NP" question, is one of the most notorious and important prob- lems in computer science. At present, there is no hope of solving exactly 10,000- to 1 mil- lion-city problems, which do arise in practical applications. There- fore researchers seek efficient algorithms that find good approxima- tions to the optimal tour. The study of approximate methods is an interesting blend of theory and experiment to assess the performance of various approaches and to gain insight toward better algorithms. For some approximate algorithms, there exist theoretical guarantees of running time and accuracy. Trade-offs between time and accuracy have also been demonstrated. Good solutions have been obtained for practical problems with 10,000 to 1 million cities. Besides its practical relevance, computational complexity provides beautiful examples of how the computing paradigm has permitted computer scientists to give precise formulations to relevant problems that previously could be discussed only in vague, nonscientific terms. Consider, for example, a problem about the basic nature of math- ematics. All our experience suggests that the creative act of finding a proof of a theorem is much harder than just checking a proof for correctness. However, until recently this problem could not be for- mulated in precise quantitative terms. Complexity theory allowed this problem to be made precise: how much harder is it computation- ally (for an algorithm) to find a proof of a theorem than to check its validity? The correctness of a properly formalized proof can be checked in polynomial time in the length of the proof. However, finding a proof of a given length can be done by "nondeterministically" guess- ing a proof and then checking in polynomial time whether it is a correct proof. Thus the finding of proofs of a given length is an NP problem. Furthermore, it is not hard to show that it is NP-complete. Hence a startling conclusion emerges: finding proofs of length n is polynomially equivalent to solving e-city TSPs! Either both can be done in polynomial time (which is strongly doubted) or neither can. Complexity theory seeks to understand the scope and limitations of computing. In doing so, it addresses questions about the basic nature of mathematics and the power of deductive reasoning. Artificial Intelligence Artificial intelligence (AI) is founded on the premise that most mental activity can be explained in terms of computation. AI's scien
200 COMPUTING THE FUTURE tific goal is to understand the principles and mechanisms that ac- count for intelligent action (whether or not performed by a human being), and its engineering goal is to design artifacts based on these principles and mechanisms. The premise of AI has a long tradition in Western philosophy. Aristotle and Plato believed that thought, like any other physical phenomenon, could be unraveled using scientific observation and logical inference. Leibniz equated thought with calculation, setting the stage for Boole's treatise on propositional logic, titled "The Laws of Thought." Much later, the advent of computers led Alan Turing to envision a new field, computing machinery and intelligence. The formal discipline of AI was inaugurated in 1956 at a Dartmouth con- ference by John McCarthy, Marvin Minsky, Allen Newell, and Her- bert Simon. As an empirical science, AI follows the classical hv~othesis-and- test research paradigm. The computer is the laboratory where AI experiments are conducted. Design, construction' testing, and mea- surement of computer programs are the major elements of the pro- cess by which AI researchers validate models and mechanisms of intelligent action. The original research paradigm in AI involved the following steps: · Identify a significant problem that everyone would agree re- quires "intelligence." · Identify the information needed to produce a solution (concep- tualization). · Determine an appropriate computer representation for this in- formation (knowledge representation). · Develop an algorithm that manipulates the representation to solve the problem (em. heuristic search automated reasoning). · Write a program that implements the algorithm and experi- ment with it. 1 ~V ' A few subareas of AI are examined below from two points of view: their impact on society (including their economic impact) and their influence on scientific thought. Impact on Society The impact of AI on society can be measured using two criteria. Do the products that result from AI help society at large? How much of an industry has been created as a consequence of AI? The use of AI technologies in industry has led to significant economic gains in tasks involving analysis (e.g., machine diagnosis), synthesis (e.g., de
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 201 sigrr and configuration), plannirlg, simulation, and scheduling. AI technologies are also helping chemists and biologists study complex phenomena, for example, in searching enormous databases, creating new molecular structures, and decoding DNA sequences. Stockbro- kers use software assistants in analysis, diagnosis, and planning at the expert level. Medical doctors can examine more hypothetical cases, thus including not-so-obvious symptoms in their diagnoses. The best-known economic impact comes from the widespread use of expert-system technologies. (Table 6.2 lists some expert systems that have been or are being used in industry.) But AI offers more to business than just applications of expert systems. Speech-generatior~ products have been in use for 15 years, arid speech-analysis products are beginning to reach the market. Im- age-processing programs are in daily use in the government, health care organizations, manufacturing, banking, and insurance. It is hard to measure the economic impact of image processing, because such systems often provide better performance rather than savings, but image processing is a billion-dollar-per-year industry. Vision and robotics are affecting manufacturing. Planning and scheduling sys- tems are used routinely in industrial and military settings. The im- pact of AI in manufacturing manifests itself at least in two ways: in: the automation of assembly, quality control, arid scheduling opera- tions and in the use of AI techniques in engineering design. TABLE 6.2 Examples of Expert Systems in Use Company Expert System Purpose Schlumb erger Dip meter Advisor Kodak Hewlett-Packard Xerox Injection Molding Advisor Trouble Shooting Advisor PRIDE Interpret data from oil wells for oil prospecting Diagnose faults and suggest repairs for plastic molding mechanisms Diagnose faults in semiconductor manufacturing Design paper-handling systems Hazeltine OPGEN Plan assembly instructions for PC boards SOURCE: Data from Raj Reddy, "Foundations and Grand Challenges of Artificial Intelligence," AI Magazine, Volume 9(4), Winter 1988, pp. 9-21.
202 COMPUTING THE FUTURE Impact on Scientific Thought Perhaps the most important impact of AI on scientific thought is the realization that computable information can be symbolic as well as numeric. The beginning of AI was marked by the introduction of the programming languages IPL and Lisp, whose purpose was the ma- nipulation of symbolic information. Symbolic manipulation became a fertile ground for problems of searching, organizing, and updating databases efficiently and for reasoning from information. Theoretical and practical results in searching, reasoning, and learning algorithms are now part of the core of CS&E. Furthermore AI has had such a deep impact on psychology, linguistics, and philosophy that a new discipline- cognitive science has emerged. AI has contributed to other branches of CS&E as well. Many concepts in programming languages and environments arose directly from attempts by AI re- searchers to build AI software. AI languages like Lisp, Prolog, and Scheme are used in many parts of CS&E. The nature of AI forces experimentation more so than in some other branches of CS&E, and the challenges brought forth by the need to experiment have led to the development of important concepts. AI has also dealt with areas of perception and interaction of artificial agents with the physical world. The challenge of how to deal with multimodal information in a consistent, predictable fashion has resulted in new efforts in ap- plied mathematics and control theory, called discrete-event dynamic systems, which combine dynamic systems and temporal logic. Such hybrid systems offer a suitable modeling tool for many difficult physical and economic models. The following subsections look more closely at three subareas of AI: heuristic search, reasoning and knowledge- based systems, and speech. Heuristic Search In the 1960s and early 1970s, the tasks that were identified as requiring intelligence were mostly of the puzzle-solving variety. They possessed simple specifications but lacked feasible al- gorithmic solutions. Tasks such as theorem proving and cryptarith- metic puzzles were studied at Carnegie Mellon University. At the Massachusetts Institute of Technology, the problems of understand- ing simple sentences in English in the world of children's blocks and solving freshman calculus problems were studied. Work at Stanford University focused on automatic speech recognition and the Advice Taker a system that would take advice specified in a logical lan- guage to solve simple problems in planning courses of action. Even though these problems sound deceptively simple in that humans ac- complish them routinely, calculating exact solutions for them can be infeasible. Instead, good-enough answers, which are close to but not
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 203 optimal, are accepted if they can be calculated within given time constraints. AI tries to find these good-enough answers using heu- ristic search. The problem is formulated as a search through the space of systematically generated possibilities, and methods are de- termined to reduce the search to likely candidates. For example, a checker-playing program would generate possible moves up to a certain play and would select the move using an eval- uation function like "choose a move that results in the largest piece gain." The evaluation functions are heuristic: they are rules of thumb that work most but not all of the time. This work in heuristic search borrows from operations research, statistics, and theoretical comput- er science. The phenomenal progress in computer chess affords a practical demonstration of the power of heuristic search. In 1967, Richard Greenblatt's program defeated a class-C player at a tourna- ment; today, the program Deep Thought has a grandmaster's rating. Advances in search strategies, combined with special-purpose hard- ware matched to these strategies, have been an important part of this success. Reasoning and Expert Systems Fascination with search strategies has led to investigations of reasoning as a process. Since reasoning re- quires knowledge, the issue of representing knowledge has become central to AI. In the early research on reasoning, it soon became apparent that general-purpose methods would not be capable of de- livering expert-level performance on problems that required domain- specific knowledge, and, because of this, early research dealt more with domain-specific problems. Such research has led to expert sys- tems (also known as knowledge-based systems) that are based on a simple idea: symbolic reasoning guided by heuristics over declara- tively specified knowledge of a domain can result in impressive problem- solving ability. The main research issues in the development of ex- pert systems are the extraction of knowledge about the domain and the criteria used for decision making. Speech Perceptual tasks, such as speech, are characterized by high data rates, the need for knowledge in interpretation, and the need for real-time processing. Error tolerance is an important issue. The usu- al methods for symbolic processing do not directly apply here. An important speech-understanding system developed in the 1970s at Carnegie Mellon University was the Harpy system, which is capable of understanding speaker-dependent continuous speech with a 1000- word vocabulary. The early 1980s witnessed a trend toward practi- cal systems with larger vocabularies but with computational and ac- curacy limitations that made it necessary to pause between words.
204 COMPUTING THE FUTURE The recent speaker-independent speech-recognition system, Sphinx, best illustrates the current state of the art. Sphinx is capable of rec- ognizing continuous speech without training the system for each speaker. Operating in near real time using a 1000-word resource management vocabulary, Sphinx achieves 97 percent word accuracy in speaker- independent mode on certain tasks. The system derives its high per- formance by careful modeling of speech knowledge, by using an au- tomatic unsupervised learning algorithm, and by fully utilizing a large amount of training data. Difficulties in building practical speech interfaces to computers include cost; real-time response; speaker in- dependence; robustness to variations such as noise, microphone, and speech rate and loudness; and the ability to handle spontaneous speech phenomena such as repetitions and restarts. While satisfactory solutions to all these problems have not been realized, progress has been substantial in the past ten years. The Future of AI The theoretical and experimental bases of AI are still under de- velopment. Initial forays on the experimental end have led to the development of a host of general-purpose problem-solving methods (e.g., search techniques, expert systems). Experimental AI can be expected to broaden the scope (scalability and extensibility) of appli- cations in the areas of speech, vision, language, robotics, expert sys- tems, game playing, theorem proving, planning, scheduling, simula- tion, and learning. Integrated intelligence systems that couple different AI components (e.g., a speech comprehension program to a reasoning program) will become more common. Collectively, these results should lead to significant economic and intellectual benefits to society. Theoretical AI should lead to the development of a new breed of approximate but nearly optimal algorithms that obtain inputs as an ongoing process during a computation and that cannot precommit to a sequence of steps before embarking on a course of action.~3 And finally, AI will continue its quest for theories about how the human mind processes information made available to it directly via the sens- es and indirectly via education and training. Computer Graphics and User Interfaces Graphics Computer graphics has its roots in data plotting for science and engineering. In many problems, the significance of a calculation does
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 205 not rest in the exact numerical results of computation, but rather in qualitative trends and patterns that are best illustrated by a graph. Indeed, pattern recognition is a well-honed skill in which humans still have substantial advantages over computers. From the earliest days of printed output, computers have thus been printing graphs as well as tables and lists of numbers. Howev- er, paper is a static output medium; electronic display screens offer the ability to create dynamic representations of data. Since the hu- man eye-brain system is better adapted to detecting change over time than to inferring it from a sequence of images or even simultaneously viewed images, the ability to display dynamically changing image forms on a screen is as much a step forward over a graphical depic- tion (or a set of them in sequence) as a static graphic depiction is over a table of numbers. Dynamic displays are particularly powerful for the interactive user when he or she can influence the parameters of both the model and its visualizations. Indeed, the shift from the batch computing typical 25 years ago to interactive computing today enables the user to make real-time changes in input data supplied to a program or in the operating parameters governing the operation of a program and to receive much more rapid feedback. Computer graphics has be- come a standard tool for visualizing large amounts of scientific data, as well as for the design of objects from scratch or from standard building-block components. WIMP Interfaces The use of computer graphics is not restricted to design and sci- entific visualization; it is rapidly becoming the standard method by which human beings communicate with computers. In particular, the use of typed commands to control the operation of a computer is giving way to the use of so-called WIMP interfaces that make use of Windows in which different programs may be run, graphical Icons on a screen that represent actions that can be taken or files that can be opened, and Mice with which the user can Point to icons or select options from a menu. WIMP graphical user interfaces have three major advantages over the use of command languages. They simplify computer operation for novices, because they provide a constant reminder of what the allowable actions are at any given moment. For most users, they are faster than typing, since it is usually easier to point to an icon or a menu selection than to type it in. Lastly, they are less susceptible to error, because the use of icons and menus limits the range of choices
206 COMPUTING THE FUTURE available to the user (unlike typing, in which the user may type any- thing). A Bit of History The history of interactive computer graphics goes back to the 1950s: pioneers using MIT's Whirlwind computer in the 1950s were the first to make use of an experimental display screen, and these graphics were later elaborated with the TX-2 computer and its exten- sive collection of input mechanisms: knobs, dials, keyboard, and light pen. In 1963, Ivan Sutherland developed a system called Sketchpad for the TX-2, which introduced the notion of interactively construct- ing hierarchies of objects on a virtual piece of paper, any portion of which could be shown at arbitrary magnification on the screen. Us- ers could specify simple constraints on picture elements to have the computer automatically enforce mathematical relationships among lines drawn with a light pen. This "constraint satisfaction" allowed a kind of free-hand sketching, with the computer "straightening out" the approximate drawings. Sketchpad was the opening round in an era of computer-driven displays as tools for specifying geometry for CAD/CAM in the automotive and aerospace industry and flight sim- ulators for pilot training. MIT's Steven Coons and other researchers in academia and industry developed various kinds of spline "patch- es" to define free-form surfaces for vehicle design. In the 1960s, Douglas Engelbart at SRI pursued the notion of using computer displays to "augment human intellect." - ~~o ~~~~-~~--~~ ~-~~r---~ -em - -- His group built the first hypermedia systems and office automation tools, in- cluding word processors, outline processors, systems for construct- ing and browsing hypermedia, software for tale-collaboration, as well as various input devices, including the mouse. In the early 1970s, the Xerox Palo Alto Research Center (PARC) pioneered bitmap raster graphics workstations with graphics in the user interface, both for office automation tools such as word processors and illustration pro- grams and for software development (e.g., Smalltalk). These devel- opments, coupled with the reduction in price of display subsystems from $100,000 in the mid-1960s to $10,000 in the early 1970s to about $1,000 today, are the underpinning for today's graphical user inter- faces. The Macintosh personal computer and Windows (for IBM-com- patible personal computers) have brought the experience of SRI and Xerox to the popular marketplace, dramatically lowering knowledge barriers to computer usage, and the commercial success of these products
WHAT IS COMPUTER SCIENCE AND ENGINEERING ? testifies to their significance and impact. 207 As users have required more and more interactive capability with their computers, the popu- larity of graphical user interfaces and graphical displays has grown by leaps and bounds. Now, millions of users have graphical interfac- es on their desks in the office or at home, and it is often possible for users to operate new applications with little or no reference to a manual. Even young children are comfortable using paint programs and illustration programs, not to mention video games and multime- dia electronic books and encyclopedias. With these developments, graphics at long last has begun to fulfill in earnest the promise of the Sketchpad days as a standard means of human-computer communi- cation. Scientific and Engineering Visualization The science and engineering community has also made good use of graphics technology. An NSF-sponsored reporti5 in 1987 empha- sized the need of computational science and engineering for graphics to help make sense of "firehoses of data" generated by supercomputers and hich-nowered workstations. In such data-rich situations, graphics are not merely desirable they are essential if users are to design objects or perceive subtle patterns and trends. Coupled to interactive computing that enables the user to use the visualization of intermedi- ate stages in the computation to direct further exploration, intuition and insight about phenomena and objects can be developed that would not otherwise be possible. Scientific visualizations make increasing use of three-dimension- al graphics. Depth perception is greatly enhanced by real three-di- mensional stereo images that are possible only when the visual in- puts to each eye are slightly different, and so some special input mechanism (e.g., glasses) is necessary to present each eye with the information necessary for the brain to construct a three-dimensional image. Technology such as stereo head-mounted displays with min- iature display screens for each eye can control all of the visual input received by the wearer and is the basis for "virtual-reality" presenta- tions that completely immerse the user in a synthetic world. Cou- pled with the ability to "walk through" such a presentation, suitable immersive representations can give the user an even better and more visceral understanding of the spatial relationships involved than is possible even with a non-immersive stereo presentation, provided that the user can control the vantage point from which the scene is viewed. Graphics are also beginning to assist scientists in developing pro ~ r ~
208 COMPUTING THE FUTURE grams to analyze their data. Traditionally, scientists had to choose between two styles of software use. They could write their own programs from scratch, one line at a time, until the entire program was written, or they could use a prewritten "canned" application. Writing from scratch gives the scientist tight control over what the program does but is time consuming and prone to error. Using a canned application is faster but lacks flexibility. However, in recent years, a style of `'visual programming" has begun to emerge that is intermediate between these two choices. The key construct within visual programming is the explicit specification of data and control flow between preexisting processing modules; such flows are implicitly specified when a program is written in the conventional manner. Using a screen and a mouse, the scientist specifies data and control flows between different modules, and the system automatically assembles the corresponding program from these mod- ules. The scientist has the freedom of specifying the flows as appro- priate to the problem at hand and also has some freedom to custom- ize each module to a limited extent by adjusting a few parameters (typically using a WIMP interface to do so). The result is that scien- tists can rapidly assemble systems that will perform a given task, much as a music buff can assemble stereo components into a working sound system without being much of an electrical engineer. Further, while this style of programming is currently limited to high-end sci- entific users, it is likely that visual programming will become in- creasingly important in the commercial world as well. Microsoft's Visual Basic is a good example of such an application. Engineering visualizations are at the heart of computer-aided de- sign today. Computer-aided design now includes design of mechan- ical parts, architectural or engineering structures, and even mole- cules. Large structures such as airplanes or buildings can be assembled "virtually," i.e., as information artifacts stored in a computer. Parts, substructures, and entire structures can be designed and fitted to- gether entirely on a display and are usually fed to on-line simulations that can analyze and virtually "test" these artifacts. The result is a dramatic shortening of the time required from concept to product. , . .. ,, , .. ~. Touch, Sound, Gestures Since vision is the communications channel with the highest band- width for information transmission, it is not surprising that a great deal of work has been done in graphics. But human beings also make use of sound, touch, and gestures to communicate information. Computer scientists and engineers have thus developed a variety of
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 209 devices that allow users to communicate with computers using these channels as well: head or eye trackers, force and tactile feedback devices, gesture recognition via wands and data gloves provided with many-degree-of-freedom sensors, and so on. These devices are espe- cially useful in virtual-reality environments. Tactile feedback is illustrated well in the problem from biochem- istry of understanding molecule "docking." How a complex organic molecule physically "fits" into another is often a key to understand- ing its biological function. It is possible, although demanding, to calculate the molecular forces that determine docking positions and orientations. But as an aid to developing the biochemist's intuition and feel for docking behavior, computer scientists and engineers have developed ways to depict molecules visually. By controlling their orientation and position through the use of a specially designed joy- stick capable of responding with graduated forces, the user can ori- ent and move the molecule along the path of least resistance as he or she tries to fit the molecule into the receptor site. Sound will become a more important medium for interaction with computers in the future. Audio feedback is widely used in key- boards today to inform the user that a key has~actually been pressed. Some computer systems have voice synthesis systems that make in- formation accessible to users without demanding their visual atten- tion. Such output would be particularly useful when the demands of a task (e.g., driving) would prohibit the diversion of visual attention; thus an intelligent on-board navigator for automobiles will almost surely provide directions (e.g., ''turn left on Willow Street") by voice. Speech input is a more challenging problem discussed in Chapter 3. Finally, human beings use gestures to communicate meaning and manipulate objects. The Dataglove is a glove with sensors that can indicate the extent to which the fingers of a hand are bent. Appro- priate processing of this information allows the computer to con- struct a representation of the hand's configuration at any given mo- ment. Coordinated with a virtual reality presented via stereo goggles, the Dataglo~re allows the user to perform certain manipulations of a synthetic object with his or her hand as though it were real; however, the glove does not provide the tactile feedback that real objects pro- vide. Intellectual Challenges Computer graphics and interactive computing pose many intel- lectual challenges for CS&E. In the earliest days of computing, most of the computational power in a computer system could be devoted
210 COMPUTING THE FUTURE to executing the algorithm to solve a problem of interest, and devel- opers of computer systems paid a great deal of attention to making the best use of available computer resources. But with interactive computing that places the user at the center of the process and ever cheaper computational power, a larger and larger fraction of the com- putational power will be devoted to making the specific application as easy and comfortable to use as possible for the user. Developers of computer systems will pay much more attention to making the best use of human cognitive resources such as attention span and comprehension time. This trend is reflected in the development of computer hardware. Real-time user interaction requires that the time between user input (e.g., pointing to a screen icon) and computer response (updating of the displayed scene) be very short, on the order of a few tenths of a second. This limit places a premium on very fast processors and also drives the development of special-purpose hardware (e.g., graphics accelerators) that can relieve the central processing unit of some of the responsibility for servicing the user interface. - The importance of special-purpose hardware is complemented by an increasing emphasis on investigating better representations of data and information. While a "better" algorithm to solve a problem is generally one that runs faster, a "better" representation of informa- tion in the context of user interaction is one that provides insights not previously accessible. For example, consider the difference between looking at an or- thographic engineering diagram of a metal bracket and holding a metal bracket in one's hand. An orthographic diagram provides front, top, and side views of an object. In some sense, the orthographic diagram is "equivalent" to the metal bracket in hand, since the engi- neering diagram can be used to manufacture the bracket. But very few individuals can look at an arbitrary object in an engineering dia- gram and comprehend just what the object is. A much better sense for the object is obtained by manipulating it, looking at it from differ- ent angles, turning it in hand. Today's computers provide the next best thing: a visual image that can be viewed from different perspec- tives under user control. Using such a display provides a better intuition for time-varying behavior than does viewing a sequence of static images, because the viewer need not cope with the cognitively demanding process of identifying correspondences between the im- ages but rather can follow the correspondences from one moment to the next. The best of today's CAD systems provide images on screen that can be rotated, exploded, collapsed, and otherwise manipulated on command.
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 211 The techniques of computer graphics offer a host of different choices to represent information, as demonstrated by modern molecular graphics. An important aspect of modern biochemistry is to understand how complex molecules fit together. Among other things, such under- standing involves knowledge of the outside contours of several mol- ecules in their "fitted-together" configuration, as well as knowledge of how surfaces from different molecules fit together "on the inside." To take a simple example, imagine two cubical dice that are brought together so that they are face to face. It would be important to know which surfaces were exposed to the outside (e.g., the 1, 2, 3, 4, 5 of die 1 and the 1, 2, 4, 5, 6 of die 2) and which surfaces were touching (the 6 of die 1 and the 3 of die 2~. Visualizations of molecule fittings could use so-called space-fill- ing models, the equivalent of models made of clay that- were fitted together. But the surfaces in contact would then be invisible from the outside, and since the precise geometry of the proper fit is deter- mined in a very complex manner, it is not as simple, as in the case of the two dice, to determine what surfaces from each molecule are in contact. But an alternative representation the dot-surface representation- provides a notable alternative. The dot-surface representation re- places the space-filling model with a shell representation. However, the shell's surface is not solid; rather it is composed of many dots. These dots are spaced far enough apart that it is possible to see past them, but close enough that the eye can perceive the surface of which they are a part. Using these dot shells instead of space-filling models to represent molecules enables the user to see both the outside con- tours (as before) but also "through" them to see formerly invisible surfaces in contact with each other. In many situations, the availability of different representations provides an unparalleled degree of flexibility in depicting informa- tion. Computer graphics-based representations can be created, mod- ified, and manipulated with such speed that the utility of different representations can be rapidly determined, and the user can choose which to use under any particular set of circumstances. These repre- sentations are limited only by the imagination of their creator, since any representation that can be imagined can be implemented. Thus computer graphics can be said to have spawned a new set of con- cepts for depicting information that were not practical prior to the computer. Finally, finding ways to provide perceptual coupling between com- puter-generated image and user is important. Evolution has provid- ed human beings with rich and coordinated senses of sight, sound,
212 COMPUTING THE FUTURE and touch; immersible virtual-reality presentations, data gloves, au- dio output, and force feedback are the first steps toward the full exploitation of human senses. SYNERGY LEADING TO INNOVATIONS AND RAPID PROGRESS As anyone who has recently purchased a personal computer knows all too well, computer technology advances at an extraordinarily rap- id rate. To a large degree, the rapidity of technological change arises from a high degree of interconnectedness among the various subdis- ciplines of CS&E. The resulting synergy is intellectually powerful and results in many practical benefits as well. Synergy arises in many contexts. Box 3.1 offered two examples of the impact of synergy between subdisciplines of CS&E. A third example, with more obvious and tangible economic impact, is that of workstations. It is common today to see a multimillion-dollar main- frame computer replaced by workstations that offer much better cost- performance ratios. The growth in the use of workstations is fueled by advances in many areas: networking (that enables workstations to be interconnected and thus enables users to share resources), re- duced-instruction-set computers (that speed up computations by large factors), portable operating systems (that can run on computers made by different vendors), and a better theoretical understanding of how compilers can best use hardware resources. No single one of these areas is solely responsible for growth in the workstation industry, but taken together they have produced a multibillion-dollar indus- try. The benefits of synergy are not limited to innovation. Synergy also speeds up developments in the field. Consider, for example, the development of the 80X86 processor chip family by the Intel Corpo- ration. (The 80X86 processor is the heart of IBM-compatible personal computers.) In designing the 80286 processor chip, Intel engineers had to use seven different brands of computers depending on the step of the design process. This was before portable operating sys- tems were available, and so a designer had to learn seven different command languages and seven different text editors to complete a microprocessor. However, shortly after the 80286 was released, portable operat- ing systems came into use at Intel. This meant that designers of the later processor chips had to learn only one command language and only one text editor, and this contributed to the shortening of the time between the 80486 and the 80586 compared to the time between
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 213 the 8086 and the 80286.~7 Other reasons for the reduced develop- ment time include a graphical user interface to the design software (making the designer more productive), better compilers and algo- rithmic improvements to the design software (making the design software faster), and simply faster computers (so that the designer can per- form even unchanged tasks in less time). And in a fast-moving tech- nology like electronics, shorter design time corresponds directly to better performance and lower cost. Hence the designers of the Intel 80486 and 80586 (as well as their customers) have and will benefit from advances in hardware technology, operating systems, compil- ers, user interfaces, design software, and theory of algorithms. INTELLECTUAL AND STRUCTURAL CHARACTERISTICS OF CS&E AS A DISCIPLINE CS&E is an entirely new entity, neither simply science nor simply engineering. Its historical roots derive from mathematics and electri- cal engineering, and this parentage gives CS&E its distinctive flavor. Perhaps most important in creating this flavor is the close rela- tionship between the intellectual content of CS&E and technology. Technological developments have a major influence in defining what the interesting problems of the field are; problems in CS&E often become interesting because the technology necessary to implement solutions becomes available. Put another way, new generations of technology open up and make interesting a variety of new and chal- lenging questions. This intimate link to technology creates a deep connection between the research and educational activities of aca- demic CS&E and a multibillion-dollar computer industry, with intel- lectual progress strongly influenced by and at times strongly influ- encing commercial development. Intellectually, CS&E includes programming, which allows a pro- grammer's thoughts to spring to life on the screen. As a result, com- puting technology can create virtual realities universes unconstrained by the laws of physics-and this ability to take part in creating new worlds is part of the excitement of programming. In other words, the objects of study in CS&E (ways to process and represent informa- tion) are created by those who study those objects- whereas other scientists study what nature gives them (atoms, cells, stars, planets). This new form of expression also offers opportunities for important intellectual contributions to the formal study of information. Theory in CS&E often develops after years of practice, with ex- periments largely establishing the feasibility of new systems. By con- trast, experiments conducted by physicists and biologists play an im
214 COMPUTING THE FUTURE portent role in proving or disproving their theories. The experimen- tal construction of algorithms as programs is more likely to uncover practical issues that were ignored in the mathematical proofs rather than flaws in the proofs themselves. Feedback from experimentation cart then lead to the creation of more realistic models that in turn give rise to more relevant theories. In other words, CS&E experi- ments often demonstrate the irrelevance and inadequacy of previous theoretical work, rather than proving that theoretical work wrong. The commercial and industrial side of computing is also unusual. Whereas most industries focus on producing tangible goods, an in- creasingly large part of computing involves software and informa- tion. Software and information are unlike other products in that they are primarily an intangible intellectual output, more akin to a useful report than a useful widget. By far the largest cost of software and information involves research, development, documentation, testing, and maintenance (primarily intellectual activities) rather than manu- facturing (typically, copying disks and manuals). As a result, capital requirements for software production are relatively much lower than those for widget production, while personnel requirements are rela- tively much higher. When the recognition of CS&E's intellectual heritage is combined with understanding of the rapid pace of change, the youth of the field, the impact of a large industry, the magical implications of pro- gramming, and the mathematical implications of algorithms, the ex- citing and enticing nature of CS&E is revealed. NOTES 1. The notion of CS&E as a discipline based on theory, abstraction, and design is described in Peter Denning, Douglas E. Comer, David Cries, Michael C. Mulder, Allen Tucker, Joe Turner, and Paul R. Young, "Computing as a Discipline," Communications of the ACM, Volume 32(1), January 1989, pp. 9-23. 2. Personal communication, Donald Knuth, March 10, 1992 letter. 3. Frederick Brooks, The Mythical Man-Month, Addison-Wesley, Reading, Mass., 1975, pp. 7-8. 4. "Computer Displays," Ivan Sutherland, Scientific American, June 1970, p. 57. 5. This division isn't even necessarily unique, since abstractions in CS&E can be created with a great deal of flexibility. A grammar checker builds on a word-process- ing program, and thus the word processor plays a "system software" role for the grammar checker. But the word processor builds upon the operating system, so that the word processor is applications software from the perspective of the operating system. 6. John E. Hopcroft and Kenneth W. Kennedy, eds., Computer Science Achievements and Opportunities, Society for Industrial and Applied Mathematics, Philadelphia, 1989. 7. In practice, the trade-off is even more favorable than this discussion implies. In
WHAT IS COMPUTER SCIENCE AND ENGINEERING? 215 the former case, the area of the chip would be more than 100 times larger, due to second-order effects that are not accounted for in the VLSI complexity model. In the latter case, it could be possible to reduce the increase in total chip area to less than a factor of ten by designing its functional elements to perform multiple operations in a "pipeline" arrangement. (A pipeline architecture is analogous to a bucket brigade; when it is finished with an elementary operation, an element passes its result to the next element in sequence, thereby allowing the entire array of elements to be kept busy nearly all of the time.) 8. The discussion that follows is taken largely from Lui Sha and John B. Goode- nough, Real-Time Scheduling Theory and Ada, Technical Report CMU/SEI-89-TR-14, Software Engineering Institute, Carnegie Mellon University, Pittsburgh, Pennsylvania, April 1989. 9. The reader may find it amusing to multiply two arbitrary 2 x 2 matrices with a minimal number of multiplications. The standard method of multiplying these matri- ces requires four additions and eight ordinary multiplications to compute the matrix product. It turns out that it is possible to compute the matrix product with only seven scalar multiplications though at the expense of additional additions (and subtractions). The algorithm for multiplying 2 x 2 matrices is the basis for a more general algorithm for multiplying matrices of any size that requires considerably fewer arithmetic opera- tions than would be expected from the standard definition of matrix multiplication. The details of the seven-multiplication algorithm are described on p. 216. 10. Actually, LP is applicable to a much broader class of problems. 11. A problem's complexity depends on the model of computation used to derive it. An area of active investigation today within theoretical computer science concerns the use of different models that differ in the fidelity with which they match actual com- puters. For example, some theoretical computer scientists consider so-called random access machine models, on the grounds that these models can access any memory location in a constant number of steps, while a Turing machine can access a given memory location only by stepping through all preceding locations. 12. The function 2n is called "exponential" in n. The function n2 is polynomial in n, as would be n raised to any exponent. An algorithm that executes in a time propor- tional to a function that is polynomial in n, where n is the size of the problem, is said to take "polynomial time" and may be feasible for large n, whereas an exponential algorithm is not. The reason is that for sufficiently large values of n, an exponential function will increase much faster than any polynomial function. 13. These algorithms would be nearly optimal in the sense that a given algorithm working on problems of a particular nature would consume no more than a certain amount of computational resources while generating solutions that are guaranteed to be very close to optimal with very high probability. 14. Batch computing refers to a mode of computing in which the user submits a program to a computer, waits for a while, and then obtains the results. If the user wishes to correct an error or change a parameter in the program, he or she resubmits the program and repeats the cycle. 15. Bruce H. McCormick, Thomas A. Defanti, and Maxine D. Brown, eds., Visualiza- tion in Scientific Computing, ACM Press, New York, July 1987. 16. Virtual reality, the object of both serious intellectual work and far-fetched hy- perbole, will be the subject of a forthcoming NRC project to be conducted jointly by the NRC's Computer Science and Telecommunications Board and the Committee on Human Factors. As a mode of information representation, virtual reality is still in its infancy compared to modes such as ordinary stereo or two-dimensional graphics. 17. The time between the 8086 and the 80286 was five years, while the time between the 80486 and the 80586 is expected to be three years (the 80586 will be released in
216 COMPUTING THE FUTURE 1992). See John L. Hennesy and David A. Patterson, Computer Architectures: A Quanti- tative Approach, Morgan Kaufmann Publishers, San Mateo, California, 1990, inside front cover. Solution to the problem posed in Note 9 above. Let the elements of matrix A be denoted by A = r all al2 1 L a21 a22 and similarly for B. If we define X1 = (all + a22) (bl1 + b22) X2 = (a21 + a22) tell x3 = all · (b12 - b22) x4 = a22 (b21 - b11) Then the entries of C are given by c1l = x1 + x4 - x5 + x7 c21 = x2 + x4 x5 = (all + a12) · b22 X6 = (a21 - all) (bl1 + bl2) x7 = (a12 - a22) (b21 + b22) c12 = x3 + x5 c22 = x1 + x3 - x2 + x6 The significance of this algorithm is not its utility for 2 x 2 matrices per se, but rather that it is the basic building block for an algorithm to multiply N x N matrices. Such a matrix can be treated simply as a 2 x 2 matrix where the elements are themselves matrices of size N/2 x N/2. The result is that instead of requiring on the order of N3 multiplications and additions (as would be expected from the definition of matrix multiplication), the matrix multiplication requires on the order of N281 arithmetic operations. While such an algorithm involves some additional overhead, it turns out that for sufficiently large values of N. it will run faster than one based on the defini- tion for matrix multiplication. SOURCE: This method was first published by V. Strassen, "Gaussian Elimination Is Not Optimal," Numerische Mathematik, Volume 13, 1969, pp. 354-356.
