CS 240A Applied Parallel ComputingCourse bureacracyHomework 1Two examples of big parallel problemsSocial newtork analysisBetweenness Centrality using Sparse GEMMBC performance in distributed memoryParallel Computers TodaySlide 9Cray XMT (highly multithreaded shared memory)Slide 11The Computer Architecture ChallengeWhy are powerful computers parallel?Technology Trends: Microprocessor CapacityScaling microprocessorsHow fast can a serial computer be?“Automatic” Parallelism in Modern MachinesNumber of transistors per processor chipSlide 19Generic Parallel Machine ArchitectureCS 240ACS 240AApplied Parallel ComputingApplied Parallel ComputingJohn R. [email protected]://www.cs.ucsb.edu/~cs240aThanks to Kathy Yelick and Jim Demmel at UCB for some of their slides.Course bureacracyCourse bureacracy•Read course home page http://www.cs.ucsb.edu/~cs240a/homepage.html•Join Google discussion group (see course home page)•Accounts on Triton, San Diego Supercomputing Center:•Use “ssh –keygen –t rsa” and then email your “id_rsa.pub” file to Stefan Boeriu, [email protected]•If you weren’t signed up for the course as of last week, email me your registration info right away•Triton logon demo & tool intro coming soon– watch Google group for detailsHomework 1Homework 1•See course home page for details.•Find an application of parallel computing and build a web page describing it.•Choose something from your research area.•Or from the web or elsewhere.•Create a web page describing the application. •Describe the application and provide a reference (or link)•Describe the platform where this application was run•Find peak and LINPACK performance for the platform and its rank on the TOP500 list•Find the performance of your selected application•What ratio of sustained to peak performance is reported?•Evaluate the project: How did the application scale, ie was speed roughly proportional to the number of processors? What were the major difficulties in obtaining good performance? What tools and algorithms were used?•Send us (John and Hans) the link (we will post them)•Due next Monday, April 5Two examples of big parallel problemsTwo examples of big parallel problems•Bone density modeling: •Physical simulation•Lots of numerical computing•Spatially local •Vertex betweenness centrality:•Exploring an unstructured graph•Lots of pointer-chasing•Little numerical computing•No spatial localitySocial newtork analysisSocial newtork analysisBetweenness Centrality (BC)CB(v): Among all the shortest paths, what fraction of them pass through the node of interest?Brandes’ algorithmA typical software stack for an application enabled with the Combinatorial BLAS6XAT(ATX).*¬X123475Betweenness Centrality using Betweenness Centrality using Sparse GEMMSparse GEMM•Parallel breadth-first search is implemented with sparse matrix-matrix multiplication•Work efficient algorithm for BCBC performance in distributed memory BC performance in distributed memory • TEPS: Traversed Edges Per Second• Batch of 512 vertices at each iteration• Code only a few lines longer than Matlab versionInput: RMAT scale N2N verticesAverage degree 8Pure MPI-1 version. No reliance on any particular hardwareParallel Computers TodayParallel Computers TodayOak Ridge / Cray Jaguar> 1.75 PFLOPSTwo Nvidia 8800 GPUs> 1 TFLOPSIntel 80-core chip> 1 TFLOPS TFLOPS = 1012 floating point ops/sec PFLOPS = 1,000,000,000,000,000 / sec (1015)AMD Opteron quad-core dieCray XMT Cray XMT (highly multithreaded (highly multithreaded shared memory)shared memory)i = ni = 3i = 2i = 1. . . 1 2 3 4 Sub- problem Ai = ni = 1i = 0. . .Su b- problem BSubproblem ASerial CodeUnused streams. . . .Programs running in parallelConcurrent threads of computationHardware streams (128)Instruction Ready Pool;Pipeline of executing instructions•Top 500 List•http://www.top500.org/list/2009/11/100The Computer Architecture ChallengeThe Computer Architecture ChallengeMost high-performance computer designs allocate resources to optimize Gaussian elimination on large, dense matrices.Originally, because linear algebra is the middleware of scientific computing.Nowadays, mostly for bragging rights.=xPALUWhy are powerful Why are powerful computers parallel?computers parallel?Technology Trends: Microprocessor CapacityTechnology Trends: Microprocessor Capacity Moore’s Law: #transistors/chip doubles every 1.5 years Moore’s LawMicroprocessors have become smaller, denser, and more powerful.Gordon Moore (co-founder of Intel) predicted in 1965 that the transistor density of semiconductor chips would double roughly every 18 months. Slide source: Jack DongarraScaling microprocessorsScaling microprocessors•What happens when feature size shrinks by a factor of x?•Clock rate used to go up by x , but no longer•Clock rates are topping out due to power (heat) limits•Transistors per unit area goes up by x2•Die size also tends to increase•Typically another factor of ~x•Raw computing capability of the chip goes up by ~ x3 !•But it’s all for parallelism, not speedHow fast can a serial computer be?How fast can a serial computer be?•Consider the 1 Tflop sequential machine•data must travel some distance, r, to get from memory to CPU•to get 1 data element per cycle, this means 10^12 times per second at the speed of light, c = 3e8 m/s•so r < c/10^12 = .3 mm•Now put 1 TB of storage in a .3 mm^2 area •each word occupies ~ 3 Angstroms^2, the size of a small atomr = .3 mm1 Tflop 1 TB sequential machine““Automatic” Parallelism in Modern MachinesAutomatic” Parallelism in Modern Machines•Bit level parallelism•within floating point operations, etc.•Instruction level parallelism•multiple instructions execute per clock cycle•Memory system parallelism•overlap of memory operations with computation•OS parallelism•multiple jobs run in parallel on commodity SMPsThere are limits to all of these -- for very high performance, user must identify, schedule and coordinate parallel tasksNumber of transistors per processor chipNumber of transistors per processor chipi4004i80286i80386i8080i8086R3000R2000R10000Pentium1,00010,000100,0001,000,00010,000,000100,000,0001970 1975 1980 1985 1990 1995 2000 2005YearTransistorsNumber of transistors per processor chipNumber of transistors per processor
View Full Document