ECE257 Numerical Methods andECE257 Numerical Methods andScientific ComputingScientific ComputingParallel AlgorithmsParallel AlgorithmsSome material adapted from K. Yelick’s Berkeley CS267 and J. Gilbert’s UCSB CS240A slidesECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTodayToday’’s class:s class:••Parallel Algorithms for Numerical MethodsParallel Algorithms for Numerical Methods––Matrix MultiplicationMatrix Multiplication––Partial Differential EquationsPartial Differential EquationsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutParallelismParallelism••Single computers have limited speedSingle computers have limited speed••In theory, putting several computersIn theory, putting several computerstogethers should increase the speedtogethers should increase the speed••Finding the parallelism and getting it to workFinding the parallelism and getting it to workis not trivialis not trivialECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutSome Challenging ComputationsSome Challenging Computations••ScienceScience––Global climate modelingGlobal climate modeling––Astrophysical modelingAstrophysical modeling––Biology: genomics; protein folding; drug designBiology: genomics; protein folding; drug design––Computational ChemistryComputational Chemistry––Computational Material Sciences and Computational Material Sciences and NanosciencesNanosciences••EngineeringEngineering––Crash simulationCrash simulation––Semiconductor designSemiconductor design––Earthquake and structural modelingEarthquake and structural modeling––Computation fluid dynamics (airplane design)Computation fluid dynamics (airplane design)––Combustion (engine design)Combustion (engine design)••BusinessBusiness––Financial and economic modelingFinancial and economic modeling––Transaction processing, web services and search enginesTransaction processing, web services and search engines••DefenseDefense––Nuclear weapons -- test by simulationNuclear weapons -- test by simulation––CryptographyCryptographyECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutUnits of Measure in HPCUnits of Measure in HPC••High Performance Computing (HPC) units are:High Performance Computing (HPC) units are:––Flops: floating point operationsFlops: floating point operations––Flop/s: floating point operations per secondFlop/s: floating point operations per second––Bytes: size of data (double precision floating point number is 8)Bytes: size of data (double precision floating point number is 8)••Typical sizes are millions, billions, trillionsTypical sizes are millions, billions, trillions……MegaMegaMflopMflop/s = 10/s = 1066 flop/sec flop/secMbyteMbyte = 10 = 1066 byte byte (also 2(also 22020 = 1048576) = 1048576)GigaGigaGflop/s = 10Gflop/s = 1099 flop/sec flop/secGbyteGbyte = 10 = 1099 byte byte (also 2(also 23030 = 1073741824) = 1073741824)TeraTeraTflop/s = 10Tflop/s = 101212 flop/sec flop/secTbyteTbyte = 10 = 101212 byte byte (also 2(also 24040 = 10995211627776) = 10995211627776)PetaPetaPflopPflop/s = 10/s = 101515 flop/sec flop/secPbyte = 10Pbyte = 101515 byte byte (also 2(also 25050 = 1125899906842624 = 1125899906842624))ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGlobal Climate Modeling ProblemGlobal Climate Modeling Problem••Problem is to compute:Problem is to compute:f(latitude, longitude, elevation, time) f(latitude, longitude, elevation, time)  temperature, pressure, humidity, wind velocity temperature, pressure, humidity, wind velocity•• Approach: Approach:––DiscretizeDiscretize the domain, e.g., a measurement point every 10 kmthe domain, e.g., a measurement point every 10 km––Devise an algorithm to predict weather at time t+1 given tDevise an algorithm to predict weather at time t+1 given t• Uses:- Predict major events,e.g., El Nino- Use in setting airemissions standardsSource: http://www.epm.ornl.gov/chammp/chammp.htmlECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGlobal Climate Modeling ComputationGlobal Climate Modeling Computation••One piece is modeling the fluid flow in the atmosphereOne piece is modeling the fluid flow in the atmosphere––Solve Navier-Stokes problemSolve Navier-Stokes problem••Roughly 100 Flops per grid point with 1 minute timestepRoughly 100 Flops per grid point with 1 minute timestep••Computational requirements:Computational requirements:––To match real-time, need 5x 10To match real-time, need 5x 101111 flops in 60 seconds = 8 Gflop/s flops in 60 seconds = 8 Gflop/s––Weather prediction (7 days in 24 hours) Weather prediction (7 days in 24 hours)  56 Gflop/s 56 Gflop/s––Climate prediction (50 years in 30 days) Climate prediction (50 years in 30 days)  4.8 Tflop/s 4.8 Tflop/s––To use in policy negotiations (50 years in 12 hours) To use in policy negotiations (50 years in 12 hours)  288 288Tflop/sTflop/s--To double the grid resolution, computation is at least 8xTo double the grid resolution, computation is at least 8x--State of the art models require integration of atmosphere, ocean,State of the art models require integration of atmosphere, ocean,sea-ice, land models, plus possibly carbon cycle, geochemistry andsea-ice, land models, plus possibly carbon cycle, geochemistry andmoremore--Current models are coarser than thisCurrent models are coarser than thisHigh ResolutionClimate Modeling onNERSC-3 – P. Duffy,et al., LLNLECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 23John A. ChandyDept. of Electrical and Computer EngineeringUniversity of Connecticut Development of ES started in 1997 with the goal of enablinga comprehensive understanding of global environmentalchanges such as global warming. 26.58 Tflops on a global atmospheric circulation code. 35.86 Tflops (87.5% of peak