My main concerns for the time being are
EWD41 · 1962–1964 · PDF · source transcription · Source language: Dutch. Machine translation: needs review.
|
|
The vector memory.
In most multi-programming systems that I have seen, each individual program must specify its memory requirement in the form of "so many consecutive memory locations". Dynamic modification of this number usually meets with difficulties - especially if a program in the course of its execution would come to the discovery that it would actually like a bit more.My observation is the following: each program expresses its memory requirement as a requirement for a vector of given length and as soon as a number of these programs are organized together in the same memory, then this overarching organization thus has some technique for placing a number of vectors in linear memory. I would like to let the coupling "an individual, sequential program versus a single vector" lapse and give each individual program the possibility to express its memory requirement in terms of as many vectors as it wishes.
This has several potential advantages. First, it is a great exception when the memory requirement posed by a particular process can be expressed most naturally as a single vector. One could also derive much pleasure from such a facility under uni-programming. Second, this creates the possibility for a more natural unit in which quantities of information from random access memory can be dumped, say to drum. Third, the individual programs are not so evidently formulated in terms of physical addresses that one might expect that reorganization of physical memory could be performed with greater freedom.
In what follows, the presence of a "two-level memory" (my translation of "two level store") will hardly be mentioned. I will not discuss the strategy according to which the information will have to be distributed over both forms of memory; nor will I discuss the administration of drum organization.
My main concerns for the time being are:
(a) that the programs in their formulation - i.e. the way they are represented in core memory - restrict themselves to the "own", intrinsically essential; in other words, that this formulation is independent of the way this program is embedded in its environment;
(b) that the effective order of addressing does not explode;
(c) that the administrative tasks arising from the obligation to update the administration when reorganizing memory remain clearly described;
(d) that it is clear what the "grain size" of the programs is, i.e. which actions may not be disturbed by memory reorganization. We could get into practical difficulties if the execution of a grain were allowed to last arbitrarily long; we would get a contradiction if the execution of a grain ... made memory reorganization necessary!
(e) finally a practical concern: finding a terminology to be able to talk about it.
To avoid Babylonian confusion, first the following convention: I will use the word "address" only in the sense of "physical address", the bit row that can be sent to the selection register of a memory. Each program will identify its elements as "number so many of a vector" and this rank number I will call an "index".
A vector of length N consists of N elements, mutually distinguished by an index value i; the inequalities 0 <= i <= N - 1 apply. The identification of the vector - necessary when several vectors occur in a given context - is possible by assigning a so-called "base" to each vector and a base, as an element of another vector, is again identifiable by a rank number.
(The intention is that a vector in core memory will occupy a number of consecutive memory locations; the base of this vector then contains, among other things, the start address and length of the supporting vector.)
The existence of a base is the right to be allowed to speak about a vector; the identification (i.e. the index row) of the base functions as the identification of this vector. It will become clear later that a base - although it is an indexable element of a vector - should not be regarded as an arbitrary element representing information that may be regarded as subject matter of the process. (Part of the base would be the start address of the supporting vector, but physical addresses have no meaning in the context of the program!) We therefore have two types of elements: elements on which the program may freely operate (numbers) and bases. For several reasons we impose the restriction that there will be no mixed vectors: all elements of the same vector must be of the same type. If the elements are numbers, we speak if necessary of a "twig", if the elements are bases of other vectors, we call the vector a "branch". (A base contains, besides length and start address, also a specification of the type of the supporting vector.)
Every context presupposes the accessibility of an "implicit base", namely the base of the vector in which the first index of an index row will be interpreted as a rank number.
Permissible operations on vector bases are: definition of the type of the supporting vector; definition of the length of the supporting vector.
When an existing vector is extended, a number of "undefined" elements are added; if it is the extension of a branch, "undefined" bases are added. An undefined base contains in the place of the type specification the notation "not yet specified". After this introduction of the base, the type of the supporting vector may be defined once. (We thus exclude type changes for existing vectors, even in the case that the vector had length 0 at that moment.) An unspecified vector is something different from an empty vector: although only "nothing" could come out of it, I still object to additions like "0 cows plus 0 geese".
When an existing vector is shortened, a number of the highest-numbered elements of this vector are lost; if the vector was a branch, then with the bases that are removed, all vectors that rested on them are lost (and if there were branches among them, all vectors that rested on those again, etc.)
(The restriction mentioned in the previous paragraph regarding constancy of type can be accommodated by introducing as an extra operation on a vector base: making it unspecified. If anything rested on this base, it is lost in the process of making it unspecified. Another solution is to let this making-unspecified be implicit in type changes. Whether all this is very important, I dare to doubt.)
Operations on vector bases are performed by specifying the index row that identifies the base in question; if this index row is empty, the implicit base is by definition intended. Thus a context will generally begin by defining the implicit base as the base of a branch of a certain length. This introduces an arbitrary number of new bases and thus creates the possibility of introducing new vectors.
Reference to element i of a vector of length N, where i does not satisfy 0 <= i <= N - 1 is nonsense and has no meaning: it is also the intention that every selection of a vector element implies that it is tested whether these inequalities are satisfied. (You require a certain degree of consistency from each program; if this is satisfied, the usual form of "Memory protect" to protect the program of Mr. Jansen against the caprices of Mr. Pieterse no longer has any meaning. After all, Mr. Pieterse no longer has the terminology to hinder Mr. Jansen.)
It is clear how every context can introduce and manipulate its local variables in an extremely flexible way in this manner. A little tree is planted on the implicit base, which can grow and be pruned during its existence. Now, however, it is high time to see how our context with its local little tree fits into its environment. The implicit base we have spoken of is, after all, not an absolute machine given: if we take such a big step back that we can overlook the entire memory of the machine, then what functions internally, i.e. in a given context as an implicit base, is externally an element that has its place in the total tree and is identified by an index row of a certain length, like any other element.
Moreover: without exception we can state that every context will not be "self-contained", but can only work by grace of prior specification of a number of parameters. A program that uses one of the communication devices will address this communication device as a "formal" device; upon activation a specific device must be supplied as the corresponding actual parameter. This too all falls under "fitting into the environment".
To effect the cooperation of a given context with quantities (vectors, communication devices) that internally have a formal name and externally a name expressed in a terminology that has no internal meaning, after mature consideration and long hesitation I have introduced a new kind of vector, the so-called "parameter vector".
A certain context can only work if it has at its disposal both the implicit base and the associated parameter vector. Because this is an inseparable pair, I propose to place them together in the same vector. (The other vectors, branches and twigs, were homogeneous. We thus now introduce in the parameter branch a vector with a very specific layout, e.g. the zeroth element is the implicit base, the first element is the current value of the instruction counter and the remaining elements are parameters. It would not surprise me if the beginning of the parameter vector were a very suitable storage place for some more implicit "state variables".) Generally the parameter vector begins with a fixed number (at least 1) of vector bases, possibly a fixed number of elements for state variables, and finally a number of parameters. If a vector is a parameter vector, this is noted in its base. In the program, formal parameters are referred to by
(a) an indication that this is a formal parameter; this selects the parameter vector;
(b) an index that specifies the parameter.
The idea is that a given context A activates context B as follows. Context A reserves a parameter vector, fills in all parameters therein and then lets the machine jump to the new parameter vector annex new implicit base.
I now especially want to examine how we give an existing vector to a new context as a parameter. I want to do this by filling in at the appropriate place of the parameter vector a copy of the base of the vector. This is very nasty, but in my feeling I must do this.
Let us briefly go back to the idea of the implicit base: a certain program is formulated in terms of its implicit base and does not speak out how long the index row is that in the external world completely identifies this implicit base. The selection resulting from an index row in a specific context would thus mean that you would have to precede this index row in thought with the index row needed to find the implicit base in the environment. That would mean that the efficiency with which a program is executed depends on the distance to the root of the tree and that was not the intention.
As soon as I copy vector bases, however, I must ensure that when such a base is changed - e.g. movement of the supporting vector - this change penetrates not only to the original, unique base but also to its copies.
The idea of the separate parameter vector was introduced to know, when a base is changed, that you only need to scan parameter vectors to see if you encounter elements that need to be updated. I believe this turns out faster than mentioning at every copying at the source where the copy is located, especially since you can achieve some savings with a base that has only one copy. (You could introduce a "copied-bit" at every base. One value means: this base is definitely not copied, the other value means: this base may be copied. At every copying of a base you note this fact at this base. A base can have a number of copies at a given moment in this way, but you do not count them. If some of these copies disappear due to vector shortening, you let that disappear for the time being unnoticed. (As long as the base is not changed, the possible copying does not matter much either.) Only when you are going to move the vector, you look at the copying bit. If it is in the state "possibly a copy", you investigate the possible parameter vectors to see if you have anything to update. If you indeed find copies, you update them, otherwise you set the "copied-bit" back.)
As long as one context only sequentially activates other contexts - one procedure only calls another when the previous one is completely finished - this activating context can suffice with only a single parameter vector. Also for the case that a certain context wants to have more than one parameter vector, there is, if I am not mistaken, an acceptable convention to be found, so that in a certain context the parameter vectors are easily found.
When you call a subroutine, you must specify which subroutine you are calling. Likewise I wanted, when activating a certain program, to give this program as a parameter of the activation mechanism. I regard a program as a vector and we agree, for example, that we copy the base of this vector to the place of the first parameter before we let the machine proceed to the new parameter vector.
Finally a few remarks.
Activating a new program in parallel programming can be regarded as an operation of which the "ordinary subroutine call" is a special case. One of the parameters you leave as a semaphore, which is set to FALSE by the outer program before activation (before the call). Then the outer program activates the subroutine and then waits for a pass of this semaphore. The subroutine ends by indicating its completion by setting the semaphore in question to TRUE, so that the calling program only proceeds when the subroutine is completed. After passage the calling program can remove this activation - this waiting machine - from the master waiting list. I doubt whether this is the most practical way to call subroutines, but it is illuminating that it is essentially nothing other than adding a new program to the waiting list.
I have silently assumed that the presence of a vector in core would imply that its base is also located in core. Preferably I would keep all branches in core, also the parameter branches. Keeping all parameter branches in core is therefore pleasant, because movement can imply that you still have to make corrections far from the root in parameter branches. If it is necessary to dump parameter branches to drum, there is still something to be done about that. Then you must also note at each parameter in the branch which index row in the context that filled the parameter retrieved this parameter. Then when you retrieve the parameter row from the drum you must realize that you are now fetching a parameter branch from the drum, on which corrections may not have been maintained, but you then have all the data in core to bring the parameter row, which has "slept" on the drum for a while, up to date.
In what terminology the waiting programs on the master waiting list should be retained is still an open question for me; the same applies to the programmed semaphores.
I have forgotten to mention that I deliberately give the program to be executed as a parameter to the activation mechanism, and that I regard such a program as a constant vector. (You can take care of this by not providing the program itself with the terminology by which it could overwrite itself. Our ALGOL programs also do not overwrite themselves.) It is very attractive to have a program that is output-limited working in a number of activations simultaneously, without having the program stored in core more than once. (What did we think of the translation process? Or the "console program" if you have more than one console?)
The basic idea behind core occupation is that a vector is either completely present in core or not at all. You note this in the base. That you cannot introduce vectors this way that are longer than the size of core memory is an inconvenience, but it is automatically solved (by an implicit order increase; you can also indicate in the base that this has happened.)
Finally: I have a feeling that the transport times to and from slow memory could well become a bottleneck. Once you have taken over a vector from slow memory, you can indicate with a bit in the base that the copy is still "intact"; if you write in that vector or change its length, you set that bit to the other state. This way you can save yourself quite a bit of unnecessary back-transport. If the time between request and start of the actual transport is long compared to the actual transport time (because the drum is in the wrong position), it could well be worth collecting requested transports for a while and sorting them via program if necessary. This may be all the more necessary because many vectors will be short compared to the capacity of a whole drum track.
Final remarks.
I am all too aware that no finished plan has been described in the foregoing. On the contrary: so many question marks remain that elaboration will be a considerable amount of work. Before I throw myself into that, I would like to have the opinion of some other people on how feasible or how hopeless this seems to them.
I can imagine that the reader feels like having caught a glimpse behind the scenes of someone else's nightmare. The perhaps unconvincing defense I can put forward against this is that when the ALGOL complex for the X1 began to take shape in its present form, the first three weeks also gave us the creeps. In retrospect it may well have been very good that we were only confronted step by step with the consequences of that approach; otherwise it would have cost us more effort to muster the courage. In my not uncommon moments of doubt I do draw courage (or should I say: overconfidence?) from that experience.
There is another reason why I would like to submit this plan to others now. Of the whole field of problems, I have chosen a few and thought about how you could solve them. I have only been able to immerse myself in them by assuming that the rest is solvable. Of course you hope that in the choice of where you look first, your intuition does not deceive you, but you always run the risk of unconsciously pushing a few very essential difficulties to the background because you cannot say a sensible word about them.
Hence this piece ends with a request for comment.
E.W.Dijkstra
transcribed by Johan E. Mebius
revised Sun, 28 Mar 2010