Χρονικές αποδόσεις/Αλγόριθμος

[yiannis]

Γειά χαρά σε όλους!

Δύο βασικά θέματα που με προβληματίζουν είναι τα εξής:

1) Έχω γράψει ένα πρόγραμμα σε Perl, που έχει να κάνει με string prossesing+μαθηματικά. Το έγραψα σε Perl, με τη λογική της εύκολης και γρήγορης υλοποίησης (σε σχέση με C/C++) και την αξιοποίηση των regular expressions.

Πιστεύετε ότι έχω να κερδίσω ουσιαστικά στην χρονική απόδοση στην περίπτωση που το υλοποιήσω σε C ή C++; Στην περίπτωση που τώρα απαιτείται χρόνος ας πούμε 90'', πόσο μπορώ να τον κατεβάσω (σε γενικές γραμμές). Υπόψιν ότι το πρόβλημα είναι NP-hard και ότι δεν έχω τον χρόνο να κάνω ιδιαίτερα πολύπλοκες υλοποιήσεις.

και

2) Θέλω να συγκρίνω 2-διάστατους πίνακες που περιέχουν μόνο 0 και 1 και να εντοπίζω σε ποιά παράθυρα μοιάζουν και σε ποιά όχι (κάτι σαν string alignment αλλά με πίνακες). Γνωρίζει κανείς κάποιον αλγόριθμο που να είναι αποδοτικός σε σχετικά μεγάλα μεγέθη πινάκων (περίπου 2000*256 ο καθένας);

Σας ευχαριστώ και με συγχωρείτε για τον κόπο

Υ.Γ Τώρα που σας τα γράφω αυτά, θυμήθηκα έναν τύπο σε μία διαφήμιση που λέει "μπορώ να έχω δωρεάν διακόπες για πάντα..? " και κάτι τέτοια.. χεχε

[KTM]

Καλως ηρθες στο site.

[circular]

Γεια χαρά Γιάννη, να σε καλωσορίσω και γω στο φόρουμ.

1) Δε νομίζω οτι θα κερδίσεις κάτι, τα regular expressions της perl είναι πολύ αποδοτικά και η επεξεργασία συμβολοσειρών ακόμα πιο αποδοτική, θα σου έλεγα να το πας σε C/C++ μονο να θες να κάνεις δραστική βελτιοποίηση (να κατέβεις πχ στο 1/10 του χρόνου). Αν δεν χρειάζεσαι κάτι τετοιο μην ασχοληθείς.
2) ϊσως θα μπορούσε να σε βοηθήσει κάποιος αλγόριθμος που να εφαρμόζει spatial hashing & pattern matching σε bitmaps αλλά αυτή τη στιγμή δεν έχω κάτι υπόψην μου.

[circular]

Δες και αυτό http://portal.acm.org/citation.cfm?id=314680

[DarthMoul]

Γειά χαρά σε όλους!

Δύο βασικά θέματα που με προβληματίζουν είναι τα εξής:

1) Έχω γράψει ένα πρόγραμμα σε Perl, που έχει να κάνει με string prossesing+μαθηματικά. Το έγραψα σε Perl, με τη λογική της εύκολης και γρήγορης υλοποίησης (σε σχέση με C/C++) και την αξιοποίηση των regular expressions.

Πιστεύετε ότι έχω να κερδίσω ουσιαστικά στην χρονική απόδοση στην περίπτωση που το υλοποιήσω σε C ή C++; Στην περίπτωση που τώρα απαιτείται χρόνος ας πούμε 90'', πόσο μπορώ να τον κατεβάσω (σε γενικές γραμμές). Υπόψιν ότι το πρόβλημα είναι NP-hard και ότι δεν έχω τον χρόνο να κάνω ιδιαίτερα πολύπλοκες υλοποιήσεις.

και

2) Θέλω να συγκρίνω 2-διάστατους πίνακες που περιέχουν μόνο 0 και 1 και να εντοπίζω σε ποιά παράθυρα μοιάζουν και σε ποιά όχι (κάτι σαν string alignment αλλά με πίνακες). Γνωρίζει κανείς κάποιον αλγόριθμο που να είναι αποδοτικός σε σχετικά μεγάλα μεγέθη πινάκων (περίπου 2000*256 ο καθένας);

Σας ευχαριστώ και με συγχωρείτε για τον κόπο

Υ.Γ Τώρα που σας τα γράφω αυτά, θυμήθηκα έναν τύπο σε μία διαφήμιση που λέει "μπορώ να έχω δωρεάν διακόπες για πάντα..? " και κάτι τέτοια.. χεχε

Στους πίνακες φρόντισε το μέγεθος της γραμμής να είναι ακέραιο πολλαπλάσιο ή υποπολλαπλάσιο του cache line. Αν δεν ξερεις το cache line της CPU που θα τρέξει το πρόγραμμα θεώρησε ασφαλές το 32.

Κάνε prefetch τον κάθε πίνακα τμηματικά με buffer ίση με το μέγεθος του cache databank. Αν δεν ξέρεις το μέγεθος του cache databank θεώρησε ασφαλές το 4096.

Με τα δύο παραπάνω υπολόγισε κέρδος κάπου στο 30%. Για παραπάνω βελτιώσεις
πάμε σε C αλλά πρέπει πρώτα να ξέρω ακριβώς τι κάνεις για να σε καθοδηγήσω.

