Η διόρθωση λαθών με κώδικες LDPC είναι μεγάλου ενδιαφέροντος σε σημαντικές νέες τηλεπικοινωνιακές εφαρμογές, όπως δορυφορικό Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) και IEEE 802.16 (WiMAX). Οι κώδικες LDPC ανήκουν στην κατηγορία των γραμμικών μπλοκ κωδικών. Πρόκειται για κώδικες ελέγχου και διόρθωσης σφαλμάτων μετάδοσης, με κυριότερο χαρακτηριστικό τους τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check), από τον οποίο και πήραν το όνομά τους. Η αποκωδικοποίηση γίνεται μέσω μιας επαναληπτικής διαδικασίας ανταλλαγής πληροφορίας μεταξύ δύο τύπων επεξεργαστικών μονάδων. Η υλοποίηση σε υλικό των LDPC αποκωδικοποιητών αποτελεί ένα ραγδαία εξελισσόμενο πεδίο για τη σύγχρονη επιστημονική έρευνα. Σκοπός της παρούσας διπλωματικής εργασίας υπήρξε ο σχεδιασμός, η υλοποίηση και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητών VLSI για κώδικες LDPC. Έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Μελετήθηκαν αρχιτεκτονικές βασισμένες σε δύο αλγόριθμους, τον log Sum-Product και τον Min-Sum. Ο πρώτος είναι θεωρητικά βέλτιστος, αλλά ο Min-Sum είναι αρκετά απλούστερος και έχει μεγαλύτερο πρακτικό ενδιαφέρον στα πλαίσια μιας ρεαλιστικής εφαρμογής. Συγκεκριμένα, αναπτύχθηκαν δύο αλγόριθμοι αποκωδικοποίησης, οι οποίοι χρησιμοποιούν ως δομικά στοιχεία, τους δύο προαναφερθέντες αλγορίθμους και τη φιλοσοφία του layered decoding. Η μελέτη μας επικεντρώθηκε σε κώδικες, η δομή των πινάκων ελέγχου ισοτιμίας των οποίων, προσφέρεται για υλοποίηση. Για αυτό το λόγο, χρησιμοποιήσαμε κώδικες του προτύπου WiMax 802.16e. Η συνεισφορά της παρούσας εργασίας έγκειται στο σχεδιασμό και την υλοποίηση αποδοτικών αρχιτεκτονικών σε επίπεδο επιφάνειας και ταχύτητας αποκωδικοποίησης (Mbps), καθώς και η διερεύνηση του σχετικού σχεδιαστικού χώρου, χρησιμοποιώντας ως σχεδιαστικές παραμέτρους, τον αλγόριθμο αποκωδικοποίησης, τη χρονοδρομολόγηση των πράξεων, το βαθμό παραλληλίας της αρχιτεκτονικής, το βάθος του pipelining και την αριθμητική αναπαράσταση των δεδομένων. Επιπλέον, είναι σημαντικό να αναφέρουμε πως, στα πλαίσια της σχεδίασης του LDPC αποκωδικοποιητή και με τη βοήθεια του εργαλείου Matlab, αναπτύχθηκαν παραμετρικά scripts για την παραγωγή του VHDL κώδικα. Οι δύο βασικές παράμετροι που χρησιμοποιήθηκαν ήταν το πλήθος των επεξεργαστικών μονάδων και το μήκος λέξης των δεδομένων. Τα scripts αυτά αποτέλεσαν ένα πολύ χρήσιμο εργαλείο κατά τη διαδικασία ανάπτυξης και βελτιστοποίησης της αρχιτεκτονικής, δίνοντας μας τη δυνατότητα να παράγουμε με αυτοματοποιημένο και γρήγορο τρόπο τον VHDL κώδικα, για τις επιμέρους μονάδες του αποκωδικοποιητή. Η υλοποίηση ενός μοντέλου αποκωδικοποιητή σε υλικό, μας δίνει τη δυνατότητα να διεξάγουμε ταχύτατες εξομοιώσεις, σε σχέση με αντίστοιχες υλοποιήσεις σε λογισμικό (π.χ. σε Matlab περιβάλλον). Διαθέτουμε, έτσι, ένα ισχυρό εργαλείο για τη μελέτη της επίδοσης διαφόρων ρεαλιστικών υλοποιήσεων αποκωδικοποιητών. Κατά τη διάρκεια της υλοποίησης, αξιοποιήθηκε αναπτυξιακό σύστημα βασισμένο σε virtex-4 fpga. / LDPC (low-density parity-check) codes are widely applied for error correction, in the development of highly efficient modern digital communication systems, as satellite Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) and IEEE 802.16 (WiMax). LDPC codes are linear block codes, characterized by a sparse parity-check matrix. They are error detection and correction codes. The most typical decoding procedure is the message passing algorithm that implements the iterative exchange of node-generated messages between two types of processing units, called check and variable nodes. Hardware implementation of an LDPC decoder is a fast growing field for contemporary scientific research. This work presents the results of the design, implementation and optimization of a VLSI decoder for LDPC codes. Several iterative decoding algorithms have been developed. At this work we present architectures based on the log Sum-Product (Log-SP) and Min-Sum algorithm. Log-SP is theoretically optimal; however Min-Sum is substantially simpler and reduces the hardware complexity. Two alternative decoding algorithms have been developed, that use these two algorithms for the check-node LLR update, and the philosophy of layered decoding for the exchange of messages. Our study focused on WiMax 801.16e LDPC codes, whose form, based on permuted identity matrices, is suitable for a hardware realization. The contribution of this work lays within the design and implementation of area and decoding throughput efficient architectures, as well a detailed investigation of design space, using decoding algorithm, message exchange scheduling, pipelining and quantization schemes as design parameters. Furthermore, important to mention is, -the development of parametric Matlab scripts, in order to achieve easy and automated structural VHDL code production. The two key parameters are the number of the processing units and the data length. A hardware realization of a LDPC decoder, gives us a simulation tool that is much faster than corresponding software implementations (for example, a matlab implementation). During the implementation procedure, development board based in virtex-4 fpga has been used.

