Chapter 2

The task of this chapter is to provide an introduction to the PMS descriptive system for the top computer-system level and to the ISP descriptive system for the program level. We take the view that informal notations exist and are in use. PMS and ISP are an attempt to tidy up these notations-to make them consistent and more powerful. Thus we depend on the reader already to understand implicitly much of the notation and how it is to be used. In consequence, there is no attempt in this chapter to provide a formal treatment of the whole system. The appendix 1, at the end of the hook contains a complete summary of the notation rules, including the component attributes and values, and their abbreviations (i.e., the main technical vocabulary). We will provide a brief discussion of the conceptual view underlying the two systems, since it is an appropriate way to make the notation understandable. But this is informal and heuristic.

The two descriptive systems are not independent. There is a common set of notational conventions for abbreviating, for giving parameter values, and so on. (The Appendix separates them.) Likewise, there exists, in effect, an ISP description for every PMS component, or, conversely, ISP statements imply particular PMS component structures. A natural way is to present PMS first, which will also serve to introduce the main notational devices. Then we will give ISP. Finally, we will add more comments on the relationship between PMS and ISP.

Digital systems can be characterized most generally as systems that at any time exist in one of a discrete set of states and that undergo discrete changes of state with time. This is a highly abstract view. Nothing is said about what physical state corresponds to a system state; nothing is said about what laws of physics transform the system from one state to another. The states are given abstract labels: S₁, S₂, . . . The transitions are provided by a state-transition table with many entries of the form: If the system is in state S_i and the input is I_j, then the system is transformed to state S_k and evokes output O₁. (Alternatively, a state diagram has the same information.) The virtue of this "state-system" view is that it truly seems to capture what we mean by a discrete (or digital) system. Its disadvantage lies in this same comprehensiveness, which makes it impossible to deal with large systems because of their immense number of states (of the order of 1010 10 states for a big computer).¹

Existing digital computers can be viewed as discrete state systems that are specialized in three ways. These three specializations make possible a much more compact and useful description of these systems, the one that we call the PMS description.

First, the state is realized by a medium, called information. which is stored in memories. Thus, a core store of N words each of 32 bits is a digital device that can exist in one of 2^32N states. Similarly, all the states of a processor are made explicit in a set of registers: an accumulator, an address register, an instruction register, status register, etc. Each holds a specified number of bits. No permanent information is kept in digital devices except as encoded in bits in a memory. There are two qualifications to this blanket statement. First, the basic unit of information need not be the bit; it could be any base: One can have ternary machines, decimal machines, etc. Second, the sequential logic circuits that carry out operations in the system have intermediate states. But this is a strictly temporary affair while the operation is occurring, for example, the intermediate, inaccessible, partial results during a multiply operation. At the end-when the smoke has cleared, so to speak-all information carried over to the next operation has been encoded into bits in memories somewhere. At the PMS level we care only about the end result of such operations.

The second specialization of the general state-system view is that current digital computer systems consist of a small number of discrete subsystems linked together by flows of information. There is a distinct component called the memory, another called the central processor, another called the card reader, etc. This is analogous to the lumped-parameter specialization at the circuit level. Thus the natural representation of a digital computer system is as a graph which has component systems at the nodes and information flows as branches. Now, in fact, the discrete character of digital encoding in bits prevents there being any truly continuous digital devices (in analogy to the continuously distributed parameter circuits). But one can have distributed networks with very small components. Such iterated arrays are a topic of much