Η παρούσα διδακτορική διατριβή
συνεισφέρει ερευνητικά στην
ανάπτυξη παράλληλων
αρχιτεκτονικών για αλγορίθμους
επεξεργασίας εικόνων και γραφικών.
Κύριος στόχος της είναι η οργάνωση παράλληλων
μνημών για αποδοτική υποστήριξη
των απαιτήσεων που εμφανίζουν οι
αλγόριθμοι του συγκεκριμένου επιστημονικού πεδίου.
Επιπροσθέτως,
ως πρακτική εφαρμογή,
η διατριβή εστιάζει στην υλοποίηση
αλγορίθμων εκτίμησης κίνησης σε εικονοροές.
Η εργασία ξεκινάει με μια εκτεταμένη
μελέτη της σχετικής βιβλιογραφίας.
Έπειτα,
περιγράφει τη σχεδίαση και ανάπτυξη σε
υλισμικό μιας προγραμματιζόμενης μονάδας
εκτίμησης κίνησης με δυνατότητα εκτέλεσης
πολλών διαφορετικών αλγορίθμων
ταιριάσματος περιοχών σε πραγματικό χρόνο.
Η μονάδα απαρτίζεται από
παράλληλη μνήμη για τοπική
αποθήκευση εικονοστοιχείων,
από αριθμητικά κυκλώματα για σάρωση
και σύγκριση περιοχών,
καθώς κι από έναν εφαρμογοείδιο
επεξεργαστή για την εκτέλεση
των αλγοριθμικών βημάτων.
Η προτεινόμενη αρχιτεκτονική
βασίζεται σε τεχνικές σωλήνωσης
και παραλληλισμό σε επίπεδο δεδομένων
για την επιτάχυνση των υπολογισμών.
Εισάγει ένα πρωτοποριακό σύνολο εντολών,
σχεδιασμένο ειδικά για τη
συγκεκριμένη κατηγορία αλγορίθμων.
Επίσης,
εισάγει μια εξειδικευμένη τεχνική για
εκτέλεση εντολών παράλληλα με την
διαδικασία εξέτασης των περιοχών,
η οποία έχει ως αποτέλεσμα την εξάλειψη των κενών
κύκλων στη σωλήνωση της διόδου δεδομένων και
την αύξηση της εκμετάλλευσης του υλικού.
Η επαναδιαρθρώσιμη αρχιτεκτονική
που προκύπτει τελικά αναπτύσσεται σε
προγραμματιζόμενους
πίνακες λογικών πυλών (FPGA),
όπου αξιολογείται το κόστος και η λειτουργία της.
Η σύγκριση των αποτελεσμάτων με
αντίστοιχα της βιβλιογραφίας
καταδεικνύει την αποδοτικότητα και
τα πλεονεκτήματα της αρχιτεκτονικής.
Γενικεύοντας σε ένα ευρύτερο πεδίο εφαρμογών,
η διατριβή συνεχίζει προτείνοντας
μια λύση στο πρόβλημα
της οργάνωσης παράλληλων μνημών
για αποθήκευση εικόνων.
Η λύση επιτρέπει την ταυτόχρονη
ανάκτηση πολλαπλών εικονοστοιχείων
από τη μνήμη υποστηρίζοντας με αυτόν
τον τρόπο την παράλληλη επεξεργασία των
δεδομένων από τον εκάστοτε αλγόριθμο.
Τα εικονοστοιχεία τοποθετούνται σε
πολλαπλές τράπεζες μνήμης μέσω
μιας προτεινόμενης
συνάρτησης αντιστοίχισης,
η οποία δημιουργεί δυνατότητα ταυτόχρονης
πρόσβασης σε σύνολα
εικονοστοιχείων που εμφανίζονται
επάνω στην εικόνα
ως γραμμές, στήλες, ορθογώνια,
ή αραιά ορθογώνια.
Τα εν λόγω σχήματα μπορούν να ανακτηθούν
από οποιαδήποτε θέση της εικόνας με αποτέλεσμα
την ικανοποίηση των συνήθων
απαιτήσεων στις εφαρμογές γραφικών.
Η καινοτομία της προτεινόμενης λύσης
έγκειται στην μείωση του αριθμού των τραπεζών που
χρησιμοποιούν οι προγενέστερες εργασίες της
βιβλιογραφίας προκειμένου να πετύχουν τις
ίδιες ή παρόμοιες δυνατότητες πρόσβασης.
Συγκεκριμένα,
αποφεύγει την έως σήμερα χρήση
πρώτων ή άλλων δύσκολων αριθμών Β
με Β>Ε, όπου Β
το πλήθος των τραπεζών
κι Ε το πλήθος των εικονοστοιχείων
στα οποία απαιτείται ταυτόχρονη
πρόσβαση ενός κύκλου.
Αντί αυτών,
οργανώνει την παράλληλη μνήμη
με τον ιδανικό αριθμό τραπεζών Β=Ε
επιτρέποντας στο Β να πάρει
τιμή ίση με οποιαδήποτε δύναμη του 2.
Επί πλέον,
εκμεταλλεύεται τις ιδιότητες της
νέας
συνάρτησης αντιστοίχισης
και τις συσχετίσεις που εμφανίζουν
οι διαδοχικές αιτήσεις μνήμης
κατά την επεξεργασία εικόνων
προκειμένου
να διορθώσει τυχόν συγκρούσεις που παρουσιάζονται
στη μνήμη ξοδεύοντας μόνο
έναν κύκλο ανά Β αιτήσεις.
Συνεπώς,
η προτεινόμενη λύση οδηγεί στη
μείωση της υποεκμετάλλευσης του υλικού,
στη μείωση του κόστους κατασκευής των
κυκλωμάτων λειτουργίας
και στη σχεδίαση βελτιωμένων και
αποδοτικότερων παράλληλων μνημών.
Η διατριβή παραθέτει
θεωρήματα κι αποδείξεις των ιδιοτήτων
της αντιστοίχισης
και της τεχνικής διόρθωσης
των αναπόφευκτων συγκρούσεων.
Ακολούθως, αναλύει τη χρήση της
νέας οργάνωσης μνήμης σε ευρέως
διαδεδομένες εφαρμογές
προκειμένου να αξιολογήσει
τις επιδόσεις της και να τη συγκρίνει
με τις προγενέστερες λύσεις
σε πρακτικό επίπεδο.
Μεταξύ αυτών,
αναλύει τη βελτίωση που επιφέρει
η ενσωμάτωση της νέας μνήμης
στην προτεινόμενη μονάδα
εκτίμησης κίνησης
και ποσοτικοποιεί τα οφέλη
της σε πόρους υλικού.
(EL)
The current dissertation contributes in designing efficient parallel
architectures
for image, video and graphics applications. The main objective is
to organize parallel memories for supporting the most common algorithmic
requirements encountered in the certain scientific field. Moreover, as a case
study, the dissertation focuses on the implementation of motion estimation
algorithms for video compression.
An elaborate study of bibliography related to both of the above objectives
precedes the design of a programmable architecture executing a variety
of block-matching algorithms with real-time performance. The design
involves a parallel memory for the local storage of pixels, parallel arithmetic
units for the examination of candidate blocks, and an application-specific
instruction-set processor to meet the computational requirements of each
algorithm. Overall, the architecture bases on pipelining techniques and data
level parallelism to speed-up the block matching procedure. It introduces a
novel instruction set and a speculative execution technique, which leads in
almost 100% utilization of the data-path by allowing the algorithm to operate
concurrently with the examination of candidate blocks. The cost and the
performance of the reconfigurable motion estimation module are evaluated
on FPGA platforms. Comparison to similar works of the literature highlights
the advantages and verifies the efficiency of the proposed design.
Furthermore, the dissertation considers the problem of storing and retrieving
pixels in parallel for a wider range of graphics applications. It introduces
a technique tackling this problem and leading to an efficient memory
organization, which facilitates parallel processing by allowing any algorithm
to access numerous pixels in a single cycle. The solution involves a non-linear
skew function to map each image pixel in one out of B memory banks.
The proposed mapping supports the most common graphics requirements by
achieving parallel access to rows, columns, rectangles, and sparse sets of
pixels
originating at any location on the image. Overall, the organization utilizes
less memory banks compared to the corresponding solutions of the literature,
which use B>E when E pixels are requested in parallel. In contrast to
the common bibliographic approach using prime –or other peculiar– numbers
for B, the proposed solution organizes the memory with only B=E banks
allowing B to be any power of 2. Moreover, based on the properties of its
mapping function, the solution exploits successive request correlations during
image/video processing to handle possible memory conflicts by spending only
one cycle every B memory accesses. The resulting organization improves the
resource utilization, reduces the hardware cost and leads to efficient parallel
memory designs. The dissertation presents theorems and proofs regarding
the properties of the proposed mapping function and the conflict handling
technique. Subsequently, it analyzes the performance of the novel memory
in example applications to show the merit of the proposed organization and
to compare with hitherto published solutions at the implementation level. In
this direction, the analysis also includes the integration of the novel memory
to the developed motion estimation architecture; the results show improved
performance/cost for the entire estimator and quantify the benefits of the
proposed memory in terms of hardware resources.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