- / -

Στην παρούσα διπλωματική εργασία έγινε υλοποίηση και πειραματική αξιολόγηση μιας μεθοδολογίας η οποία έχει αναπτυχθεί στο Εργαστήριο Ολοκληρωμένων Κυκλωμάτων και αφορά τη βελτιστοποίηση του Πολλαπλασιασμού Πίνακα επί Διάνυσμα (ΠΠΔ) σε μονοπύρηνους και πολυπύρηνους επεξεργαστές. Η μεθοδολογία εκμεταλλεύεται το σύνολο των χαρακτηριστικών της αρχιτεκτονικής που χρησιμοποιείται και συγκεκριμένα (α) την ιεραρχία της μνήμης, (β) το μέγεθος της κρυφής μνήμης, (γ) το βαθμό συσχέτισης κάθε επιπέδου της κρυφής μνήμης, (δ) την καθυστέρηση της μνήμης και (ε) το πλήθος των πυρήνων. Είναι η πρώτη φορά που λαμβάνεται υπόψη ο βαθμός συσχέτισης της μνήμης. Σκοπός της μεθοδολογίας είναι η βελτιστοποίηση με βάση όλες τις παραμέτρους μαζί και όχι καθεμία ξεχωριστά. Για να βελτιωθεί η απόδοση προτείνεται διαφορετικός χρονοπρογραμματισμός ανάλογα με το μέγεθος του πίνακα. Για την πειραματική αξιολόγηση χρησιμοποιήθηκαν οι επεξεργαστές γενικού σκοπού Intel Core 2 Duo E6065 και Τ6600, ο Intel i7-3930K και ο ενσωματωμένος επεξεργαστής ειδικού σκοπού Microblaze από το Virtex-5 FPGA (Xilinx). Τα αποτελέσματα συγκρίνονται με την state-of-the-art βιβλιοθήκη ATLAS (Automatically Tuned Linear Algebra Software) και παρουσιάζουν βελτίωση 30%. Από τα πειραματικά αποτελέσματα είναι φανερό ότι η κύρια μνήμη είναι το bottleneck του προβλήματος. Επίσης, η απόδοση βελτιώνεται όταν αλλάζει το layout του πίνακα τόσο σε μονοπύρηνες όσο σε πολυπύρηνες αρχιτεκτονικές. Όσον αφορά τη μέθοδο του tiling τα πειραματικά αποτελέσματα δείχνουν ότι η μείωση των αστοχιών δεν βελτιώνει πάντα την απόδοση γιατί υπάρχει trade-off ανάμεσα στο μέγεθος του tile και στις εντολές διευθυνσιοδότησης. Επίσης, είναι φανερό ότι στις πολυπύρηνες αρχιτεκτονικές δεν υπάρχει γραμμική σχέση της απόδοσης και του πλήθους των πυρήνων που χρησιμοποιούνται. Αυτό οφείλεται στο περιορισμένο εύρος ζώνης της μνήμης. / The subject of this MSc Thesis is the implementation and the experimental evaluation of a methodology that has been developed at the Laboratory of Integrated Circuits and optimizes the Matrix Vector Multiplication (MVM) in single-core and multi-core processors. The methodology fully exploits the characteristics of the architecture. Specifically, it exploits (a) the hierarchy of the memory, (b) the cache size, (c) the cache associativity, (d) the memory latency and (e) the number of the cores. It is the first time that the cache associativity is taken into account. The methodology optimizes all the parameters together as one problem and not separately. A different scheduling is proposed according to the size of the matrix. The general purpose processors Intel Core 2 Duo E6065, Intel Core 2 Duo T6600 and Intel i7-3930K and the embedded processor Virtex-5 Microblaze have been used. The results have been compared with the state-of-the-art library ATLAS (Automatically Tuned Linear Algebra Software) and the performance is improved by 30%. According to the experimental results, it is obvious that the bottleneck is the memory latency. Moreover, the performance is increased when a new way of saving the matrix in the main memory (data array layout) is used in both single-core and multi-core architectures. As far as the tiling is concerned, the experimental results indicate that the decrease of the misses does not always improve the performance because there is a trade-off between the tile size and the addressing instructions. According to the experimental results, as far as multicore architectures are concerned, there is no linear relation between the performance and the number of the cores, because of the limited memory bandwidth.

