Parallel Computing · · Roman Trobec Maria´n Vajtersˇic Peter Zinterhof Editors Parallel Computing Numerics, Applications, and Trends 123 Editors RomanTrobec Maria´nVajtersˇic Dept.ofComm.Systems DepartmentofComputerSciences JozˇefStefanInstitute UniversityofSalzburg Jamova39 Jakob–HaringerStr.2 SI-1000Ljubljana 5020Salzburg Slovenia Austria [email protected] [email protected] and PeterZinterhof MathematicalInstitute DepartmentofComputerSciences DepartmentofInformatics UniversityofSalzburg SlovakAcademyofSciences Jakob–HaringerStr.2 Du´bravska´9 5020Salzburg 84000Bratislava Austria Slovakia [email protected] [email protected] ISBN978-1-84882-408-9 e-ISBN978-1-84882-409-6 DOI10.1007/978-1-84882-409-6 SpringerDordrechtHeidelbergLondonNewYork BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary LibraryofCongressControlNumber:2009926892 (cid:2)c Springer-VerlagLondonLimited2009 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permittedundertheCopyright,DesignsandPatentsAct1988,thispublicationmayonlybereproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers,orinthecaseofreprographicreproductioninaccordancewiththetermsoflicensesissued bytheCopyrightLicensingAgency.Enquiriesconcerningreproductionoutsidethosetermsshouldbe senttothepublishers. Theuseofregisterednames,trademarks,etc.,inthispublicationdoesnotimply,evenintheabsenceofa specificstatement,thatsuchnamesareexemptfromtherelevantlawsandregulationsandthereforefree forgeneraluse. Thepublishermakesnorepresentation,expressorimplied,withregardtotheaccuracyoftheinformation containedinthisbookandcannotacceptanylegalresponsibilityorliabilityforanyerrorsoromissions thatmaybemade. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Toallwhomakeourlivesworthwhile. Preface The use of parallel programming and architectures is essential for simulating and solvingproblemsinmoderncomputationalpractice.Therehasbeenrapidprogress in microprocessor architecture, interconnection technology and software develop- ment, which are influencing directly the rapid growth of parallel and distributed computing.However,inordertomakethesebenefitsusableinpractice,thisdevel- opment must be accompanied by progress in the design, analysis and application aspects of parallel algorithms. In particular, new approaches from parallel numer- ics are important for solving complex computational problems on parallel and/or distributedsystems. Thecontributionstothisbookarefocusedontopicsmostconcernedinthetrends of today’s parallel computing. These range from parallel algorithmics, program- ming,tools,networkcomputingtofutureparallelcomputing.Particularattentionis paid to parallel numerics: linear algebra, differential equations, numerical integra- tion,numbertheoryandtheirapplicationsincomputersimulations,whichtogether form the kernel of the monograph. We expect that the book will be of interest to scientistsworkingonparallelcomputing,doctoralstudents,teachers,engineersand mathematicians dealing with numerical applications and computer simulations of naturalphenomena. The roots of this book are in Parallel Numerics, an initiative that has been ac- tiveintheCentralEuropeanRegionsince1994,startingwiththeCentralEuropean Initiative(CEI)jointresearchprojectProgrammingEnvironments,Algorithms,Ap- plications,CompilersandToolsforParallelComputation(PACT).Theinitialscope was focused on the new results and ideas related to parallel numerics. Later the research and applied interests were broadened to theoretical and practical aspects ofparallelanddistributedcomputing,creatingafruitfulcombinationoftheoretical andappliedresearch.Besidesnumericalapplications,theparallelsolutionoffinan- cial, medical and other problems from the natural and technical sciences has been incorporated. We are glad to see that the output of this initiative has become use- fulineverydaycomputationalpractice,throughadoptingnewalgorithmicsolutions and/orprogressiveprogrammingtechniquesandarchitecturalimprovements. vii viii Preface We are grateful to the authors for their valuable contributions which make this book rich in content. We are grateful also to Springer-Verlag London for their ex- cellenttechnicalandeditorialsupport.WeareindebtedtotheJožefStefanInstitute andtheUniversityofSalzburgfortheirgeneroussupportofourwork. RomanTrobec Ljubljana,Salzburg MariánVajteršic December,2008 PeterZinterhof List of Contributors SelimG.Akl SchoolofComputing,Queen’sUniversity,Kingston,Ontario,Canada, e-mail:[email protected] ToreBirkeland DepartmentofMathematics,UniversityofBergen,Norway, e-mail:[email protected] UrbanBorštnik NationalInstituteofChemistry,Ljubljana,Slovenia, e-mail:[email protected] RajkumarBuyya GridComputingandDistributedSystemsLaboratory,UniversityofMelbourne, Australia,e-mail:[email protected] UrošCˇibej FacultyofComputerandInformationScience,UniversityofLjubljana,Slovenia, e-mail:[email protected] MatjažDepolli DepartmentofCommunicationSystems,JožefStefanInstitute,Ljubljana,Slovenia, e-mail:[email protected] StefanDonath ChairforSystemSimulation,Friedrich-AlexanderUniversityErlangen-Nuremberg, Germany,e-mail:[email protected] ThomasFahringer InstituteforComputerScience,UniversityofInnsbruck,Austria, e-mail:[email protected] ix x ListofContributors ChristianFeichtinger Chair for System Simulation, Friedrich-Alexander University Erlangen- Nuremberg,Germany,e-mail:christian.feichtinger@informatik. uni-erlangen.de BogdanFilipicˇ DepartmentofIntelligentSystems,JožefStefanInstitute,Ljubljana,Slovenia, e-mail:[email protected] JanGötz ChairforSystemSimulation,Friedrich-AlexanderUniversityErlangen-Nuremberg, Germany,e-mail:[email protected] AndreasGrothey SchoolofMathematics,UniversityofEdinburgh,England, e-mail:[email protected] KlausIglberger ChairforSystemSimulation,Friedrich-AlexanderUniversityErlangen-Nuremberg, Germany,e-mail:[email protected] DušankaJanežicˇ NationalInstituteofChemistry,Ljubljana,Slovenia, e-mail:[email protected] PeterJez DepartmentofComputerSciences,UniversityofSalzburg,Austria, e-mail:[email protected] RadeKutil DepartmentofComputerSciences,UniversityofSalzburg,Austria, e-mail:[email protected] MariusNagy SchoolofComputing,Queen’sUniversity,Kingston,Ontario,Canada, e-mail:[email protected] GabrielOkša MathematicalInstitute,DepartmentofInformatics,SlovakAcademyofSciences, Bratislava,Slovakia,e-mail:[email protected] MatejPraprotnik NationalInstituteofChemistry,Ljubljana,Slovenia, e-mail:[email protected] ListofContributors xi JarmoRantakokko DepartmentofInformationTechnology,UppsalaUniversity,Sweden, e-mail:[email protected] UlrichRüde ChairforSystemSimulation,Friedrich-AlexanderUniversityErlangen-Nuremberg, Germany,e-mail:[email protected] TorSørevik DepartmentofMathematics,UniversityofBergen,Norway, e-mail:[email protected] AnthonySulistio GridComputingandDistributedSystemsLaboratory,UniversityofMelbourne, Australia,e-mail:[email protected] MichaelThuné DepartmentofInformationTechnology,UppsalaUniversity,Sweden, e-mail:[email protected] RomanTrobec DepartmentofCommunicationSystems,JožefStefanInstitute,Ljubljana,Slovenia, e-mail:[email protected] AndreasUhl DepartmentofComputerSciences,UniversityofSalzburg,Austria, e-mail:[email protected] MariánVajteršic Department of Computer Sciences, University of Salzburg, Austria, and MathematicalInstitute,DepartmentofInformatics,SlovakAcademyofSciences, Bratislava,Slovakia, e-mail:[email protected] PeterZinterhof DepartmentofComputerSciences,UniversityofSalzburg,Austria, e-mail:[email protected] Contents 1 Overview – Parallel Computing: Numerics, Applications, and Trends..................................................... 1 MariánVajteršic,PeterZinterhofandRomanTrobec 1.1 Introduction.............................................. 1 1.1.1 ParallelNumerics ................................. 2 1.1.2 ParallelArchitectures .............................. 4 1.1.3 Scalability ....................................... 6 1.1.4 Supercomputers................................... 7 1.1.5 GridComputing................................... 8 1.1.6 ParallelProgrammingLanguages .................... 9 1.1.7 ParallelCompilers................................. 11 1.2 BookChapters............................................ 13 1.2.1 IntroductiontoParallelComputation ................. 13 1.2.2 ToolsforParallelandDistributedComputing .......... 14 1.2.3 GridComputing................................... 15 1.2.4 ParallelStructuredAdaptiveMeshRefinement ......... 16 1.2.5 ApplicationsandParallelImplementationofQMC Integration ....................................... 17 1.2.6 Parallel Evolutionary Computation Framework forSingle-andMultiobjectiveOptimization ........... 18 1.2.7 WaLBerla:ExploitingMassivelyParallelSystemsfor LatticeBoltzmannSimulations ...................... 20 1.2.8 ParallelPseudo-Spectral Methods for theSolution oftheTimeDependentSchrödingerEquation .......... 21 1.2.9 ParallelApproachesinMolecularDynamicsSimulations 23 1.2.10 Parallel Computer Simulation of Heat Transfer inBio-Tissue ..................................... 24 1.2.11 SVDComputinginLSIApplicationsforDataRetrieval . 25 1.2.12 Short-VectorSIMDParallelizationinSignalProcessing . 27 1.2.13 FinancialApplications:ParallelPortfolioOptimization .. 29 1.2.14 FutureofParallelComputing........................ 30 xiii