Αφού παίζεις με πίνακες, κοίταξε για loop unrolling, software pipelining, vectorozation, και αν τελικά πας σε C για sse/sse2 εντολές.

[yiannis]

Παιδιά σας ευχαριστώ όλους για το καλωσόρισμα και για το άμεσο ενδιαφέρον.
Με συγχωρείτε για την αργοπορία... έπρεπε να δω κάποια πράγματα σχετικά με αυτά που μου απαντήσατε.

Τα άρθρα του DarthMoul σχετικά με το Performance είχαν ιδιαίτερο ενδιαφέρον.

circular μία τέτοια μείωση χρειάζομαι. Το άρθρο είναι πολύ ενδιαφέρον και θα το μελετήσω με την πρώτη ευκαιρία.

DarthMoul είναι πάρα πολύ χρήσιμα τα tips σου. Το μέγεθος της γραμμής του πίνακα είναι σταθερό (256) οπότε έρχεται κουτί για την cache line.
Σχετικά με την ισορροπημένη χρήση της Dcache και της Icache: Πως μπορούμε να υπολογίζουμε το βέλτιστο βάθος του unrolling σε έναν βρόγχο;
Επίσης, μπορείς να προτείνεις κάποιο βιβλίο ή review paper για High Performance Computing;
Γενικά, το συμπέρασμα που έβγαλα είναι ότι βιάστηκα πολύ να αρχίσω να γράφω κώδικα. θα το σχεδιάσω/υλοποιήσω από την αρχή σε C με μεγαλύτερη προσοχή.

Σας ευχαριστώ πολύ

[DarthMoul]

Το ζήτημα με την γραμμή του πίνακα έχει να κάνει και με το allocation pattern που εφαρμόζει ο compiler που χρησιμοποιείς. Πρέπει πρώτα να βεβαιωθείς ότι δύο διαδοχικές θέσεις της ίδιας γραμμής καταλαμβάνουν διαδοχικές θέσεις μνήμης. Αν όχι, πρέπει να αντιστρέψεις τις διαστάσεις του πίνακα και να γυρίσεις "τούμπα" όλον τον αλγόριθμο.

Το loop unrolling προκαλεί register pressure. Τα x86 zombies που χρησιμοποιούμε οι περισσότεροι είναι register starved. Υπολόγισε πόσους registers χρησιμοποιεί το κομμάτι του κώδικα που θα κάνεις unroll και έχε στο μυαλό σου ότι έχεις διαθέσιμους το πολύ 8 registers και πως στο παιχνίδι παίζουν και οι απαριθμητές. Αν θα το τρέξεις σε κάποιο risc, οι διαθέσιμοι registers που έχεις είναι από 32 εώς 512 αναλόγως την αρχιτεκτονική.

Αν κάνει unrolling ο compiler ενεργοποίησε το και μην ανακατευτείς καθόλου.
Φρόντισε σε κάθε περίπτωση να έχεις απαλλείψει κάθε data dependency στο κομμάτι που θα κάνεις unroll ακόμα και με κόστος την χρήση κάποιου παραπάνω register.

Τώρα για το Icache και το Dcache. Αν δεν είσαι βέβαιος για την μηχανή που θα τρέξει το πρόγραμμα, χρειάζεται να γράψεις κώδικα που να ελέγχει τα μεγέθη τους και το μέγεθος του bank. Για να μην μπλέξεις με τέτοια, θεώρησε πως το πρόγραμμα σου θα τρέξει σε κάποιον P3 και κάνε optimization βάσει αυτού.

Την χρήση του Dcache την υπολογίζεις εύκολα και με το χέρι. Για το Icache, ζήτα assembly output από τον compiler και μέτρα το μέγεθος του κώδικα που παράγει στα επίμαχα κομμάτια που σε ενδιαφέρουν (συνήθως είναι μέσα σε loop). Αν τελικά αυτά τα κομμάτια δεν χωράνε στο Icache, ζήτα από τον compiler να κάνει Optimization for size, και ανέλαβε το speed optimization (loop unrolling κλπ) εσύ. Σ'αυτή την περίπτωση σκέψου σοβαρά και το ενδεχόμενο να γράψεις sse κώδικα. Οι sse εντολές είναι ενσωματωμένος μικροκώδικας στην CPU (μούφα εντολές κοροϊδία δηλαδή) που όμως κάνουν βέλτιστη αξιοποίηση και πιάνουν πολύ λίγο χώρο στην μνήμη αφού ουσιαστικά είναι κλήσεις και έχουν πολύ μικρό opcode. Πρόσεξε πολύ αν τις χρησιμοποιήσεις γιατί κάποιες από αυτές παρακάμπτουν το cache οπότε βολεύουν μόνο στην περίπτωση που κάνεις multithreading σε SMT capable CPU (πχ P4).

Για High Performance computing, ψάξε σε πηγές που αναφέρονται σε προγραμματισμό για supercomputers και στα architecture και optimization handbooks του επεξεργαστή σου.

[yiannis]

DarthMoul σ'ευχαριστώ πολύ για τις συμβουλές. Όλα αυτά θα τα μελετήσω. Βρήκα ήδη κάποια κείμενα σχετικά με SSE προγραμματισμό (που μάλλον είναι και γενικότερα χρήσιμος).