Στην παρούσα διδακτορική διατριβή προτείνονται μεθοδολογίες σχεδίασης εφαρμογών σε ενσωματωμένες πλατφόρμες ειδικού σκοπού για την βελτίωση της απόδοσης εφαρμογών που εκτελούνται σε αυτές. Τα θεωρούμενα συστήματα στοχεύουν σε αριθμητικά απαιτητικές εφαρμογές, όπως είναι εφαρμογές Ψηφιακής Επεξεργασίας Σήματος και πολυμέσων. Οι περιγραφές των εφαρμογών γίνεται σε γλώσσα υψηλού επιπέδου γεγονός που διευκολύνει την υλοποίηση των εφαρμογών στις θεωρούμενες επεξεργαστικές πλατφόρμες. Οι μεθοδολογίες έχουν αυτοματοποιηθεί, με την χρήση πρωτότυπων και εμπορικά διαθέσιμων εργαλείων, για την αποτελεσματική και γρήγορη αποτίμηση των λύσεων σχεδίασης και απεικόνισης. Αρχικά, προτείνεται μια μέθοδος για την αποτελεσματική υλοποίηση εφαρμογών Ψηφιακής Επεξεργασίας Σήματος σε ένα σύστημα μικροεπεξεργαστή που περιέχει σαν επιταχυντή κρίσιμων τμημάτων ένα ευέλικτο χειριστή δεδομένων (data-path). Η υπεροχή του προτεινόμενου data-path σε σχέση με υπάρχοντες χειριστές δεδομένων δείχνεται για ένα σύνολο χαρακτηριστικών αριθμητικών υπολογιστικών πυρήνων (kernels). Παρουσιάζεται μια αυτοματοποιημένη μέθοδος σύνθεσης πυρήνων για το χειριστή δεδομένων. Αυτή η διαδικασία σύνθεσης ενσωματώνεται σε ένα γενικό περιβάλλον σχεδίασης εφαρμογών για το θεωρούμενο σύστημα που έχει σαν στόχο την βελτίωση της απόδοσης και την μείωση κατανάλωση ενέργειας. Στην συνέχεια, παρουσιάζεται ένα περιβάλλον λογισμικού που υλοποιεί μια φορμαλισμένη μεθοδολογία για τον διαχωρισμό εφαρμογών Ψηφιακής Επεξεργασίας Σήματος μεταξύ επαναπροσδιοριζόμενων τμημάτων μικτής υφής για πρώτη φορά στην βιβλιογραφία. Κρίσιμα τμήματα επιταχύνονται στο επαναπροσδιοριζόμενο υλικό χονδροειδούς υφής για να ικανοποιηθούν οι χρονικοί περιορισμοί του κώδικα της εφαρμογής που απεικονίζεται στην επαναπροσδιοριζόμενη λογική του συστήματος. Η επαναπροσδιοριζόμενη λογική λεπτής υφής υλοποιείται από ένα ενσωματωμένο Field Programmable Gate Array (FPGA), ενώ η επαναπροσδιοριζόμενη λογική χονδροειδούς υφής από ένα δικό μας αναπτυγμένο χειριστή +δεδομένων υψηλής απόδοσης. Η αποτελεσματικότητα του πρωτότυπου λογισμικού επιβεβαιώνεται χρησιμοποιώντας ρεαλιστικές εφαρμογές. Αναλυτικά πειράματα δείχνουν σημαντικές βελτιώσεις στην απόδοση, ενώ καθορισμένοι χρονικοί περιορισμοί ικανοποιούνται για όλες τις δοκιμασμένες εφαρμογές. Παρουσιάζεται η ενσωμάτωση ενός προτεινόμενου ευέλικτου προτύπου Επαναπροσδιοριζόμενης Αρχιτεκτονικής Πίνακα (ΕΑΠ) χονδροειδούς υφής σε δύο διαφορετικά συστήματα σε ολοκληρωμένα κυκλώματα. Για την αποτελεσματική εκτέλεση υπολογιστικά απαιτητικών τμημάτων στην ΕΑΠ αναπτύχθηκε μια πρωτότυπη αυτοματοποιημένη διαδικασία απεικόνισης, που βασίζεται σε έναν νέο αλγόριθμο διοχέτευσης βρόχου. Η αποτελεσματικότητα της ΕΑΠ και της αντίστοιχης διαδικασίας απεικόνισης διαπιστώνονται με εκτέλεση ρεαλιστικών εφαρμογών. Στο πρώτο σύστημα η ΕΑΠ μαζί με ένα FPGA σχηματίζουν την επαναπροσδιοριζόμενη λογική μιας υβριδικής πλατφόρμας. Στο δεύτερο σύστημα σε ολοκληρωμένο κύκλωμα, η ΕΑΠ συνδέεται άμεσα με έναν μικροεπεξεργαστή γενικού σκοπού ενεργώντας σαν συνεπεξεργαστής για την εκτέλεση κρίσιμων βρόχων. Πρωτότυπα αυτοματοποιημένα περιβάλλοντα σχεδίασης προτείνονται για την αποτελεσματική και εύκολη υλοποίηση ολόκληρων εφαρμογών στα συστήματα. Τέλος, προτείνεται μια πρωτότυπη μεθοδολογία διαχωρισμού υλικού/λογισμικού για την βελτίωση της απόδοσης ρεαλιστικών εφαρμογών σε ένα ενσωματωμένο σύστημα σε ολοκληρωμένο κύκλωμα που αποτελείται από έναν προγραμματιζόμενο μικροεπεξεργαστή και FPGA επαναπροσδιοριζόμενη λογική. Η μεθοδολογία έχει αυτοματοποιηθεί σε μεγάλο βαθμό με την χρήση ακαδημαϊκών και εμπορικών εργαλείων. Το FPGA ενεργεί σαν επιταχυντής κρίσιμων τμημάτων κώδικα βελτιώνοντας την απόδοση των εφαρμογών κοντά σε θεωρητικά μέγιστα όρια επιταχύνσεων. Αναλυτικά πειράματα με διαφορετικού τύπου μικροεπεξεργαστές και FPGA δείχνουν την αποτελεσματικότητα της μεθοδολογίας. / In this Ph.D. dissertation, design methodologies for embedded platforms with the aim of improving the performance of realistic applications executed on them are proposed. The considered system platforms target on arithmetic intensive applications, as in the case of Digital Signal Processing and multimedia applications. The applications are coded in a high-level language, fact that eases the implementation of applications in the considered processing platforms. The methodologies have been automated, with the usage of prototype and commercial tools, for the efficient and rapid evaluation of the design and mapping solutions. Initially, a method is proposed for the effective implementation of Digital Signal Processing applications on a microprocessor system that includes as an accelerator of critical application parts a flexible data-path. The effectiveness of the proposed data-path relative to existing ones is illustrated for a set of characteristic arithmetic intensive kernels. An automated synthesis methodology for kernels is presented. This synthesis method is incorporated on a design flow for the considered system that aims in improving application performance and reducing energy consumption. Afterwards, a software framework that implements a formalized methodology for partitioning Digital Signal Processing and multimedia applications between mixed granularity reconfigurable hardware parts is presented. Critical application parts are accelerated on the coarse-grained reconfigurable hardware for satisfying timing constraints of application code mapped on the reconfigurable logic of the platform. The fine-grained reconfigurable hardware is implemented by an embedded Field Programmable Gate Array (FPGA), whereas the coarse-grained reconfigurable logic by an our-developed high-performance reconfigurable data-path. The efficiency of the prototype software is justified using realistic applications. Analytical experiments illustrate that important performance improvements are achieved, while the targeted timing constraints are satisfied for all the tested applications. The incorporation of a proposed flexible template of a Coarse Grained Reconfigurable Array (CGRA) in two different system on chip is presented. For the efficient execution of computational intensive parts on the CGRA an automated mapping process, that it is based on a software loop pipelining algorithm, is developed. The efficiency of the CGRA and of its respective mapping procedure are realized with the execution of real-life applications. In the first system, the CGRA together with an FPGA form the reconfigurable logic of a hybrid platform. In the second system on chip, the CGRA is directly attached to a general purposed microprocessor acting as a co-processor for the execution of critical loops. Automated design frameworks are proposed for the efficient and straightforward implementation of complete applications on the systems. Finally, a hardware/software partitioning methodology is proposed for the performance improvements of realistic applications in an embedded system on chip that it is composed by a programmable microprocessor and an FPGA reconfigurable hardware. The methodology has been automated in a large extend with the usage of academic and commercial tools. The FPGA acts as an accelerator for critical code segments improving by this way the performance of applications close to maximum theoretical bounds. Extensive experiments with different types of microprocessors and FPGAs show the effectiveness of the methodology.

