Ταξινόμηση σε Linear array

1) Θεωρητική παρουσίαση του αλγόριθμου

Ας θεωρήσουμε ότι έχουμε ένα linear array με Ν επεξεργαστικές μονάδες. Η είσοδος και η έξοδος των δεδομένων γίνεται σε κάθε επεξεργαστική μονάδα.(για άλλου είδους είσοδο-έξοδο υπάρχουν διαφορετικοί αλγόριθμοι).

Ο αλγόριθμος θεωρεί ότι το Ν είναι άρτιος αριθμός. Οι MCUs αριθμούνται από το 1 μέχρι το Ν. Η διαδικασία χωρίζεται σε δύο βήματα.

- Στο πρώτο βήμα, οι μονές MCUs συγκρίνουν τα δεδομένα τους με τα δεδομένα της MCU που βρίσκεται στα δεξιά τους (η MCU1 με την MCU2, η MCU3 με την MCU4, και λοιπά). Αν οι τιμές δεν βρίσκονται σε σωστή διάταξη, αλλάζουν θέση μεταξύ τους.

- Στο δεύτερο βήμα οι ζυγές MCUs συγκρίνουν και ανταλλάσσουν τις τιμές τους με τις τιμές των MCU που βρίσκονται στα δεξιά τους (η MCU2 με την MCU3, και λοιπά).

Η διαδικασία επαναλαμβάνεται Ν/2 φορές.

Το παρακάτω σχήμα δείχνει παραστατικά την διαδικασία (για Ν=8).

Περισσότερες λεπτομέρειες σχετικά με την ορθότητα και την απόδοση του αλγορίθμου βρίσκονται στο βιβλίο του F.T.Leighton.

Η υλοποίηση του αλγόριθμου γίνεται με οκτώ (8) μονάδες επεξεργασίας (Μ.Ε.)

2) Δίκτυο διασύνδεσης και Ι/Ο

Η υλοποίηση γίνεται σε "Parallel PIC" (Revision 1.0).

Κάθε μονάδα επεξεργασίας πρέπει να διαβάζει τα δεδομένα από κάποια πόρτα που έχει ελεύθερη. Στο συγκεκριμένο παράδειγμα η είσοδος έχει εύρος μόνο 2 Bits και υλοποιείται μέσω των σημάτων PortA(0,1). Αντίστοιχα η έξοδος βγαίνει στα σήματα PortA(3,4).

Κάθε MCU χρησιμοποιεί ένα (1) UART. Ο πομπός αντιστοιχίζεται στο RP15 για την επικοινωνία με την αριστερή MCU, και με το RP13 για την επικοινωνία με την δεξιά MCU. Ο δέκτης αντιστοιχίζεται με το RP14 για την επικοινωνία με την αριστερή MCU, και με το RP12 για την επικοινωνία με την δεξιά MCU. Το δίκτυο διασύνδεσης δημιουργείται συνδέοντας το RP13 από κάθε MCU με το RP14 από την MCU στα δεξιά, και το RP12 από κάθε MCU με το RP15 από την MCU δεξιά.

Μια φωτογραφία με την πλακέτα (Revision 1.0) βρίσκεται εδώ. Η πλακέτα προς τα δεξιά παρέχει τα 8 σήματα εισόδου των 2-bits και απεικονίζει τα 8 σήματα εξόδου (των 2 bits βέβαια).

3) Υλοποίηση με ψευδοκώδικα

Κάθε ένα από τα δύο βήματα που περιγράφηκαν στην θεωρητική παρουσίαση του αλγορίθμου χωρίζεται σε δύο (2) μέρη: ένα για τις "μονές" μονάδες επεξεργασίας (1,3,5,7) και ένα για τις "ζυγές" μονάδες επεξεργασίας( 2,4,6,8). Στο δεύτερο βήμα του αλγορίθμου η πρώτη και η τελευταία μονάδα επεξεργασίας δεν συμμετέχουν, οπότε θα πρέπει να βρίσκονται σε ελεγχόμενη αδράνεια, δηλαδή να περιμένουν μέχρι να ολοκληρωθεί η διαδικασία του δεύτερου βήματος από τις υπόλοιπες μονάδες επεξεργασίας. Συνολικά λοιπόν υπάρχουν τέσσερις (4) παραλλαγές του βασικού κώδικα στις οποίες δίνουμε ονόματα: Odd_Left, Odd_Middle, Even_Middle, Even_Right.

Ο ψευδοκώδικας δίνεται παρακάτω:

