Αρχική σελίδα Παράλληλης Επεξεργασίας
English version (Αγγλική έκδοση)
Άθροισμα Ακεραίων σε Δυαδικό Δένδρο
Ας θεωρήσουμε ότι έχουμε ένα δυαδικό δένδρο με Ν επεξεργαστικές μονάδες (όπου Ν=2κ-1, κ=2 ή 3 ή 4). Η είσοδος των δεδομένων γίνεται από τα "φύλλα" του δένδρου. Κάθε "φύλλο" έχει δύο εισόδους των 8-Bit η κάθε μία. Το άθροισμα παράγεται από τη "ρίζα" του δένδρου και έχει κι αυτό πλάτος 8 bit.
Κάθε Μονάδα Επεξεργασίας (φύλλο, εσωτερική, ή ρίζα) δέχεται είσοδο στις πόρτες DOWN και RIGHT και βγάζει έξοδο στην πόρτα UP. Στην έξοδο εμφανίζεται το άθροισμα των τιμών των εισόδων.
Ο κώδικας που εκτελεί μια τέτοια διαδικασία είναι:
MOV A,DOWN ;read DOWN port
MOV B,A
MOV A,RIGHT ;read RIGHT port
ADD A,B
MOV P0,UP ;Write UP port
HALT: SJMP HALT
Ο πλήρης κώδικας βρίσκεται στο αρχείο SumtreeA.asm και μπορεί κανείς να το μεταφράσει και να το "κατεβάσει" σε μία μονάδα επεξεργασίας και να το δοκιμάσει βάζοντας δύο βοηθητικές μονάδες εισόδου στις πόρτες DOWN και RIGHT, και μια βοηθητική μονάδα εξόδου στην πόρτα UP.
Όταν εκτελείται το πρόγραμμα η μονάδα εξόδου θα πρέπει να δείχνει το άθροισμα των τιμών που δίνονται με τις μονάδες εισόδου. Προσοχή: το πρόγραμμα εκτελεί την λειτουργία του και μετά μπαίνει σε κατάσταση αδράνειας. ΑΝ αλλάξουμε τα δεδομένα εισόδου, θα πρέπει να κάνουμε RESET για να δούμε το νέο αποτέλεσμα!
Μπορούμε να βάλουμε τις μονάδες επεξεργασίας να διαβάζουν συνεχώς τις εισόδους και να παράγουν νέες τιμές εξόδου. Ο κώδικας είναι (αρχείο SumtreeB.asm):
LOOP:
MOV A,DOWN ;read DOWN port
MOV B,A
MOV A,RIGHT ;read RIGHT port
ADD A,B
MOV P0,UP ;Write UP port
SJMP LOOP
Με τον κώδικα αυτό μπορεί κανείς να συνδέσει και περισσότερες μονάδες σε δένδρο και να πάρει στην έξοδο της "ρίζας" του δένδρου το συνολικό άθροισμα. Σημείωση: στην πραγματικότητα όταν ξεκινάει η εκτέλεση του προγράμματος καθώς και όταν συμβαίνουν αλλαγές στα δεδομένα εισόδου, πρέπει να μεσολαβήσει κάποιος χρόνος μέχρι η τιμή της εξόδου να αντικατοπτρίζει το άθροισμα των τιμών εισόδου.
Σε περίπτωση που δεν θέλουμε να υπάρχουν "άχρηστες" τιμές εξόδου μπορούμε να κατασκευάσουμε ένα πρόγραμμα που δουλεύει μόνο μια φορά (όπως ο πρώτος κώδικας) και υπολογίζει τον χρόνο που μεσολαβεί από το RESET μέχρι την παρουσία σταθερών δεδομένων στις εισόδους της επεξεργαστική μονάδας. Ένα τέτοιο παράδειγμα κώδικα χρησιμοποιεί τρεις (3) μονάδες επεξεργασίας (κ=2, Ν=3). όπου στα δύο "φύλλα" τρέχει ο κώδικας από το SumtreeA.asm και στη "ρίζα" τρέχει ο παρακάτω κώδικας (SumtreeC.asm):
NOP
NOP
NOP
NOP
NOP
MOV A,DOWN ;read DOWN port
MOV B,A
MOV A,RIGHT ;read RIGHT port
ADD A,B
MOV P0,UP ;Write UP port
HALT: SJMP HALT
Η φωτογραφία δείχνει το Array Of MCU σε συνδεσμολογία δένδρου (κάτω αριστερά μονάδες).