Τα τελευταία χρόνια είδαν την άνθιση διαδικτυακών εφαρμογών και υπηρεσιών διαμοιρασμού αντικειμένων πολυμέσων. Την τιμητική τους είχαν τα αντικείμενα οπτικοακουστικού περιεχομένου (video), δίνοντας πρωταγωνιστικό ρόλο στην ανάπτυξη συστημάτων διαμοιρασμού βίντεο. Μάλιστα, ανταποκρινόμενα στην δυνατότητα των χρηστών για επιλογή περιεχομένου, που παρείχαν η ραγδαία αύξηση της χρήσης του διαδικτύου και η βελτίωση των υποδομών αυτού, έγιναν ιδιαίτερα δημοφιλή τα συστήματα και οι υπηρεσίες διαμοιρασμού βίντεο κατόπιν ζήτησης Ωστόσο οι αυξημένες απαιτήσεις τους σε κλιμάκωση, προσαρμοστικότητα, απόδοση και ανεκτικότητα σε σφάλματα, κατέστησαν απαραίτητη την υποστήριξή τους από κατανεμημένες ή και παράλληλες αρχιτεκτονικές. Μία αρκετά υποσχόμενη προσέγγιση προς αυτή την κατεύθυνση είναι τα διομότιμα συστήματα καθώς οι ίδιοι οι χρήστες των εφαρμογών διαθέτουν ένα τεράστιο σύνολο από δικτυακούς και υπολογιστικούς πόρους. Στα συστήματα αυτά το περιεχόμενο που κατεβάζουν οι χρήστες διασπάται σε κομμάτια τα οποία ανταλλάσσονται από αυτούς ,με σκοπό την τελική επανασύνδεση και ανάκτηση του συνολικού μεγέθους των δεδομένων. Σκοπός αυτής της διπλωματικής είναι η μελέτη της αξιοποίησης του εύρους ζώνης στα πλαίσια ενός διομότιμου συστήματος διαμοιρασμού βίντεο κατόπιν ζήτησης με πολλαπλά κανάλια. Η παρατήρηση του τρόπου συμπεριφοράς των χρηστών και του συνολικού συστήματος ως προς τον πολύτιμο αυτό δικτυακό πόρο, μπορεί να αποτελέσει την βάση για την ανάπτυξη εφαρμογών με μεγαλύτερη αποδοτικότητα, πιο οικονομικών στην λειτουργία τους, και με βελτιωμένη ευελιξία. / The last year saw the flourishing of Internet applications and services sharing media objects. Their honor were the objects of audiovisual content (video), giving a leading role in the development of video sharing. Indeed, in response to users' ability to select content, provided by the rapid growth of internet usage and to improve the infrastructure of this, became very popular in the systems and services for sharing video on demand However, the increased demands on scalability, flexibility, performance and fault tolerance, made it necessary to support them or from distributed and parallel architectures. A very promising approach in this direction is the diomotima systems and the users themselves applications have a huge amount of network and computing resources. In these systems the content download users cleaved into pieces which are exchanged by them, with the final reconnection and recovery of the total size of data. The aim of this thesis is to study the utilization of bandwidth within a peer sharing system video on demand with multiple channels. The observation of how user behavior and the overall system to this valuable web resource, can provide the basis for developing applications with greater efficiency, more economical to operate, and with improved flexibility.

