952 IEEE TRANSACTIONS ON COMPUTERS,SEPTEMBER 1972 Thus from this most general point of view there is little. difference in the resolution of entropy in space or time. The reader will note,however,that space resolution is not necessarily as effcient as time sequences.In fact,the N/2 number of time sequence operations Ne is a linear func- tion of input size n: N:=k+2 % 2xt洛骆2 while Muller 32 has shown that for combinational Fig.3."Parallelism"in problems. circuits of arbitrary functional basis a measure for the number of circuits required N.is serve as input data.The program or algorithm operates 2n 2n on this input data and produces output results corres- k1一≤N。≤k2 ponding to N2 words each of p bits.If we presume that as a maximum each of the input bits could affect each where n is the number of input lines.See Cook [33]and of the bits in the output,then there are NiXp bits of Cook and Flynn 34 for a more general and complete uncertainty or entropy which specify an output bit. treatment of space-time functional measures.Later in Thus a table-oriented solution algorithm (i.e.,generate this paper we will discuss similar inefficiencies in parallel a table of solutions-one solution for each input combi- SIMD processors. nation)requires 2DNentries and uses N2 bits per entry. The total number of bits required is pN22pN. Recursive Functions We could generalize this for variable length input and Substantial difficulties arise when the preceding "gen- output by treating Na and Ni as the maximum number eral point of view"is reduced to the specific.In particu- of words required to specify output or input informa-lar,the class of functions for which arbitrary "space- tion.Note that this imposes a limit on the size of output time"transformations can be developed is not equiva- strings,and hence the table algorithm is too restrictive lent to the class of all recursive(computable)functions. for generalized computable functions.However,within Recursion (in Kleene's sense [7])is based on the appli- this restricted class the entropy O to be resolved by an cation of the composition operation on a finite set of algorithm is initial functions.This composition operation 8]is the pN2≤Q≤pN22pw1. association of functions h(Xi,Xg,···,Xn)with F(X,··,X,g1(X,··,X)g2(X,··,X, The lower bound also needs special interpretation for ···,gn(Xi,···,Xn,so that(Xi,···,Xm) trivial algorithms (e.g.,strings of identical ones);the =F(g1(Xi,···,Xn),···,gn(X,···,Xn).Clearly, pN2 bits were assumed to be independently derived. the application of F on the results of g:is a sequential Hence the N2 bits must be reduced by their depen- operation.Any general attempts to resolve the func- dency.(See Kolmogarov [10]for an alternate notion on tional entropy without such sequential (time)depen- the specification of Q.) dence leads to "recursion"based on infinite sets of initial In any event,O bits of uncertainty must be resolved. functions. This resolution may be performed in space or time. Bernstein [9]has developed three (rather strong) Typically it is resolved in space by combinatorial logic. sufficient conditions for two programs to operate in Each decision element may resolve between zero and parallel based on the referencing of partitions of storage. one bit of information depending upon the associated As in the preceding discussion,these conditions specify probabilities of the binary outcomes.Usually a useful limitations on the interactions between programs. repertoire or vocabulary of logical decisions is available Notice that none of the foregoing serves to limit the to an instruction stream.Let an element of the vocabu-capability of a processor organized in a parallel fashion lary consist of M decisions.Depending upon the type of to perform computation,but rather serves as a limit operation to be performed,these execution unit decision on the efficiency of such an operation.Also note that the elements resolve less than M bits of information;thus composing function F may induce similar inefficiencies Q≤m'MN, in a confluent simplex processor (depending on the nature of F and the last g:to be evaluated).Such per- where m'is the number of data stream execution units formance degradation will be discussed later.The com- and N.is the number of time operations that were used position mechanism that causes a problem here is an (i.e.,number of sequential instructions).In order to interprogram action,while the stream inertia difficulty retire the complete algorithm,of course,a sequence of occurs more prominently in purely intraprogram condi- operations is performed to execute the instruction tional actions.Indeed,there are techniques for the stream;each operation in the sequence resolves or ex- elimination of branches in simple programs by use of ceeds the required amount of entropy for a solution.Boolean test variables (0 or 1)operating multiplica-952 IEEE TRANSACTIONS ON COMPUTERS, SEPTEMBER 1972 Thus from this most general point of view there is little. . difference in the resolution of entropy in space or time. .4 [\ The reader will note, however, that space resolution is not necessarily as efficient as time sequences. In fact, the NlR' \^|t/2 number of time sequence operations Nt is a linear func￾tion of input size n: _ _ _ _ Nt = k-n too °%of ptublem requzefxq iv sequent4a7 executw# while Muller [32] has shown that for combinational Fig. 3. "Parallelism" in problems. circuits of arbitrary functional basis a measure for the number of circuits required N, is serve as input data. The program or algorithm operates 2" 2" on this input data and produces output results corres- k1-. Ns . k2 - ponding to N2 words each of p bits. If we presume that as a maximum each of the input bits could affect each where n is the number of input lines. See Cook [33] and of the bits in the output, then there are NjXp bits of Cook and Flynn [34] for a more general and complete uncertainty or entropy which specify an output bit. treatment of space-time functional measures. Later in Thus a table-oriented solution algorithm (i.e., generate this paper we will discuss similar inefficiencies in parallel a table of solutions-one solution for each input combi- SIMD processors. nation) requires 2PN1 entries and uses pN2 bits per entry. The total number of bits required is pN22PN1. We could generalize this for variable length input and Substantial difficulties arise when the preceding "gen￾output by treating N2 and N1 as the maximum number eral point of view" is reduced to the specific. In particu￾of words required to specify output or input informa- lar, the class of functions for which arbitrary "space￾tion. Note that this imposes a limit on the size of output time" transformations can be developed is not equiva￾strings, and hence the table algorithm is too restrictive lent to the class of all recursive (computable) functions. for generalized computable functions. However, within Recursion (in Kleene's sense [7]) is based on the appli￾this restricted class the entropy Q to be resolved by an cation of the composition operation on a finite set of algorithm is initial functions. This composition operation [8] is the pN2 Q < pN2.2PN1. association of functions h(X1, X2, , Xn) with - - ~~~~~~~~F(Xlt* X,), gl(XI,* Xn), g2(X17 . , Xn) i The lower bound also needs special interpretation for , gn(Xl, , Xn), so that h(X1, , Xj) trivial algorithms (e.g., strings of identical ones); the =F(gi(Xj, Xn), , gn(Xl, Xn)). Clearly, pN2 bits were assumed to be independently derived. the application of F on the results of gi is a sequential Hence the pN2 bits must be reduced by their depen- operation. Any general attempts to resolve the func￾dency. (See Kolmogarov [10] for an alternate notion on tional entropy without such sequential (time) depen￾the specification of Q.) dence leads to "recursion" based on infinite sets of initial In any event, Q bits of uncertainty must be resolved. functions. This resolution may be performed in space or time. Bernstein [9] has developed three (rather strong) Typically it is resolved in space by combinatorial logic. sufficient conditions for two programs to operate in Each decision element may resolve between zero and parallel based on the referencing of partitions of storage. one bit of information depending upon the associated As in the preceding discussion, these conditions specify probabilities of the binary outcomes. Usually a useful limitations on the interactions between programs. repertoire or vocabulary of logical decisions is available Notice that none of the foregoing serves to limit the to an instruction stream. Let an element of the vocabu- capability of a processor organized in a parallel fashion lary consist of M decisions. Depending upon the type of to perform computation, but rather serves as a limit operation to be performed, these execution unit decision on the efficiency of such an operation. Also note that the elements resolve less than M bits of information; thus composing function F may induce similar inefficiencies Q<m'MAT, - in a confluent simplex processor (depending on the ~~~~~~nature of F and the last gi to be evaluated). Such per￾where m' is the number of data stream execution units formance- degradation will be discussed later. The com￾and N1 is the number of time operations that were used position mechanism that causes a problem here is an (i.e., number of sequential instructions). In order to interprogram action, while the stream inertia diffculty retire the complete algorithm, of course, a sequence of occurs more prominently in purely intraprogram condi￾operations is performed to execute thae instruction tional actions. Indeed, there are techniques for the stream; eachl operation in the sequence resolves or ex- elimination of branches in simple programs by use of ceeds thae required amount of entropy for a solution. Boolean test variables (0 or 1) operating multiplica-