Scribd
Upload
31 views73 pages

PDS Notes

Uploaded by

Edu Free
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
31 views73 pages

PDS Notes

Uploaded by

Edu Free
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Chapter 1 INTRODUCTION 1.1 PARALLEL COMPUTING Over a period, beginning from ancient times, man has been consciously or otherwise building ‘complex systems. In these endeavors, he has often resorted to the employment of several people (workers) to cooperate and carry out a given task in a reasonable time, The idea of employing «4 multitude of workers is to reduce the completion time of the work. It is common knowledge that for a given job, a certain number of workers is optimal and use of more workers beyond this number gives rise to inefficiencies, leading to very small increase inthe gain. This situation is analogous to the one in parallel computing, but with the proviso that, man has the ability to ‘create workers (processors) of different speeds and capabilities ‘Two important influences on the speed of computing machines are 1, Advances in technology, that increases raw eleetronie speed ofthe underlying circuitry and 2. Architectural and programming techniques, that harnesses the amount of parallel activity (parallel processing) 1.4.1 ADVANCES IN TECHNOLOGY Over the years, technological progress has made possible for today’s machines to operate at higher clock rate, by an order of seven, than those built in the 1950s, First generation digital computers used vacuum tube diodes and triodes equivalentof transistor but consuming 10-20 W of power). Shockley’s invention of transistor device at Bell labs in 1947-48 got him the Nobel Prize in 1957 It lead to semiconductor technological revolution in electronics. Transistors ‘were used in radios in the 1950s but computers were late in utilizing them. It was said that 'T J. Wattson, the then IBM chief, presented pocket radios to his design engineers so that they could be convinced about adapting this semiconductor device in the computers. During late 508 and early 60s, computers were manufactured using transistor devices. They operated at a frequeney of a few 100 kHz. Technology used was the bipolar junction devices. It had a major bearing on power consumption (Jess) and clock speed (improved) In the 60s, with the advent of ‘small sale integration(SS1), SSI circuits were fabricated that had 10's of transistors and were used commercially resulting in improved packaging and clock speed. This was done by Fairchild “ 2 PARALLEL COM, Cegraionaompany funded ye fo pepe whoa eh mgs fee Sh to manufacture transistors, Later Gordon Moore le Fairchild to form Intel that preg? fraten chip mcropresr That mace dt precese O04 desgved opomet sc semiconductor technology development and ite applications. The 8085 microprocessor fe clock speed of only 4 MH2(1973) and the mainframes ofthat time had speed of few ting? 10% Twa not uncommon to havea clock with «prada few nanasecnds in superomgeag” sn the ite 10's ung Bgl Emer Couple Lge (ECL) tehaogy tat sonnet dinate lng aunt of over sing spec casing Cig roge) anand ce bonrds ‘A machin running acs pero of ne vores evrything tte pakogs ‘phere ofa ras light revels inene mason wich rings noo ee Facts on he connecting wes CRAY tapes Ran 1978] wd a ceck ee CrS0 Mis roquinng he machine ob packaged no spec linda shape tote? the sna travel dances CRAY YMP operates ata ce 200Mle Toy isa tchaves cnt seed offew GHs Due VEST ectasony besides beng gly Sena ee with very ome dimension have Become more rahe tafser Both he dante eat {eed othe someon echnlogy have doubled very 2 year ores ey SEMICONDUCTOR TECHNOLOGY ‘Semiconductor technology is breeding ground for all the developments in the computers and the communications since last 35 years, tool 64 tant * ——| f= 2 come tl Pentium Poem 5 Sa ba 91 92 93 OF 85 9 97 98 99 2000 01 02 Yer —_______» Fig, 1.1 Processor Clock Growth Trend The 35 year long trends in microelectronics have led to increase in both the speed a”! the packing density as shown in Fig. 1.1 and Fig. 1.2. srRoDUCTION 3 i wo 3 6 89 @ s 68 « 7 mes 6 9 WS Yer > Fig. 1.2 Semiconductor Toemelogy Tend ‘The semiconductor fabrication technology trend is shown in Fig. 13. In 2000, we have «quietly entered into nanotechnology age (size of devices fabricated in nanometers). Te i size of transistor was a few 10's of mieron (micrometer) and today we have sub-micron sizes that is few 10's of nanometer), thereby progressing from microeletronics and microtechnology to nanoeleetronies and nanotechnology. This increase in device density requires means for allowing power dissipation, which inereases as a function of frequency. However, thie upward trend will come to an end as we approach the barrier of heat removal ability. We need an ability to remove the heat from the chip at a faster rate so as to maintain its temperature within working limits, Today the power considerations and the operational speeds are the conflicting parameters and one has to trade off between these. We have entered into a time Where tradeoffs are required between speed and density. This is quite in contrast to the traditional simultaneous benefits in speed and density. Imagine if the technological ‘advancements continued on the speed enhancements, as stated by Moore's law till 2015, the chip temperature will exceed the surface temperature of the Sun, In the next ten years, the impact of nano-lectronics research is expected in enabling improvement in the evolution and the advancement of the CMOS technology. This requires new materials and processes to reduce the gate and the channel leskage problems associated with the devices size reduction. Different MOSFET structures may be required to sustain the size reduction beyond the 22-nm technology, ee et Fig, 1.3 Intel Processor Technology = \WitY 00 WE NEED PARALLEL COMPUTERS? The need for parallel computers stems from the need to build faster machines. Do we ray need very fast machines? This question can best be answered by an analogy from the ace automobiles. Initially, man was happy moving or his own or at most using animal carts Ba then, his world of activity was limited and he was used to that kind of world. When te automobiles were invented snd introduced, the sphere of his activity and the interaction wis others grew. Today due to advances in ai travel and telecommunicatios, man can intra with others at almoit any place onthe earth, which men could not have thought panne earlier centuries. Even with today’s fast jets, the ned for faster tavel felt There ave ogeay projects to enable travel to any corer ofthe earth possible in an hour or 20 ‘What we see in these trends is that when a technology is available, its use initially» restricted but when it matures, the cont reduces, which in turn makes the application spectre row giving further boost tothe growth of the technology and consequent price redacti: Similar scenario exists in computer industry. As an analogy, if we assume that aviation nds hhas advanced technology lke semiconductor techrology, i would mean travel tins from Nev York to Mumbai takes only 8 miliseconds and cows 1 paisa The increased computing power and the decreased cost, changes one's thinking inter» ofthe machine's use and envisages new applications, Problems requising lange scale comp (in terms of the memory and the computing speed are numerous, Most notable among t= are large sized problems in optimization, planning, scheduling, network flows Held prble™® artifical intelligence requiring logical deductions and search, These problesns becom °° computable when the size ofthe problem becomes too large to fit nta the sompating P™*” (the memory and the speed) ofthe available machines Applications that require high-speed computers for the solution of some of the a class of problems are 1. Design of VLSI circuits 2 CAD/CAM applications in all spheres of engineering activity Solving the field problems. These are modeled using partial differential equations and require operations on large sized matrices. These problems appear in all the ‘areas of engineering, notable among them are (q) Structural dynamies in aerospace and civil engineering (6) Material and nuclear research (c) Particle system problems in Physics Weather forecasting, meteorological and oceanographic processing. Intelligent systems Modeling and simulation in economics, planning and many other areas Remote sensing requires processing of large data gathered from satellites Problems in nuclear energy Chemical and nuclear reactions 10, Biological, human genome. 11, Geological, seismic activity In the absence of adequate computing power, we still solve these problems, but with a sealed down version. For example, the weather forecasting can be made more accurate by ‘modeling with ever decreasing grid size, However, the grid size selection is based on the power available, so we accept the predictions with lesser accuracy. MASSIVE PARALLEL PROCESSING: A DIFFICULT ROAD Due to the limit on speed of processing by sequential computers and the ease of availability of VLSI technology and its cost effectiveness. it has hecome possible to think in terms of employing «large numberof processors to carry outa given computation. Should the high-speed computers be built using few, very fast processors or large number of low cost processors. This is analogous ‘to asking: Do we use few elephants or million ants to do a job? We would like to caution our readers that putting million cheap processors (million ants approach) may not give the required speed advantage in general. Commercial practice till late 1990s show that for the general ‘Purpose computing intensive applications, the few elephants approach has not been challenged by the million ants approach because better and better elephants are being ereated. But today, it seems that we have reached the limit of harnessing the computing power from a single processor. So, any increase in computing power must come from employing the processors in large numbers. The chaos inherent in the development is shown in Fig. 1.4. IBM Blue Gene/L operational at LLNL California has 32K processors and gives 71 TeraFlops (1 TeraFlop = 1000 GFlops). The obstacle to use of a large number of processors stems from the following: 1. The presence of sizable sequential codes in the otherwise parallel programs, and 2. The time spent in talking (communicating), even for a millionth of a second among themselves, is necessarily large on many occasions. “Thus doing more talk (communication) than work (computation). READS Pentaflop ™ 1 apncomill Tg SPMD 229 7 gs ut FU Cc Message Pa: oY 5 . Load Balancing | sy am Waiting ROAD SO wal Wie PRAM AST oy Mista «Mon TERABLOPS & onanvonl SY SLAVE Coe Wa, Cluster DISTRIBUTED tae CC ——_—C a, —————T— inthe above scenario fr ew elephants and milion ate obvious The operatonsen ee dna ae example of uch cose dg eesing) in ect compttationn The ees ae ar 's analogous in having too much tak and too little work when a large crowd works on a commen ‘goal in an apparently unorganized manner. It should be noted that the individual compiatatina problems could be studied and those with good communieation and computing regulantis could be effectively solved using massive paralle ism GRANULARITY OF PARALLELISM Parallel processing emphasizes the use of several processing elements (processors) with a pring objective of gaining the speed in carrying out atime consuming computing job A multitackirs operating system exeeutes jobs concurrently, but te objective is to affect the continued progren of all the tasks by sharing the resources in an orderly manner. The parallel process emphasizes the exploitation of concurrency available in a problem for carrying out th ‘omputation by employing more than one processor to achieve better speed andr throvhyit ‘The concurrency in the computing process could be looked upon for parallel processing & Various levels (granularity of parallelism) in the system. The granularity of parallelism ma be thought of as the amount of work (computation) constituting the unit of allocation to th Processing elements. A computing system may have several granularities coexisting Th following granularities of parallelism can be easily identified in the existing systems 1. Program level parallelism, 2. Process or task level parallelism, 3. Parallelism at a level of group of statements 4 Statement level parallelism. eeTON 7 5 Parallelism within a statement 6. Instruction level parallelism 7 Parallelism within an instruction 8. Logic and circuit level paralelans ‘The above granularities are listed inthe inerea the most coarse level ‘coarse grain paraleligey, parallelism). The granularties at the higher levee ing degree of fineness. The level 1 is hile evel Sis the finest level (fine grain level 1, 2nd 3\ can be implemented « 1.2 PARALLEL ARCHITECTURES JRE Ar numerous architectures that have been used inthe design o high peed computers, ‘The architectures basically fall nto two basic classes vie (a) General purpose and (6) Special purpose 2 feral purpose computer architectures are designed o as to provide the rated speeds nd ther computing requirements for a wide class of problems with more ar eee oeees perfrmance. The important architectural ideas that are beng tried out in designing genera) Purpose high speed computers are based on the following. 1 Pipeline Architectures 2. Asynchronous Multiprocessors 8. Data Flow Computers ‘The special purpose machines should excel in their performance for which they are designed ‘fthouh they may or may not do so for other applications. Some ofthe important erchitere st “deas in the design of special purpose computers are. 4 Synchronous Multiprocessors (array processors) 5. Systolic Arrays _— 8 en, 6 Neural Networks (connectio r onint architocturon) A brief introduction to the architectural ide PIPELINED ARCHITECTURES pipeline architecture have been de ene area These machina are cot sucive ca he re evr the conventional software writen i tn 124 Machines based o success of a simple an 0 higher sees view af «compu oan ve tian enn on these Int thee ao ne conventionl von Neumann muh th ee i ee ecoele mee ne Mr 1 ma the assembly line, ‘each one in a different stage f pleti bttaledetaers) ‘stage of completion. The pipeline mw - fhe corer saesor is bose on a sini rile, A Ss igs pe han tein a tg mn cd a ins a petaane tetany as en ae be simultaneously active i ided into a ‘This model all Th in Pigure 1 hows tng isiecon Instruction ] merge | | opment ee Fa asians rocessing and Executor PIPE architecture, Its base hen accessllY OH of granular anulanty)® Fig. 1.5 Instruction PF successful 1 idea in compute roto the tasks. It bas P plicable at any level reric units (ne 8 essing is the most st ‘concept and orderly processing is 0? {arith veessing 4nd lalthough its use in de teen most widely exploited sywcHRoNous MULTH hased on synchronous parallel Cf * phar all of which execute the aA p ae ony pnoadcaste to all the PES PY ao ormiding in their own memory, DVS st gteeton seam eth multple date streams ( Oe ranray proceasor The individual PES ar yected vil wt data communieation between th ral ways of Elements fare usually fetebe instructions on the "There are sever peing researched by 4 ATR stays of intereennection self was ond it sertae These chins aaeye epoca prams efots 1 achieve wivanton ava carried! out xynchronosly by the hardware # oss ist problem, Figure 16 shows the "schematics of the iwrRODUCHION = SEE processor architectures. The architecture shown in Fig. 1.6 (a) consist of processor memory males conneeted by an ntereonnection network, wile the architecture shown in Fig. 1.6 (6) has processors and memory modules connected by en alignment network. Note that in this architecture, the number of memory modules and the number of processing elements may be different, In SIMD processing, all the ‘its execute the same instruction at any sven clock cycle on their local data. Bach processing unit ean operate on a diferent data element. This type of machine typically has an instruction dispatcher, avery high-bandwidth internal network and a very large array of very small-capacity processing nits. These machines are best suited for specialized problems, characterized by a high degree of regularity, such a8 ‘mage processing. It performs synchronous (lockstep) and deterministic execution as shown in a oo / =| ie ee vn om ine a me eo ent | (= = rt =| & L— Es ' oc) = (0) SIMD Array Processor Using Alger Network Fig. 1.6 SIMD Array Processor Architecture ‘Several machines have been built using this model, Most notable are TLLIAC IV [Bernes 1968], Burrough Scientific Processor (Kuck and Stroke 1982]. ICL DAP [1976], MPP (Batcher 1980] and Connection Machines CMI and CM2 (Hillis 1985) are SIMD processors having one bit processing elements and smal local memory. Each processor in these supports only one bit arithmetic and logical operations. To implement word operations, itis required to program the brocessor using bit sequential algorithms (SIPS 1984]. A product called GAPP was available in ‘arly 80s from NCR Corporation to design SIMD parallel processor with large number of PEs, 10 Pe, aa LOAD RIA Lon q 0 pee DRI A) LOAD Ri Az) TOAD Ra. 8 LOAD Fa. 8 LOAD R28) MULT, RZ MUL RI 2 MR Re | TOAD RC LOAD _ RS. Ct LOAD Ra cia ‘ADDI. RS ‘A00__ RRS 700 RAR STORE RIO | |_at_A1.0(0) MAT m0) ALL exact the same isco on een ta. (Vet opraan ‘Scalar Operations 0) SIND Program (a) 880 Progam Fig. 1.7 SISD ard SIMD Programs ee eee GAPP chips, it was possible to design arrays of PEs of any size. The chip eae ie an Peale ay aplstons Dre Ts kkind of bit sequential architecture is one of the ways to build Vector sa Tis Kind of segue rh ar ul ang tle appre on Connetion Maine CO ae ng sn I at pl arcing Oe ar Cuter Ve, ME Sh, tod 0" rcs uh BM 200 Cr 8 poe oes ik Pet 4 eS Sector cen aaah on ap afen cpl n exhing bn FEN Per a tun ey Sine the press ce er eer ang eh none iner ae ch ant mega si wi om bya ange Istacon. Tis snp a» SDE sch ures he A ig ar ma pleatinf execs in Feat Ta ey mA Vises ne errant id gen pts al of 2 sf malin st yin nn 2. ine ster heer cn ah ed Py ta in aaa ns aes mar re rion oe al snlenraon tats i lana bindu ni he frais ere PP pry ntnre ing an ie tet apatons types si pon cathe deka Buty ny os cent Pens wey aunichnRoNOUS (CONVENTIONAL) MULTIPROCESSORS a con chs an manay bans cnscsd te i 2 (Fig. 1.8 (a) or connection network (Fig. 1. 8 (b) and Fig. 1.8(¢)) is a ‘commonly employed technia# (aaron ete 1 oe time aa genre pare environment. In such systems, ea iy on the quantum of Wr implement 85). This ich CPU operates independent! iting goal or an independer fiven wit The computation, which could bea partof a larger compu! a ser an thos reoeads in parallel onthe CPUs and progresses independently 60% bit ofthe other resources. Multiprocessors have been highly succesfl in 1RODUCTION _ increased throughput andor respons time in time shared systems. Eective reduction ofthe ‘xeaton time of given job requires that the jb be broken into subs that are tobe hand separately by the available physical processors. It works well for tasks running more or less independently, i., for tasks having low communication and synchronization requirements. Communication and synchronization is implemented either through the shared memory or by message system. Based on this aspect of communication, following basic multiprocessor architectures are possible: wen | [wen ve = | ali) | i I I Sched Ache I — I [ eu ou). cou | [ cru ] cu | we | ou omen ce oe Bae ttre (Sein nee cou || opp cou Prono | [ Prosar Proceso | NEM | |_ MEM ol iieory oo ‘one ot I Wome | | Mews | | ema anaes I i I os a a Cameco ok =a ia (oMessne Baad tte 1 ian any adage awd cre Fig. 1.8 Mutprocessor Architectures 1. Shared memory multiprocessor 2. Message based multiprocessor 3. Hybrid approach using both shared memory and message based multiprocessor 4. Cluster based computing ‘Tre shared memory multiprocessors (SMP) have been common in practice due to their pity’ and the eas of eperation ona single bus system. In such eytems, there ina init on the mumber of processors that can be effectively operated in parallel. This limit is usually af few processors, typically af order 10. Anather approach is to use the eommunication network forthe talk among the PEMs (processor memory modules). This approach allows the number of processors to grow without limit, but the coanection and the communication east may ‘dominate and thus saturate the performance gain. Due to this reason, a hybrid approach shown in Fig .8(@ may be followed. Many general purpose commercial systems use common bus architecture to access global memory, disk and input/output, while separate memory processor bus network handles the processor memory trafic. luster based computing employs onsite clusters of computers that are network connected using standard network technology and ‘used as message based parallel computers. Currently, the most modern parallel computers tt 2 {fall into this category of MIMD. Here, every proceuior may be oxecuti are synchronous devant hei og reper eres ictcheesiort mt a ee cree eat een nT ee multi-processor SMP computers are also in the common wie. Scalubility in the weg’ (hardware and/or software) ability to demonstrate a proportionate increano in vd at Chane endl ctor A ear ot crs Wie saishlier nea jmemory-CPU bandwidths and network bandwidth and different kinds of coms monies ‘Table 1.1 lists some of current commercial machines with their memory arct lectures ‘Table 1.1 Shared and Distributed Memory Commercial Architectures Memory Architect MULTiPRocESsORS | Closely Coupled | Closely Coupled Non- | Distributed eat aor eg, | Nowe) Sommer wanes | SMPs, San Yrs, | SG! Oi oy a au cane | ete | a Pere, | Sonat eee Siete | ea owes oe pa [conmvniion | mrt mt = Mirai Mais ae Sete ne [any ee tnt cans cre | Mmon-ceu | Pan doit sae se | etn se ine | te Saar vig ae = [Beare svg [rien | wk | Poe “The largest and fastest computers in the world | ‘today employ both shared and distributed ent sul 0a ‘memory architectures as shown in Fig. 1.9. The shared mé howe symmetric mukiproceseo(SMP) machine Processors on a given SMP can adr that machine’ memory through a global address spice. The distributed memory componen © the networking of multiple SMPs. SMPs know only about their own memory not the meme ‘on another SMP. Therefore, network communications are required to move data from of SM to another Current trends soom to indicate that this type of memory architecture Wi inti to prevail and incre atthe high end f computing for the fresoable re Mercer multicore CPUs with multithreading will easily make i possible. have around 16 Processors ona single chip in near future (Mocule in Fig. 1.9 has 4 CPUs shown) inraonuerion 8 eS = MeMoRY MewoRy MeMoRY cpu| cpu cpu | cru cpu} cpu cru | cru cpu) cou cpu} cru eter MewoRY Newory wewory cru | cpu cou] cru cpu] cru cpu | cpu cu] cpu cou] cou Fig. 1.9 Shared and Distributed Memory Architecture 1.2.4 DATA FLOW COMPUTERS Jack Dennis [Dennis 1975,1980] has suggested a new fine grain parallel processing appréach ‘based on data flow computing model. In the data flow model, a numberof data flow operators, each capable of doing an operation are employed. A program for such a machine is a connection graph of the operators. The operators form the nodes of the graph while the arcs represent the data movement between the nodes. An ar is labeled with a token to indicate that it contains the data. A token is generated on the output ofa node when it computes the function based on ‘the data on ite input ares. Tho is called es “Gring” of the node. A node cas fire vnly whi all of its input arcs have tokens and there is no token on the output are. When a node fires, it removes the input tokens to signify that the data have been consumed. Usually, computation ‘starts with the arrival of the data on the input nodes ofthe graph. 1.40 Data Flow Graph Figure 1.10 shows the data flow graph forthe computation: A:= 6 * C + D. Inthe above raph, the operator can fire ifboth ts inputs are available. The input 8 is availabe as shown, bythe token (a filed cirele shown) but the input Cis not yet available, When it arrives (may be from memory), the multiplication node fires. In doing so, it removes the tokens from the input fares and puts one token on the output are. In the graph shown, the addition starts after the ‘multiplication is completed, provided thatthe deta on the input D is available. The data Jow sraphs depict the data dependencies in the computations and therefore the eomputatons progress as per the data availability. Since the sequence of computations are ordered by the " 1“ data flow, the machines based on these ideas are called dataflow machines in eon coe conventional control flow machines. Many conventional machines employing matnnc nt Shite employ the data flow modol for echeduling the Rinetional unit pipelinn sere sly te tno model shu tnt wt in ais tho operands are avallable (both tags O), th FU initiates operation and generics eee (eokea) which fe placed at desired destinations as given hy Tomsul’salgorthes so See ren nen is colle acd and [amerasel ibe clea epee eae aoe a aoitectare model. There wre wide interest in the architecture and several workers a Fe eetmontal machines, Notable among these are Manchester machine (1984 and ft aa ea regO) The data Now computers provide ine granularity of parallel procesing act rachine 100 Tr dos ically elemacaryerithmetic and logic operators. In piety rain parallelism being exploited, a practical coneivable data flow machine is hindered ni performance by sequentiality in the control functions that are centralized. ied eis not promature today to say that these efforts may not suceed to provide the effecting solution tor nue very lange number of compating elements in parallel. While with iy synchronous data driven control it has a promise for exploitation ofthe parallelism availabe ‘ine implementations are no better than conventional pipelined in the problem, but its machi aan sos employing multiple functional units using Tomasulo’s algorithm (Tomasulo 196) 1.2.5 SYSTOLIC ARCHITECTURES ‘The two important architectural ideas that have been of contemporary interest are syle wn puree [Kung 1982] and neural networks. The advent of VLSI has made it possible te ation special architectures suitable for direct implementation in the VLSL. Sysolie ae eeee aes are basically pipelines operating in one or more dimensions. The name systole is arent trom the analogy of the operation of the Hood circulation system through the heart cere val architectures operate on the data using load and store operations from Se santo Processing usually involves several operacions, Each aperation accesses the memo Fae dare,proceaes it and then stores the result. This requires too many memory reference tae 11 (0), Alternate processing method i shown in Fig. 1.11 (ain which che date ie processed flows through various operation stagos and then finally is put in the meme Tao verchitectures, data to be processed is taken from the memory and enters the prociss saa conf, as shown in Pig. 1-11 (a), The data processed by i givon tof, and soon. Inthe ‘end, the processed data from f, is stored in the memory. co MEMORY wsyaacrocuine (cameron aceeg Fi. Sine View tS Acco ‘The proearng method dscused : method ican above, hast smilarity to the eager heart pumps the pret ou fom need and he impure ane retort te wrRopucTioN. 15 heart from the other side. In the process, it branches out into various subarteries and veins, hence the name Systolic Architecture. Tis possible to develop special architectures fora given pplication and fabricate the same in VLSI, These architectures give very high eomputing ‘throughputs due to regular data flow and pipeline operation and are useful in designing the special processors for graphics, signal and image processing and many other applications Major research efforts in the systole architectures have been in the synthesis, the analys tnd the fault tolerance of systolic arrays from the problem deseription. Figure 11 (a) shows only one-dimensional array. Nevertheless it is possible to design complex multidimensional trays with complex low pattern in various dimensions 1.2.6 NEURAL NETWORKS ‘Computing based on connectionist model is not new and has been under study (Grossberg, 1986, 1988, Kohonen 1978, Hopfield 1986), The idea in these models is derived from the fact that the human brain, although very slow with routine numeric computations, does a remarkable job in complicated tasks like observation (vision) speech and cognition. The research in these application areas have not yet produced computational models to give the desired performance. In fact, these are recognized as highly complex tasks. The neural network model uses the neural system to provide the analog of the brain by using artificial neurons and their dense connections having, weights to store and process the knowledge and carry out the cognitive tasks. Some of the models have been experimented by Bhattacharya and Bhujade (1989) in character recognition problems. The neural networks provide a non-algorithmie approach to ‘agnitive tasks in which the connections represented by weights are modified using models from adaptive systems theory. These theories have been used in various diverse disciplines, Recently, the interest has gone beyond the academic circles with soveral companies offering special boards and softwares to provide usors with experimental neural nets that can be used {or developing applications. to, . cnn tiles Val re ay = J . \s St HareLimter Tested Sigmoit Nolet: Gis some tresholé ato Some of tie fants fae shown above % oe 5 inthe weigh assocated wi (0) rl Neuron (b) Hops Neural Network 4142 Noutal Network ‘Aneural network is a set of nodes and connections, in which each node may be connected toallother nodes, A connection has a weight associated with it. All nodes compute their output athe weighted sum oftheir inputs, and the output of the node i fred ifthe ways ‘coos some threshold node could be in an excted state ed or in nena fred, The base idea here ie thatthe weights store the knowledge required fon ge task Typically, sample example patterns are applied fo the net andthe nate ne modified through some algorithm (learning algorithm). When the patterns to he sot * reapplied, theme assis them using the fring rule the nt. Figure 122 shoos see cot several possible neural network models, 13. ARCHITECTURAL CLASSIFICATION SCHEMES lr eset cae ee hasta eas op ae area ae ce ese coe tbe das na eats oe lla i een may oot sede ala by a ete esha cian Ses pronto ie haa Ss eee a ieaiaene 1.3.1 FLYNN’S CLASSIFICATION Flynn [1966] classified architectures in terms of streams of data and instructions. The essen of the idea is that computing activity in every machine is based on: (a) Stream of instructions, i., sequence of instructions executed by the machine (@) Stream of data, ie., sequence of data including input, temporary or partial result referenced by instructions. Purther a machine may have a single or multiple streams of each kind. Based on these, computer architectures are characterized by the multiplicity of the hardware to serve instruetiva and data streams as follows: 1, SISD; Single Instruction and Single Data Stream 2, SIMD: Single Instruction and Multiple Data Stream 3, MIMD: Multiple Instruction and Multiple Data Stream 4, MISD: Multiple Instruction and Single Data Stream Figure 1.18 shows the architectures hased on the above four possibilities. The SISD architecture corresponds to the conventional sequential computers. The SIMD architecture represents the synchronous multiprocessors in which a common instruction stream coming from a control unit is applied to all the PEs operating in its own data stream. The examples are ILLIAC IV [Bernes 1968], ICL DAP [1979] and many others The conventional multiprocessor are based on the MIMD architectures since the individual processors operate on the programs hhaving their own instructions and data. MISD architecture is used in specialized applications, where same data stream is required to be transformed simultaneously in a number of ways ‘There are no visible examples of MISD architecture. mr = a me ssnncumntnanae pe abovecasiaton scheme sto bod. It pots everthing except mul Procet none cas Jhnaon Johnson 1988 expaned the cassication of MIMD machines as shown, ing. 1.14 to account for current architectures \t il 80 | (ano) i u ome | ome RL» [om | os ul my | ausv ig. 1.14 dotmso’s Expanded Classica of MIMD Machines Clasifation scheme does not rele the concurrency available through the pipeline pressing and thus pts veetr eomputers in SISD clas 4182 SHORE'S CLASSIFICATION Unlike Flynn, Shore (1973) classified the compoters on the basis of organization of the bonatituent elements in the computer Six different kinds of machines were recognized and Aitingushed by numerical designators as discussed next. Machine 1 ‘Thc ae conventional Von Neumann architectures with following unit in single quantities (a) Control Unit (CU) (0 Processing Unit PU) (©) Instruction Memory (1) (ad) Data Memory (DM) A single DM read proces al the bits of any word for proces ‘The PU seap contain multiple Rctional wats which ay or ene a8 PAPA yy {his group again includes both the selarcanputors (eg IBM S801, CU suns pipelined vector computers (eg, Cray YMP. Cyber 205). Figure 1.15 (a) shows the st plied vec compotrs gs, Cay YMP, Cyr 28) Pie 115 swe parallel as a word). ot tite ‘Machine 2 onganization is similar to that of Machine 1 except that DM hy slice from all the words in the memory and PU are organized to perform the operations ny sin om a a re ig I tae semen ogee wee date aor r ah ona word narod per row, ten tne Machine 2 reads verte ss tg an ver whereas the machine 1 reads and processes horizontal Peat re tehine are ICL DAP (1079) and MPP [Batchor 1860] and CM 2 (lic 9s @)Mactine 2 (2) Macino Fig. 1.15 Horizontal and Verical Processing “Machine 3 is a combination of Machine 1 Fig. 1.16 Machine 3 Architect could be characterized processing pet Well knows tecture and Machine 2. It ‘zontal and vertical reading aid sd the horizontal processing units the memory [Link] array of bits with both hori igure 1.16 shows the archit ‘The machine, thus, will have both the vertical an‘ example is the machine OMENN 60 (Higbie 1973). Fi Machine 3. 1 and Machine 4 architecture as shown in Fig 1.17 (is obtained by repliating the PY DM of the Machine I, An ensemble of PU and DM is called as Processing Blement (7° snatrctions are issued to the PBs by a single contd uni. There is no communication Par PEs except through the CU, Well Known example ofthis is PEPE (Thurber 1976] mash! Absence of the connection between the PEs limit the applicability of the machine. he Pa a iachine 5s similar to Machine 4, with the addition ofthe communication between Mecpathewn in Fig 1.17 (6). ILLIAC IV, CM2 and nany SIMD processors fallin he cate fins nagt 1106 maintain separation between data memory und processing units Wt unit providing the communication between them. The machine ini 117 cinco Indes the logic inthe memory itselfand is called an Associative proceso" mories to complex oehiner based on such architecture spans aang om simple associative me" ive processors pu le ~ | PU pT |i (0) Machine S (epMactine 6 (a Macine + Fig. 1.17 Paral! and Associative Architectures 4.3.3. FENG’S CLASSIFICATION Feng [1973] also proposed a scheme on the basis lrchitectures. Maximum number ofits that can be je ealled ‘maximum degree of parallelism’. Based on aia parallel operations at the bit and the word levels to proce the follow Classification Examples WSBS (Word Serial/Bit Serial) [No conceivable implementation WBS (Word ParalleV/Bit Serial) —_(Staran) WSBP (Word Seria/Bit Parallel) Conventional computers WPBP (Word ParalleV/Bit Parallel) ILIAC TV of degree of parallelism to classify the computer processed every unit of time by the system the Feng’s scheme, we have sequential ng classification: Worsenghn ———> Fig, 1.18 Machines at Bit and Word Coordinates ‘The product of the number of bits and number of words processed gives the maximum degre of parallelism. Classification of some of the commercially available machines (current tnd past) is shown in the Fig. 1.18. In this diagram, one axis represents the word length and mm ad $$$ ¢ the thr ai roprsete the nanber of word proce in ar A machine oe print in the space defined by these coordinates, The area ofthe rectangle tons Py tnd the point representing the machine gives the maximum degree of paraleg°4 ‘machine. For example, Cray 1 and IA-64 have areas of 64 each. It sto be noted again scheme fails to project the concurrency in pipeline processors. that 4.4 PERFORMANCE OF PARALLEL COMPUTERS ‘The quantification ofthe performance characterization of «computer applicable scrse applications isnot simple. Even for sequential eomputer, we donot have appropriate ga umes that tay ref te power of a parcular machine, The Linack pera commonly used for evaluating high performanc: computer (HPO), though other prograns« ‘voll would serve part ofthe purpose. For example, .0 GH Xeon and 12 GHz AMD aig fave 760.62Mflops and 967.73 sustained Mflops respectively on conjugate gradient sn {Holmgren, Don 20021. The speedup is one such measure of performance of «parallel compas nds the ratioof time taken by single processor system and that taken bya parallel proweane system. Thus speedup is given by: the number of processors 1, = single processor execution time, 1, S = speedup. Folk Theorem 1.1:1 1000. ‘The observations made by Lee are thus derivable from Folk Theorem 1.3. Figure 1.22 shows the speedup as a function of the number of processors. The studies on the execution time, the effective parallelism as funetion of the number of processors was studied by Jordon (1984] for HEP MIMD architecture. Figures 1.23 and 1.24 show the graphs depicting the asymptotic time reduction and the saturation of the available degree of parallelism for two important problems, viz., numerical integration and LU decomposition. Table 1.3 gives Linpack performance of some of the important machines of 80-90's [Dongara 1992} ‘Table 1.2 Speedup and the Number Hence: Ss maze a sone ee Value of S fay | Ss LK, 1 ‘Oy 100 modem ee a O{nilog n) Fig. 1.22 Speedup as a function of the 10000 and above O(n) number of processors: Etecive Paral le) Oe a0 geese et unter Procesors Sumterat Presson > Fo. 1.23 Asymptotic Time Reduction Fig, 1.24 Eftctve Paaleliam —________PMALLEL cou, 26 ‘Table 1.3 Linkpack Performance _Table 1.8 Linkpack Performance of Some. ne Computer (Dongura 1992) cee |_ Performance Megoflons tons) aca [— Proton sine Peak_[100 100 [Gray YMP G00 42 ne clock CFF7.5 16 Processors 16000 | 470 A Processors 4000 | 388 1 Processor i000 | 387 Fajen VP2200 10-4 ns clock Fortran 100 | 127 THEXIVPVIATAO FTBM 6519000 9 ns lock under VAST-2¥8 72668 ae Fortean “GDC Chor B000V Fortran V2 @ a Ma) iso [2 ia n TBM RISC System/6000-550 6 5 under v2.2 x16P-Wp, 00.478 HP 90007790 (BONE) Under HP UX 8:05 £77 +0P4+03 “CUBE 2 1024 Processors 2400 38 602 165 3 21 202 2.35 oat ealable 1 Milion processor mac “Today's top machine IBM Blue gone 9 vedas: 1 Milli wei 9009 Prove vrs per chip, 64 (2) cbiPs, cee a tower cabit with 8 2) taal ee vas planned 5 years and 64(2°)towers, a powerPC architecture. An ins fn 2001 and gives 500 top machines 500 puters in 2008 with telco supetsp), while Fig. 125 shows the Preps 4 TT rege «| E+ Ghops 1 ie Fig. 1.25 Supercomputers Performance Trends — a ‘Table 14 The Quest for Higher Performance [Erico 2005] ‘No. of Processars, | ma | | Name | Purpose RAM and Disk’ | Speedand | recbnoiogy fe capacity = cecal [meee | Nasal and [2768 -ARLOPS a Daly aioe Genta” | Nuclear” | ‘Sip RAM 00M | Power chipe | aap UATLINL |simaation | 26S dat torge (1015 Wem | LOPS | Catia Lina and Custom 05) Sa a | Atnzace | 1240 nos, 207, [sa TFLOPS, ATR GD | oumbin [simulation | 440 TBiak sar | .7F Team ike [ask [timate "| nu by by nina | Ames Lab_| rveech NEC | Aimowphers, | 6120 ms, 101, | aeTRLOPS | pan deoamn Basi | oceanic and | TOOTH ak storage | graopo?S | Balto Gener [earth | Tia ieproessn| Shama 1.6 PERFORMANCE METRICS FOR PROCESSORS Performance metrics ar the measures (numbers) a quantify the processor’ peformance and ‘ence are useful in making comparisons. Execution time of the running jobe from n wie ot ‘sbson4 processor as measure can be useful. In fat, today, where all Kinds of peak performance ‘sed onthe clock speed is being pushed by the manufacturers; the execution tie isthe eal measure ofthe performance ofa processor. Avichmetic Mean provides a simple average forthe time T, taken by n diferent programs run on the system, ‘These programs typically characterize the job mix ofthe user organisation, a(S Je the runtime oa Jb Weighed Arithmetic Mean Since the frequency of running a job may be different for different jobs, a better measure is ‘needed that takes this factor into account. Lat M, be poe for jb and P, = probability of runing a job whose run ime ie Weighted arithmetic mean is a better measure and may be defined as time Ty given by Ty (Ee}e i are avaiable (speed I’ we do not have the execution times and instead the speeds are availa tated as the inverse of the execution time), we could use speeds and obtain the harmonic "mean Sy of the speeds. It is defined as: where T, oJ — - : PARAL co, syn] im. Geometric Mean Time Metric: R, When speeds are known as relative to the sped of some processor and nat ita ah we define a normalized metric in such situa‘ons. In that case, a normalized tga machine) metic could be defined. Geometric Mean R i defined as nth rot on ih all ratios, ce R= gfIRy , k= 1,2... whore R, = Time on CPU/Time on reference cy iextbie a ie propery ie, Rat ee means = Mean othe ron en runing nes oil pres, Hast mesure bt han ae Set doesnot frm erate Prodiion model or the perormanc ‘Amdahl’s Law Revisited: ‘We formulate the overall speedup for a processor, which has the specific feature that main, uncertain instruction/ faster, due to hardware enhancements. These enhancements are. only if these instruction/s form a part of program code. Folk Theorem 1.4: Overall Speedup = ———_______1____ -, Fraction enhanead (Fraction enhanced) +r Proof: Let F = fraction of instructions that use the enhanced feature (Fraction enhane 5, = speedup enhanced for the fraction of instructions ‘T= execution time without enhancement ‘Ty = execution time with enhancement ‘Ty = time for the part without enhancement + time forthe part with enhancemen =(-P.T +P. 1S, Overall Speedup = T/ Ty Overall Speedup = ap. t+h. 1 Overall Speedy aps Sy Example ‘A program has 50% of the code that refers to the 7 frst the main memory (RAM), out of which 95% r ‘othe cache: If we have RAM of 100 ns and cache of 10 ns, then Sy ~ 10, Fraction enbes je 50% ° 0.98 = 0.475 (We assume here thatthe cache time is predominant in the execution sie ihon 0% rcs pong ahr ef snp Se 8 sor with the eache is roves 0.525 + 0.0475 ) = 1/0,5725 = 1.746 ‘The CPU shall run 1.746 times faster with a cache than CPU with no cache calating CPU Performance ‘Alemmerial machines are synchronous with some clock tick driving its work, hence, a useful asi metric could be clock frequeney in GH (1 GHz = 1000 Mz), Thus, clock escle time 7 alock frequency (1 GH gives clock eycle time of 1 nano-second). CPU Time ~ CPU Crees fora program Clock Frequency We tend to count the instructions executed, ie Instruction Count (1C).A program may save N instructions in its object code, but that is nt IC;, What is important, is the dynamic count ofthe instructions actully executed. (A program may skip certain instructions due to ‘perf enditons, may repeat others due to loops ete). Clocks required per Instruction (CP!) $a figure of merit and is given by: cpr = CPU Clock eyle for program 1c (The great RISC vs. CISC debate where RISC proponents say one clock per instruction for RISC machines in contrast to CISC). 10x CPI (CPU time = 10x CPL x Cyl Time = Gk Freanengy cle Time, CPL and 1C ‘These are interdependent and making one better often makes another worse, Cycle time depends on hardware technology and organization. CPI depends on organization and Instruction Set Architecture (ISA), while IC depends on ISA and compiler technology. Often CPY's are easier ‘odeal with ona per instruction basis. ‘Where should Architect Spend Resources? ‘The frequency ofthe various instructions supposed to run on the machine is counted. Based on this information, itis easy to work out where the designer requires to spend resources to simu benefits. 7 CPU time = Cycle Tine x CPL, x1C, paige Mera case shown in Table 15 that gives the instruction frequency (mix) forthe ‘Resi applications on the processor and its current design giving the clock eycles utilized per struction in these categories, aeeeaee =! 30 ——— _ ‘able 8 Processor Time Spent in Typical Mix of Istrvtion Time ape | — Po bered MIN ines | Pow) { Operation | Fregueney [CPE CP * 1055 aeay | bar {fuser = 08 [nat an Ho 2 za = or fous ae Hest ip} Se eae 2 co oans=2m | ( io atl = | Since technology may not allow all the improvements at once, they must cone order of priority: From the table 1.5, iis clear what the improvement priority shy first improve ALU, then improve Load from memory and then branch executiong ! Overall Effects of Enhancements : An Example Consider a processor and program run characteristics with current and improved yeni ‘shown below. Work out the speedup obtained by improvements. ‘Table 1.6 Example Program Mix Teatraction —] Tatrtion ] —Ecation Time per Tt ‘Brecon Tine pr Ta Type Count trent Version 16H) improved Version Li Memory reference 4 clock eycles 1 clock eycles Anite 0% clock eveles 2 clock cycles Branch 20% 3 clock eveles TH eloek exces 1 elock eyeles [otters 10% 1 clock eyeles "| otal Been Tin Total Execution Time Instruction Type qe te) | improved version _ (Current Version 1GH2) Ee | Memory reference instructions | 20% | O24 ‘03071 = 0.3 Unite Arithnsticinatructions | 8086] 080° ant 9 = 1oTint Branch Instruct 20% [ozs (03071 = 02 Units (Other instructions 10% [O11 = 01 *1=01 Units PRoat 0080 15 Unite Units are different since clock rates are different ‘Speedup = Time taken by old version/time by new version = (6.5° clock period of current version|\(1.5* clock period of improved vers 5515 3 ‘Measuring Performance —. Fs Performance is done by instruction level simulator and the tm is cult due to the memory effects and the dependencies and stalls in a lla manufacorers speci kilometey ” frmance may go er 2 ter of pay ipa freee scr ft eB oe hte, rag Tete irre tami ED ara ee tan ie oftheir real pets Sse rograns wow an be mea race. Onecan as atl apg Seen dein wig known mixta 1 seo oh ad bey SPC ast eg nA lets ‘SPECInt96 had 8 integer nt SP ees SEB ncaa Progr ns SPECS had new PPO 2000 (SPEC stands fr Sytas poeD rt 10a ee (b) Message Passing (6) Treads (a) Data Parallel, darn raring which molt we is oan «combination of prs ie raneeeilabiity. There is no “best” model, aithouh thre cena ne Co, ‘Bplenentations of some models ovr others. One must lanka the st line pont ne ‘cs of sing the model on the knderyng aritectare Shared Memory Model {nthe shared memory programming model tasks share cmon espe, which ey "eed and write asynchronously Varios mechanisms like lek semaphae re ceal read {he sores tothe shared memory. An advantage ofthis model fom the programming ptt of rier i that the notion of data “ownership” is not present, 0 thee i o need wo expcly ‘pei the communication of data batween the tasks. Ths lads singel progr devloment. Major dzadvantage is du tthe por lal undersanding end manag dats lraly. On shared memory patos, th native compiles alate wr pra it actu memory adresses, which are lal stormy —_______"##tit coring 32 ee ‘Threads Model rae ea th thrend model it shown in Fig. 1.26, Main program Pisa ry To aed goa lhe ene andthe ser resures es (tun. rine 08 Fas raf heads as ents that ran i paral Threads can be cena ag may creme norenty, Each thread may havea lecal data, thread alo share the my ‘urease of P including global memory ofP ———_—J Treas Progam vee Aa Bac: cau Ti — > i ca Te é . Forks tend Begin | ‘Al FOKLi) 13 v4 Sum= Sum End | cats cats — We, Fig. 1.26 Threads Programming Model ‘A thread’s work may best be deseribed as a subprogram within the main program. Any thread ean eroute any subroutine atthe same time as the other threads. Threads communicate iithreach other through global memory (updating addressed locations), This requires ‘ynchronization contracts to ensure that more than one thread is not updating the sans ‘fobal adress at any time. Threads can come and go, but P remains present to provide be eoessary shared resourees until the application run has completed. Threads are commosly {ssociated with shared memory architectures and also the operating systems and today Sun “Microsystem’s Java programming language has excellent thread support. Implementations: Historically, hardware vendors have implemented their own proprietary versions of threads ‘These implementations differed substantially from each other making it difficult fr programmers io erly pra thread ppliatins. Independent standardization efforts we resulted in two very different implementations of threads, viz: Posix Threads and OpenMP POSIX Threads [een stray Stone (n IBEE standard called IBBE POSIX 109.6 andar 1998)08 in rams, support to ereate threads that run concurrently. The threads Seiad arse share al the ours ofthe process, other support insu, joining and esrving te thrash he trad regu lng with he ter support required Eee nc eee semmooveo 33 open (eaMPisan Application Program Interface (APN jointly defined bya group ofmajorcamputer harmare and software vendors OpenMP provides a portable, sealable model for developer of shared memory pralel applications. The API supports CiC++ and FORTRAN on mos ofthe reutetre, ncading UNIX & Windows NT. The maja features of OpenMP are ts verious coors and diretves for specifying parallel regions, work sharing, syneheonzaton and dain enirnment. Message Passing Model ‘Multiple tasks can reside on the same physical machine as well across an arbitrary number of machines. Tasks exchange data through communications by sending and receiving snesagea\Pig 1, 27, Data transfer usually requires ooperative operations to be performed by ‘ach proves, For example, a send operation must have a matching receive operation. From & programming point of view, message passing implementations eommonly comprise a library of tubroutines that are embedded in the source code. The programmer determines all the ‘alls required. sce vane ‘ara arr = ae ‘ona ezene roy ‘ara Fig, 1.27 Message Passing Moe! A variety of message passing libraries have been availabe sinee last 25 years but Implementations differed from each other making it diffeult for programmers to develop Peruble applications. The MPI (Message Passing Interface) Forum was formed in 1992 to ‘ecommend s standard interface for message passing implementations. Message Passing niece, MPI pat-1 was released in 1994 while MPI-2 was released in 1906. These are available cathe website www. [Link] gov/projecs/mpilstandard html. MPs now theindustry standard fr message passing, replacing most of the other message passing implementations. MPI ‘implementation usually don't uses network fr task communication, Instead, they use shared "mor memory eypies) for perfurmance reasons since MPI was designed fr high performance ‘moth, the massively parallel machines and also on the workstation clusters. Data Parallel Model aralel computing work in this model focuses on performing operations on a data set. The ‘sta sets organized into a common structure, such as an array. A set of tasks work collectively ‘nthe same date structure, each task working on part oft. Tasks perform the same operation their part of work, ARRAY XY ae james Fomie || Foret Fori=41 10 face eee dficee® || ee ee ee cave || amerems |) as 2 a Fig. 1.28 Data Parallel Model For example, ereate an array X by multiplying Y elements by value of Pas shown i ig 28, whore each processing element works on 20 distinct elements ofthe arrays, In share saan architectures, all the tasks have access tothe data structure through global mena On the other hand, in the distributed memory architectures, the data structure is split ups specs, cuh piece resides inthe local memory ofa task. Progransming the dats parallel model qe ewumplished by writing @ program with data parallel constructs. The constructs ean be calls toadata parallel subroutine library or, compiler directives recognized by a data parle ‘Compiler, High Perfomance FORTRAN (HPP) provides extensions to Fortran 90 to supprt data parallel programming. 7 PARALLEL ALGORITHMS Studies inthe dasign of parallel algorithms are interesting. Any algorithm development and analysis stadies involve how best one can do the given job. Sequential algorithms have been extensively studied for several important problems. One important measure ofthe performance ofany algorithm isthe time complexity. It isthe time required to execute the algorithm spectied as some function ofthe problem size. Another important performance measure is the spat compleity defined as memory required by the algorithm. I is also specified as some function fhe problem sie, Many times, the time and space complexities depend on the data structure ‘sed, Another important measure therefore isthe preprocessing time complexity to generat {hedasie dat strurtare. Algorithms giving the best figures fr the above measures natural alle preferred. To determine the theoretical lower bound on the time and space complexities isan important research activity. impr ste algorithms are the algorithms to be ran on parallel machines. The most imuant mesure of performane of a paral! agri ie how fst one can save a 2 Drovers the company fesacr a8 Feauired. Since the parallel algorithm uses several The cmmuneaton ca ommuniation among the processors is also an important meas ‘he machine Mareen ett in tun depends onthe communication hardware supported bY ster Des ot ans th yf ayo oe machine and do muck ete 08 “tH ne pa an the eth on arta inet lorithms. Speedup and efficiency are also important 35 popu Je measures for parallel algorithm when mapped on tu a given architetare, A Solel lgrithm fra given problem may be developed using one or more ofthe following: 1. Detect and exploit the inherent parallelism available in the existing sequential algorithm. 2 Independently invent a new parallel algorithm. 4, Adapt an existing parallel algorithm that solves a similar problem Stuties on the structure of problems tobe solved mechanically are an exciting field ise ancient times. These studies provide an insight into the problem structure and its sopetes, which are useful in many ways including those for finding the parallelism avaable. Many tines the internal structure ofthe problem solving proces is so complex that people have to work for centuries fo gain an insight into the problem. Four color problems, tinear pransing problems are the few problems that are being extensively studied, Some of the important problems that have been extensively studied for parallel algorithms include serting, Fast Fourier Transform (FFT), search and graph problems and matrix operations 18 DISTRIBUTED PROCESSING Distt presing i alo form of parallel processing bt fora diferent purpose has a different working model of the computers and the cor cee mputing process. Parallel computers are blo reduce the computation time ofa given problem, Distributed computing servis are tse marily fo the reasons of physical distribution of subabs. For example a ening anpcation requires the processing of transactions generated through the distant ‘elle. rachines. Central important idea of distributed e are not of much importance However, the cst of communication in “+ ____— Put pre nan abstract wa highly challenging nd wey Kin stn ptenndhnyensrepg a snmmiin pr anne ante pra en ws a a Se sing aCtcmpr rns A an tnt Sons IEEE Compt Comments oA TREE Ten eet sel of Programming, orl of Pula Ditters Computing, ACM Transactions on Computer Systems, Journal of Parallel ana Dist Computing (Academie Press), Journal of Parallel ard Distributed Computing Blsevie Ista domo gh trenton eee i Sry 20 Indscnerpobee Aen ee Sn A mr tp Otero flr Mos EXERCISES M1 Prove that stage pipeline processor can be at most tmses faster than 4 corresponding pipelined serial processor 12. Give examples of granularites of parallelism known to you 13 Prove Amdahs law. 1g. Guy te speedup is approximately linear for n procestor parallel system with large values 15 Give two reasons why Amdah's law should hold? Ts ¢ poe law may fail? If yes, explain, 16 Why could Folk theorem 1.1 fail? 17 Is Minsky's conjecture true and under what conditions? parallel processing in near futuro? Ne Mhy dou think that the parallel procesing with large number of nodes has been stil FP cada the instruction mix is collected. Loaders mame 60%, FP multiply divide na others 5% and Brandis whichasrustions are: Loads 2, Intoger add/oab 1, FP ail INTRGOUSTION —__ a7 116 Answer TRUE /PALSE with one ln jusifaton (a) A processor system gives higher efficiency than a 2 processor eystem for a given value of sequential computing fraction. (0) program with sequential computing fenetin of 0.2, run on parallel system having 100 proceso gives the speedup greater than 8. 117 Blin the Blanks: (@) To obtain a speedup of 4, a Sstage pipe requires to run — tasks, 6b) Anda’ lw gives possible maximum speedup as (© Pipeline PI has stages, while pipeline P2 has 7 stages, the speedup of chained pipe P1.P2 for 196 tasks is 118. program has following factions of computation with degrees of parallelism as below sequential fraction = 010 {parallel fraction of degree of parallelism 3 {parle fraction of degree of parallelism 6 Al other fraction are ‘A machine wth 8 processors i used to run the program, Draw an energy diagram for machine Using enengy diagram, find the effieney and speadup for the program. (no ather formula ot derivation tbe sed). 119, A prcesor and program run characteris with curret and improved version is own below. ‘Workout the speed up obtained by improvement radio Tratracion | Breeton Time ‘Breeton Time Instruction Type Count | (Current version 1GHie) | (Improved versin 1.5GHz) 20% 4 lock cles Teck oe 50% elo eeles| 2 elo al 20% dock eles Telock eles 10% elk eles 1 eoek eles 1.20 A program has flowing fractions of computation with degroes of parallelism as sequential faction ‘pele fraction of degree 2 ‘parle faction of degree 3 Fi acl ection of degre 10 Allother factions are Lt Machine M, be a single PE with 100 MOPS spout and Machine M, bea 10 PE machine with each PE having 10 MOPS speed. (o) Which ofthe machines M, and M, tak less time to complete the program ? (b) Dea the energy diagrams fr running the problem on machines M, and M, and fom i find the efficiencies for machines M, and M, in solving the problem REFERENCES, Andi, 6. 1967, Capa Validity of Single Processor Approach to Achieving Large Seale Computing Proceedings APIPS Computer Conference, Vol. 0, 1967, pp. 483-485. Chapter 2 PIPELINE PROCESSING — INTRODUCTION Pipeline processing is a well known, century old technique employed in industrial prog Hines. Basie idea behind pipelining is simple hut elegant. We are all aware ofthe dasa ‘working of sembly lines in factories, where ajob passes through various stages of the wea (Pipe) line and finally vols out. The pipeline is continuously fed at the input with new jan ata time, At each stage a part of the job is done and is passed on to the next stage, whe passes through the last stage, it gets completed, and the finished product rolls ext, fe ‘example, consider a job of construction of several houses, where each house is consine ‘through a four step process consisting of 1. Foundation 2, Walls 8. Roof 4. Interior There are two fundamentally different ways of carrying out this kind of jobs, The Nay ie fo Put several teams working independently, each on one house. ‘The teams witk “parale! and complete their jobs, finishing all the houses more or les atthe same time, pro 2.1 of another house. Meanwhile, the second team complete, This team constructs the walls, Whe the first stage and then after being processed Job is fed to the first stage, There are now ‘executed in the second stage while the {thre goes to the next stage. At this time, {vo joos in the processing stage. The frst jo Second job is being executed in the first sta¥® 40 - a pane moss ‘yntinues and new jobs are taken up by the ieee Fire 21 shows cat there are four job th a the pietne afer Uh iil Bling tne ae i first stage, This way, jobs move in the tat are being executed at any given point pipeline, [2] TS = d 7 = wt =} } ar] Fig, 21 Bxample-Phpeine ‘the stages. The fourth important alized to do particular sub-functions are is replicated, This amounts to saying Tame bcs could be designed wit better east and sre (Bimlaed forthe specialized Contrast this with a usual approach sors are replicated thus requitin. more Pectca Pe i PARLE co, 2:14 PIPELINED LOGIC i lecithin The pipeline fouematized in Fig. 22. In Fig. 22, an individual stage pero retage Pini pected (0 by the nich (ora cacked reper 8 tom operation on este arial o data the pipeline, This dain latched ya arrival st ja the input ltciatch othe first stage). The input arrival signa isda’ 2 Eagan subsequently to the other stages) wherein it ltche ty Fae alge fist sage which provides inp to the second nig. Tie {Fenn erie nt when toni alin tga sn ntl np itch he tage yee ed yale (ohh Wis tous stage lly the oleae oo git longwth hs a ns ahown n Fig 2.2 The schematic prevented in Fi, 22 fms eo a tao in lgie ori The iret may be cocked ata maxing for pling compete ime delay the combinational logic inthe stage and he dey rate whic ee porceample, we aeume Tne and 13 9 an the setting tes fr the ack the creuit with # maximum clock frequency a fand the Inteh respectively, we can cl Crees Le. 60 MHz and Gerefore we can obtain one computation every 20 ne fem: ‘The pipelines found UL] : JI 7 i r a eee Note L Latch o Register Fig. 22 Electroric Implementation of @ Pipoine 2.1.2 ORTHOGONALITY OF PIPELINE AND SIMD PARALLEL PROCESSORS he assured length of vet? In vector processors, pipelining is commonly employed due to t dual vector elements. which allows the same instruction to be executed on the indivi ‘example consider a vector operation: R=(X* Y) + 2/M, where XY, Z-and Mare the input vectors and Bis the result A vector machine program for the above job would look like: LOAD x MULTY ADDZ DIV M STORE R

You might also like