[Advcomparch] Relaxed models και αναδιάταξη εντολών.

Mon Jul 1 22:57:42 EEST 2013

Καλησπέρα,

πουθενά στο μάθημα ή στις διαφάνειες δεν αφήνουμε να εννοηθεί ότι
επιτρέπονται και αναδιατάξεις οι οποίες δε σέβονται τα data
dependencies. Επαναλαμβάνω και την αντιστοιχία με έναν out-of-order
επεξεργαστή και το πότε επιτρέπεται το out-of-order execution των
εντολών μνήμης.

Σε καμία περίπτωση δε χρειάζεται barrier για να εκτελέσει σωστά ένα thread το

flag=1
print flag

που αναφέρεις. Τα barriers δίνονται ως εργαλεία τα οποία διασφαλίζουν
ότι όλα τα threads θα δουν τις εγγραφές με τη σειρά που επιθυμεί ο
προγραμματιστής και όχι με κάποια άλλη. Tα relaxed memory order models
έχουν σα σκοπό να μειώσουν τα miss latencies, επιτρέποντας να
εκτελεστούν εκτός σειράς εντολές μνήμης όσο εξυπηρετείται κάποιο miss.
Διατηρώντας όμως πάντα τα data dependencies.

K.

2013/7/1 el09004 <el09004 at mail.ntua.gr>:
> On Mon, 1 Jul 2013 17:08:26 +0300, Konstantinos Nikas wrote:
>>
>> Καλησπέρα,
>>
>> από ότι καταλαβαίνω έχει δημιουργηθεί
>> μια παρεξήγηση όσον αφορά την
>> αναδιάταξη των εντολών.
>>
>> Η αναδιάταξη λοιπόν των εντολών
>> μνήμης επιτρέπεται καταρχάς εφόσον
>> δεν επηρεάζονται τα data dependencies.  Για να
>> κατανοήσετε καλύτερα το τί γίνεται,
>> φανταστείτε έναν out-of-order επεξεργαστή,
>> στα LD/ST queues του οποίου μπαίνουν οι
>> αντίστοιχες εντολές μνήμης. Είναι
>> προφανές, ότι τυχόν αναδιάταξη μπορεί
>> να αφορά μόνο εντολές που είναι
>> έτοιμες να εκτελεστούν (να πάνε στη
>> μνήμη)! Έτσι στην περίπτωση:
>>
>> lw r4, 0(r8)
>> sw r4, 0(r9)
>>
>> η 2η εντολή ποτέ δε θα είναι έτοιμη
>> πριν εκτελεστεί η πρώτη και άρα δεν
>> πρόκειται να αναδιαταχθεί. Για τις
>> εντολές τώρα που είναι έτοιμες να πάνε
>> στη μνήμη, η αναδιάταξη επιτρέπεται
>> μόνο μεταξύ αυτών που πηγαίνουν σε
>> διαφορετική θέση της μνήμης. Δηλαδή
>> στον κώδικα:
>>
>> sw r1, 0(r8)
>> sw r2, 0(r8)
>>
>> δεν επιτρέπεται η αναδιάταξη.
>>
>> Όσον αφορά τα control dependencies τα πράγματα
>> δεν είναι απόλυτα ξεκάθαρα, μιας και
>> δεν εξαρτώνται από το memory model αλλά από
>> την υλοποίηση σε κάθε επεξεργαστή. π.χ.
>> για τον κώδικα:
>>
>> while (flag == 0) continue;
>> assert (x == 1);
>>
>> o Power επεξεργαστής σέβεται το control
>> dependence και δεν επιτρέπει την
>> αναδιάταξη (βάζοντας ένα implicit barrier
>> ανάμεσα στις 2 εντολές) ενώ ο ARM δεν το
>> σέβεται και μπορεί να αναδιατάξει τις
>> εντολές (κάτι που ισχύει και στα
>> περισσότερα σύγχρονα συστήματα).
>> Εμείς γενικά θεωρούμε ότι ισχύει το 2ο,
>> δηλαδή στον κώδικα
>>
>> while (flag == 0) ;
>> print A;
>>
>> μπορεί να υπάρξει αναδιάταξη.
>> Σκεφτείτε το πάλι ως εξής. Έχετε έναν
>> οut-of-order processor, ο οποίος κάνει branch predicition
>> και "τυχαίνει" το prediction να λέει ότι το
>> branch θα είναι NT (δε θα εκτελεστεί δηλαδή
>> ξανά το loop). Αυτό έχει σαν αποτέλεσμα
>> να μπαίνουν κάθε φορά στο LD queue τα load
>> flag, load A τα οποία και μπορούν να
>> αναδιαταχθούν μιας και πάνε σε
>> διαφορετικές διευθύνσεις. Προφανώς σε
>> κάθε λάθος prediction, κάνεις flush το LD queue,
>> όταν όμως το prediction στο τελευταίο iteration
>> θα είναι σωστό, τότε μπορεί να έχει
>> διαβαστεί το A πριν να διαβάσεις ότι
>> flag!=0.
>>
>> Κ.
>>
>>  2013/7/1 Σαρρής θεόδωρος
>>
>>> Γεια σας. Με ποιο τρόπο σέβεται ο
>>> επεξεργαστής τα data και control dependecies;
>>> Γιατί αν σέβεται τα data hazards πρέπει σε
>>> ένα (1a)A=1 (1b)Print A να μην θεωρούμε εφικτό
>>> 1b->1a γιατί είναι RAW hazard. Ομοίως για τα
>>> control dependecies (1a)While (A==0) ; (1b)Print A πρέπει να
>>> μην θεωρούμε εφικτό 1b->1a. Από τις
>>> διαφάνειες και τα παλιά θέματα εγώ
>>> έχω καταλάβει ότι στα δύο
>>> παραδείγματα που ανέφερα το RMO
>>> επιτρέπει αυτές τις αναδιατάξεις.
>>> Ευχαριστώ,
>>> Σαρρής Θεόδωρος
>>>
>>> On Mon, 1 Jul 2013 15:04:40 +0300, Konstantinos Nikas wrote:
>>>
>>>> Καλησπέρα,
>>>>
>>>> Στο συγκεκριμένο παράδειγμα που
>>>> αναφέρεις, το block παραμένει στο Ι
>>>> παρά
>>>> το PrWr γιατί η cache είναι write-no-allocate.
>>>> Δηλαδή αν κάνει write miss, δεν κάνει
>>>> allocate
>>>> το block στην cache.
>>>>
>>>> Για το δεύτερο ερώτημα, καταρχάς
>>>> αναφερόμαστε σε κάποιο από τα
>>>> μοντέλα
>>>> που παρουσιάστηκαν στο μάθημα. Κατά
>>>> δεύτερον, τα consistency models ασχολούνται
>>>> μόνο με τη σειρά των memory εντολών. Οι
>>>> τυχόν αναδιατάξεις των υπόλοιπων
>>>> εντολών είναι θέμα του επεξεργαστή
>>>> και δεν έχει σχέση με το
>>>> coherence/consistency.
>>>>
>>>> Βέβαια, ακόμα και το πλέον relaxed memory
>>>> order,
>>>> δε σημαίνει ότι επιτρέπονται όλες
>>>> οι
>>>> πιθανές αναδιατάξεις. Μη ξεχνάτε
>>>> ότι ο
>>>> επεξεργαστής εξακολουθεί και
>>>> σέβεται
>>>> τα data και control dependencies!
>>>>
>>>> Κ.
>>>>
>>>> 2013/6/29 Ανδρέας Παντελόπουλος
>>>>
>>>>> Καλησπέρα,στο FSM του simple V/I protocol
>>>>> (διαφ.30) παρατηρώ ότι με PrWr στην Ι
>>>>> ξαναγυρνάει στην κατάσταση Ι.
>>>>> Κανονικά δεν θα έπρεπε να γίνεται
>>>>> μετάβαση στην κατάσταση V ?
>>>>>
>>>>> Επίσης,στην θεωρητική άσκηση της
>>>>> 3ης
>>>>> σειράς αναφέρεστε στο "πλέον relaxed
>>>>> memory
>>>>> order".Τι σημαίνει αυτό ακριβώς? Στην
>>>>> ουσία οποιαδήποτε αναδιάταξη
>>>>> εντολών ή αναδιάταξη εντολών που
>>>>> επιτελούν λειτουργίες μνήμης ?
>>>>>
>>>>> Ευχαριστώ πολύ.
>>>>> _______________________________________________
>>>>> Advcomparch mailing list
>>>>> Advcomparch at lists.cslab.ece.ntua.gr [1] [1]
>>>>> http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch [2]
>>>>> [2]
>>>>
>>>>
>>>> --
>>>> Dr. Konstantinos Nikas
>>>> Computing Systems Laboratory
>>>> School of Electrical and Computer Engineering
>>>> National Technical University of Athens
>>>>
>>>> Tel: +30-210-7724159 [3]
>>>>  e-mail: knikas at cslab.ece.ntua.gr [4] [4]
>>>> http://www.cslab.ece.ntua.gr/~knikas [5] [5]
>>>>
>>>> Links:
>>>> ------
>>>> [1] mailto:Advcomparch at lists.cslab.ece.ntua.gr [6]
>>>> [2] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch
>>>> [7]
>>>> [3] mailto:padelopoulos at gmail.com [8]
>>>> [4] mailto:knikas at cslab.ece.ntua.gr [9]
>>>> [5] http://www.cslab.ece.ntua.gr/~knikas [10]
>>>
>>>
>>> _______________________________________________
>>> Advcomparch mailing list
>>> Advcomparch at lists.cslab.ece.ntua.gr [11]
>>> http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch [12]
>>
>>
>> --
>> Dr. Konstantinos Nikas
>> Computing Systems Laboratory
>> School of Electrical and Computer Engineering
>> National Technical University of Athens
>>
>> Tel: +30-210-7724159
>>  e-mail: knikas at cslab.ece.ntua.gr [14]
>> http://www.cslab.ece.ntua.gr/~knikas [15]
>>
>> Links:
>> ------
>> [1] mailto:Advcomparch at lists.cslab.ece.ntua.gr
>> [2] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch
>> [3] http://webmail.ntua.gr/tel:%2B30-210-7724159
>> [4] mailto:knikas at cslab.ece.ntua.gr
>> [5] http://www.cslab.ece.ntua.gr/~knikas
>> [6] mailto:Advcomparch at lists.cslab.ece.ntua.gr
>> [7] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch
>> [8] mailto:padelopoulos at gmail.com
>> [9] mailto:knikas at cslab.ece.ntua.gr
>> [10] http://www.cslab.ece.ntua.gr/~knikas
>> [11] mailto:Advcomparch at lists.cslab.ece.ntua.gr
>> [12] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch
>> [13] mailto:el09148 at mail.ntua.gr
>> [14] mailto:knikas at cslab.ece.ntua.gr
>> [15] http://www.cslab.ece.ntua.gr/~knikas
>
>
>
> Αν κατάλαβα καλά,  αυτό που λέτε είναι ότι απαγορεύεται η αναδιάταξη όταν
> έχουμε RAW hazard και όταν έχουμε WAW dependency στην ίδια θέση μνήμης. Όμως
> η όλη λογική των weak ordering models δεν είναι να τα επιτρέπουν όλα αυτά
> και απλά να περνάνε το βάρος στο προγραμματιστή ώστε να βάζει τα κατάλληλα
> barriers?
>
> Παράδειγμα, αν έχουμε
> flag = 1;
> print flag;
> που είναι read after write και έχουμε και το πλέον relaxed memory model, οι
> εντολές δεν μπορούν να αναδιαταχθούν?
> Ευχαριστώ!
>
> --
> Δανασής Παναγιώτης
> Εθνικό Μετσόβιο Πολυτεχνείο
> Σχολή Ηλεκτρολόγων Μηχανικών Και Μηχανικών Υπολογιστών
> _______________________________________________
> Advcomparch mailing list
> Advcomparch at lists.cslab.ece.ntua.gr
> http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch

--
Dr. Konstantinos Nikas
Computing Systems Laboratory
School of Electrical and Computer Engineering
National Technical University of Athens

Tel: +30-210-7724159
e-mail: knikas at cslab.ece.ntua.gr
http://www.cslab.ece.ntua.gr/~knikas