Εθνικό Μετσόβιο Πολυτεχνείο. Διπλωματική Εργασία - PDF

Description
Εθνικό Μετσόβιο Πολυτεχνείο Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Optim ization Techniques for Task-based Parallel Program m ing M odels

Please download to get full document.

View again

of 71
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Gadgets

Publish on:

Views: 23 | Pages: 71

Extension: PDF | Download: 0

Share
Transcript
Εθνικό Μετσόβιο Πολυτεχνείο Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Optim ization Techniques for Task-based Parallel Program m ing M odels Διπλωματική Εργασία του Α θ α ν ά σ ιο υ Ά κ α ν θ ο υ Χ α σ ά π η Ε π ιβ λ έπ ω ν : Νεκτάριος Κοζύρης Καθηγητής Ε.Μ.Π. Εργαστήριο Υπολογιστικών Συστημάτων Αθήνα, Ιούλιος Εθνικό Μετσόβιο Πολυτεχνείο Σ ο ή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Εργαστήριο Υπολογιστικών Συστημάτων Optim ization Techniques for Task-based Parallel Program m ing M odels Διπλωματική Εργασία του Α θ α ν ά σ ιο υ Ά κ α ν θ ο υ Χ α σ ά π η Ε π ιβ λ έπ ω ν : Νεκτάριος Κοζύρης Καθηγητής Ε.Μ.Π. Εγκρίθηκε από την τριμελή εξεταστική επιτροπή την 8 η Ιουλίου, Νεκτάριος Κοζύρης Αριστείδης Παγουρτζής Γεώργιος Γκούμας Καθηγητής Ε.Μ.Π. Επικ. Καθηγητής Ε.Μ.Π. Λέκτορας Ε.Μ.Π. Αθήνα, Ιούλιος ... Α θ α ν ά σ ιο ς Ά κ α ν θ ο ς Χ α σ ά π η ς Διπλωματούχος Ηλεκτρολόγος Μηχανικός και Μηχανικός Υπολογιστών Ε.Μ.Π. Copyright All rights reserved Αθανάσιος Άκανθος Χασάπης,. Με επιφύλαξη παντός δικαιώματος. Απαγορεύεται η αντιγραφή, αποθήκευση και διανομή της παρούσας εργασίας, εξ ολοκλήρου ή τμήματος αυτής, για εμπορικό σκοπό. Επιτρέπεται η ανατύπωση, αποθήκευση και διανομή για σκοπό μη κερδοσκοπικό, εκπαιδευτικής ή ερευνητικής φύσης, υπό την προϋπόθεση να αναφέρεται η πηγή προέλευσης και να διατηρείται το παρόν μήνυμα. Ερωτήματα που αφογια κερδοσκοπικό σκοπό πρέπει να απευθύνονται προς τον Οι απόψεις και τα συμπεράσματα που περιέχονται σε αυτό το έγγραφο εκφράζουν τον συγγραφέα και δεν πρέπει να ερμηνευθεί ότι αντιπροσωπεύουν τις επίσημες θέσεις του Εθνικού Μετσόβιου Πολυτεχνείου. Π ε ρ ίλ η ψ η Ένα από τα πιο απαιτητικά προβλήματα στα σύγχρονα παράλληλα υπολογιστικά συστήματα είναι η εκμετάλλευση του μεγάλου αριθμού των νημάτων/πυρήνων που προσφέρει το σύγχρονο υλικό, με σκοπό την βελτίωση της αποδοτικότητας εφαρμογών που εκτελούν κομμάτια κώδικα παράλληλα. Στην βιβλιογραφία και την βιομηχανία έχουν προταθεί διάφορα προγραμματιστικά μοντέλα για αυτό τον σκοπό, στα οποία περιλαμβάνεται και το μοντέλο με παράλληλες εργασίες. Στο συγκεκριμένο μοντέλο, που έχει σκοπό την απλοποίηση του παράλληλου προγραμματισμού, ο προγραμματιστής εκφράζει τον παραλληλισμό της εφαρμογής ως εργασίες που μπορούν να εκτελεστούν παράλληλα και το σύστημα εκτέλεσης αποφασίζει πως αυτές οι εργασίες θα ανατεθούν σε νήματα του λειτουργικού συστήματος προς εκτέλεση. Στόχος της παρούσας εργασίας είναι να εξερευνήσει και να βελτιστοποιήσει τους εσωτερικούς μηχανισμούς της βιβλιοθήκης Intel TBB κάτω από συγκεκριμένους αρχιτεκτονικούς περιορισμούς. Αρχικά εξετάζουμε τον scheduler εργασιών της βιβλιοθήκης, με έμφαση στον μηχανισμό «κλοπής εργασιών», ώστε να αναγνωριστούν οι βασικές λειτουργίες του και ε- κτελούμε profiling για να μετρήσουμε την επιβάρυνση που επιφέρει η καθεμία. Εν συνεχεία, γίνεται προσπάθεια να βελτιστοποιήσουμε τον μηχανισμό τυχαίας κλοπής προσθέτοντας πληροφορίες που αφορούν την αρχιτεκτονική, κυρίως την ιεραρχία κρυφών μνημών και την διαμόρφωση των packages. Υλοποιούμε έναν μηχανισμό κλοπής εργασιών που ακολουθεί δύο πολιτικές: ) κλοπή από τους κοντινότερους πυρήνες (σε απόσταση ιεραρχίας μνήμης), ) κλοπή από τον πιο φορτωμένο με εργασίες πυρήνα. Η πρώτη πολιτική έχει στόχο να μεγιστοποιήσει την επαναχρησιμοποίηση δεδομένων που μοιράζονται πυρήνες στην ιεραρχία μνήμης, μείωση της μόλυνσης της κρυφής μνήμης με μη σχετικά δεδομένα (μείωση των conflict/coherence misses), ενθαρρύνοντας την πρόσβαση δεδομένων σε τοπικό αρχιτεκτονικό επίπεδο. Η δεύτερη πολιτική έχει στόχο την βελτίωση της εξισορρόπησης φορτίου μεταξύ των πυρήνων. Για την αξιολόγηση των παραπάνω παρουσιάζουμε πειραματικά αποτελέσματα που αφορούν την βελτίωση της απόδοσης διάφορων εφαρμογών σε μία SMP πλατφόρμα πυρήνων, μία NUMA πλατφόρμα πυρήνων και μία NUMA πλατφόρμα 3 πυρήνων (με πολυνηματισμό). Λέξεις-Κλειδιά: Intel TBB, παράλληλα προγραμματιστικά μοντέλα βασισμένα σε εργασίες, εξισορρόπηση φορτίου, ιεραρχία κρυφών μνημών, κλοπή εργασιών, τοπικότητα δεδομένων Abstract Abstract One of the most challenging problems in modern parallel processing systems is to exploit the large number of cores/threads available in modern hardware, in order to improve the efficiency of applications by executing pieces of code in parallel. Various programming models have been proposed for this purpose, among which the task programming model. This model aims at simplifying parallel programming. In this model, the programmer expresses parallelism as tasks to be executed in parallel and the runtime system decides how these tasks are assigned to system threads. The goal of this thesis is to explore and optimize the internals of the Intel TBB Library under certain architectural conditions. Initially we examine the library task scheduler, focusing on the task stealing mechanism, in order to identify its basic functions and we run some profiling to verify the task stealing functionality and to measure the overheads of each basic function. Subsequently we attempt to optimize the architecture agnostic random stealing function by adding architecture information, mainly about the cache hierarchy and the socket configuration. We implement a stealing mechanism that adopts certain policies: i) stealing from the closest (in terms of cache/numa locality) core, ii) stealing from the most loaded core. The first policy aims to maximize the reuse of data shared between cores, reduce cache pollution due to irrelevant data (i.e. minimize conflict/coherence misses), and promote data accesses from local NUMA memory nodes. The second policy tries to achieve better load balancing among the cores. To that end, we present experimental results on performance improvement by measuring the speedup of several applications on a -core SMP and a -core (with hyperthreading) NUMA multicore machine. Keywords: Intel TBB, task-based parallel programming models, load balancing, cache hierarchy, work stealing, data locality 6 Ε υ χ α ρ ισ τίε ς Η παρούσα διπλωματική εργασία εκπονήθηκε στο Εργαστήριο Υπολογιστικών Συστημάτων της Σχολής Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών του Εθνικού Μετσόβιου Πολυτεχνείου, υπό την επίβλεψη του Καθηγητή Νεκτάριου Κοζύρη. Θα ήθελα καταρχήν να ευχαριστήσω τον καθηγητή μου κ. Νεκτάριο Κοζύρη για τη εποπτεία του κατά την εκπόνηση της εργασίας μου, για τις γνώσεις και την έμπνευση που μου προσέφερε με την διδασκαλία του, αλλά και για την ευκαιρία που μου έδωσε να ασχοληθώ με ένα θέμα εξαιρετικά ενδιαφέρον στο άριστο περιβάλλον του εργαστηρίου του. Θα ήθελα να εκφράσω την ιδιαίτερη ευγνωμοσύνη μου στον μεταδιδακτορικό ερευνητή κ. Νίκο Αναστόπουλο για την συνεχή του καθοδήγηση στην διάρκεια εκπόνησης της διπλωματικής αυτής εργασίας, ο οποίος με την ανεξάντλητη υπομονή του με ενθάρρυνε συνεχώς και με γέμιζε αισιοδοξία για την πορεία της εργασίας, καθώς και για τις γνώσεις και την εμπειρία που μου μεταλαμπάδευσε μέσω των συζητήσεών μας γύρω από το θέμα της εργασίας. Θα ήθελα ακόμη να ευχαριστήσω τους φίλους και συναδέλφους μου για την στήριξη που μου προσέφεραν και τις εμπειρίες που μοιραστήκαμε. Τέλος, θα ήθελα να ευχαριστήσω την σύντροφό μου, η οποία με στήριζε ψυχολογικά σε όλη την ακαδημαϊκή μου πορεία μέχρι τώρα, δείχνοντας εμπιστοσύνη στις επιλογές μου και στις δυνάμεις μου, και την οικογένειά μου, η οποία με στήριξε με υπομονή στην πορεία μου στο ΕΜΠ τόσα χρόνια, αποτελώντας την σταθερότερη αξία στην ζωή μου. Table of Contents Table of Contents Περίληψη... 5 Abstract... 6 Ευχαριστίες... 7 Table of Contents... List of Figures... 3 List of Listings... Chapter Introduction.... Overview.... Multi-socket, multi-processor systems..... Shared Memory Architectures..... Distributed Memory Architectures Hybrid Architectures..... A Multi-Socket Multi-Core Machine Parallel Programming, Amdahl s Law, scalability Parallel Programming Models Shared Memory programming model Distributed Memory programming model Hybrid Programming model Overview of Key Features for Performance Problems and pitfalls of parallel programming that should be avoided Desired Properties of Parallel Programming Models Chapter Motivation Overview of the Problem Regular vs. Irregular &Nested/Recursive Parallelism Oversubscription - Implicit vs. Explicit Parallelism The TBB Library Overview of the library How it satisfies the desired properties TBB Scheduler Overview, Basic Architectures and Components, Basic Functionalities. 39 . Table of Contents.3. Executing Tasks - Work Stealing Mechanism & Load Balancing Algorithms Cache Coherence Protocols and Problems with Work Stealing.... Profiling of basic functionalities Characterization of overhead scalability..... Systems Used TBB Scheduler Basics Basic TBB Functionalities Applications used for characterization... 8 Chapter 3 Techniques Used Optimization targets Stealing from the nearest neighbor Technique description Implementation details Stealing from the most loaded processor Technique description Implementation details Chapter Evaluation Physical Systems Stealing from the nearest neighbor Benchmarks Used Results Remarks Load Balancing Benchmarks Used Results Finding Max Results Global vs Local Sorted List... 8 Chapter 5 Epilogue Conclusions & Future Work Conclusions Related Work Future Work Chapter 6 Bibliography - References Chapter 7 Appendix A Profiling Results Quicksort... 9 Table of Contents 7. Swaptions Matrix Multiplication Convex-hull Chapter 8 Appendix B Evaluation Results Cache-Aware Techniques Heat Gauss elimination Floyd-Warshall Quicksort Matrix Multiplication Load Balancing Techniques Searching for the heaviest once in five steals Global vs Local Sorted List... 5 List of Figures Figure. Shared Memory Architecture... 3 Figure. Distributed Memory Architecture... Figure 3. Hybrid Architecture... 5 Figure. Amdahl s Law... 7 Figure 5. TBB Components Figure 6. Scheduler Architecture Overview Figure 7. Recursive Splitting & Work Stealing... Figure 8. Recursive Splitting & Work Stealing... 3 Figure 9. -core Dunnington SMP Platform... 6 Figure. -core Termi NUMA Platform... 6 Figure. Blackscholes speedup on SMP... 5 Figure. Blackscholes speedup on NUMA... 5 Figure 3. Blackscholes User-Library time on SMP for each thread count... 5 Figure. Blackscholes User-Library time on NUMA for each thread count... 5 Figure 5. Blackscholes basic functionalities breakdown on SMP for each thread count. 5 Figure 6. Blackscholes basic functionalities breakdown on NUMA for each thread count... 5 Figure 7. Blakscholes basic functionalities scalability on SMP for each thread count... 5 Figure 8. Blackscholes basic functionalities scalability on NUMA for each thread count... 5 Figure 9. Blackscholes stealing components breakdown on SMP for each thread count 5 Figure. Blackscholes stealing components breakdown on NUMA for each thread count... 5 Figure. Blackocholes scalability of stealing components on SMP for each thread count... 5 Figure. Blackscholes scalability of stealing components on NUMA for each thread count... 5 Figure 3. Fluidanimate speedup on SMP Figure. Fluidanimate speedup on NUMA Figure 5. FluidanimateUser-Library time on SMP for each thread count Figure 6. FluidanimateUser-Library time on NUMA for each thread count Figure 7. Fluidanimate basic functionalities breakdown on SMP for each thread count 5 Figure 8. Fluidanimate basic functionalities breakdown on NUMA for each thread count... 5 Figure 9. Fluidanimate basic functionalities scalability on SMP for each thread count 5 Figure 3. Fluidanimate basic functionalities scalability on NUMA for each thread count... 5 Figure 3. Fluidanimate stealing components breakdown on SMP for each thread count... 55 List of Figures Figure 3. Fluidanimate stealing components breakdown on NUMA for each thread count Figure 33. Fluidanimate scalability of stealing components on SMP for each thread count Figure 3. Fluidanimate scalability of stealing components on NUMA for each thread count Figure 35. Strassen speedup on SMP Figure 36. Strassen speedup on NUMA Figure 37. StrassenUser-Library time on SMP for each thread count Figure 38. Strassen User-Library time on NUMA for each thread count Figure 39. Strassen basic functionalities breakdown on SMP for each thread count Figure. Strassen basic functionalities breakdown on NUMA for each thread count Figure. Strassen basic functionalities scalability on SMP for each thread count Figure. Strassen basic functionalities scalability on NUMA for each thread count Figure 3. Strassen stealing components breakdown on SMP for each thread count Figure. Strassen stealing components breakdown on NUMA for each thread count Figure 5. Strassen scalability of stealing components on SMP for each thread count Figure 6. Strassen scalability of stealing components on NUMA for each thread count 58 Figure 7. Streamcluster speedup on SMP Figure 8. Streamcluster speedup on NUMA Figure 9. Streamcluster User-Library time on SMP for each thread count Figure 5. Streamcluster User-Library time on NUMA for each thread count Figure 5. Streamcluster basic functionalities breakdown on SMP for each thread count... 6 Figure 5. Streamcluster basic functionalities breakdown on NUMA for each thread count... 6 Figure 53. Streamcluster basic functionalities scalability on SMP for each thread count... 6 Figure 5. Streamcluster basic functionalities scalability on NUMA for each thread count... 6 Figure 55. Streamcluster stealing components breakdown on SMP for each thread count... 6 Figure 56. Streamcluster stealing components breakdown on NUMA for each thread count... 6 Figure 57. Streamcluster scalability of stealing components on SMP for each thread count... 6 Figure 58. Streamcluster scalability of stealing components on NUMA for each thread count... 6 Figure 59. The numbers represent the cpu ids the OS assigns to each core on Dunnington Figure 6. Cpu-id distribution to arena s slots Figure 6. 3-core Sandman NUMA Platform... 7 5. List of Figures Figure 6. Speedup of 5-point Heat on Termi (Cache-aware) Figure 63. Execution times of 5-point Heat on Termi (Cache-aware) Figure 6. Performance gains of 5-point Heat on Termi (Cache-aware) Figure 65. Speedup of 5-point Heat on Sandman (Cache-aware)... 7 Figure 66. Execution times of 5-point Heat on Sandman (Cache-aware)... 7 Figure 67. Performance gains of 5-point Heat on Sandman (Cache-aware)... 7 Figure 68. Word Count speedup on Sandman (Cache-aware) Figure 69. Word Count execution times on Sandman (Cache-aware) Figure 7. Word Count performance gains on Sandman (Cache-aware) Figure 7. Word Count speedup on Dunnington (Cache-aware) Figure 7. Word Countexecution times on Dunnington (Cache-aware) Figure 73. Word Count speedup on Termi (Cache-aware) Figure 7. Word Count execution times on Termi (Cache-aware) Figure 75. Streamcluster speedup on Dunnington (Just pick max) Figure 76. Streamcluster execution times on Dunnington (Just pick max) Figure 77. Streamcluster speedup on Termi (Just pick max) Figure 78. Streamcluster execution times on Termi (Just pick max) Figure 79. Streamcluster once in five steals speedup on Dunnington (Once in five)... 8 Figure 8. Streamcluster once in five execution times on Dunnington (Once in five)... 8 Figure 8. Streamcluster once in five Dunnington % Performance Improvement (Once in five)... 8 Figure 8. Streamcluster once in five Sandman Speedup (Once in five)... 8 Figure 83. Streamcluster once in five Sandman Execution Times (Once in five)... 8 Figure 8. Streamcluster once in five Sandman % Performance Improvement (Once in five)...
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks