.NET Framework

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Thu, 31 May 2012 20:47:27 GMT

Νομίζω ότι βρήκα ένα καλό παράδειγμα στο Parallel Aggregation το οποίο εξετάζει το map/reduce ως παραλλαγή του Parallel Aggregation.

Έστω ότι έχεις ένα social network και θέλεις να κάνεις friend recommendations. Τα recommendations θα είναι τα μέλη που δεν είναι φίλοι σου αλλά έχετε τους περισσότερους mutual.

Στο πρώτο βήμα, ο αλγόριθμος βρίσκει τους φίλους των φίλων σου που δεν είναι ήδη φίλοι. Αυτό θα βγάλει μία λίστα με candidates από κάθε φίλο. Στο δεύτερο βήμα, ο αλγόριθμος υπολογίζει για κάθε candidate τον αριθμό των mutuals. Τέλος, επιλέγει τους top X για να σου τους προτείνει

Το πρώτο βήμα αντιστοιχεί στο Map (από φίλους σε candidates) ενώ το δεύτερο το reduce (από πολλαπλές λίστες candidates σε ένα set από candidates με την αξιολόγηση τους).

Και τα δύο βήματα είναι σχετικά απλά, οπότε η αξία του map/reduce προέρχεται από το ότι μπορεί να κατανείμει το κάθε βήμα σε όσο το δυνατόν περισσότερα cores χωρίς προβλήματα blocking: ο κάθε mapper ή reducer παίρνει το δικό του αντίγραφο των δεδομένων χωρίς προβλήματα locking αφού δεν μοιράζεται τίποτε με τους άλλους.

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Thu, 31 May 2012 17:51:49 GMT

Bill :
Αυτό που αναφέρεις ότι είναι συντηριτικός ο αλγόριθμος σε PLINQ μπορούμε να το αλλάξουμε όπως είδα με το WithExecutionMode.(ParallelExecutionMode.ForceParallelism) στο PLINQ ερώτημα και να το εκτελέσουμε με ότι κόστος συνεπάγετε αυτό παράλληλα (βέβαια αυτό μπορεί να είναι και κακή τεχνική αν ο φόρτος εργασίας του μηχανήματος είναι μεγάλος) .

Δεν είναι θέμα φόρτου. Αν το overhead της παράλληλης επεξεργασίας είναι μεγαλύτερο από το όφελος, το ForceParallelism θα προκαλέσει καθυστέρηση, όχι επιτάχυνση. Από την άλλη, υπάρχουν απλά περιπτώσεις που το .NET 4 θα κάνει λαθος. Αν π.χ. εκτελείς μία μακρόχρονη ασύγχρονη διαδικασία μέσα στο PLINQ query, μπορείς να σηκώσεις πολύ περισσότερα ταυτόχρονα tasks απ' ότι αν εκτελείς CPU heavy αλγόριθμους. Το PLINQ δεν το ξέρει όμως και έτσι επιλέγει συντηρητικά.

Για να πεις στο PLINQ πόσα ταυτόχρονα tasks να σηκώσει χρησιμοποιείς την WithDegreeOfParallelism για να δώσεις μέχρι 64 ταυτόχρονα tasks. Λογικό το νούμερο αν μιλάμε για CPU bound (ποιός έχει μηχάνημα με 64 cores?) μικρό αν μιλάμε για ασύγχρονη επεξεργασία, όπως π.χ. crawling

Επιπλέον, υπάρχουν operations που το .NET 4 θα εκτελέσει πάντα σύγχρονα ενώ το 4.5 θα εκτελέσει παράλληλα. Το PLINQ Queries that run in parallel in .NET 4.5 του Stephen Toub έχει ένα πίνακα με τις εντολές που εκτελούνται πλέον παράλληλα.

Τέλος, το πρόβλημα με τα παραδείγματα που ψάχνεις είναι ότι ζητάς κάτι πολύ συγκεκριμένο - ΚΑΙ MapReduce ΚΑΙ TPL ΚΑΙ ένα μόνο μηχάνημα. Τα περισσότερα παραδείγματα ασχολούνται με ένα αντικείμενο τη φορά.