W1 <-- read_data

for i = 1 to 4

// first phase //

if (even) then SEND(left) <-- W1

if (odd) then W2 <-- RECEIVE(right)

if (odd) then

if W1 < W2 then swap(W1,W2)

endif

if (odd) then SEND(right) <-- W2

if (even) then W1 <-- RECEIVE(left)

//second phase //

if (odd & not leftmost) then SEND(left) <-- W1

if (even & not rightmost) then W2 <-- RECEIVE(right)

if (even & not rightmost) then

if W1 < W2 then swap(W1,W2)

endif

if (even & not rightmost) then SEND(right) <-- W2

if (odd & not leftmost) then W1 <-- RECEIVE(left)

next i

Write_data(W1)

4) Κώδικας

Ο κώδικας δίνεται στον παρακάτω πίνακα:

;Odd_L

;=================
; read value
MOV	PORTA,W1
AND	W1,W4,W1
;=================
; Set counter
MOV  #4,W7
;=================

loop:

setup_RxD_RP12
;=================
; send data
NOP
;=================
wait
;=================
; receive data
MOV	U1RXREG,W2
;=================
; compare-exchange
CP	W1,W2
BRA	LE,labA
MOV	W1,W3
MOV	W2,W1
MOV	W3,W2
BRA	labB
labA:
NOP
NOP
NOP
NOP
labB :
;=================
; send data
MOV	W2,U1TXREG
;=================
wait
;=================
; receive data
NOP
;=================
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
;=================
; send data
NOP
;=================
wait
;=================
; receive data 
NOP
;=================
; compare-exchange
NOP
NOP
NOP
NOP
NOP
NOP
NOP






;=================
; send data
NOP
;=================
wait
;=================
; receive data 
NOP
;=================

DEC W7,W7
BRA	NZ,loop
;=================
; Write value
AND	W1,W4,W1
SL	W1,#3,W1
MOV	W1,PORTA

;Even_M

;=================
; read value
MOV	PORTA,W1
AND	W1,W4,W1
;=================
; Set counter
MOV  #4,W7
;=================

loop:

setup_RxD_RP14
;=================
; send data
MOV	W1,U1TXREG
;=================
wait
;=================
; receive data 
NOP
;=================
; compare-exchange
NOP
NOP
NOP
NOP
NOP
NOP
NOP





;=================
; send data
NOP
;=================
wait
;=================
; receive data
MOV	U1RXREG,W1
;=================

setup_RxD_RP12






;=================
; send data
NOP
;=================
wait
;=================
; receive data 
MOV	U1RXREG,W2
;=================
; compare-exchange
CP	W1,W2
BRA	LE,labA
MOV	W1,W3
MOV	W2,W1
MOV	W3,W2
BRA	labB
labA:
NOP
NOP
NOP
NOP
labB :

;=================
; send data
MOV	W2,U1TXREG
;=================
wait
;=================
; receive data 
NOP
;=================

DEC W7,W7
BRA	NZ,loop
;=================
; Write value
AND	W1,W4,W1
SL	W1,#3,W1
MOV	W1,PORTA

;Odd_M

;=================
; read value
MOV	PORTA,W1
AND	W1,W4,W1
;=================
; Set counter
MOV  #4,W7
;=================

loop:

setup_RxD_RP12
;=================
; send data
NOP
;=================
wait
;=================
; receive data
MOV	U1RXREG,W2
;=================
; compare-exchange
CP	W1,W2
BRA	LE,labA
MOV	W1,W3
MOV	W2,W1
MOV	W3,W2
BRA	labB
labA:
NOP
NOP
NOP
NOP
labB :
;=================
; send data
MOV	W2,U1TXREG
;=================
wait
;=================
; receive data
NOP
;=================

setup_RxD_RP14






;=================
; send data
MOV	W1,U1TXREG
;=================
wait
;=================
; receive data 
NOP
;=================
; compare-exchange
NOP
NOP
NOP
NOP
NOP
NOP
NOP






;=================
; send data
NOP
;=================
wait
;=================
; receive data 
MOV	U1RXREG,W1
;=================

DEC W7,W7
BRA	NZ,loop
;=================
; Write value
AND	W1,W4,W1
SL	W1,#3,W1
MOV	W1,PORTA

;Even_R

;=================
; read value
MOV	PORTA,W1
AND	W1,W4,W1
;=================
; Set counter
MOV  #4,W7
;=================

loop:

