,me Thoughts on trallc| Processing LYNN [). YA t~I~J{()U(~tI North America ~p~ .Jt ~iation Inc., [nglewood, (lag@ ))I ,- :i In the past two vears or so [ have seen a numt)er of {papers and hCar(t ~ m:m, ber of talks describing the char- ;iaeteristies~,- of (m~d ~:he wonders inherent in) certain com- puters like Gamma 60, Ln,~c, H-8(X), STm!:TC,, and others. Of course, all these machines share a capacity for parallel asynehronous multiple processing. Now this is a '~truly marvelous property, especially from the point of ii ;view of the common variety of "my-job's-on-the-machine- ( " . , ..,, keep-your-c ~tton-pmkm -hands-off programmer. However, it appears to rne that the application of the i multi-program technique, in any manner which ap- proaches the true capacity of the hardware, creates some • • • }. • r~ , - headaches of imposing magmtude. [tm most obwous problem is how to prevent one code from mutilating not 0nly itself but any of the other half-dozen or so programs currently sharing the main memory. Although much has been said and written about the i solution of this and other problems (e.g., accounting and I scheduling) associated with such multi-proeessors, I have yet to heat' of anyone who has found a reasonable solution h~lt ol the problem of mutual code-mutilation, or even has raueh faith that a solution actually exists on a particular i computer. ! Furthermore, I do not believe that the policy of restriet- ,i 'in" " " , "r" " " " :I g multi-processing aet~x lty to produetmn programs is ~i a wholly satisfaetory solution. Being an experienced i programmer, I know how hard it, is to get all the bugs out of a large program, and I know of very few large programs that will not run wild when particular (incorrect) data sets are submitted to them. So I say there always exists the spectre, however faint, of even "produetion" programs killing each other. Therefore I offer the following hardware scheme, for what, it is worth. It does riot solve all the problems, but I believe it does move the solutions to the biggest ones within the reach of the programmer. i Assume a system of n processors, operating in parallel and sharing a common fast-access memory with binary address logic. Allow one processor, called the Monitor (M), access to i all of storage. Then allocate storage to the remaining n- 1 processors (A, B, C, "..) according to the following iiseheme: Assign tit(; leftmost n - 1 bits of the address as allocation selectors so that it tim. ith bit isal, the ith p'toeessc;;s,.n, has access to th'tt (tell, and it' that bit is a O, that cell is not availltble to the ith processor. ] For example,/t 32-K memory would be used by ibm" )ilpr°cessors in the following t'ashion: -t-K Module Processors using this module 000 M 001 M, A 010 M, B 011 M, A, B 100 M, C 101 M, A, C 110 M, B, C 1 ll M, A, B, C Consequences of this scheme would be: 1. One module of storage would be unassailable by processors A, B, C. Similarly, one module accessible to A could not be ruined by programs on processors B and C; and so forth. 2. Each of A, B, C would have access m half of storage. 3. Any of the processors could communicate with any others through the appropriate module. 4. Any priority method (that I have been able m dream up) can be handled easily within this scheme. (But of course I don't have a really objective point of view.5 5. The scheme would, I believe, allow parallel execution of programs which use dynamic storage allocation (e.g., list togie) without resorting to the use of the Monitor as referee, and wi~h a minimum of headaches. A variant of this scheme would be to allow free use of memory for readout, and use the memory allocation seheme to restrict writing only. This would keep the safety features intaet and allow freer communication between processors, but would complicate to some degree the task of storage assignment programs such as Com- pilers and Assemblers. There are problems in this scheme (such as address eomputation involving eomplements) which I have not, even attempted to solve. My hope is that the presentation of this seheme, complete with fallacies, will jar someone into finding a really good solution. ACM Compiler Symposium On Thursday and Friday, November 17-18 an Open Tutorial Symposium on Compiler Construction will be held at the National Bureau of Standards, Washington, D. C. under the sponsorship of the ACM Programming Language Committee. Writers of scientific- and business-oriented language com- pilers will present detailed explanations of the more in- teresting features of their compilers, and new techniques will be discussed. The papers are intended primarily for experienced programmers who are interest, ed in compiler design. M1 papers will be published either in an ACM monograph or in the Communications. No registrat.ion fee; attendees please make own housing arrangements. Programs available upon re.. quest to J. Wegstein, NBS Comnnlnications of tile XCM 539 ~ i ¸ i; ¸! l
`
`AA/SWA Ex. 1009, p.1 of 1
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`
