More Related Content
What's hot (20)
Viewers also liked (19)
Similar to Scalable Parallel Computing on Clouds (20)
Recently uploaded (20)
Scalable Parallel Computing on Clouds
- 1. Scalable Parallel Computing on Clouds Thilina Gunarathne (tgunarat@indiana.edu) Advisor : Prof.Geoffrey Fox (gcf@indiana.edu) Committee : Prof.Judy Qui, Prof.Beth Plale, Prof.David Leake
- 2. Clouds for scientific computations No Zero Horizontal upfront maintenance scalability cost Compute, storage and other services Loose service guarantees Not trivial to utilize effectively
- 3. Scalable Programming Models Parallel Computing on Clouds Scalability Performance Fault Tolerance Monitoring
- 4. Pleasingly Parallel Frameworks Cap3 Sequence Assembly 100% 90% Parallel Efficiency 80% 70% DryadLINQ Hadoop 60% EC2 50% Azure 512 1512 2512 3512 Number of Files 150 Per Core Per File Time (s) 100 DryadLINQ 50 Hadoop EC2 Azure 0 Classic Cloud Frameworks 512 1024 1536 2048 2560 3072 3584 4096 Number of Files
- 5. Programming Model Fault Map Moving Computation Tolerance Reduce to Data Scalable Ideal for data intensive pleasingly parallel applications
- 6. MRRoles4Azure Azure Cloud Services • Highly-available and scalable • Utilize eventually-consistent , high-latency cloud services effectively • Minimal maintenance and management overhead Decentralized • Avoids Single Point of Failure • Global queue based dynamic scheduling • Dynamically scale up/down MapReduce • First pure MapReduce for Azure • Typical MapReduce fault tolerance
- 7. MRRoles4Azure Azure Queues for scheduling, Tables to store meta-data and monitoring data, Blobs for input/output/intermediate data storage.
- 9. SWG Sequence Alignment Performance comparable to Hadoop, EMR Costs less than EMR Smith-Waterman-GOTOH to calculate all-pairs dissimilarity
- 10. Data Intensive Iterative Applications Compute Communication Reduce/ barrier Broadcast Smaller Loop- Variant Data New Iteration Larger Loop- Invariant Data • Growing class of applications – Clustering, data mining, machine learning & dimension reduction applications – Driven by data deluge & emerging computation fields
- 11. Extensions to support Iterative MapReduce for Azure Cloud broadcast data Merge step Hybrid intermediate In-Memory/Disk data transfer caching of static data http://salsahpc.indiana.edu/twister4azure
- 12. Hybrid Task Scheduling First iteration through queues Cache aware hybrid scheduling Decentralized Fault Tolerant Multiple MapReduce applications within an iteration Left over tasks Data in cache + Task meta data history New iteration in Job Bulleting Board
- 13. First iteration performs the Overhead between iterations initial data fetch Task Execution Time Histogram Number of Executing Map Task Histogram Scales better than Hadoop on bare metal Strong Scaling with 128M Data Points Weak Scaling
- 14. Applications • Bioinformatics pipeline Clustering Cluster Indices Pairwise Gene Alignment & Visualization 3D Plot Sequences Distance Calculation Coordinates Distance Matrix Multi- Dimensional Scaling http://salsahpc.indiana.edu/
- 15. Multi-Dimensional-Scaling • Many iterations • Memory & Data intensive • 3 Map Reduce jobs per iteration • Xk = invV * B(X(k-1)) * X(k-1) • 2 matrix vector multiplications termed BC and X BC: Calculate BX X: Calculate invV Calculate Stress Map Reduce Merge Map (BX) Merge Reduce Map Reduce Merge New Iteration
- 16. Performance adjusted for sequential performance difference First iteration performs theSize Scaling Data Weak Scaling initial data fetch Azure Instance Type Study Number of Executing Map Task Histogram
- 17. BLAST Sequence Search Scales better than Hadoop & EC2- Classic Cloud
- 18. Current Research • Collective communication primitives • Exploring additional data communication and broadcasting mechanisms – Fault tolerance • Twister4Cloud – Twister4Azure architecture implementations for other cloud infrastructures
- 19. Contributions • Twister4Azure – Decentralized iterative MapReduce architecture for clouds – More natural Iterative programming model extensions to MapReduce model – Leveraging eventual consistent cloud services for large scale coordinated computations • Performance comparison of applications in Clouds, VM environments and in bare metal • Exploration of the effect of data inhomogeneity for scientific MapReduce run times • Implementation of data mining and scientific applications for Azure cloud as well as using Hadoop/DryadLinq • GPU OpenCL implementation of iterative data analysis algorithms
- 20. Acknowledgements • My PhD advisory committee • Present and past members of SALSA group – Indiana University • National Institutes of Health grant 5 RC2 HG005806-02. • FutureGrid • Microsoft Research • Amazon AWS
- 21. Selected Publications 1. Gunarathne, T., Wu, T.-L., Choi, J. Y., Bae, S.-H. and Qiu, J. Cloud computing paradigms for pleasingly parallel biomedical applications. Concurrency and Computation: Practice and Experience. doi: 10.1002/cpe.1780 2. Ekanayake, J.; Gunarathne, T.; Qiu, J.; , Cloud Technologies for Bioinformatics Applications, Parallel and Distributed Systems, IEEE Transactions on , vol.22, no.6, pp.998-1011, June 2011. doi: 10.1109/TPDS.2010.178 3. Thilina Gunarathne, BingJing Zang, Tak-Lon Wu and Judy Qiu. Portable Parallel Programming on Cloud and HPC: Scientific Applications of Twister4Azure. In Proceedings of the forth IEEE/ACM International Conference on Utility and Cloud Computing (UCC 2011) , Melbourne, Australia. 2011. To appear. 4. Gunarathne, T., J. Qiu, and G. Fox, Iterative MapReduce for Azure Cloud, Cloud Computing and Its Applications, Argonne National Laboratory, Argonne, IL, 04/12-13/2011. 5. Gunarathne, T.; Tak-Lon Wu; Qiu, J.; Fox, G.; MapReduce in the Clouds for Science, Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference on , vol., no., pp.565-572, Nov. 30 2010- Dec. 3 2010. doi: 10.1109/CloudCom.2010.107 6. Thilina Gunarathne, Bimalee Salpitikorala, and Arun Chauhan. Optimizing OpenCL Kernels for Iterative Statistical Algorithms on GPUs. In Proceedings of the Second International Workshop on GPUs and Scientific Applications (GPUScA), Galveston Island, TX. 2011. 7. Gunarathne, T., C. Herath, E. Chinthaka, and S. Marru, Experience with Adapting a WS-BPEL Runtime for eScience Workflows. The International Conference for High Performance Computing, Networking, Storage and Analysis (SC'09), Portland, OR, ACM Press, pp. 7, 11/20/2009 8. Judy Qiu, Jaliya Ekanayake, Thilina Gunarathne, Jong Youl Choi, Seung-Hee Bae, Yang Ruan, Saliya Ekanayake, Stephen Wu, Scott Beason, Geoffrey Fox, Mina Rho, Haixu Tang. Data Intensive Computing for Bioinformatics, Data Intensive Distributed Computing, Tevik Kosar, Editor. 2011, IGI Publishers.
- 22. Questions? Thank You! http://salsahpc.indiana.edu/twister4azure http://www.cs.indiana.edu/~tgunarat/
Editor's Notes
- #3: The utility computing model introduced by cloud computing combined with the rich set of cloud infrastructure services offers a very viable environment for the scientists to process massive amounts of data. Absence of upfront infrastructure spending and zero maintenance cost coupled with the ability to horizontally scale makes scientists very happy.However, clouds offer unique reliability and sustained performance challenges for large scale parallel computations due to the virtualization, multi-tenancy, non-dedicated commodity connectivity and etc..Also the cloud services offer unique loose services guarantees such as eventual consistency.This makes it necessary to have specializeddistributed parallel computing frameworks build specifically for cloud characteristics to harness the power of clouds both easily and effectively.
- #4: My research focuses on creating scalable parallel programming frameworks specifically designed for cloud environments to support efficient, reliable and user friendly execution of data intensive iterative computations.The goals of my work are designing suitable programming models, achieving good scalability and good performance, providing framework managed fault tolerance ensuring eventual completion of the computations and having good monitoring tools to perform scalable parallel computing on clouds.
- #5: Out first step was to build a pleasingly computing framework for cloud environments to process embarrassingly parallel applications. This would be similar to a simple job submission framework. We implemented several applications including sequence assembly, Blast sequence search and couple of dimensional scaling interpolation algorithms . We were able to achieve comparable performance. This motivated us to go a step further and extend our work to MapReduce type applications..
- #6: MapReduce provides a easy to use programming model together with very good fault tolerance and scalability for large scale applications. MapReduce model is proving to be Ideal for data intensive pleasingly parallel applications in commodity hardware and in clouds.In our current research, we improve and extend MapReduce programming model to support richer applications patterns efficiently.
- #7: We started by creating a decentralized MapReduce framework for Azure cloud utilizing the highly-available and scalable, Azure infrastructure services as the building blocks. MRRoles4Azure hides the complexity of cloud services from the users and is designed to co-exist with the eventual consistent nature of cloud services. The decentralized architecture avoid the single point of failure and bottleneck, while global queue based dynamic scheduling achieves better load balancing.We selected Azure platform, as at that time there weren’t any distributed data processing frameworks available for Azure. We performed the first public release of MRRoles4Azure in the 4th quarter of 2010 as the first pure MapReduce framework for Azure.
- #8: Ability to dynamically scale up/downEasy testing and deployment Combiner stepWeb based monitoring console
- #9: One major challenge we encountered is in implementing the global barrier before the reduce task processing. It became a challenge due to the eventual consistency nature of cloud services. We got through it by using special data structures to keep track of the number of reduce data products each map task generated for each reduce task
- #10: ~123 million sequence alignments, for under 30$ with zero up front hardware cost,Add call-outs
- #11: Iterative computations are at the core of the vast majority of data intensive scientific computations. need to process massive amounts of data and the emergence of data intensive computational fields, such as bioinformatics, chemical informatics and web mining. Most of these applications consists of iterative computation and communication steps where single iterations can easily be specified as MapReduce computations.Large input data sizes which are loop-invariant and can be reused across iterations.Loop-variant results.. Orders of magnitude smaller…
- #12: additional merge step to the programming model, which would be the point where the computations decide whether to go for a new iteration or not. Extensions to support broadcast data as an additional input to Map & reduce functions.support in-memory caching of static loop-invariant data between iterations. We achieved this by having cacheable input formats, requiring no changes to the map reduce programming model. The tasks of iterative computations are much finer grained and the intermediate data are relatively smaller than typical map reduce computations. We added support for hydrid transfer of intermediate data.First iterative MR on Azure.. Released in early May 2011.
- #13: No master with global knowledge of cached data products. Rather than pushing the workers pick tasks.Multiple MapReduce applications within an iteration supporting much richer application patterns
- #14: Right(c): Twister4Azure executing Map Task histogram for 128 million data points in 128 Azure small instancesFigure 5. KMeansClustering Scalability. Left(a): Relative parallel efficiency of strong scaling using 128 million data points. Center(b): Weak scaling. Workload per core is kept constant (ideal is a straight horizontal line).
- #17: Weak scaling where workload per core is ~constant. Ideal is a straight horizontal line. Center : Data size scaling with 128 Azure small instances/cores, 20 iterations. Instance type study using 76800 data points, 32 instances, 20 iterations. Right: Twister4Azure executing Map Task histogram for 144384 x144384 distance matrix in 64 Azure small instances, 10 iterations
- #20: Include inhomogeneity and VM overhead resultsGPU work as a contributionApplication implementation on Azure as a contribution
- #30: Client driver loads the map & reduce tasks to queues in parallel using TPL..Create the task monitoring table. Standalone client or a web client. Can wait for completion.Explain the advantages of using Azure queues.Explain the advantages of using Azure table.. Scalability. Ease of use.. No maintenance overhead. No need to install DB. Easily visualize using a webrole.
- #31: Map & Reduce workers pick up map tasks from the queue
- #32: Map workers download data from Blob storage and start processing- – update the status in the task monitoring table.Advantages of blob storage.Custom input/output formats & keys..
- #33: Finished Map tasks upload result data sets to Azure Storage and then add entries for the respective reduce task tables. – update the status. Get the next task from the queue and start processing it.Custom part
- #34: Reduce tasks notice the intermediate data product meta-data in reduce task tables and start downloading them -> update the reduce task tablesThis happens when the map tasks are actually processing the next set of map tasks..
- #35: Reduce tasks start reducing, when all the map tasks are finished and when the respective reduce tasks are finish downloading the intermediate data products.Custom output formats