Επισκέπτης Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 Στα πλαισια του μαθηματος "Λειτουργικα Συστηματα" εχω να απαντησω στα ερωτηματα αυτης της ασκησης. Οι μεταγλωττιστές έχουν δύο τρόπους να αποθηκεύουν τους δισδιάστατους πίνακες – κατά γραμμή και κατά στήλη. Και στις δύο περιπτώσεις, σε κάθε πίνακα m[X][Y] ανατίθεται μία διεύθυνση βάσης όπου αποθηκεύεται το στοιχείο m[0][0]. Στην κατά γραμμή αποθήκευση, τα υπόλοιπα στοιχεία του πίνακα αποθηκεύονται με τη σειρά: m[0][0] m[0][1] … m[0][Y-1] m[1][0] m[1][1] … m[1][Y-1] … m[X-1][0] m[X-1][1] … m[X-1][Y-1] ενώ στην κατά στήλη αποθήκευση, η σειρά αποθήκευσης είναι: m[0][0] m[1][0] … m[Χ-1][0] m[0][1] m[1][1] … m[Χ-1][ 1] … m[0][Υ-1] m[1][Υ-1] … m[X-1][Y-1] Θεωρήστε τώρα τα δύο προγράμματα που ακολουθούν: Πρόγραμμα 1 char m[10000][10000]; int a, b; for (a = 0; a < 10000; a++) for (b = 0; b < 10000; b++) m[a] = ʽ\0ʼ; Πρόγραμμα 2 char m[10000][10000]; int a, b; for (a = 0; a < 10000; a++) for (b = 0; b < 10000; b++) m[a] = ʽ\0ʼ; Σε ένα σύστημα με σελιδοποίηση όπου έχουμε 1 ΜΒ φυσικής μνήμης οργανωμένο σε 512 πλαίσια σελίδων, πόσα σφάλματα σελίδων θα δημιουργήσει το πρόγραμμα 1 αν ο μεταγλωττιστής χρησιμοποιεί αποθήκευση κατά γραμμές, και πόσα αν ο μεταγλωττιστής χρησιμοποιεί αποθήκευση κατά στήλες; Επαναλάβετε για το πρόγραμμα 2. Σχολιάστε αν ο προγραμματιστής θα πρέπει να γνωρίζει και να λαμβάνει υπόψη του την προσέγγιση που ακολουθεί ο μεταγλωττιστής. Ποια είναι η προσέγγιση που ακολουθεί η γλώσσα C; αυτο που θελω ειναι καποιος να μου πει πως θα πρεπει να απαντησω στην ακολουθη ερωτηση... Σχολιάστε αν ο προγραμματιστής θα πρέπει να γνωρίζει και να λαμβάνει υπόψη του την προσέγγιση που ακολουθεί ο μεταγλωττιστής. Ποια είναι η προσέγγιση που ακολουθεί η γλώσσα C; που μπορω να βρω πως ενας C compiler διαχειριζεται τους διδιαστους πινακες...;Εψαξα αλλα δε βρηκα κατι...υπαρχει καποιος που μπορει να βοηθησει;Παντως ειναι πολυ περιεργη ερωτηση...imho.
Sta Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 Η C αποθηκεύει τους διδιάστατους πίνακες σε "row major order", δηλαδή κατά γραμμή. Τέτοια πράγματα είναι γενικά διαφανή προς τον προγραμματιστή και δεν οφείλει να τα ξέρει ή καλύτερα να γράφει κώδικα βέλτιστο ανάλογα με τις προδιαγραφές του μεταγλωττιστή.
Επισκέπτης Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 ok,eyxaristw poly.. exeis na moy steileis kana link panw se ayta...? αυτο δε το πολυκαταλαβα Τέτοια πράγματα είναι γενικά διαφανή προς τον προγραμματιστή και δεν οφείλει να τα ξέρει ή καλύτερα να γράφει κώδικα βέλτιστο ανάλογα με τις προδιαγραφές του μεταγλωττιστή. Εννοεις οτι κατω απο κανονικες συνθηκες ο προγραμματιστης δεν οφειλει να γνωριζει πως λειτουργει ο C compiler(προφανως η ασκηση αναφερεται στον gnu c compiler-αν δε κανω λαθος) και μονο σε περιπτωση που θελει να γραφει optimized κωδικα μονος του οφειλει να γνωριζει τις προδιαγραφες του compiler του (οπως manual loop unrolling dld?) pantws eyxaristw poy mphkes ston kopo na apanthseis.. an mporeis omws na moy to eksigiseis kapws kalytera..
chiossif Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 Ο τρόπος αποθήκευσης ενός πίνακα στην μνήμη ΔΕΝ ΕΠΗΡΕΑΖΕΙ τον προγραμματιστή όταν αναφέρεται στα στοιχεία του με χρήση αριθμοδεικτών (indexes) πχ α[ι][ξ]. Αντίθετα τον ΕΠΗΡΕΑΖΕΙ αν αναφέρεται στα στοιχεία του με χρήση (pointers) πχ *(α+ι*κολόνες+ξ). Επίσης ο προγραμματιστής ΕΠΗΡΕΑΖΕΤΑΙ από τον τρόπο αυτό όταν: 1) κάνει "μαζική" είσοδο / έξοδο των στοιχείων του πίνακα ΧΩΡΙΣ δηλαδή χρήση αριθμοδεικτών πχ με το ζεύγος εντολών read, write 2) εκτελεί αντιγραφές / συγκρίσεις / πράξεις τμημάτων μνήμης τα οποία ΔΕΝ αντιστοιχούν σε απολύτως όμοια δηλωθείσες μεταβλητές πχ απόσπασμα πίνακα με memcpy Τα παραπάνω τα σκέφτηκα πρόχειρα, προφανώς Ο ΔΑΣΚΑΛΟΣ ΣΟΥ θα ξέρει περισσότερα. Επειδή προφανώς πρόκειται για μάθημα και νομίζω ότι από το ηλεκτρονικό αυτό τόπο ΔΕΝ πρέπει να παρεμβαίνουμε στην λειτουργία εκπαιδευτικών ιδρυμάτων, (φανταστείτε να λύναμε από εδώ θέματα του ΕΑΠ πριν την ημερομηνία παράδοσης), θα ήθελα να μετασχηματίσω το ερώτημα στο ακόλουθο: Γράψτε ένα πρόγραμμα σε γλώσσα C ή άλλη το οποίο να εντοπίζει τον τρόπο με τον οποίο αποθηκεύεται ένας διδιάστατος πίνακας στην μνήμη του Η/Υ. Για παράδειγμα αν το πρόγραμμα λέγεται kokovios η εκτέλεση του θα πρέπει να έχει το ακόλουθο αποτέλεσμα: $kokovios [Enter] Row major order ή Column major order $
dop Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 Για την πρώτη ερώτηση σε σχέση με τις hit/miss ratio δε θα απαντήσω γιατί θα σου λύσω την άσκηση. Έχε απλώς υπόψην ότι σε κάποιες περιπτώσεις υπάρχει ισχυρό data locality και σε κάποιες άλλες πάει περίπατο. Βρες πόσα bytes χωράν σε κάθε πλαίσιο και τρέξε τον αλγόριθμό σου. Τέλος, μήπως 1MB είναι η cache; Δεν σε νοιάζει τι θα κάνει ο compiler, εκτός αν πρόκειται για αρχαίο/embedded systems compiler. Ο κώδικας C που γράφεις πρέπει να είναι συνεπής με το ακολουθούμενο standard (C89/C99/κάτι άλλο) και να μην έχει bugs. Ότι κώδικα και να δώσεις, ένας καλός compiler θα κάνει τα αντίστοιχα optimizations ώστε να βολεύει όσο το δυνατόν καλύτερα το μηχάνημα. Μην ξεχνάς ότι εφόσον έχουμε superscalar επεξεργαστές, δύναται το 3ο loop να ξεκινήσει ταυτόχρονα και με το 2ο. Και αυτό δεν μπορείς να το ελέγξεις στην C. Όπως και ανάποδα loops να κάνεις, δεν θα αλλάξει και πολλά πράματα: αυτά τα κάνει ήδη ο compiler. Όσο για το πως διαχειρίζεται τους πίνακες ο compiler (δηλαδή πως κάνει το referencing) για τρέξε το παρακάτω: > #include <stdio.h> int main(void) { int a[10][10]; printf("%d %d\n", &(a[1][0])-&(a[0][0]), &(a[0][1])-&(a[0][0])); return 0; } Σε μένα επιστρέφει "10 1", δηλαδή ανά [0][0], [0][1] κλπ στην μνήμη.
Επισκέπτης Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 @chiossif eyxaristw gia thn apanthsh.. exeis dikio sta osa les...giayto kai thn ergasia egw thelw na th kanw monos moy..(giayto zhthsa link apo ton Sta kai den rwthsa gia to prwto skelos ths askhshs poy tha prepei na eimai se thesh na apanthsw me bash ta osa exoyme kanei)de thelw etoima psaria...xreiazomai kateythynseis... omws h ergasia erxetai kai mpainei th stigmh poy emeis sta leitoyrgika den exoyme anaferthei kan se pragmata opws "row major order" kai arxitektonikes-prodiagrafes compiler (to mathima poy afora compilers einai sto 5o eksamhno-egw eimai tetarto...ara oyte compilers exw kanei...). Sta "Leitoyrgika Systhmama " ayta poy exoyme kanei einai diaxeirish mnhmhs-eikonikh mnhmh-systhmata selidopoihshs-pinakes selidwn-tlb-algorithmoys antikatastashs selidwn-systhmata katatmhshs kai liga apo cache an de kanw lathos...katalabaineis loipon oti den einai thema baremaras (h oti zhtaw na moy apanthsoyn oi alloi sthn askhsh) alla einia thema agnoias kai eleipshs plhroforiwn,giayto kai zhtaw kateythyntiries grammes perissotero (afotoy exw prospathisei na apanthsw sto erwthma monos moy...). Epishs, o kathigiths oydepote anaferthike se tetoia pragmata kai oyte mas edwse kateythyntiries grammes etsi wste na psaksoyme na ta boyme..xtes, egw anti na psanxw sto google gia "Row major order" epsaxna anepityxws gia "gnu c compiler specifications"... katalabaineis loipon... anyway,kai pali eyxaristw gia thn bohtheia...katalaba arketa.
chiossif Δημοσ. 17 Ιουλίου 2006 Δημοσ. 17 Ιουλίου 2006 Λυπάμαι αλλά το εξέλαβες λάθος. Με την φράση μου "Επειδή προφανώς πρόκειται για μάθημα και νομίζω ότι από το ηλεκτρονικό αυτό τόπο ΔΕΝ πρέπει να παρεμβαίνουμε στην λειτουργία εκπαιδευτικών ιδρυμάτων" ΑΝΑΦΕΡΘΗΚΑ στο τι πρέπει να κάνουμε "εμείς" και κατά συνέπεια και εσύ και ΑΛΛΑ και εγώ. Άρα λοιπόν ρώτα ελεύθερα (ανοιχτά) και όχι ΤΖΑΜΠΑ (χωρίς κόπο) (free as freedom not as free beer) Επίσης, σκέφτηκα πολύ τί να γράψω για τον δάσκαλό σου. Γράφοντας "Ο ΔΑΣΚΑΛΟΣ ΣΟΥ θα ξέρει περισσότερα" δεν σημαίνει ότι "εσύ πρέπει να τα ξέρεις". Τώρα γιατί δεν τα ξέρεις; Δεν νομίζω μπορώ να απαντήσω αυτό το ερώτημα...
Επισκέπτης Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 @chiossif nai,endexomenws na mh katalaba kala... an kai exw thn entypwsh oti katalaba..eksoy kai to exeis dikio sta osa les...giayto kai thn ergasia egw thelw na th kanw monos moy..(giayto zhthsa link apo ton Sta kai den rwthsa gia to prwto skelos ths askhshs poy tha prepei na eimai se thesh na apanthsw me bash ta osa exoyme kanei)de thelw etoima psaria...xreiazomai kateythynseis... ayto poy soy lew mporeis na to deis kai edw... http://www.insomnia.gr/vb3/showthread.php?t=150583 kai sth sygkekrimenh periptwsh de zhthsa apo ta paidia na moy grapsoyn to script...to script to eixa grapsei..apla eixa apories sto pws tha to oloklhrwsw...moy dwthikan loipon kateythyntiries grammes kai apo kei kai pera epsaksa gia sed,awk,vi etc.etc... kai oloklhrwsa to script me epityxia twra,sta osa lew gia to mathima kai ton kathigith...mh dineis shmasia..bgazw to parapono moy twra..katalabes? lol to egrapsa gia na soy deiksw oti einai kati palikaria (40 xronwn kai me kamia 100-aria papers sth plath toys) poy perimenoyn na kaneis p@p@des apo to poythena.(xwris na dwsoyn kapoia tips h kateythynseis)..se genikes grammes ayta...twra brhskw phges me bash ta osa moy anaferate,opote proxwraei kala h doyleia...
bobosss Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 ναι πραγματι οπως λες και συ ειναι πολύ περίεργη η ερώτηση του αλλα κάπως πρέπει να ξεχωρήσει το 9,8 απο το 10. Επεισεις πάνω σε όσα λές για το οτι σου ζητάει παπαδες απο το πουθενα και κρίνεις το μαθημα του κλπ κλπ κλπ έχω να σου κάνω μία ερώτηση. Δοκίμασες ποτε να απευθηνθεις στο e-mail του? Θα σου απαντησει μέσα σε ενα 10 λεπτο ότι ερώτηση και να του κάνεις οποτε δεν χάνεις τίποτα να δωκιμάσεις την επόμενη φορά πρίν απευθηνθέις σε φορα. Σε αυτο το χάλι που φοιτούμε έχει μαζευτεί όλη η ακαδημαική σκαρταδουρα και συ φωνάζεις για έναν απο τους ελαχιστους ανθρωπους που ξεχωρίζουν εκει μέσα?? δεν είναι αδικο αυτο?
Επισκέπτης Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 Τέλος, μήπως 1MB είναι η cache; oxi file moy...de nomizw na anaferetai sth cache...kai apo ti gnwrizw h diafores cache mapping texnikes den anaferontai se page frames..mono sth fysikh mnhmh synantwntai ta page frames...diorthwse me an kanw lathos..kai gw sthn arxh nomiza oti hthele na oty analysoyme ta page faults me bash olh thn ierarxia tlb-cache-memory-virtual memory ..rwthsa kai alla paidia kai moy eipan oxi..twra,ti na soy pw..mporei na to ennoei kai na mhn to exei diatypwsei swsta.. Σε ένα σύστημα με σελιδοποίηση όπου έχουμε 1 ΜΒ φυσικής μνήμης οργανωμένο σε 512 πλαίσια σελίδων pantws gia na anaferetai se selidopoihsh opwsdipote thelei na laboyme ypopsin mas kai th virtual memory..apla,ayto poy me problhmatizei einai oti den kathorizei to megethos ths eikonikhs mnhmhs....na ypothesw to diplasio egw?
Επισκέπτης Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 @bobosss file moy,exeis dikio... pragmatika einai apo toys elaxistoys poy ksexwrizoyn edw mesa..prosekse omws..stis teleytaies ergasies poy kanw twra to kalokairh (Prohgmenes arxitektonikes,SDBD k.a) stelnw email kai me grafoyn @@...eimai sigouros oti katalabes poioi... egw loipon de tha kathomai na zhtaw apo ton kathena mesw mail na moy dwsei parapanw plhrofories,kai ayto gia treis logoys 1)einai ypoxrewsh toy kathighth na dieykrinhzei ti zhtaei kai na dwsei kateythynseis gia pragmata poy den exoyme kanei-giayto plhrwnetai... 2)einai adiko pros olloys toys ypoloipoys h epilektikh plhroforish(an kai shkwnei koybenta olo ayto..) 3)exw apofasisei na mh stelnw pia mail giati sxedon kanenas den apantaei gia ton sygkekrimeno kathigith twra.. opws proeipa,ksexwrizei... malista,me exei bohthisei oyk oliges fores se periptwseis poy xreiastika bohtheia(kyriws oson afora alla mathimata..) endexomenws to sxolio moy to egrapsa gia na soy deiksw oti einai kati palikaria (40 xronwn kai me kamia 100-aria papers sth plath toys) poy perimenoyn na kaneis p@p@des apo to poythena.(xwris na dwsoyn kapoia tips h kateythynseis) na htan astoxo se ekeino to shmeio mias kai den hthela na anaferthw se ayton...apla exw fortwsei agria me kati alla palikaria..(nomizw katalabes)..Gia to en logw kathighth ayto poy ennoysa synopsizetai sto eksis :blakeia toy poy mas zhtaei pragmata poy den exoyme anaferei pote sth taksh xwris na dinei epiprostheth plhroforish...(h estw poy den ebgale anakoinwsh poy na dinei kapoies kateythynseis ) elpizw na hmoyn safhs ayth th fora...
dop Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 Δε σε νοιάζει το πόσο είναι η virtual: θεώρησε ότι είναι όση και τα δεδομένα σου και είσαι εντάξει. Όσο για την cache και αυτή δουλεύει με σελίδες: η μετακίνηση δεδομένων από/προς την κύρια μνήμη γίνεται σε σελίδες και ανάλογα με τον αλγόριθμο αντικατάστασης γίνεται η αντικατάσταση παλιών σελίδων από καινούριες. Φυσικά cache από/προς CPU μπορεί να κουβαλά όσο και ότι θέλει, αν και συνήθως ανά λέξη μεταφέρονται τα δεδομένα. Εγώ πάντως θα περίμενα να μιλούσε για cache misses.
GrMikeD Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 bebaiws kai paizei rolo kai prepei na kserei o programmatistis pws apothikevontai ta stoixeia tou pinaka stin mnimi. Giati ama exeis to loop me lathos seira, ginontai polles prospelaseis stin mnimi se diaforetika simeia, xwris na xrisimopoiei oso to dunaton perissotera idi apothikevmena tmimata logw topikotitas anaforwn stin cache. Den tha ton eniaze stin periptwsi den eftiaxne toso low kwdika pollaplasiasmou, alla xrisimopoiouse uparxousa sunartisi tou sustimatos. Alla kai tote, o programmatistis autis tis uparxousas sunartisis tha eixe pronoisei na kanei ta loops me tin seira pou prepei. Klasiko paradeigma einai na efarmoseis tous parapanw algorithmous gia megalo arithmo epanalipsewn se C kai pascal, pou exoun apothikeusi kata seires kai kata steiles antistoixa, kai na metriseis xronous...
dop Δημοσ. 18 Ιουλίου 2006 Δημοσ. 18 Ιουλίου 2006 @GrMikeD: ναι πριν από 7-8 χρόνια. Ο παρακάτω κώδικας > #include <stdlib.h> #include <stdio.h> #define ONE int main(void) { char m[10000][10000]; int a, b; #ifdef ONE for (a = 0; a < 10000; a++) for (b = 0; b < 10000; b++) m[a][b] = '\0'; #else for (a = 0; a < 10000; a++) for (b = 0; b < 10000; b++) m[b][a] = '\0'; #endif return 0; } δίνει το ίδιο ακριβώς εκτελέσιμο σε gcc -O3 είτε τρέχει το 1ο loop είτε το 2ο.
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.