setup_RxD_RP14
;=================
; send data
MOV	W1,U1TXREG
;=================
wait
;=================
; receive data 
NOP
;=================
; compare-exchange
NOP
NOP
NOP
NOP
NOP
NOP
NOP





;=================
; send data
NOP
;=================
wait
;=================
; receive data
MOV	U1RXREG,W1
;=================
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
;=================
; send data
NOP
;=================
wait
;=================
; receive data 
NOP
;=================
; compare-exchange
NOP
NOP
NOP
NOP
NOP
NOP
NOP






;=================
; send data
NOP
;=================
wait
;=================
; receive data 
NOP
;=================

DEC W7,W7
BRA	NZ,loop
;=================
; Write value
AND	W1,W4,W1
SL	W1,#3,W1
MOV	W1,PORTA

- Στο τμήμα "read_value" οι μονάδες επεξεργασίας διαβάζουν τα δεδομένα (Το W4 έχει τιμή 0x0003 (mask pattern: επιτρέπει μόνο τα δύο LSBits)

- Στο τμήμα "set_counter" καθορίζεται ο αριθμός των επαναλήψεων του βρόχου (τέσσερις φορές, 4= Ν/2)

- Στο επόμενο τμήμα γίνεται αποστολή δεδομένων από τις "ζυγές" μονάδες στις "μονές".

- Στο τμήμα "compare-exchange" οι μονές Μ.Ε. κάνουν τη σύγκριση και αν χρειάζεται την ανταλλαγή (swap) των δεδομένων.

- Στο επόμενο τμήμα γίνεται αποστολή δεδομένων από τις "μονές" μονάδες στις "ζυγές". Στο σημείο αυτό ολοκληρώνεται το πρώτο βήμα του αλγορίθμου.

- Στα επόμενα τμήματα μεταδίδονται δεδομένα από τις "μονές" Μ.Ε. στις "ζυγές" Μ.Ε., οι "ζυγές" Μ.Ε. κάνουν την σύγκριση και ανταλλαγή (swap) και την αποστολή των τιμών στις "μονές" Μ.Ε.

- Η διαδικασία επαναλαμβάνεται τέσσερις (4) φορές.

- Στο τμήμα "write_value" οι μονάδες επεξεργασίας γράφουν τις (ταξινομημένες πια) τιμές στην PortA.

Οι macros που χρησιμοποιούνται είναι:

.macro wait
		MOV	#100,W8
2:
		NOP
		DEC	W8,W8
		BRA	NZ,2b
.endm

.macro setup_RxD_RP14
		MOV	#0x0008,W6
		MOV	W6,U1MODE
		MOV	#0x1F0E,W6
		MOV	W6,RPINR18
		MOV	#0x8008,W6
		MOV	W6,U1MODE
		MOV	#0x04C0,W6
		MOV	W6,U1STA
.endm

.macro setup_RxD_RP12
		MOV	#0x0008,W6
		MOV	W6,U1MODE
		MOV	#0x1F0C,W6
		MOV	W6,RPINR18
		MOV	#0x8008,W6
		MOV	W6,U1MODE
		MOV	#0x04C0,W6
		MOV	W6,U1STA
.endm

Οι εντολές NOP εισάγονται για vα κρατούν τις MCUs σε πλήρη συγχρονισμό.

Τα αρχεία βρίσκονται στο συμπιεσμένο αρχείο Parallel_PIC_Sort_LA_WideIO.zip. Το αρχείο “Sort.s” κρατάει τον πηγαίο κώδικα σε assembly για την αριστερή MCU. Όταν το πρόγραμμα μεταγλωττιστεί, το αρχείο hex που θα παραχθεί θα πρέπει να μετονομαστεί με το χέρι (αυτό έχει ήδη γίνει και το αρχείο έχει ονομαστεί “Sort_Odd_L.hex”). Μετά ο χρήστης θα πρέπει να αλλάξει την directive “.set column, Odd_L” σε “.set column,Odd_M", μετά σε Even_M και Even_R”, και κάθε φορά να ξαναγίνεται μεταγλώττιση και μετονομασία του αρχείου hex. Μετά από τις μεταγλωττίσεις, ο χρήστης μπορεί να χρησιμοποιήσει το λογισμικό για το PC για να μεταφέρει τον κώδικα στους μικροελεγκτές.

Στη σελίδα που περιγράφει τον ParallelPIC παρουσιάζεται και μια εναλλακτική πρόταση που επιταχύνει την εκτέλεση του αλγόριθμου.

Αρχική σελίδα Παράλληλης Επεξεργασίας