948 IEEE TRANSACTIONS ON COMPUTERS,VOL.C-21,NO.9,SEPTEMBER 1972 Some Computer Organizations and Their Efectiveness MICHAEL J.FLYNN,MEMBER,IEEE Abstract-A hierarchical model of computer organizations is more "macroscopic"view,yet without reference to a developed,based on a tree model using request/service type re- particular user environment.Clearly,any such effort sources as nodes.Two aspects of the model are distinguished:logical and physical. must be sharply limited in many aspects;some of the General parallel-or multiple-stream organizations are examined more significant are as follows. as to type and effectiveness-especially regarding intrinsic logical 1)There is no treatment of I/O problems or 1/O as a difficulties. limiting resource.We assume that all programs of inter- The overlapped simplex processor (SISD)is limited by data est will either not be limited by I/O,or the I/O limita- dependencies.Branching has a particularly degenerative effect. The parallel processors [single-instruction stream-multiple- tions will apply equally to all computer memory con- data stream (SIMD)]are analyzed.In particular,a nesting type figurations.That is,the I/O device sees a "black box" explanation is offered for Minsky's conjecture-the performance of computer with a certain performance.We shall be con- a parallel processor increases as log Mf instead of M (the number of cerned with how the computer attained a performance data stream processors). potential,while it may never be realized due to I/O con- Multiprocessors(MIMD)are subjected to a saturation syndrome siderations. based on general communications lockout.Simplified queuing models indicate that saturation develops when the fraction of task time spent 2)We make no assessment of particular instruction locked out(L/E)approaches 1/n,where n is the number of proces- sets.It is assumed that there exists a(more or less)ideal sors.Resources sharing in multiprocessors can be used to avoid set of instructions with a basically uniform execution several other classic organizational problems time-except for data conditional branch instructions Index Terms-Computer organization,instruction stream,over- whose effects will be discussed. lapped,parallel processors,resource hierarchy. 3)We will emphasize the notion of effectiveness (or efficiency)in the use of internal resources as a criterion INTRODUCTION for comparing organizations,despite the fact that either TTEMPTS to codify the structure of a computer condition 1)or 2)may dominate a total performance have generally been from one of three points of assessment. Within these limitations,we will first attempt to view:1)automata theoretic or microscopic; 2)individual problem oriented;or 3)global or statisti- classify the forms or gross structures of computer sys- tems by observing the possible interaction patterns cal. between instructions and data.Then we will examine In the microscopic view of computer structure,rela- tionships are described exhaustively.All possible inter- physical and logical attributes that seem fundamental to achieving efficient use of internal resources (execution actions and parameters are considered without respect to their relative importance in a problem environment facilities,memory,etc.)of the system. Measurements made by using individual problem CLASSIFICATION:FORMS OF COMPUTING SYSTEMS yardsticks compare organizations on the basis of their Gross Structures relative performances in a peculiar environment.Such comparisons are usually limited because of their ad hoc In order to describe a machine structure from a nature. macroscopic point of view,on the one hand,and yet Global comparisons are usually made on the basis of avoid the pitfalls of relating such descriptions to a par- elaborate statistical tabulations of relative performances ticular problem,the stream concept will be used [1]. on various jobs or mixtures of jobs.The difficulty here Stream in this context simply means a sequence of items lies in the fact that the analysis is ex post facto and usu- (instructions or data)as executed or operated on by a ally of little consequence in the architecture of the sys- processor.The notion of“instruction”or“datum”is tem since the premises on which they were based (the defined with respect to a reference machine.To avoid particular computer analyzed)have been changed. trivial cases of parallelism,the reader should consider a The object of this paper is to reexamine the principal reference instruction or datum as similar to those used interactions within a processor system so as to generate a by familiar machines (e.g.,IBM 7090).In this descrip- tion,organizations are categorized by the magnitude Manuscript received February 26,1970;revised May 25,1971, (either in space or time multiplex)of interactions of and January 21,1972.This work was supported by the U.S.Atomic their instruction and data streams.This immediately Energy Commission under Contract AT(11-1)3288. gives rise to four broad classifications of machine or- The author is with the Department of Computer Science,The Johns Hopkins Cniversity,Baltimore,Md.21218. ganizations.948 IEEE TRANSACTIONS ON COMPUTERS, VOL. c-21, NO. 9, SEPTEMBER 1972 Some Computer Organizations and Their Effectiveness MICHAEL J. FLYNN, MEMBER, IEEE Abstract-A hierarchical model of computer organizations is more "macroscopic" view, yet without reference to a developed, based on a tree model using request/service type re- particular user environment. Clearly, any such effort sources as nodes. Two aspects of the model are distinguished: logical m ustb shr limitedtim anyasc somefoft and andphysical. ~~~~~~~mustbe sharply limited In many aspects; some of the physical. mr infcn r sflos General parallel- or multiple-stream organizations are examined more significant are as follows. as to type and effectiveness-especially regarding intrinsic logical 1) There is no treatment of I/O problems or I/O as a difficulties. limiting resource. We assume that all programs of inter￾The overlapped simplex processor (SISD) is limited by data est will either not be limited by I/O, or the I/O limita￾dependencies. Branching has a particularly degenerative effect. * w The parallel processors [single-instruction stream-multiple- tionsawill ap eul to all c e me mory con- data stream (SIMD)J are analyzed. In particular, a nesting type figurations That is, the I/O device sees a "black box" explanation is offered for Minsky's conjecture-the performance of computer with a certain performance. We shall be con￾a parallel processor increases as log M instead of M (the number of cerned with how the computer attained a performance data stream processors). potential, wThile it may never be realized due to I/O con￾Multiprocessors (MIMD) are subjected to a saturation syndrome siderations. based on general communications lockout. Simplified queuing models We t t indicate that saturation develops when the fraction of task time spent 2) \\e make no assessment of particular instruction locked out (L/E) approaches 1!, where n is the number of proces- sets. It is assumed that there exists a (more or less) ideal sors. Resources sharing in multiprocessors can be used to avoid set of instructions with a basically uniform execution several other classic organizational problems. time-except for data conditional branch instructions Index Terms-Computer organization, instruction stream, over- whose effects will be discussed. lapped, parallel processors, resource hierarchy. 3) We will emphasize the notion of effectiveness (or efficiency) in the use of internal resources as a criterion INTRODUCTION for comparing organizations, despite the fact that either ATTEIMPTS to codify the structure of a computer condition 1) or 2) may dominate a total performance lhave generally been from one of three points of assessment. view: 1) automata theoretic or microscopic; Witlhin these limitations, we will first attempt to .. . ..' ~~~~~~~~classify the forms or gross structures of computer sys- 2) individual problem oriented; or 3) global or statisti- y g y cal. tems by observing the possible interaction patterns In the microscopic view of computer structure,rela-between instructions and data. Then we will examine In the microscopic view of computer structure, rela- phscladogaltriuetatemfnaetl tionshis are escribd exliustivel. All ossibl inter physical and logical attributes that seem fundamental tionships are described exhlaustively. All possible inter-.. . to achieving efficient use of internal resources (execution actions and parameters are considered without respect fclte,mmr,ec)o h ytm to their relative importance in a problem environment. Measurements made by using individual problem CLASSIFICATION: FORMS OF COMPUTING SYSTEMS yardsticks compare organizations on the basis of their Gross Structures relative performances in a peculiar environment. Suclh comparisons are usually limited because of tlheir ad hoc In order to describe a machine structure from a nature. macroscopic point of view, on the one lhand, and yet Global comparisons are usually made on the basis of avoid the pitfalls of relating such descriptions to a par￾elaborate statistical tabulations of relative performances ticular problem, the stream concept will be used [1]. on various jobs or mixtures of jobs. The difficulty hiere Stream in this context simply means a sequence of items lies in the fact that the analysis is ex post facto and usu- (instructions or data) as executed or operated on by a ally of little consequence in the arclhitecture of the sys- processor. The notion of "instruction" or "datum" is tem since the premises on wvliclh they were based (the defined with respect to a reference machine. To avoid particular computer analyzed) have been changed. trivial cases of parallelism, the reader should consider a Tnhe object of thliS paper is to reexamine thle principal reference instruction or datum as similar to those used interactions withlin a processor system so as to generate a by familiar machines (e.g., IBMi 7090). In this descrip￾tion, organizations are categorized by thle magnitude Manscrpt ecive Feruay 6, 970 reisd My 2, 171 (either in space or time multiplex) of interactions of and January 21, 1972. This work was supported by the U.. S. Atomic their instruction and data streams. Thils immlediately Energy Commission under Conltract AT (11-1) 3288. gvsrs ofu ra lsiiain fmcln r The author is with the Department of Computer Science, The giersetforbadcsiiainsfmcheo￾Johns Hopkins UJniversity, Baltimore, M/d. 21218. ganizations