Study and implementation of wavelet-based video coding for dynamic transition environments

Abstract

From action games to ultra-high-definition movies and from music playback to augmented reality, heterogenous multimedia completely dominate our mobiles. At the same time, the computing resources become more and more distributed, from the multiple cores of a processor, to the on-line – cloud – computing and storage services. Applications exhibit more and more dynamism with regards to their resource requirements. Consequently, devices should be able to tolerate a wide variety of execution conditions and system or transition resource availability, all of which have the potential to vary unpredictably at run-time. Scalable, wavelet-based applications can form a large piece of the solution to this puzzle by enabling maximum application quality, scaled towards the encountered execution conditions. Clearly, this will also lead to dynamically and unpredictably varying complexity demands on the executing platform. Due to the low power requirements of embedded systems related to the limited battery lifetime, it will no longer be acceptable to cope with these complexity variations using worst-case mapping choices, as these will lead to a heavily suboptimal use of the available resources.This thesis demonstrates an approach to avoid such a worst-case mapping for wavelet-based applications, by switching at run-time to an execution order adapted to the encountered execution conditions. In order to efficiently exploit this switching principle at run-time, the middleware should be in possession of systematic mapping guidelines expressing the knowledge about which execution order offers the lowest miss-rate and which gains can be obtained by switching to it. These mapping guidelines are derived by formalizing the miss-rate behavior of the Wavelet Transform in function of temporal locality. Moreover, it illustrates the impact of the inherent dynamics within an application, in the process of the exploration of the optimal execution order and the exploitation of the memory data mapping in the platform memory hierarchy. In data-dependent applications the memory accesses are not predefined, but depend on the input values. Consequently, it is not only the unpredictable resource availability, but also the input data characteristics that determine the decisions for the optimal execution schedule in the context of minimum power consumption in the memory.

Από τα παιχνίδια δράσης έως τις ταινίες υπερ-υψηλής ευκρίνειας και από την αναπαραγωγή μουσικής έως την επαυξημένη πραγματικότητα, ετερογενή πολυμέσα κυριαρχούν απόλυτα στα κινητά μας. Ταυτόχρονα, οι υπολογιστικοί πόροι διανέμονται ολοένα και περισσότερο, από τους πολλαπλούς πυρήνες ενός επεξεργαστή, έως τις υπηρεσίες on-line - cloud computing και αποθήκευσης. Οι εφαρμογές παρουσιάζουν όλο και περισσότερο δυναμισμό όσον αφορά τις ανάγκες τους σε πόρους. Συνεπώς, οι συσκευές θα πρέπει να είναι σε θέση να ανέχονται μια ευρεία ποικιλία συνθηκών εκτέλεσης και διαθεσιμότητας των πόρων τους ή του μέσου μετάδοσης, τα οποία όλα έχουν τη δυνατότητα να μεταβάλλονται απρόβλεπτα κατά το χρόνο εκτέλεσης. Οι κλιμακούμενες (scalable) εφαρμογές που βασίζονται σε wavelets μπορούν να αποτελέσουν ένα μεγάλο κομμάτι της λύσης σε αυτό το παζλ, επιτρέποντας τη μέγιστη ποιότητα εφαρμογής, κλιμακούμενη προς τις συντελούμενες συνθήκες εκτέλεσης. Είναι σαφές ότι αυτό θα οδηγήσει επίσης σε δυναμικές και απρόβλεπτα μεταβαλλόμενες απαιτήσεις πολυπλοκότητας στην πλατφόρμα εκτέλεσης. Λόγω των χαμηλών απαιτήσεων ρεύματος των ενσωματωμένων συστημάτων που σχετίζονται με την περιορισμένη διάρκεια ζωής της μπαταρίας, δεν θα είναι πλέον αποδεκτό να αντιμετωπίζουμε αυτές τις παραλλαγές πολυπλοκότητας χρησιμοποιώντας επιλογές χαρτογράφησης δεδομένων χειρότερης περίπτωσης (worst case mapping), καθώς αυτές θα οδηγήσουν σε πολύ υποβέλτιστη χρήση των διαθέσιμων πόρων. Αυτή η εργασία επιδεικνύει μια προσέγγιση για την αποφυγή της χαρτογράφησης χειρότερης περίπτωσης για εφαρμογές βασισμένες σε wavelets, εναλλάσοντας κατά το χρόνο εκτέλεσης τη σειρά εκτέλεσης του αλγορίθμου, προσαρμοζόμενη στις συντελούμενες συνθήκες εκτέλεσης. Για την αποτελεσματική εκμετάλλευση αυτής της αρχής εναλλαγής κατά τον χρόνο εκτέλεσης, το middleware θα πρέπει να διαθέτει συστηματικές κατευθυντήριες γραμμές χαρτογράφησης που εκφράζουν τη γνώση σχετικά με το ποια σειρά εκτέλεσης προσφέρει το χαμηλότερο ποσοστό απωλειών χρήσης της τοπικής μνήμης (cache misse-rate) και ποια κέρδη μπορούν να επιτευχθούν με τη μετάβαση στην εν λόγω σειρά εκτέλεσης. Αυτές οι κατευθύνσεις χαρτογράφησης προκύπτουν από την τυποποίηση της συμπεριφοράς του miss-rate του Wavelet Transform σε συνάρτηση με τη χρονική τοπικότητα της χρήσης των δεδομένων. Επιπλέον, απεικονίζει την επίδραση της εγγενούς δυναμικής μέσα σε μια εφαρμογή, στη διερεύνηση της βέλτιστης σειράς εκτέλεσης του αλγορίθμου και στην εκμετάλλευση της χαρτογράφησης δεδομένων στην ιεραρχία της μνήμης της πλατφόρμας. Στις εφαρμογές που εξαρτώνται από δεδομένα, οι προσπελάσεις στη μνήμη δεν είναι προκαθορισμένες, αλλά εξαρτώνται από τις τιμές εισόδου. Συνεπώς, δεν είναι μόνο η απρόβλεπτη διαθεσιμότητα πόρων, αλλά και τα χαρακτηριστικά των δεδομένων εισόδου που καθορίζουν τις αποφάσεις επιλογής της βέλτιστης σειράς εκτέλεσης του αλγορίθμου στο πλαίσιο της ελάχιστης κατανάλωσης ενέργειας στη μνήμη.