FLYNN:COMPUTER ORGANIZATIONS 949 1)The single-instruction stream-single-data stream anticipate a hierarchy of requests,where the transition organization (SISD),which represents most conven- between the initiating level p and the next level tasks tional computing equipment available today. R:is viewed as the logical role of each of the Ri,while 2)The single-instruction stream-multiple-data actual service is through a combination of a tree of stream (SIMD),which includes most array processes, lower level logical requests and eventual physical ser- including Solomon [2](Illiac IV). vice at the leaves of the tree 3)Multiple-instruction stream-single-data stream Thus consider type organizations (MISD),which include specialized f(x,T）→(y,*) streaming organizations using multiple-instruction streams on a single sequence of data and the derivatives where f is a functional mapping (in a mathematical thereof.The plug-board machines of a bygone era were sense)of argument x into result y.Here,x,yEB,where a degenerate form of MISD wherein the instruction B is the set of values defined by the modulo class of the streams were single instructions,and a derived datum arithmetic (logical and physical notions of arithmetic (SD)passed from program step i to program step i+1 should be identical).Ther and r*indicate logical time (MI). or precedence;T is a Boolean control variable whose 4)Multiple-instruction stream-multiple-data stream validity is established by one or more predecessor logical (MIMD),which include organizations referred to as functionsf. "multiprocessor."Univac [3],among other corpora- The requirement for a r control variable stems from tions,has proposed various MIMD structures. the need for specification of the validity of f and its These are qualitative notations.They could be quan-argument x.Notice that two tasksf,f are directly tified somewhat by specifying the number of streams of dependent if either r:=1 implies r;*=1 or rj=1 implies each type in the organization or the number of instruc- r:*=1.This precedence specification may be performed tion streams per data stream,or vice versa.But in order implicitly by use of a restrictive convention (e.g.,by to attain a better insight into the notions of organiza- strict sequence)-that the physical time t at which the tion,let us formalize the stream view of computing.ith task control variable r:becomes valid,t(:=1),has Consider a generalized system model consisting of a (r:=1)>t(ri1*=1),for all ior by explicit control of reguestor and a server.For our purposes we will con- T and r*. sider the requestor as synonymous with a program(or That there can be no general way of rearranging the user)and the server as synonymous with the resources, request sequence f(or finding an alternate sequence both physical and logical,which process the elements of g)such that the precedence requirement vanishes,is a the program.Note that,for now,the distinction be- consequence of the composition requirement f(g(x)), tween a program and a resource is not precise;indeed, intrinsic to the definition of a computable function. under certain conditions a resource may be a program That is,f cannot be applied to an argument until g(x) and vice versa.Then a problem can be defined as a has been completed. stream (or sequence)of requests for service (or re- The notion of an explicit precedence control has been sources).Since each request is,in general,a program and formalized by Leiner 16 and others by use of a prece- can also specify a sequence of requests,we have a re- dence matrix. quest hierarchy. Given an unordered set of requests (tasks) Let p be a program.A program is defined simply as a f1<jn,an nXn matrix is defined so that:ai=1 request for service by a structured set of resources.P if we require t(;=1)2t(*=1),i.e.,task f must be specifies a sequence of other(sub)requests:Ri,R2,R3,completed before f;can be begun.Otherwise,=0. R,···,Ru,called tasks.While the tasks appear here The matrix M so defined identifies the initial priority. as a strictly ordered set,in general the tasks will have a By determining M2(in the conventional matrix product more complex control structure associated with them. sense),secondary implicit precedence is determined. Each request,again,consists of a sequence of sub- This process is continued until requests (the process terminates only at the combi- MP+1=0: national circuit level).Regardless of level,any request R:is a bifurcated function having two roles: The fully determined precedence matrix H is defined as R=f,f H=M+M2+M3+···+MP,P≤ the logical role of the requestor f and the combined where is the Boolean union operation:(a+b) logical and physical role of a server f. =a十b: 1)Logical Role of Reguestor:The logical role of the Thus HI defines a scheduling of precedence among the requestor is to define a result given an argument and to n tasks.At any moment of logical time(T),perhaps a define a control structure or precedence among the other set of tasksf;k either a,=0,for all j,or if a=1, tasks directly defined by the initiating program P.We then 7,*=1 are independently executable.FLYNN: COMPUTER ORGANIZATIONS 949 1) The single-instruction stream-single-data stream anticipate a hierarchy of requests, where the transition organization (SISD), which represents most conven- between the initiating level P and the next level tasks tional computing equipment available today. { Ri } is viewed as the logical role of each of the Ri, while 2) The single-instruction stream-multiple-data actual service is through a combination of a tree of stream (SIMD), which includes most array processes, lower level logical requests and eventual physical ser￾including Solomon [2] (Illiac IV). vice at the leaves of the tree. 3) Multiple-instruction stream-single-data stream Thus consider type organizations (M ISD), which include specialized fAx, r) (y r* streaming organizations using multiple-instruction streams on a single sequence of data and the derivatives where fil is a functional mapping (in a mathematical thereof. The plug-board machines of a bygone era were sense) of argument x into result y. Here, x, y&B, where a degenerate form of MISD wherein the instruction B is the set of values defined by the modulo class of the streams were single instructions, and a derived datum arithmetic (logical and physical notions of arithmetic (SD) passed from program step i to program step i+1 should be identical). The r and T* indicate logical time (MI). or precedence; r is a Boolean control variable whose 4) Multiple-Instruction stream-multiple-data stream validity is established by one or more predecessor logical (MIMD), which include organizations referred to as functions {fii }. "multiprocessor." Univac [3], among other corpora- The requirement for a r control variable stems from tions, has proposed various 'M\IIMD structures. the need for specification of the validity of fil and its These are qualitative notations. They could be quan- argument x. Notice that two tasks fil, fj1 are directly tified somewhat by specifying the number of streams of dependent if either 7i= 1 implies Tj* = 1 or rj = 1 implies each type in the organization or the number of instruc- ri* = 1. This precedence specification may be performed tion streams per data stream, or vice versa. But in order implicitly by use of a restrictive convention (e.g., by to attain a better insight into the notions of organiza- strict sequence)-that the physical time t at which the tion, let us formalize the stream view of computing. ith task control variable Tr becomes valid, t(r = 1), has Consider a generalized system model consisting of a t(Tr = 1) . t(Ti1* = 1), for all i-or by explicit control of requestor and a server. For our purposes we will con- r and r*. sider the requestor as synonymous with a program (or That there can be no general way of rearranging the user) and the server as synonymous with the resources, request sequence fil (or finding an alternate sequence both physical and logical, which process the elements of gi') such that the precedence requirement vanishes, is a the program. Note that, for now, the distinction be- consequence of the composition requirement f(g(x)), tween a program and a resource is not precise; indeed, intrinsic to the definition of a computable function. under certain conditions a resource may be a program That is, f cannot be applied to an argument until g(x) and vice versa. Then a problem can be defined as a has been completed. stream (or sequence) of requests for service (or re- The notion of an explicit precedence control has been sources). Since each request is, in general, a program and formalized by Leiner [16] and others by use of a prece￾can also specify a sequence of requests, we have a re- dence matrix. quest hierarchy. Given an unordered set of requests (tasks) Let P be a program. A program is defined simply as a {fjl' 1 j <n}, an n Xn matrix is defined so that: ai3= 1 request for service by a structured set of resources. P if we require t(Tj = 1) > t(ri* = 1), i.e., task fi must be specifies a sequence of other (sub) requests: R1, R2, R3, completed beforefj can be begun. Otherwise, aij,=0. R4, - , RnsR called tasks. While the tasks appear here The matrix M so defined identifies the initial priority. as a strictly ordered set, in general the tasks will have a By determining M2 (in the conventional matrix product more complex control structure associated with them. sense), secondary implicit precedence is determined. Each request, again, consists of a sequence of sub- This process is continued until requests (the process terminates only at the combi￾national circuit level). Regardless of level, any request MP±= 0. Ri is a bifurcated function having two roles: The fully determined precedence matrix H is defined as R- fuly Hd=eM+rM2i+eM3 +p.e.e.n+eMa, P < n the logical role of the requestor f si and the combined where + is the Boolean union operation: (a +b)~ logical and physical role of a serverfiv. a+b. 1) Logical Role of Requestor: The logical role of the Thus H defines a scheduling of precedence among the requestor is to define a result given an argument and to n tasks. At any moment of logical time (ri), perhaps a define a control structure or precedence among thle other set of tasks {fk'; k |eithler ack = 0, for all j, or if aj = 1, tasks directly defined by the initiating program P. We then Tj*-=1 } are independently executable