Παράλληλος προγραμματισμός

[kostantinaras]

Επιτρέπεται η χρήση παράλληλου προγραμματισμού στον ΠΔΠ;Όλοι οι σύγχρονοι αλγόριθμοι είναι παράλληλοι ενώ οι σειριακοί πάλιωσαν.Γιατί δεν τους φτιάχνουμε τότε και εμείς παράλληλους;

[chris]

Όλοι οι σύγχρονοι αλγόριθμοι είναι παράλληλοι ενώ οι σειριακοί πάλιωσαν

Πηγή; Παραδείγματα;

[kostantinaras]

wikipedia
http://www.it.uom.gr/project/parallel/index.htm

[chris]

wikipedia
http://www.it.uom.gr/project/parallel/index.htm

Τα διάβασα όλα και πουθενά δεν λέει πως όλοι οι σύγχρονοι αλγόριθμοι είναι παράλληλοι και οι σειριακοί πάλιωσαν.

[kostantinaras]

Ένας αλγόριθμος είναι καλός εάν βγάζει σωστά αποτελέσματα σε μικρό χρονικό διάστημα. Για μικρή είσοδο δεδομένων στο πρόγραμμα τι νόημα έχει να είναι γρήγορος ο αλγόριθμος;παράδηγμα: θέλουμε να υψώσουμε ενα νούμερο στην 5 δύναμη είτε πάρουμε διαίρει και βασίλευε είτε κάνουμε χ*χ*χ*χ*χ ίδιο χρόνο εκτέλεσης θα έχουμε. Άρα στους αλγόριθμους νόημα έχει η ταχύτητα με μεγάλη είσοδο δεδομένων. Ενώ οι σειριακοί αλγόριθμοι είναι γρήγοροι δεν είναι τόσο γρήγοροι για τεράστια είσοδο δεδομένων. Για να αυξήσουμε την ταχύτητα μπορούμε να βάλουμε καλύτερο επεξεργαστή. Όμως οι επεξεργαστές έχουν φτάσει στο σημείο που δεν μπορούν να βελτιωθούν άλλο γιατί δεν μικραίνουν άλλο οι κρισταλοτρίοδοι (transistor)ούτε μπορούν να βρουν καμιά καλύτερη αρχητεκτονική.Για να αυξήσουν ,λοιπον,την ταχύτητα στα ολοκληρωμένα κυκλώματα (chip) βάζουν περισσότερες από μία επεξεργαστικές μονάδες(πυρήνες)Για να χρησιμοποιηθούν αποδοτικά όμως οι πηρήνες απαιτούν κατάληλους αλγόριθμους οι οποίοι θα χρησιμοποιούν στο μέγυστο τους πηρήνες.Αυτοί είναι οι παράλληλοι αλγόριθμοι.Επομένως εάν μας νιάζει η απόδοση ενώς αλγόριθμου δεν έχει νόημα να χρησιμοποιούμε σειριακούς διότι τώρα οι περισότεροι επεξεργαστές είναι πολυπύρηνοι.

Ελπίζω τώρα να σε κάλυψα.

[mariosal]

Επιτρέπεται η χρήση παράλληλου προγραμματισμού στον ΠΔΠ;

Προφανώς όχι.

Όλοι οι σύγχρονοι αλγόριθμοι είναι παράλληλοι ενώ οι σειριακοί πάλιωσαν.

Ποιοι είναι όλοι αυτοί οι "σύγχρονοι" αλγόριθμοι; Πώς ορίζεις τη λέξη "σύγχρονος"; Έπειτα τι σημαίνει ότι οι σειριακοί πάλιωσαν; Τα λόγια σου αυτά έρχονται από έρευνα ή από το μυαλό σου;

Θα στην πει κάποιος άσχημα αν συνεχίσεις να είσαι απόλυτος.

[kernelpanic]

Η χρήση multithreading βελτιώνει(θεωρητικά) την ταχύτητα του αλγορίθμου Α (που έχει είσοδο Ι) με τέτοιο τρόπο, ώστε αν η συνάρτηση χρόνου Τ(Ι) του αλγορίθμου είναι ο αριθμός κύκλων μηχανής που θα χρειαστεί για να δώσει την επιθυμητή έξοδο ένας υπολογιστής von Neumann(σαν αυτόν που έχεις περίπου) με μία μονάδα επεξεργασίας(πυρήνα), τότε ο ίδιος αλγόριθμος θα εκτελεστεί σε χρόνο c*T(I), όπου c σταθερά.
Δηλαδή η πολυπλοκότητα του αλγορίθμου δεν επηρεάζεται από την εφαρμογή παράλληλου προγραμματισμού, και ο σκοπός διαγωνισμών αλγορίθμων όπως ο ΠΔΠ κι η IOI είναι (σχεδόν πάντα) η ανάπτυξη αλγορίθμου με βέλτιστη πολυπλοκότητα.
tl;dr: Ο ΠΔΠ είναι διαγωνισμός αλγορίθμων, και μπορείς να χρησιμοποιήσεις ελεύθερα multithreading/compute vertices/CUDA στα δικά σου project, όπου η γραμμική βελτίωση της ταχυτητας πραγματικά μετράει.
tl;dr 2:Είτε χρησιμοποιήσεις παράληλες τεχνικές είτε όχι, μάλλον τα ίδια testcase θα προλάβει να λύσει με ένα σειριακό αλγόριθμο αντίστοιχης πολυπλοκότητας.