Το αντικείμενο που πραγματεύεται η παρούσα διδακτορική διατριβή σχετίζεται με την ανάπτυξη βελτιστοποιητικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα γενικού και ειδικού σκοπού. Στόχος είναι η βελτιστοποίηση της εκτέλεσης των εφαρμογών ως προς την ταχύτητα, την επιφάνεια ολοκλήρωσης και την κατανάλωση ισχύος. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών μεταγλώττισης αλλά και από την ανεύρεση βέλτιστων αρχιτεκτονικών. Η αυτοματοποίηση των μεθοδολογιών επιτυγχάνεται με την ανάπτυξη εργαλείων βελτιστοποίησης που υλοποιούν την μεθοδολογία μεταγλώττισης. Τα πειράματα έδειξαν γρήγορο προσδιορισμό βέλτιστων λύσεων και σημαντικές βελτιώσεις στην ταχύτητα, επιφάνεια ολοκλήρωσης και κατανάλωση ισχύος για μια σειρά από εφαρμογές ψηφιακής επεξεργασίας σήματος. / The research material that is presented in this PhD Phesis is related with developement of compilation techniques for reconfigurable systems and application specific integrated circuits. The objective is the optimization of the execution of the applications in terms of speed area and power consumption in these architectures. This is achieved by developing original compiling techniques and efficient architecture instances. Moreover, one of the fundamental objectives of this thesis is the automation of these techniques for fast solution determination. Experiments showed that applications are executed faster while keeping the area and power overhead low. The experiments are based on a set of Digital Signal Processing applications.

