Jack B. Dennis
MIT Laboratory for Computer Science
1. Factors Driving the Evolution of Computer Systems
Overwhelming pressure on the evolution of computer systems is placed by demand of software producers to distribute computer programs and software components to a wide a customer base as possible for the least effort. (and with a guarantee of equivalent functionality on all platforms, and comparable performance on similar platforms). This demand is complemented by pressure from consumers who want computer systems that will support the widest class of software products that includes the desired functionality and provides sufficient performance and reliability. The primary source of this pressure is from the personal computer world (and now the server world) where software is distributed in millions of copies. It is addressed by an application program interface (API) defined by the combination of standard processor chips together with standard operating system interfaces.
Yet the API defined by this combination of architecture and operating system does not provide anything close to an ideal programming environment for software construction, as most of the priniciples of modular software construction (see below) are violated. Neither does the API allow achievement of the levels of performance that are possible with a system architecture designed from the ground up to support a good program execution model---one that statisfies all principles of modular software, for example.
The benefits of the common API that have been realized for "shrink-wrapped" personal computer software do not extend to most commercial and industrial software where distributed processing is often required and large databases must be supported with high reliability.
In these systems the main limitations to the practice of modular software construction arise from two sources: One is the distinction between files processed by the operating system and objects directly manipulated by program execution in memory. The other is the facilities provided by operating systems (interrupt handlers and interprocess communication support (IPC)) for the coordination of concurrent acitivies, both internal and external.
2. Parallel Computing
Parallel and distributed computing have become essential parts of most software. It has become significantly more cost-effective to utilize many small, simple processors for a job than to use a single uniprocessor. Yet parallel computing has taken the art of software construction back to the dark ages: There are no standard features of popular programming languages for calling on the mechanisms of parallel processing. In practice, low-level programming methods using message-passing and/or process synchronization commands lead to programs that are needlessly large, and difficult to understand and debug. Moreover, these low-level methods fail to provide any natural interface for modular software construction.
3. Principles of Modular Software Construction
A primary concept in modular programming is the interface of a component---the manner in which the component interacts with its users. The most common kind of interface in software construction is the procedure call. Execution of a procedure call supplies a module with a set of input values and requests that the module use the values in constructing result values made available to the caller.
To attain the full benefits of modular programming the support provided by the computer system in support of the component interface should meet the following requirements:
Information Hiding Principle: The user of a module must not need to know anything about the internal mechanism of the module to make effective use of it.
Invariant Behavior Principle: The functional behavior of a module must be independent of the site or context from which it is invoked.
Data Generality Principle: The interface to a module must be capable of passing any data object an application may require.
Secure Arguments Principle: The interface to a module must not allow side-effects on arguments supplied to the interface.
Recursive Construction Principle: A program constructed from modules must be useable as a component in building larger programs or modules.
System Resource Management Principle: Storage management for data objects must be performed by the computer system and not by individual program modules.
These requirements are violated in one way or another by the popular imperative programming languages. Yet achieving the full benefits of modular programming is not merely a matter of programming language design because large programs and application packages generally depend on operating system services for their correct operation. Using a semantic model that spans all functions and services needed by application programs offers the possibility of making the benefits of modularity in software widely available, and encouraging the use of component-based software in computing pratice.
In contrast, functional programming languages express parallelism implicitly, and are known to simplify the process of writing correct programs. Functional programming languages are consistent with the principles of modular program construction and provide a sound basis for component-based software. There have now been several demonstrations of the effectiveness of functional programming in reducing programming costs, including use of Sisal in scientific computation, and tests of Erlang in communications industry applications.
These ideas must be extended to encompass all facilities used for writing software, most importantly facilities currently provided by operating systems. That this is a feasible objective is partially demmonstrated by some past successes. The MIT Project MAC Multics project showed the power of relieving programmers from concern with the memory/file dichotomy, and the IBM AS/400 system has shown the merit of supporting a single universal address space for the component-based construction of commercial software and the efficiency of context switching and cache management that results.
4. Object-Oriented Programming Environemnts
Object-oriented methodology is used at two levels in applications: Object-oriented languages such as SmallTalk and C++ are used with "in-memory" objects, whereas standards for objects as software components such as CORBA and OLE are used to describe transaction interfaces to persistent objects in distributed systems. The O-O languages have nice modularity properties when used for sequential computations, but this breaks down when they are extended to encompass concurrency and/or file system operations. The standards for distributed objects must use data descriptions that cannot exactly match the properties of data types of the several languages used to write object methods. Consequently these standards cannot provide an interface that satisfies modular programming principles. For these reasons current O-O models are not the best choice for guiding computer system architecture.
5. Nondeterminacy
One problem with O-O methodologies is that the introduction of means to represent concurrency generaly leads to the possibility of nondeterminate behavior. (Indeed, this is essential for most transaction processing applications.)
Nondeterminacy arises when the outcome may be different for different runs of a computation with the same input. A common example occurs when two asynchronous, concurrent activities request use of some shared resource---a block of memory, perhaps. Another example is transaction processing, where the order in which commands take effect on a database depends on the timing of request arrival, or of asynchronous events within the computer system. Most programming languages, including O-O languages, that support parallel computing do so by means of message-passing or synchronization commands that open the door to nondeterminate computation, even when this is not essential to the application. This is one of the reasons parallel programs are notoriously difficult to make correct.
Functional programming languages, in contrast, permit exploitation of parallelism while providing a guarantee of determinate execution. Of course, there is a need for an escape mechanism that allows nondeterminate program modules to be written for applications that require this capability. The best means for expressing nondeterminacy within a functional programming environment is a subject of debate.
6. The Coming Crisis in Microprocessor Architecture
In microprocessor architecture we are at the brink of a major revolution: The number of transistors that can be fabricated on a single chip is continuing to increase, but designers are running out of sound ideas on how to use them. Superscalar architecture is running out of steam: already the instruction-level parallelism in benchmark codes is not sufficient to allow utilization of more than a fraction of the processor's potential performance. VLIW architecture cannot take us much farther. On the basis of technology the next step is to put multiple processors on a chip. However, much current research in computer architecture seems to be examining minor adjustments to superscalar designs, especially schemes involving speculative use of resources.
The practical difficulty with a multi-processor chip is there is no standard API, no standards for distrubuting "shrink-wrapped" software for such a processor, let alone for building component-based software. This is where the action will be and where the research community should be showing industry principles and concepts upon which to build viable products.
One ray of light in this scene is the Tera computer which uses a novel multi-threading and latency-hiding architecture. Here we see a commercial venture that is exploring new territory while many academic projects are doing the development evaluation experiments that the vendors should be doing for themselves.
7. Memory Models versus Program/Computation Models
In current studies of multiprocessor computer systems, the specification of memory system behavior plays a very important role. The criterion of a correct design has been that the memory system can support valid execution of multiprocess programs prepared for execution by a single processor system, or a multiprocessor system without cache memories. The rule is that the system must present to the programmer a memory that behaves as though all write operations to the memory are observed to occur in the same order -- this is the sequential consistency property of leslie Lamport. However, adoption of sequential consistency leads to some nasty difficulties given that processors have evolved to have superscalar architecture and the distance between processors and remote memory has risen to tens or hundreds of clock times. It is difficult to design synchronizing protocols that work, and traditonal optimizations performed by compilers can change a program from one that runs correctly to one that is erroneous. The reason is that work on memory models has these difficulties is that sufficient attention has not been paid to the program execution model assumed by programmers and compilers. What is important to the programmer is that is code be executed exactly according to the semantics of the progamming lanaguage in which it is expressed, not that the "memory model" have certain properties. The proper approach to computer system design is to select a program execution model and then devise a system architecture that correctly executes programs expressed according to the model.
8. Research Projects in Computer Systems
Research projects are needed that demonstrate the possibilities from the adoption of novel system architectures that support modern methods of program construction and organization, and satisfy all principles of modularity for software components.
It is not necessary that such a project produce the final silicon chip from which comercial systems would be built. It is only necessary to provide a convincing demonstration that fabricating such a chip is feasible and the device would perform as envisioned. It is very fortunate that the means is available for quickly constructing prototypes of systems having novel architecture: field programmable gate arrays (FPGAs). Using FPGAs it is possible to build a prototype that will operate within a factor of ten of the speed of a corresponding custom device at modest cost. This is sufficient to demonstrate sophisticated software capabilities.
Because such a project involves a range of skills and infrastructure support that may not all be available in one research institution, it would be worthwhile to support collaborative projects among groups of institutions.
A disuading factor for such a project is the amount of software that must be provided with a new processor for it to become a viable product. I have three responses to this argument.
1. The novel processor can be layered with an interpreter for an old standard API to facilitate use of important legacy software such as editing tools and text processors. (The drop in performance due to interpretation/emulation will be made up in part by (a) better performance of the novel architecture; and (b) the exploitation of parallelism. Also many tools work satisfactorily on low-performance machines.)
2. One can pick an application domain for demonstrating novel principles that has relatively little dependence on legacy code.
3. The greatly improved API of the novel system will make it relatively easy to reimplement important pieces of legacy code.
Although the effort involved in such a project is large and there is risk that its completion may not be timely or effective, the enormous potential benefits will make the effort a worthwhile investment.
9. Conclusion
In summary, existing standard APIs based on current microprocessor architecture and operating system interfaces do not cover the full range of computer applications and are in conflict with principles of modular software construction. Moreover, these APIs must evolve or be replaced because technological advance will force the use of multiprocessor chips and expoitation of parallelism in application code. This presents an opportunity to develop and demonstrate the benefits of new programming models that promise both improved programmability and fuller utilization of forthcoming technologies.
The portability of software components will be needed in Computer systems spanning a wide range of performance and reliability requirements, where performance requirements cover different combinations of processing, memory and communications.
Remark: There has been some discussion of the World Wide Web as a gigantic global computing engine. In my view, a very significant change of perspective must occur when one crosses the boundary between systems that operate under a single authority and sytems that link millions of independent agents acting without responsibility to one another. There are many interesting research problems concerning the structure, operation, and management of the Internet and the Web. These include security issues, the efficient caching of information objects, and the possibility of a role for what I have called an "operator": A computer systems managed to provide a supporting environment for computer/communication services implemented and offered by independent vendors.