Les systèmes prévisionnels reposent généralemnt sur des entrepôts de données pour le stockage et sur les outils OLAP pour la visualisation. Des données prédictives agrégées pourraient être modifiées. Par conséquent, la problématique derecherche peut être décrite comme la propagation d'une modification faite sur un agrégat à travers des hiérachies et des dimensions dans un environnement d'entrepôt de données. Il existe un grand nombre de travaux de recherche sur les problèmes de maintenance de vues. Cependant, à notre connaissance, l'impact de la mise à jour interactive d'un agrégat sur les données de base n'a pas été exploré. Cette thèse CIFRE est soutenue par l'ANRT et l'entreprise Anticipeo. L'application Anticipeo est un système prévisionnel de ventes, qui prédit des ventes. Elle était précise avec des résultats de la prédiction, mais le temps de réponse était un problème. Cette thèse comporte deux parties. La première partie est d'identifier la provenance de la latence. Nous avons proposé une méthodologie s'appuyant sur différentes approches et techniques pour améliorer les performances d'une application. Cependant, la propagation d'une modification effectuée sur une agrégat dans un entrpôt de données ne pouvait pas être résolue par ces biais techniques. La deuxième partie du travail consiste en la proposition d'un nouvel algorithme (PAM - Propagation de modification basée sur une agrégat) avec une version étendue (PAM II) pour cette situation. Les algorithmes identifient et mettent àjour les ensembles exactes de données sources et d'aurtes agrégats influencés par la modification d'agrégat. La version optimisées PAM II réalise une meilleure performance par rapport à PAM quand l'utilisation d'une sémantique supplémentaire (par exemple, les dépendances) est possible. Les expériences sur des données réelles d'Anticipeo ont montré que l'algorithme PAM et son extension apportent de meilleures performances dans la propagation des mises à jour. / Forecasting systems are usually based on data warehouses for data strorage, and OLAP tools for historical and predictive data visualization. Aggregated predictive data could be modified. Hence, the research issue can be described as the propagation of an aggregate-based modification in hirarchies and dimensions in a data warehouse enironment. Ther exists a great number of research works on related view maintenance problems. However, to our knowledge, the impact of interactive aggregate modifications on raw data was not investigated. This CIFRE thesis is supported by ANRT and the company Anticipeo. The application of Anticipeo is a sales forecasting system that predicts future sales in order to draw appropriate business strategy in advance. By the beginning of the thesis, the customers of Anticipeo were satisfied the precision of the prediction results, but not with the response time. The work of this thesis can be generalized into two parts. The first part consists in au audit on the existing application. We proposed a methodology relying on different technical solutions. It concerns the propagation of an aggregate-based modification in a data warehouse. the second part of our work consists in the proposition of a newx allgorithms (PAM - Propagation of Aggregated-baseed Modification) with an extended version (PAM II) to efficiently propagate in aggregate-based modification. The algorithms identify and update the exact sets of source data anf other aggregated impacted by the aggregated modification. The optimized PAM II version archieves better performance compared to PAM when the use of additional semantics (e.g. dependencies) is possible. The experiments on real data of Anticipeo proved that the PAM algorithm and its extension bring better perfiormance when a backward propagation.