Η διαμόρφωση με πολύπλεξη συχνότητας ορθογωνίων φερουσών (Orthogonal Frequency Division Multiplexing - OFDM) είναι μια μέθοδος η οποία εξασφαλίζει άριστη αξιοποίηση του διαθέσιμου εύρους συχνοτήτων, ενώ παράλληλα παρέχει τα πλεονεκτήματα της μετάδοσης μέσω πολλαπλών φερουσών (multicarrier transmission). Το σημαντικότερο χαρακτηριστικό της είναι ότι επιτρέπει τη μετάδοση μέσω επιλεκτικών στη συχνότητα καναλιών χρησιμοποιώντας απλές διαδικασίες ισοστάθμισης. Το χαρακτηριστικό αυτό συνέβαλε στην εδραίωσή της ως μία από τις επικρατέστερες μεθόδους διαμόρφωσης για την υψηλού ρυθμού μετάδοση δεδομένων μέσω ασύρματων μέσων. Το αντικείμενο της εργασίας είναι η μελέτη αλγορίθμων και αρχιτεκτονικών για το συγχρονισμό σε ασύρματους τηλεπικοινωνιακούς δέκτες που στηρίζονται στη διαμόρφωση OFDM. Ο συγχρονισμός είναι μία διαδικασία η οποία αποτελεί ακρογωνιαίο λίθο για οποιοδήποτε τηλεπικοινωνιακό σύστημα. Ιδιαίτερα όμως για δέκτες OFDM, έχει εντοπιστεί ως ένας από τους σημαντικότερους παράγοντες που επηρεάζουν την απόδοση. Το πρόβλημα παρουσιάζει εξαιρετικό ενδιαφέρον, καθώς η φύση της διαμόρφωσης καθιστά απαγορευτική την εφαρμογή πολλών από τις μεθόδους που έχουν αναπτυχθεί για συστήματα μετάδοσης με μονή φέρουσα, ενώ παράλληλα θέτει νέες παραμέτρους στο πρόβλημα. Η μεθοδολογία που ακολουθήθηκε κατά την εκπόνηση της εργασίας περιλάμβανε σε πρώτη φάση τη μελέτη αλγοριθμικών λύσεων που έχουν προταθεί κατά καιρούς για το συγχρονισμό. Το ενδιαφέρον επικεντρώθηκε σε βασικές τεχνικές με ευρεία εφαρμοσιμότητα ενώ ο στόχος της ανάλυσης ήταν να γίνουν κατανοητές με διαισθητικό τρόπο, στοιχειώδεις ιδέες οι οποίες χρησιμοποιούνται κατά κόρον για την επίλυση του προβλήματος του συγχρονισμού. Κατά τη δεύτερη φάση έγινε μια μελέτη γύρω από τις λεπτομέρειες που σχετίζονται με την υλοποίηση ορισμένων από τους αλγορίθμους συγχρονισμού σε επίπεδο αρχιτεκτονικής VLSI. Το ενδιαφέρον επικεντρώθηκε σε μια αρχιτεκτονική μέσω της οποίας μπορεί να επιτευχθεί τυφλός συγχρονισμός για έναν ασύρματο δέκτη OFDM. Κατά την ανάλυση χρησιμοποιήθηκε ως βάση ένα αρκετά γενικό μοντέλο συστήματος OFDM βασικής ζώνης. Για την αξιολόγηση της αρχιτεκτονικής εκτελέστηκε ένα εκτενές σύνολο πειραμάτων, το οποίο είχε ως στόχο τον προσδιορισμό και την ποσοτικοποίηση των επιδόσεων τόσο για τη μονάδα συγχρονισμού, όσο και για το συνολικό τηλεπικοινωνιακό σύστημα. Από τα αποτελέσματα της πειραματικής διαδικασίας προέκυψαν πολύ ενδιαφέροντα συμπεράσματα για την ευαισθησία της τεχνικής OFDM σε σφάλματα συγχρονισμού καθώς επίσης και για την πολυπλοκότητα υλοποίησης της μονάδας συγχρονισμού. / The summary is not available.