Ειδικά για το word count μπορείς να δεις αυτό το walkthrough για το DataFlow, όπου σπάει το πρόβλημα σε βήματα ξεκινώντας από το split του αρχικού κειμένου. Το παράδειγμα που κοίταζες στην αρχή θεωρεί ότι το αρχείο έχει ήδη γίνει split σε λέξεις, κάτι το οποίο κοστίζει αρκετά και μπορεί να γίνει επίσης ασύγχρονα.

Μπορεί να μην είναι το καλύτερο παράδειγμα για map reduce, αλλά δίνει μία καλή εικόνα μίας πιο γενικής αντιμετώπισης (pipeline από agents, όχι μόνο mappers, reducers).

Για να δούμε μήπως βρούμε κανα καλύτερο παράδειγμα (ή το χρόνο να γράψουμε κανένα)

Απ: TPL & Map Reduce

Markos — Thu, 31 May 2012 08:16:41 GMT

Έχεις διαβάσει το "PLINQ: Parallel queries in .NET";

Απ: TPL & Map Reduce

Bill — Thu, 31 May 2012 06:58:32 GMT

Αυτό που αναφέρεις ότι είναι συντηριτικός ο αλγόριθμος σε PLINQ μπορούμε να το αλλάξουμε όπως είδα με το WithExecutionMode.(ParallelExecutionMode.ForceParallelism) στο PLINQ ερώτημα και να το εκτελέσουμε με ότι κόστος συνεπάγετε αυτό παράλληλα (βέβαια αυτό μπορεί να είναι και κακή τεχνική αν ο φόρτος εργασίας του μηχανήματος είναι μεγάλος) .

Απ: TPL & Map Reduce

Bill — Thu, 31 May 2012 06:48:03 GMT

Έχω ψάξει και έχω δει το ActionBlock απο τα DataFlow που λες τα οποία είναι πολυ ελκυστικά αν όντως έχουν καλά αποτελεσμα . Αλλά έχω χαθεί ένα απλό παράδειγμα που να τα δένεις όλα αυτά και με το BufferBlock στο τέλος θα με βοηθούσε αρκετά να το αποσαφηνίσω.
Ψάχνω στο google και δε βρίσκω κάτι με όλα τα καλούδια αυτά...!!
Ζητάω πολλά ε

Υ.Γ και στην Bing τίποτε..

Απ: TPL & Map Reduce

Markos — Thu, 31 May 2012 01:57:56 GMT

Στα "Acknowledgements" αναφέρει ότι η συγκεκριμένη έρευνα, καθώς και το "Parallel Dwarfs" project, χρηματοδοτήθηκαν εν μέρει από τη Microsoft. Μόλις τώρα είδα ότι το Parallel Dwarfs project είναι ανεβασμένο στο Codeplex, οπότε μπορεί κάποιος ελεύθερα να το μελετήσει. Μου φαίνεται, λοιπόν, λίγο τραβηγμένο τα αποτελέσματα να είναι μεροληπτικά. Βέβαια, ποτέ δε μπορείς να αποκλείσεις την ύπαρξη σφαλμάτων.

Πάντως η έρευνα δείχνει να έχει σταματήσει στο 2009....

ΥΓ: Δε σκοπεύω ν' ασχοληθώ μαζί του, τουλάχιστον στην παρούσα συγκυρία.

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Wed, 30 May 2012 20:59:14 GMT

Έριξα μόλις τώρα μία ματιά στο project που αναφέρει στο codeplex, και βρήκα την φοβερή SumThreadResult που απαιτεί locks. Ο λόγος που το κάνει αυτό είναι επειδή εκεί μέσα φτιάχνει ένα dictionary που πάει και το αποθηκεύει στην θέση που βρισκόταν πριν ένα άλλο dictionary. To lock, του lock

Απ: TPL & Map Reduce

Bill — Wed, 30 May 2012 20:48:58 GMT

Ειλικρινά χτες αυτό έβλεπα και αναρωτιομουν γιατι δεν καταλαβαίνω γρι απο όσα λεεί. Επίσης δίνει και αποτελέσματα ως προς το χρόνο και μου ήρθε πολύ περιέργο που η F# είναι αργή.
anyway....

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Wed, 30 May 2012 20:38:06 GMT

