=. as onnnt AND NETWORK PROPERTIES a 63 between SI and $5. 95 PROGRAM FLOW MECHANISMS Mery pe computers ire built using the conventional Von Neumann architecture Ce a caduen Iding block. These parallel computers put the entire burden of srallelising @ procedure on the programmer. A programmer has to understand the uaderlying architecture of the parallel computer to write efficient parallel programs. The systems do not attack the issue of parallelism at a fundamental level. The data flow approach to computing considers the issue of parallelism as its foundation. It proposes ynew machine language which offers a powerful formalism for describing parallel computation ata fine grain level. Reduction computers are based on a demand driven mechanism. It initiates an operation based on the demand for its results by other computations. We discuss each of these now, 26 CONTROL FLOW, DATA FLOW AND REDUCTION COMPUTERS We have three categories of computers : {@) Control flow computers (or Von Neumann Computers) (b} Data flow Computers. {) Reduction Computers. We shall describe each of them one by one. |. Control flow or Von Neumann's Conventional Computers These computers use a program counter (PC) to sequence the execution of instructions ina program. These machines are also called as control-driven machines because the Program flow is explicitly controlled by programmers. ‘These computers use shared-memory data. Instructions operate on variables in shared tostore program instructions as well as i r memory. Because the memory is shared so execution of one instruction may produce side tllecls sar ether instructions too. This is not preferable as it prohibits parallelism, These systems are uniprocessor system ‘and are sequential machines /.¢., exciton of instructions lake place from: left to sight and top to bottom. However, note that these contol flow machines can be made parallel by using parallel language constructs or parallel computers, For example : 8085 CPU, 8086 CPU, Pentium-IV work on control flow mechanism. ". Data Flow Computers/Data-driven Computers/Eager Machine, These machi eager for data to be present. If it is presentthen the instruction Seen es ar tors ae thus known as data diriven computers or eager machines. Ina date tee comput he jnstructions are not ordered. There is 10 shared memory. riven programy ctions. The results or data tokens are passed directly Th i epee ata is stored inside inst ae ata is passed t0 Instructions. If an instruction a copy J are not available for reuse by other . en the instructions. Actually, ns consumed these data token thi tuctions. In these computers thi * No shared memory. ere 1S No Program Counter (PC)64 ADVANCED COMPUTER ARCHITECT 3 © No Control Sequencer. . Since there is no memory sharing so there are no side ites seen here a computers require is that they should be able to detect at s presences or eat te tokens with the needy instructions and to enable the ¢ ati reaction ov anya Fonoy instruction executions. We shall be discussing about these bt ater He wet eoee, that a pure data flow computer exploits fine grain paralleli 7 level, What is a data flow program graph ? A machine language program of a data flow compute a . is represented by_a data flow. program graph. This grap! is made up of operators connected by arcs. Arcs carry tokens which have values. An operator with two input acs and one output arc is shown below in Fig. 2.6. The operator of Fig, 2.6 is enabled: only if tokens are presen in both its input ares and no token is present in lS 9 6 a data ow opty output arc. Tokens are placed on and removed from the ares according to the firing rules. To explain the firing rule, let us say @ = 5 and b = 6 in above Fig. 2.6. Then, we have : a=5 Y b=6 4 (after firing) ‘e ee (a+b) " Fig. 2.7. Firing rules Please note that here, an operator fires, i.c., the tokens in the two input arcs are removed, the operation (+) is applied on the values carried by the tokens and a token with the result value is placed on the output arc. This is what exactly happens in this example. We solve a problem now. Example 1, Draw a data flow graph to compute the expression given below : (x+y) (xy)? Solution. Here, x and y ce are two operands and there are 3 operators (+, ~,*), We draw now! x y tye GayADVANCED COMPUTER ARCHITEgy, Re 66 Other operators used in Data flow graph ¢ 1. Fork. A fork looks like this + => Fig. 2.8, Fork operation ea token arrives on the input arc His copied in gg In this notation, as soon a: ‘e of its output arcs; as shown in Fig. 2.8. 2. Function. Fig, 2.9. depicts a function. abe | | f a f ToT Fig, 2.9. Function operation — Herein, after the tokens arrive on all the input arcs, this operator fires and the result token is placed on the output arc. 3. True gate, A true gate is shown in Fig. 2.10. x Control ome > o- (Case-l) x x F > (Casertt) Fig. 2.10. True gate Ce ives a Tree pave: on the control are of this graph aml! are. , the gate fires and ‘x’ is transmitted to the ou Case Il. When a "false" token (E) arti ‘ arrives o: beet the input are, then the gate fies with no token ee omeol are and on tokens on the input arc are destroyed on the output arc. Both 2"{gost WAND NETWORK PROPER TEs Thus, we can draw a 7 'rue gate operation table as follow: § i Ss input Content Status of ee the operator Datpae Remarks Nil are x . Not fired Nil Not fired Nil Waiting for inputs Nil F Not fired Nil Waiting for input nil Not fired Na Waiting for input a fired Nil Waiting for control F fired Mi x and T consumed i x and F consumed 4, False gate. A false gate is shown in Fig, 2.11, Oh = ¢ (Cases) > Fig. 2.11. False gate Fig. 2. 11, works in a similar fashion. It fires when token both arrive. F then the input token is transmitted to the output. both input and control tokens are destroyed A false gate shown above in an input token and a control Case - I. If the control token is Case — II. If the control token is T then and no output token appears. 5. Merge. A merge operator is shown below in Fig. 2.12. y => Li (cases) F x T } 1 Fig. 2.12. Merge operatoros ADVANCED COMPUTER ARCHITECT. 68 is seen in Fig, 2.12, that depending on whether the eee tees ate is Tor F, the input token from the appropriate are a Feito fel. The fives Ih token on the input arc which is not selected in not dlestroyec’- 8 Teles of the merge-operator as listed below + — Input Input Control Status of Output Remarks T are Fare are operation ae Nil Nil Nil Not fired Nil Nil Nil T Not fired Nil Nil Nil E Not fired Nil Nil v T Not fired Nil Nu y . fired y Both x and Nil y Nil Not fired Nil y are not es Nil T fired x destroyed x Nil F Not fired Nil x y i fired * x y F fired y x Nil Nil Not fired Nil a y Nil Not fired Nil 6. Predicate. A predicate operator is shown below in Fig. 2.13. Thé values of the token in the two input arcs are compared by the predicate operator. x y i> y then else T F x if Poo then else T F Fig. 2.13. Predicate operator A T(true) or Flfalse) token is pl Sea piles ot, Paced on the output are based on whether thePedicate, merge and switch Bie AMiand NETWORK PROPERTIES, switch. 9 switch is not a new * . " opel & Shown below in Fig, 214, Po"™#0" It is a combination of T and F gates as con (a switch) Fig. 2.14, Switch operator The notation in concise is shown as a switch, How it works ? Case - I. When x appears on the input arc and the control arc receives T then x appears on the T branch of the switch as an output. Case - IL. => —G») x Similarly, when x appears on the input arc and F appears on the control arc then by ars a ut arc. Not hove tat a eh eet anew operator. Itis actually a combination of T and F gates. We are now in a position to solve some problems now. Example 1. Consider the following statements : ifx>y then -y) else (x*y) endif Draw its data flow graph ? Solution, Herein, we have used ‘ators to implement the statement.