Η έρευνα αναφορικά με την εξέλιξη του Παγκόσμιου Ιστού (WWW) κινείται τα τελευταία χρόνια προς πιο ευφυείς και αυτοματοποιημένους τρόπους ανακάλυψης και εξαγωγής της πληροφορίας. Ο Σημαντικός Ιστός (Semantic Web) είναι μία επέκταση του σημερινού Ιστού, όπου στην πληροφορία δίνεται σαφώς προσδιορισμένη σημασία, δίνοντας έτσι τη δυνατότητα στις μηχανές να μπορούν πλέον να επεξεργάζονται καλύτερα και να «κατανοούν» τα δεδομένα, τα οποία μέχρι σήμερα απλώς παρουσιάζουν. Για να λειτουργήσει ο Σημαντικός Ιστός, οι υπολογιστές θα πρέπει να έχουν πρόσβαση σε οργανωμένες συλλογές πληροφοριών, που καλούνται οντολογίες (ontologies). Οι οντολογίες παρέχουν μια μέθοδο αναπαράστασης της γνώσης στο Σημαντικό Ιστό και μπορούν επομένως να αξιοποιηθούν από τα υπολογιστικά συστήματα για τη διεξαγωγή αυτοματοποιημένου συλλογισμού (automated reasoning). Για την περιγραφή και την αναπαράσταση των οντολογιών του Σημαντικού Ιστού σε γλώσσες αναγνώσιμες από τη μηχανή, έχουν προταθεί και βρίσκονται υπό εξέλιξη διάφορες πρωτοβουλίες, με πιο σημαντική τη Γλώσσα Οντολογίας Ιστού (Web Ontology Language – OWL). H γλώσσα αυτή αποτελεί πλέον τη βάση για την αναπαράσταση γνώσης στο Σημαντικό Ιστό, λόγω της προώθησής της από το W3C, και του αυξανόμενου βαθμού υιοθέτησής της στις σχετικές εφαρμογές. Το βασικότερο εργαλείο για την υλοποίηση εφαρμογών που διαχειρίζονται OWL οντολογίες, είναι το OWL API. Το OWL API αποτελείται από προγραμματιστικές βιβλιοθήκες και μεθόδους, οι οποίες παρέχουν μια υψηλού επιπέδου διεπαφή για την πρόσβαση και τον χειρισμό OWL οντολογιών. Το θεωρητικό υπόβαθρο που εγγυάται την εκφραστική και συλλογιστική ισχύ των οντολογιών, παρέχεται από τις Λογικές Περιγραφής (Description Logics). Οι Λογικές Περιγραφής αποτελούν ένα καλώς ορισμένο αποφασίσιμο υποσύνολο της Λογικής Πρώτης Τάξης και καθιστούν δυνατή την αναπαράσταση και ανακάλυψη γνώσης στο Σημαντικό Ιστό. Για την ανακάλυψη άρρητης πληροφορίας ενδείκνυται, επομένως, να αξιοποιηθούν συστήματα βασισμένα σε Λογικές Περιγραφής. Τα συστήματα αυτά ονομάζονται και εργαλεία Συλλογισμού (Reasoners). Χαρακτηριστικά παραδείγματα τέτοιων εργαλείων αποτελούν τα FaCT++ και Pellet. Από τα παραπάνω γίνεται προφανής ο λόγος για τον οποίο, τόσο το OWL API, όσο και τα εργαλεία Συλλογισμού, χρησιμοποιούνται από προτεινόμενα μοντέλα υλοποίησης εφαρμογών του Σημαντικού Ιστού επόμενης γενιάς (WEB 3.0), για την επικοινωνία και την υποβολή «έξυπνων» ερωτημάτων σε βάσεις γνώσης (knowledge bases). Στα μοντέλα αυτά προτείνεται, επίσης, η χρήση κατανεμημένης αρχιτεκτονικής 3-επιπέδων (3-tier distributed architecture), για την υλοποίηση εφαρμογών του Σημαντικού Ιστού. Σκοπός της διπλωματικής αυτής είναι ο σχεδιασμός και η ανάπτυξη μιας διεπαφής Πελάτη – Εξυπηρετητή (Client – Server interface) για την υποστήριξη υπηρεσιών Συλλογισμού (reasoning) σε κατανεμημένες εφαρμογές του Σημαντικού Ιστού. Πιο συγκεκριμένα, η διεπαφή που θα υλοποιήσουμε αποτελείται από δύο μέρη. Το πρώτο παρέχει τα απαραίτητα αρχεία για την εκτέλεση ενός εργαλείου Συλλογισμού σε κάποιο απομακρυσμένο μηχάνημα (Server). Με τον τρόπο αυτό, το συγκεκριμένο μηχάνημα θα παρέχει απομακρυσμένες (remote) υπηρεσίες Συλλογισμού. Το δεύτερο μέρος (Client) περιέχει αρχεία, που δρουν συμπληρωματικά στις βιβλιοθήκες του OWL API, και του δίνουν νέες δυνατότητες. Συγκεκριμένα, δίνουν την δυνατότητα σε μια εφαρμογή, που είναι υλοποιημένη με το OWL API, να χρησιμοποιήσει τις υπηρεσίες που προσφέρονται από κάποιο απομακρυσμένο εργαλείο Συλλογισμού. Συνεπώς, η διεπαφή μας θα δώσει την δυνατότητα υιοθέτησης της χρήσης του OWL API και των εργαλείων Συλλογισμού από κατανεμημένες αρχιτεκτονικές για την υλοποίηση εφαρμογών του Σημαντικού Ιστού. / In the past few years, the research that focus on the development of the World Wide Web (WWW) has moved towards more brilliant and automated ways of discovering and exporting the information. The Semantic Web is an extension of the current Web, that explicitly defines the information, thus providing the machines with the possibility to better process and “comprehend” the data, which until now they simply present. For the Semantic Web to function properly, computers must have access to organized collections of information, that are called ontologies. Ontologies provide a method of representing knowledge in the Semantic Web and, consequently, they can be used by computing systems in order to conduct automated reasoning. In order to describe and represent the ontologies of the Semantic Web in machine-readable language, various initiatives have been proposed and are under development, most important of which is the Web Ontology Language - OWL. This language constitutes the base for representing knowledge in the Semantic Web, due to its promotion from the W3C, and its increasing degree of adoption from relative applications. The main tool for the development of applications that manages OWL ontologies, is the OWL API. The OWL API consists of programming libraries and methods, that provide a higher-level interface for accessing and handling OWL ontologies. The theoretical background that guarantees the expressivity and the reasoning of ontologies, is provided from Description Logics. Description Logics constitute a well defined and decidable subset of First Order Logic and make possible the representation and discovery of knowledge in the Semantic Web. As a consequence, in order to discover “clever” information, we have to develop and use systems that are based in Description Logics. These systems are also called Reasoners. Characteristic examples of such tools are FaCT++ and Pellet. From above, it must be obvious why both the OWL API and the Reasoners are used by proposed models of developing next generation (WEB 3.0) Semantic Web applications, for the communication and the submission of “intelligent” questions in knowledge bases. These models also propose the use of a 3-level distributed architecture (3-tier distributed architecture), for the development of Semantic Web applications. Aim of this diploma thesis is to design and implement a Client-Server interface to support Reasoning in distributed applications of the Semantic Web. Specifically, the interface that we will implement consists of two parts. First part provides the essential files for a Reasoner to run in a remote machine (Server). As a result, this machine will provide remote Reasoning services. Second part (Client) contains files, that act additionally to (enhance) the libraries of the OWL API, and give them new features. More precisely, they provide an application, that is implemented with OWL API, with the possibility of using the services that are offered by a remote Reasoner. Consequently, our interface will make possible the use of the OWL API and the Reasoners from proposed distributed architectures for the development of Semantic Web applications.

