FLYNN:COMPUTER ORGANIZATIONS 957 SIMD.In fact,we have returned to the overlapped SISD. 4E=,025 MIMD and Its Effectiveness The multiple-instruction stream organizations (the LE-.050 "multiprocessors")include at least two types. 1)True Mulliprocessors:Configurations in which sev- N:dId eral physically complete and independent SI processors /E气.200 share storage at some level for the coopertive execution 0 40 of a multitask program. Number of processors 2)Shared Resource Multiprocessor:As the name im- plies,skeleton processors are arranged to share the sys- Fig.8.MIMD lockout. tem resources.These arrangements will be discussed later. where T:;is the communications time discussed earlier Traditional AIIMD organizational problems include: and pi is the probability of task j accessing data from 1)communications/composition overhead;2)cost in- data stream i.Note that the lockout here may be due to creases linearly with additional processors,while per- the broader communications problem of the jth proces- formance increases at a lesser rate (due to interference); sor requesting a logical data stream i.This includes the and 3)providing a method for dynamic reconfiguration physical data stream accessing problem as well as addi- of resources to match changing program environment, tional sources of lockout due to control,allocation,etc. (critical tasks)-this is related to 1). In any event,Madnick [11]used a Markov model to Shared resource organization may provide limited derive the following relationship: answers to these problems,as we will discuss later. (-1) 1 Communications and composition is a primary source (idle)= of degradation in MI systems.When several instruction E E streams are processing their respective data streams on a common problem set,passing of data points is inevit- able.Even if there is naturally a favorable precedence where (idle)is the expected number of locked-out pro relationship among parallel instruction streams insofar cessors and n is the total number of processors.If a as use of the data is concerned,composition delays may single processor has unit performance,then for n pro- ensue,especially if the task execution time is variable cessors The time one instruction stream spends waiting for data perf.=n-8 (idle) to be passed to it from another is a macroscopic form of the strictly sequential problem of one instruction and normalized performance (max=1)is given by waiting for a condition to be established by its immedi- n-8 (idle) ate predecessor. perf. Even if the precedence problem (which is quite pro- gram dependent)is ignored,the "lockout"problem asso- Fig.8 is an evaluation of the normalized performance as ciated with multiple-instruction streams sharing com- the number of processors (instruction stream-data mon data may cause serious degradation.Note that stream pairs)are increased for various interaction ac- multiple-instruction stream programs without data tivity ratios L/E. sharing are certainly as sterile as a single-instruction Regis [15]has recently completed a study substan- stream program without branches. tially extending the simple Markovian model previously Madnick 11 provides an interesting model of soft- described (homogeneous resources,identical processors, ware lockout in the MIND environment.Assume that etc.)by developing a queuing model that allows for an individual processor (instruction stream control unit) vectors of requests to a vector of service resources.Leh- has expected task execution time (without conflicts)of man [30]presents some interesting simulation results E time units.Suppose a processor is "locked out"from related to the communications interference problem. accessing needed data for L time units.This locking out Since shared resource MIMD structures provide some may be due to interstream communications(or accessing) promising (though perhaps limited)answers to the AII problems (especially if the shared storage is an I/O problems,we will outline these arrangements.The exe- device).Then the lockout time for the ith processor (or cution resources of an SISD overlapped computer (ad- instruction stream)is ders,multiplier,etc.-most of the system exclusive of registers and minimal control)are rarely efficiently used, L,=∑pT as discussed in the next section. In order to effectively use this execution potentialFLYNN: COMPUTER ORGANIZATIONS 957 SIMD. In fact, we have returned to the overlapped SISD. \/IE=.025 AfIMD and Its Effectiveness The multiple-instruction stream organizations (the \L/Ex.05o "multiprocessors") include at least two types. \ 1) True Multiprocessors: Configurations in whiclh sev￾eral physically complete and independent SI processors L/-z20 share storage at some level for the coopertive execution ; 40 of a multitask program. Number0fprocessors 2) Shared Resource Multiprocessor: As the name im￾plies, skeleton processors are arranged to share the sys- Fig. 8. MIMD lockout. tem resources. These arrangements will be discussed later. where Tij is the communications time discussed earlier Traditional :AIIi\I[D organizational problems include: and pij is the probability of task j accessing data fronm 1) comnmunications/composition overhead; 2) cost in- data stream i. Note that the lockout here may be due to creases linearly with additional processors, Nwlaile per- the broader communications problem of the jth proces￾formance increases at a lesser rate (due to interference); sor requesting a logical data streamn i. This includes the and 3) providing a method for dynamic reconfiguration plhysical data stream accessing problem as wvell as addi￾of resources to match changing program environment, tional sources of lockout due to control, allocation, etc. (critical tasks)-this is related to 1). In any event, i\Iadnick [11 ] used a \'i\arkov model to Shared resource organization may provide limited derive the following relationship: answers to these problems, as we will discuss later. n 1) n1 Communications and composition is a primary source 8 (idle) = E --- - / - - - of degradation in 14I systems. When several instruction i=2 (n-i) !E/ (E - streams are processing their respective data streams on L\L/ a common problem set, passing of data points is inevit￾able. Even if there is naturally a favorable precedence w relationship among parallel instruction streams insofar cessors and n is the total number of processors. If a as use of the data is concerned, composition delays may single processor has unit performance, then for n pro￾ensue, especially if the task execution time is variable. cessors The timie one instruction stream spends wvaiting for data perf. = n - 8 (idle) to be passed to it from another is a macroscopic form of the strictly sequential problem of one instruction waiting for a condition to be establislhed by its immedi- n - 8 (idle) ate predecessor. perf.N -n Even if the precedence problem (whiclh is quite pro￾graml- dependent) is ignored, the "lockout" problem asso- Fig. 8 is an evaluation of the normalized performiiance as ciated witlh multiple-instruction streams slharing coni- the number of processors (instruction stream-data mon data nmay cause serious degradation. Note that stream pairs) are increased for various interaction ac￾multiple-instruction stream programs without data tivity ratios LIE. sharing are certainly as sterile as a single-instruction Regis [15] has recently completed a study substan￾stream progranm witlhout branclhes. tially extending the simple M.Iarkovian model previously i\ladnick [1Fl ] provides an interesting nmodel of soft- described (homogeneous resources, identical processors, ware lockout in the llIIS\ID environmzent. Assume tlhat etc.) by developing a queuing miodel that allows for an individual processor (instruction stream control unit) vectors of requests to a vector of service resources. Lelh￾hlas expected task execution time (witlhout conflicts) of man [30] presents some interesting simulation results E time units. Suppose a processor is "locked out" fronm related to the communications interference problenm. accessing needed data for L tie units. This locking out Since shared resource II\ID structures provide som1-e mlay b)e due to interstream1 commnunications (or accessing) promising (thloughl perhlaps limlited) anlswers to thle ANllI problemas (especially if thae shaared storage is an I/O problem1s, wte w-ill outline thlese arrangemwents. Thle exe￾device). Th1en thle lockout timae for thle jthl processor (or cution resources of an SISD overlapped comlputer (ad￾instruction stream1) is ders, mlultiplier, etc. mo1St of thae system-1 exclusive of registers and mlinimlal control) are rarely efficiently uIsed, Lj =pfjTfj , = ,T,as discussed in thae next section. ~~~Inorder to effectively use thlis execution potenatiall