Markos:
Εντελώς ενημερωτικά, έπεσα πάνω σε ένα paper (κάτι που δε συμβαίνει και τόσο συχνά):

Implementing parallel algorithms of MapReduce

Δεν ξέρω αν τα αποτελέσματα είναι χαρακτηριστικά, αλλά τα threads φαίνεται να κερδίζουν, ενώ η F# εμφανίζεται ως η πιο αργή.

Διαβάζοντας το paper βλέπω τον πραγματικό κώδικα να λάμπει δια της απουσίας του: δεν υπάρχει πουθενά ο κώδικας των map, reduce. Ο κώδικας που δίνεται είναι μόνο το scaffolding. Είναι απλά αδύνατον να βγάλεις συμπέρασμα κοιτώντας το scaffolding.

Και το χειρότερο, η χρήση ενός Duo σημαίνει ότι δεν υπάρχει καμμία ένδειξη για το πως κάνει scale η κάθε υλοποίηση. Το MapReduce δεν φτιάχτηκε για 2 επεξεργαστές αλλά για να εκμεταλλεύεται όσο περισσότερους επεξεργαστές γίνεται. Και μόνο η χρήση locks στην υλοποίηση με C++ και OpenMP σημαίνει ότι το scale είναι κακό. Το ότι τρέχει μέσα στο ίδιο thread και το map και το reduce, σημαίνει απλά ότι η υλοποίηση ΔΕΝ είναι map reduce.

Όσο για τη χρήση ενός απλού Parallel.For στην υλοποίηση για TPL, μαζί με LOCK για να γράψει σε ένα dictionary .... εντάξει ο τύπος δεν ξέρει από TPL και μιλάει. Τί να πω. Προφανώς δεν άκουσε ποτέ για concurrent collections ή για άλλα πιο χρήσιμα primitives όπως η Interlocked.Increment.

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Wed, 30 May 2012 06:43:25 GMT

Bill :
Βρήκα το παρακάτω παράδειγμα σε PLINQ για map / reduce κάτι απλό :

Οκ με το map το reduce query είναι σωστό ???
και γιατί είναι τόσο αργό ?

Το παράδειγμα είναι πολύ μικρό για να δεις επιτάχυνση από την παράλληλη επεξεργασία. Επιπλέον, το parallel processing έχει το δικό του overhead. Σε τόσο μικρό δείγμα το overhead είναι πολύ μεγαλύτερο από τον καθαρό χρόνο επεξεργασίας.

Επιπλέον, το PLINQ ελέγχει τον όγκο των δεδομένων και τον αριθμό των cores και μπορεί να αποφασίσει να χρησιμοποιήσει μόνο 1 core αν κρίνει ότι το overhead είναι πολύ μεγάλο. Στο .NET 4.0 ο αλγόριθμος που επιλέγει τα cores είναι συντηρητικός ενώ στο 4.5 επιτρέπει την παράλληλη επεξεργασία σε πολύ περισσότερες περιπτώσεις.

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Wed, 30 May 2012 06:37:18 GMT

Bill :
Χεχε δεν την εγκατέλειψα (Η HOL φταιει) είδα με PLINQ παράδειγμα όπως αναφέρεις... αλλά ακόμη ψάχνω να καταλάβω.
Απλά έχω δει σε MPI map reduce και με την TPL ήθελα να δω τι μπορώ να κάνω .

Το MPI ταιριάζει περισσότερο στη λογική του Dataflow και των agents. Εϊναι κι αυτό άλλη μία τεχνική, η οποία κυρίως εφαρμόζεται όταν έχεις πραγματικά πολλούς επεξεργαστές, ή/και ασύμμετρες αρχιτεκτονικές όπως NUMA. Σε τέτοιες περιπτώσεις κάθε επεξεργαστής έχει ταχύτερη πρόσβαση σε ένα μέρος της μνήμης και αργότερη στην υπόλοιπη. Εκεί έχει νόημα το κάθε processing block να μιλάει με τα άλλα μέσω μηνυμάτων και μόνο. Το TPL δεν εκμεταλλεύεται ούτε καταλαβαίνει αυτές τις αρχιτεκτονικές, καθώς πρόκειται για ένα γενικό μηχανισμό να επεξεργαστεί δεδομένα παράλληλα.