This PhD dissertation proposes innovative methodologies to support the designing and the mapping process of embedded systems. Due to the increasing requirements, embedded systems have become quite complex, as they consist of several partially dependent heterogeneous components. Systematic Design Space Exploration (DSE) methodologies are required to support the near-optimal design of embedded systems within the available short time-to-market. In this target domain, the existing DSE approaches either require too much exploration time to find near-optimal designs due to the high number of parameters and the correlations between the parameters of the target domain, or they end up with a less efficient trade-off result in order to find a design within acceptable time. In this dissertation we present an alternative DSE methodology, which is based on systematic creation of scalable and near-optimal DSE frameworks. The frameworks describe all the available options of the exploration space in a finite set of classes. A set of principles is presented which is used in the reusable DSE methodology to create a scalable and near-optimal framework and to efficiently use it to derive scalable and near-optimal design solutions within a Pareto trade-off space. The DSE reusable methodology is applied to several stages of the embedded system design flow to derive scalable and near-optimal methodologies. The first part of the dissertation is dedicated to the development of mapping methodologies for storing large embedded system data arrays in the lower layers of the on-chip background data memory hierarchy, and the second part to the DSE methodologies for the processing part of SW/HW architectures in embedded systems including the foreground memory systems. Existing mapping approaches for the background memory part are either enumerative, symbolic/polyhedral and worst case (heuristics) approximations. The enumerative approaches require too much exploration time, the worst case approximation lead to overestimation of the storage requirements, whereas the symbolic/polytope approaches are scalable and near-optimal for solid and regular iteration spaces. By applying the new reusable DSE methodology, we have developed an intra-signal in-place optimization methodology which is scalable and near-optimal for highly irregular access schemes. Scalable and near-optimal solutions for the different cases of the proposed methodology have been developed for the cases of non-overlapping and overlapping store and load access schemes. To support the proposed methodology, a new representation of the array access schemes, which is appropriate to express the irregular shapes in a scalable and near-optimal way, is presented. A general pattern formulation has been proposed which describes the access scheme in a compact and repetitive way. Pattern operations were developed to combine the patterns in a scalable and near-optimal way under all the potential pattern combination cases, which may exist in the application under study. In the processing oriented part of the dissertation, a DSE methodology is developed for mapping instance of a predefined target application domain onto a partially fixed architecture platform template, which consists of one processor core and several custom hardware accelerators. The DSE methodology consists of uni-directional steps, which are implemented through parametric templates and are applied without costly design iterations. The proposed DSE methodology explores the space by instantiating the steps and propagating design constraints which prune design options following the steps ordering. The result is a final Pareto trade-off curve with the most relevant near-optimal designs. As the scheduling and the assignment are the major tasks of both the foreground and the datapath, near-optimal and scalable techniques are required to support the parametric templates of the proposed DSE methodology. A framework which describes the scheduling and assignment of the scalars into the registers and the scheduling and assignment of the operation into the function units of the data path is developed. Based on the framework, a systematic methodology to arrive at parametric templates for scheduling and assignment techniques which satisfy the target domain constraints is developed. In this way, a scalable parametric template for scheduling and assignment tasks is created, which guarantees near-optimality for the domain under study. The developed template can be used in the Foreground Memory Management step and Data-path mapping step of the overall design flow. For the DSE of the domain under study, near-optimal results are hence achieved through a truly scalable technique. / Η παρούσα διδακτορική διατριβή προτείνει καινοτόμες μεθοδολογίες για τον σχεδιασμό και τη διαδικασία απεικόνισης σε ενσωματωμένα συστημάτα. Λόγω των αυξανόμενων απαιτήσεων, τα ενσωματωμένα συστήματα είναι αρκετά περίπλοκα, καθώς αποτελούνται από πολλά και εν μέρει εξαρτώμενα ετερογενή στοιχεία. Συστηματικές μεθοδολογίες για την εξερεύνηση του χώρου λύσεων (Design Space Exploration – DSE) απαιτούνται σχεδόν βέλτιστες σχεδιάσεις ενσωματωμένων συστημάτων εντός του διαθέσιμου χρονου. Οι υπάρχουσες DSE μεθοδολογίες απαιτούν είτε πάρα πολύ χρόνο εξερεύνησης για να βρουν τους σχεδόν βέλτιστους σχεδιασμούς, λόγω του μεγάλου αριθμού των παραμέτρων και τις συσχετίσεις μεταξύ των παραμέτρων, ή καταλήγουν με ένα λιγότερο βέλτιστο σχέδιο, προκειμένου να βρειθεί ένας σχεδιασμός εντός του διαθέσιμου χρόνου. Στην παρούσα διδακτορική διατριβή παρουσιάζουμε μια εναλλακτική DSE μεθοδολογία, η οποία βασίζεται στη συστηματική δημιουργία επεκτάσιμων και σχεδόν βέλτιστων DSE πλαισίων. Τα πλαίσια περιγράφουν όλες τις διαθέσιμες επιλογές στο χώρο εξερεύνησης με ένα πεπερασμένο σύνολο κατηγοριών. Ένα σύνολο αρχών χρησιμοποιείται στην επαναχρησιμοποιήούμενη DSE μεθοδολογία για να δημιουργήσει ένα επεκτάσιμο και σχεδόν βέλτιστο DSE πλαίσιο και να χρησιμοποιήθεί αποτελεσματικά για να δημιουργήσει επεκτάσιμες και σχεδόν βέλτιστες σχεδιαστικές λύσεις σε ένα Pareto Trade-off χώρο λύσεων. Η DSE μεθοδολογία εφαρμόζεται διάφορα στάδια της σχεδιαστικής ροής για ενσωματωμένα συστήματα και να δημιουργήσει επεκτάσιμες και σχεδόν βέλτιστες μεθοδολογίες. Το πρώτο μέρος της διατριβής είναι αφιερωμένο στην ανάπτυξη των μεθόδων απεικόνισης για την αποθήκευση μεγάλων πινάκων που χρησιμοποιούνται στα ενσωματωμένα συστήματα και αποθηκεύονται στα χαμηλότερα στρώματα της on-chip Background ιεραρχία μνήμης. Το δεύτερο μέρος είναι αφιερωμένο σε DSE μεθοδολογίες για το τμήμα επεξεργασίας σε αρχιτεκτονικές λογισμικού/υλικού σε ενσωματωμένα συστήματα, συμπεριλαμβανομένων των συστημάτων της προσκήνιας (foreground) μνήμης. Υπάρχουσες μεθοδολογίες απεικόνισης για την Background μνήμης είτε εξονυχιστικές, συμβολικές/πολυεδρικές και προσεγγίσεις με βάση τη χειρότερη περίπτωση. Οι εξονυχιστικές απαιτούν πάρα πολύ μεγάλο χρόνο εξερεύνησης, οι προσεγγίσεις οδηγούν σε υπερεκτίμηση των απαιτήσεων αποθήκευσης, ενώ οι συμβολικές είναι επεκτάσιμη και σχεδόν βέλτιστές μονο για τακτικούς χώρους επαναλήψεων. Με την εφαρμογή της προτεινόμενης DSE μεθοδολογίας αναπτύχθηκε μια επεκτάσιμη και σχεδόν βέλτιστη μεθοδολγοία για την εύρεση του αποθηκευτικού μεγέθους για τα δεδομένα ενός πίνακα για άτακτους και για τακτικούς χώρους επαναλήψεων. Προτάθηκε μια νέα αναπαράσταση των προσπελάσεων στη μνήμη, η οποία εκφράζει τα ακανόνιστα σχήματα στο χώρο επεναλήψεων με επακτάσιμο και σχεδόν βέλτιστο τρόπο. Στο δεύτερο τμήμα της διατριβής, μια DSE μεθοδολογία αναπτύχθηκε για το σχεδιασμό ενός προκαθορισμένου τομέα από εφαρμογές σε μια μερικώς αποφασισμένη αρχιτεκτονική πλατφόρμα, η οποία αποτελείται από ένα πυρήνα επεξεργαστή και αρκετούς συνεπεξεργαστές. Η DSE μεθοδολογία αποτελείται από μονής κατεύθυνσης βήματα, τα οποία υλοποιούνται μέσω παραμετρικών πλαισίων και εφαρμόζονται αποφέυγοντας τις δαπανηρές επαναλήψεις κατά τον σχεδιασμό. Η προτεινόμενη DSE μεθοδολογία εξερευνά το χώρο βρίσκοντας στιγμιότυπα για καθε βήμα και διαδίδονατς τις αποφάσεις μεταξύ βημάτων. Με αυτό το τρόπο κλαδεύουν τις επιλογές σχεδιασμού στα επόμενα βήματα. Το αποτέλεσμα είναι μια Pareto καμπύλη. Ένα DSE πλαίσιο προτάθηκε που περιγράφει τις τεχνικές χρονοπρογραμματισμού και ανάθεσης πόρων των καταχωρητών και των μονάδων εκτέλεσης του συστήματος. Προτάθηκε μια μεθοδολογία για να δημιουργεί σχεδόν βέλτιστα και επεκτάσιμα παραμετρικά πρότυπα για τον χρονοπρογραμματισμό και την ανάθεση πόρων που ικανοποιεί τους περιορισμούς ενός τομέα εφαρμογών.