Με την ολοένα και αυξανόμενη τάση για ενσωματωμένα (embedded) και φορητά υπολογιστικά συστήματα της σύγχρονης εποχής, έχειδημιουργηθεί ένας ολόκληρος επιστημονικός κλάδος γύρω από τεχνικές βελτιστοποίησης μεταγλωττιστών για ειδικούς πυρήνες λογισμικού που εκτελούνται στα συστήματα αυτά. Κάνοντας χρήση τεχνικών βελτιστοποίησης τα κέρδη είναι πολλαπλά. Καταρχήν οι πυρήνες μπορούν να ολοκληρώσουν το χρόνο που απαιτείται για να ολοκληρωθεί η εκτέλεση τους σε πολύ μικρότερο διάστημα, έχοντας πολύ μικρότερες απαιτήσεις μνήμης. Επίσης μειώνονται οι ανάγκες τους σε επεξεργαστική ισχύ κάτι το οποίο άμεσα οδηγεί στη μείωση κατανάλωσης ενέργειας, στην αύξηση αυτονομίας τους σε περίπτωση που μιλάμε για φορητά συστήματα και στις ανάγκες για ψύξη των συστημάτων αυτών καθώς εκλύονται πολύ μικρότερα ποσά ενέργειας. Έτσι λοιπόν επιτυγχάνονται κέρδη σε πολλούς τομείς (χρόνος εκτέλεσης, ανάγκες μνήμης, αυτονομία, έκλυση θερμότητας) καθιστώντας τον κλάδο των βελτιστοποιήσεων ένα από τους πιο ταχέως αναπτυσσόμενους κλάδους. Εκτός όμως από την σκοπιά της αύξησης επιδόσεων, στην περίπτωση των ενσωματωμένων συστημάτων πραγματικού χρόνου (real time operations) που όταν ξεπερνιούνται οι διορίες χρόνου εκτέλεσης οδηγούνται σε υποβαθμισμένες επιδόσεις (soft real time) και ειδικότερα στην περίπτωση αυτών που οδηγούνται σε αποτυχία όταν ξεπερνιούνται οι διορίες αυτές (hard real time operations), οι τεχνικές αυτές αποτελούν ουσιαστικά μονόδρομο για την υλοποίηση των συστημάτων αυτών σε λογικά επίπεδα κόστους. Η διαδικασία όμως της ανάπτυξης βελτιστοποιήσεων δεν είναι αρκετή καθώς είναι εξίσου σημαντικό το κατά πόσο οι βελτιστοποιήσεις αυτές ταιριάζουν στην εκάστοτε αρχιτεκτονική του συστήματος. Εάν δε ληφθεί υπόψη η αρχιτεκτονική του συστήματος που θα εφαρμοστούν, τότε οι βελτιστοποιήσεις μπορούν να οδηγήσουν σε αντίθετα αποτελέσματα υποβαθμίζοντας την απόδοση του συστήματος. Στην παρούσα διπλωματική εργασία βελτιστοποιείται η διαδικασία πολλαπλασιασμού διανύσματος με πίνακα toeplitz. Κατά την εκπόνηση της αναπτύχθηκε πληθώρα χρονοπρογραμματισμών που στοχεύουν στην βελτιστοποίηση της διαδικασίας αυτής. Μετά από μια εις βάθους μελέτη της ιεραρχίας μνήμης και των τεχνικών βελτιστοποίησης που προσφέρονται για αποδοτικότερη εκμετάλλευσή της, αλλά και των κυριότερων τεχνικών βελτιστοποίησης μεταγλωττιστών, παρουσιάζονται οι κυριότεροι χρονοπρογραμματισμοί, από όσους αναπτύχθηκαν, με τον κάθε ένα να προσφέρει κέρδος σε διαφορετικές αρχιτεκτονικές συστημάτων. Κατά αυτό τον τρόπο αναπτύσσεται ένα εργαλείο που δέχεται σαν είσοδο την αρχιτεκτονική του συστήματος πάνω στο οποίο πρόκειται να γίνει βελτιστοποίηση του εν λόγω πυρήνα, αποκλείονται αρχικά οι χρονοπρογραμματισμοί που δεν είναι κατάλληλοι για την συγκεκριμένη αρχιτεκτονική, ενώ για τους υποψήφιους πιο αποδοτικούς γίνεται εξερεύνηση ούτως ώστε να επιλεγεί ο αποδοτικότερος. / --

Σε αυτή την εργασία μελετάμε τους αλγορίθμους που χρησιμοποιούνται στην αποκωδικοποίηση των LDPC, με έμφαση στους κώδικες του προτύπου 802.11n. Αντιμετωπίζουμε τις δυσκολίες που αντιμετωπίζουν στην υλοποίηση στο υλικό, κυρίως στην εκτέλεση αριθμητικών πράξεων, και προτείνουμε πρακτικές λύσεις. Χρησιμοποιώντας τα αποτελέσματα εκτενών εξομοιώσεων, καταλήγουμε στις βέλτιστες παραμέτρους που θα έχουν οι προτεινόμενες υλοποιήσεις. / In this thesis, we study the LDPC decoding algorithms, with emphasis on the 802.11n standard codes. We tackle the hardware implementation difficulties, especially those related to arithmetic computations, and propose practical solutions. Leveraging the results of extensive simulations, we find the optimal parameters of the proposed implementations.