Απ: TPL & Map Reduce

Παναγιώτης Καναβός — Wed, 30 May 2012 06:32:25 GMT

Markos:
Εντελώς ενημερωτικά, έπεσα πάνω σε ένα paper (κάτι που δε συμβαίνει και τόσο συχνά):

Implementing parallel algorithms of MapReduce

Δεν ξέρω αν τα αποτελέσματα είναι χαρακτηριστικά, αλλά τα threads φαίνεται να κερδίζουν, ενώ η F# εμφανίζεται ως η πιο αργή.

Απογοητεύτηκα λίγο από το Parallel Programming with Microsoft .NET, κυρίως γιατί προσπαθεί να πουλήσει μέσω του CodePlex. Αλήθεια, διαφέρει σε κάτι από το Patterns for Parallel Programming που μπορεί κανείς να κατεβάσει από το download center της Microsoft;

Μάρκο, μάλλον τα έμπλεξες. Αυτό που είδες στο codeplex είναι διαθέσιμο online τσάμπα από την Microsoft. Το βιβλίο, σε ebook ή τυπωμένο είναι διαθέσιμο από την O'Reilly και δεν είναι τσάμπα. Αν δεν θέλεις να το αγοράσεις, απλά διάβασε το online.

Νομίζω ότι δεν είναι η καλύτερη τακτική να κρίνεις ένα βιβλίο επειδή κάποιες εκδόσεις του δεν είναι τσάμπα.

Και το Patterns είναι όντως άλλο βιβλίο.

Απ: TPL & Map Reduce

Bill — Wed, 30 May 2012 04:01:56 GMT

Βρήκα το παρακάτω παράδειγμα σε PLINQ για map / reduce κάτι απλό :

        public static List<string> words = new List<string>
        {
            "there","is","a",
            "great","house","and",
            "an","amazing","lake",
            "there","is","a","computer",
            "running","a","new","query","there",
            "is","a","greate","server","ready","to","process",
            "map","and","reduce"
        };

        static void Main(string[] args)
        {
            // Map
            // Generate a (word, 1) key, value pair
            ILookup<string, int> map = words.AsParallel().ToLookup(p => p, k => 1);
            // End of Map
            // Reduce
            // Calculate the number of times a word appears and
            // select the words that appear more than once
            var reduce = from IGrouping<string, int> wordMap
            in map.AsParallel()
            where wordMap.Count() > 1
            select new
            { Word = wordMap.Key, Count = wordMap.Count() };
            // End of Reduce
            // Show each word and the number of times it appears
            foreach (var word in reduce)
            Console.WriteLine("Word: '{0}'; Count: {1}",
            word.Word, word.Count);
            Console.ReadLine();
        }

Οκ με το map το reduce query είναι σωστό ???
και γιατί είναι τόσο αργό ?

Απ: TPL & Map Reduce

Markos — Wed, 30 May 2012 01:51:32 GMT

Εντελώς ενημερωτικά, έπεσα πάνω σε ένα paper (κάτι που δε συμβαίνει και τόσο συχνά):

Implementing parallel algorithms of MapReduce

Δεν ξέρω αν τα αποτελέσματα είναι χαρακτηριστικά, αλλά τα threads φαίνεται να κερδίζουν, ενώ η F# εμφανίζεται ως η πιο αργή.

Απογοητεύτηκα λίγο από το Parallel Programming with Microsoft .NET, κυρίως γιατί προσπαθεί να πουλήσει μέσω του CodePlex. Αλήθεια, διαφέρει σε κάτι από το Patterns for Parallel Programming που μπορεί κανείς να κατεβάσει από το download center της Microsoft;

Απ: TPL & Map Reduce

Bill — Tue, 29 May 2012 23:06:48 GMT

Χεχε δεν την εγκατέλειψα (Η HOL φταιει) είδα με PLINQ παράδειγμα όπως αναφέρεις... αλλά ακόμη ψάχνω να καταλάβω.
Απλά έχω δει σε MPI map reduce και με την TPL ήθελα να δω τι μπορώ να κάνω .