MONTE CARLO METHODS
MONTE CARLO METHODS CIS 5930
Popular in Course
Popular in Comm Sciences and Disorders
This 23 page Class Notes was uploaded by Mrs. Rahul Wuckert on Thursday September 17, 2015. The Class Notes belongs to CIS 5930 at Florida State University taught by Xin Yuan in Fall. Since its upload, it has received 17 views. For similar materials see /class/205697/cis-5930-florida-state-university in Comm Sciences and Disorders at Florida State University.
Reviews for MONTE CARLO METHODS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
PROCESS ARRIVAL PATTERN FOR MPI COLLECTIVE OPERATIONS Based on Paper A Study of Process Arrival PaHerns for MPI Collec ve Operafions Presenter Zheng GU Obiective of this study B What are the process arrival patterns in practical MPI programs I Whether we can control the process arrival patterns in our MPI program 1 What is the impact of imbalanced process arrival patterns on collective communicatin algorithms III How can we deal with imbalanced process arrival patterns Definition MPI collective communication Process arrival pattern Balance amp imbalance process arrival pattern MPI Collective Communication III In MPI collective communication are implemented on top of pointtopoint operationssendrecv and require more than two paries eg broadcast reduce D Three classes of collective operations Synchronization MPIBarrier data movement broadcast scatter gather collective computation reduce scan Process Arrival Pattern III The timing when different processes arrive at an MPI collective operation I Caused by early completion or late start of some messages El Process arrival pattern VS application load balancing problem I ALB is orders of magnitude larger I It is possible to balance ALB but not PAP why Why hard to balance PAP III The process arrival pattern is affected by Application a Operating System System hardware Communication library 9 F1 92 p3 arrivaltime 3 exit time IZao 50 average E 1 A mivaltime 7 E 39 E 1 i i 6 E glee 39 al 3er 3 V V v Process Arrival PatternCon r Define balance amp imbalance I Let T be the time to communicate one message in the operation El Represent process arrival pattern ai III Worst case imbalance time maxai minai El Worst case imbalance factor is wT T is time to communicate one message in the operation I If worst case imbalance fator lt l balanced El Else imbalanced How balance is the process arrival pattern of existing MPI operations I Existing collective communication algorithms are designed analyzed and evaluated with the assumption ofthe balanced process arrival pattern Is this good enough Benchmarks on 2 typical clusters Lemieux Beowulf Lemieux III 750 compoq olphoserver E545 nodes with iGHz SMP processors amp AGB memory I Connection Quodrics El 08 Tru64 Unix Operating System Beowulf III 16 Dell Dimension 2400 nodes with 28 GHZ P4 Processorr amp 128MB memory I Connection Dell Powerconnec r 2624 leps Ethernet switch 1 OS LinuxFedoro Data Collection D The data is collected by the MPI wrapper library I Wrapper records an event at each MPI process for each entrance and exit of each MPI collective communication routine El Information includes timing the operation the message size D Times are measured using the MPIWtime routine benchmark description FT solves PDE with forward and inverse FFTs IS sorts integer keys in parallel LAMMPS simulates dynamics of molecules in different states PARADYN aim dynamics of metals and metal alloys molecules NBODY simulates effects of gravitational forces on N bodies NTUBE 1 performs molecular dynamics calculations of diamond NTUBE 2 performs molecular dynamics calculations of diamond b enchmark routine size FT alltoall 131076 1 6 33 1 93 4 P W 6 1 290 N BODY 5000 N TUBE 1 16000 E 2 8 Summary of Benchmar kcont imbalance factor benchmark Lemieux Ir 128 Beowulf average worst average worst FT 910 652 278 12K IS 010 358 14K 11K LAMMPS 400 190 273 630 PARAD YN 910 460 120 790 NBODY 130 132 120 500 NTUBE 1 48K 38K 430 170 NTUBE 2 85K 347K 900 390 average of the worst case imbalance factors for all programs on both clusters are quite large which excludes the 39Factor of load balance PAP depends on system architecture NTUBEl amp NTUBE2 has smaller IF on Beowulf Micro benchmark 1 MPIBarrier 2 for 10 ilt1000 i 3 compute for roughly X milliseconds 4 for m0 mlt XTIME m 5 for kzl klt1000 k 6 ak bk1 ak 1 2 7 arrive MPLWtimeO 8 MPIAlltoall 9 leavei MPLWtimeO 10 Figure 4 Code segment for a micro benchmark comp time worst case imba1111100 facta ign exit computation arrival 501115 152 1 07 234 i 03 325 1 08 1001113 152 i 06 468 1 16 545 i 19 2001118 150 03 874 1 18 927 i 19 4001113 151 d 08 160 i 19 164 i 20 8001118 150 i 03 320 i 36 322 i 36 comp time worst case imbalance factor exit computation arrival 501113 507 l 129 316 i 002 702 l 129 100ms 432 l 100 752 i 002 953 i 099 2001113 371 i 011 1418 i 002 1517 I 000 4001113 022 i 023 3141 i 030 3317 t 035 800mg 1102 i 041 5024 i 005 5029 i 020 Conclusion from statistics III Different processors take different time to run the same computation II Different processors take different time to perform the communication CI The imbalance in both communication and computation are contributing to the imbalance in the process arrival patterns Impacts of imbalanced PAP MPIBccs r MPIAII roaI Attribute of operations II MPAtoa El Inherently synchronized I MPIBcast I Not inherently synchronized
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'