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

Ο τομέας μας. ;)
Απάντηση
kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

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

Δημοσίευση από kostantinaras » Τετ Σεπ 05, 2012 9:33 am

Επιτρέπεται η χρήση παράλληλου προγραμματισμού στον ΠΔΠ;Όλοι οι σύγχρονοι αλγόριθμοι είναι παράλληλοι ενώ οι σειριακοί πάλιωσαν.Γιατί δεν τους φτιάχνουμε τότε και εμείς παράλληλους;
In a world without walls and fenches who needs Windows and Gates?

chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

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

Δημοσίευση από chris » Πέμ Σεπ 06, 2012 6:18 pm

kostantinaras έγραψε:Όλοι οι σύγχρονοι αλγόριθμοι είναι παράλληλοι ενώ οι σειριακοί πάλιωσαν
Πηγή; Παραδείγματα;
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.

kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

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

Δημοσίευση από kostantinaras » Πέμ Σεπ 06, 2012 8:40 pm

In a world without walls and fenches who needs Windows and Gates?

chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

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

Δημοσίευση από chris » Πέμ Σεπ 06, 2012 11:51 pm

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

kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

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

Δημοσίευση από kostantinaras » Παρ Σεπ 07, 2012 10:34 am

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

Ελπίζω τώρα να σε κάλυψα.
In a world without walls and fenches who needs Windows and Gates?

Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

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

Δημοσίευση από mariosal » Παρ Σεπ 07, 2012 4:17 pm

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

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

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

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

Δημοσίευση από kernelpanic » Σάβ Σεπ 08, 2012 8:04 pm

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

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

ΥΓ:
Donald E. Knuth έγραψε: 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.
πηγή
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

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

Δημοσίευση από kostantinaras » Κυρ Σεπ 09, 2012 9:02 am

kernelpanic έγραψε:Είτε χρησιμοποιήσεις παράληλες τεχνικές είτε όχι, μάλλον τα ίδια testcase θα προλάβει να λύσει με ένα σειριακό αλγόριθμο αντίστοιχης πολυπλοκότητας.
Έχεις δίκιο.
kernelpanic έγραψε: Επίσης όσο πιο πολλές είσοδοι στα ενδότερα του συστήματος, τόσο μεγαλύτερος ο κίνδυνος κακόβουλης επίθεσης σε αυτό-γι'αυτό απαγορεύονται και οι κλήσεις συστήματος και η χρήση inline assembly ;)
Και πως θα βάλουμε multithreading;
In a world without walls and fenches who needs Windows and Gates?

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

العظيم

Δημοσίευση από kernelpanic » Κυρ Σεπ 09, 2012 6:39 pm

konstantinaras έγραψε: Και πως θα βάλουμε multithreading;
Γιατί να βάλουμε multithreading;

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

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

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

Αλγόριθμος العظيم
Δεδομένα //χ,n//
αν n<0 τοτε
	εμφανισε 'FAIL'
αλλιως
	χ <- 1
	α <- χ
	οσο χ > 0 επαναλαβε
		αν n mod 2 = 1 τοτε
			χ <- χ * α
		τελος_αν
		α <- α * α
		n <- n div 2
	τελος_επαναληψης
τελος_αν
Αποτελέσματα //χ//
Τελος العظيم
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: العظيم

Δημοσίευση από sotiris » Δευ Σεπ 10, 2012 11:20 am

kernelpanic έγραψε: ΥΓ:
Spoiler: show
Το ότι οι παράλληλοι αλγόριθμοι είναι σχετικά νέοι δε σημαίνει οτι οι σειριακοί πάλιωσαν, ούτε οτι μπορούν να αντικατασταθούν γενικά.

Για παράδειγμα ο υπολογισμός του χn, 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
	τελος_επαναληψης
τελος_αν
Αποτελέσματα //χ//
Τελος العظيم
Εικόνα

Απάντηση