Επίσης όσο πιο πολλές είσοδοι στα ενδότερα του συστήματος, τόσο μεγαλύτερος ο κίνδυνος κακόβουλης επίθεσης σε αυτό-γι'αυτό απαγορεύονται και οι κλήσεις συστήματος και η χρήση inline assembly

ΥΓ:

To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrific—until it turned out that the wished-for compilers were basically impossible to write.

Let me put it this way: During the past 50 years, I’ve written well over a thousand programs, many of which have substantial size. I can’t think of even five of those programs that would have been enhanced noticeably by parallelism or multithreading.
How many programmers do you know who are enthusiastic about these promised machines of the future? I hear almost nothing but grief from software people, although the hardware folks in our department assure me that I’m wrong.

I know that important applications for parallelism exist—rendering graphics, breaking codes, scanning images, simulating physical and biological processes, etc. But all these applications require dedicated code and special-purpose techniques, which will need to be changed substantially every few years.

Even if I knew enough about such methods to write about them in TAOCP, my time would be largely wasted, because soon there would be little reason for anybody to read those parts.

πηγή

[kostantinaras]

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

Έχεις δίκιο.

Επίσης όσο πιο πολλές είσοδοι στα ενδότερα του συστήματος, τόσο μεγαλύτερος ο κίνδυνος κακόβουλης επίθεσης σε αυτό-γι'αυτό απαγορεύονται και οι κλήσεις συστήματος και η χρήση inline assembly

Και πως θα βάλουμε multithreading;

[kernelpanic]

Και πως θα βάλουμε multithreading;

Γιατί να βάλουμε multithreading;

ΥΓ:

Spoiler: show

Το ότι οι παράλληλοι αλγόριθμοι είναι σχετικά νέοι δε σημαίνει οτι οι σειριακοί πάλιωσαν, ούτε οτι μπορούν να αντικατασταθούν γενικά.

Για παράδειγμα ο υπολογισμός του χⁿ, n φυσικός μπορεί να υπολογιστεί σε Ο(logn) με ένα σειριακό αλγόριθμο:

Κώδικας: Επιλογή όλων

Αλγόριθμος العظيم
Δεδομένα //χ,n//
αν n<0 τοτε
	εμφανισε 'FAIL'
αλλιως
	χ <- 1
	α <- χ
	οσο χ > 0 επαναλαβε
		αν n mod 2 = 1 τοτε
			χ <- χ * α
		τελος_αν
		α <- α * α
		n <- n div 2
	τελος_επαναληψης
τελος_αν
Αποτελέσματα //χ//
Τελος العظيم

[pman]

ΥΓ:

Spoiler: show

Το ότι οι παράλληλοι αλγόριθμοι είναι σχετικά νέοι δε σημαίνει οτι οι σειριακοί πάλιωσαν, ούτε οτι μπορούν να αντικατασταθούν γενικά.

Για παράδειγμα ο υπολογισμός του χⁿ, n φυσικός μπορεί να υπολογιστεί σε Ο(logn) με ένα σειριακό αλγόριθμο:

Κώδικας: Επιλογή όλων

Αλγόριθμος العظيم
Δεδομένα //χ,n//
αν n<0 τοτε
	εμφανισε 'FAIL'
αλλιως
	χ <- 1
	α <- χ
	οσο χ > 0 επαναλαβε
		αν n mod 2 = 1 τοτε
			χ <- χ * α
		τελος_αν
		α <- α * α
		n <- n div 2
	τελος_επαναληψης
τελος_αν
Αποτελέσματα //χ//
Τελος العظيم

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

Spoiler: show

Κώδικας: Επιλογή όλων

Αλγόριθμος العظيم
Δεδομένα //χ,n//
αν n<0 τοτε
	εμφανισε 'FAIL'
αλλιως
	χ <- 1
	α <- χ
	οσο n > 0 επαναλαβε
		αν n mod 2 = 1 τοτε
			χ <- χ * α
		τελος_αν
		α <- α * α
		n <- n div 2
	τελος_επαναληψης
τελος_αν
Αποτελέσματα //χ//
Τελος العظيم