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

Made available in DSpace on 2015-04-11T14:02:53Z (GMT). No. of bitstreams: 1 Mauricio Tia Ni Gong Lin.pdf: 636193 bytes, checksum: f576d0b7751120d8c4eaafb2517b1e22 (MD5) Previous issue date: 2006-02-10 / The growth of Linux operating system has taken it to become a worthy competitor to commercial software such as Microsoft s Windows and Sun s Solaris. Although the development and the improvement of several Linux s features, the problem related to Linux out of memory and the current mechanism used to solve it, named as OOM Killer, has brought a long discussion at Linux kernel community. The lack of scientific works related to OOM Killer process selection algorithm motivates this dissertation to propose a mechanism for identifying and classifying memory consumption patterns of Linux applications. Such mechanism is based on a neural network technique known as Self Organizing Maps. The development of a tool based on Self Organizing Maps presented the possibility of applying such approach for memory consumption patterns classification related to Linux applications use cases. / A evolução do sistema operacional Linux possibilitou que o mesmo se tornasse o principal concorrente dos sistemas operacionais do mercado como o Windows da Microsoft e Solaris da Sun. Apesar de diversas funcionalidades e melhorias desenvolvidas no Linux, o problema relacionado à falta de memória e o mecanismo existente de solucioná-lo, chamado de OOM Killer, ainda é motivo de longas discussões na comunidade do kernel Linux. A carência de pesquisas científicas relacionada ao algoritmo de seleção de processos do OOM Killer leva esta dissertação a propor um mecanismo de identificação e classificação de padrões de consumo de memória no Linux baseada no modelo de rede neural auto-organizável. A ferramenta desenvolvida nesta dissertação mostra a possibilidade de utilizar Mapas Auto-Organizáveis para classificar e identificar os padrões de consumo de memória de determinadas aplicações inseridas em contextos de casos de uso.

This master's thesis main aim is to design minimal Bluetooth stack for embedded applications running on an education platform FITkit. This paper contains a theoretical foundation for that work and implementation description. The main section includes Bluetooth protocol stack design and main opportunities which such a design raises.

Le Calcul Haute Performance, regroupant l’ensemble des acteurs responsables de l’amélioration des performances de calcul des applications scientifiques sur supercalculateurs, s’est donné pour objectif d’atteindre des performances exaflopiques. Cette course à la performance se caractérise aujourd’hui par la fabrication de machines hétérogènes dans lesquelles chaque composant est spécialisé. Parmi ces composants, les mémoires du système se spécialisent, et la tendance va vers une architecture composée de plusieurs mémoires aux caractéristiques complémentaires. La question se pose alors de l’utilisation de ces nouvelles machines dont la performance pratique dépend du placement des données de l’application sur les différentes mémoires. Dans cette thèse, nous avons développé une formulation du problème d’allocation de donnée sur une Architecture à Mémoires Hétérogènes. Dans cette formulation, nous avons fait apparaître le bénéfice que pourrait apporter une analyse temporelle du problème, parce que de nombreux travaux reposaient uniquement sur une approche spatiale. À partir de cette formulation, nous avons développé un outil de profilage hors ligne pour approximer les coefficients de la fonction objective afin de résoudre le problème d’allocation et d’optimiser l’allocation des données sur une architecture composée deux de mémoires principales aux caractéristiques complémentaires. Afin de réduire la quantité de modifications nécessaires pour prendre en compte la stratégie d’allocation recommandée par notre boîte à outils, nous avons développé un outil capable de rediriger automatiquement les allocations de données à partir d’un minimum d’instrumentation dans le code source. Les gains de performances obtenus sur des mini-applications représentatives des applications scientifiques codées par la communauté permet d’affirmer qu’une allocation intelligente des données est nécessaire pour bénéficier pleinement de ressources mémoires hétérogènes. Sur certaines tailles de problèmes, le gain entre un placement naïf est une allocation instruite peut atteindre un facteur ×3.75. / High Performance Computing, which brings together all the players responsible for improving the computing performance of scientific applications on supercomputers, aims to achieve exaflopic performance. This race for performance is today characterized by the manufacture of heterogeneous machines in which each component is specialized. Among these components, system memories specialize too, and the trend is towards an architecture composed of several memories with complementary characteristics. The question arises then of these new machines use whose practical performance depends on the application data placement on the different memories. Compromising code update against performance is challenging. In this thesis, we have developed a data allocation on Heterogeneous Memory Architecture problem formulation. In this formulation, we have shown the benefit of a temporal analysis of the problem, because many studies were based solely on a spatial approach this result highlight their weakness. From this formulation, we developed an offline profiling tool to approximate the coefficients of the objective function in order to solve the allocation problem and optimize the allocation of data on a composite architecture composed of two main memories with complementary characteristics. In order to reduce the amount of code changes needed to execute an application according to our toolbox recommended allocation strategy, we have developed a tool that can automatically redirect data allocations from a minimum source code instrumentation. The performance gains obtained on mini-applications representative of the scientific applications coded by the community make it possible to assert that intelligent data allocation is necessary to fully benefit from heterogeneous memory resources. On some problem sizes, the gain between a naive data placement strategy, and an educated data allocation one, can reach up to ×3.75 speedup.

Modern network traffic processing became a challenging task as there are increasing demands on network security devices. Packet-level processing is not sufficient for advanced network traffic analysis and it is necessary to design processing over entire network flows. Stateful processing in software does not offer enough performance for high-speed networks over 10 Gbps and therefore acceleration in hardware should be utilized. Currently there exists no universal platform for stateful processing in hardware and this task has to be implemented individually. Utilization of such platform significantly speed-up development of stateful network applications. This master thesis analyzes all aspects of stateful network processing platform design. Component based architecture increases platform flexibility and ability to optimize for chosen network applications.

The thesis deals with optimization of network flow monitoring. Flow-based network traffic processing, that is, processing packets based on some state information associated to the flows which the packets belong to, is a key enabler for a variety of network services and applications. The number of simultaneous flows increases with the growing number of new services and applications. It has become a challenge to keep a state per each flow in a network device processing high speed traffic. A flow table, a structure with flow states, must be stored in a memory hierarchy. The memory closest to the processing is known as a flow cache. Flow cache management plays an important role in terms of its effective utilization, which affects the performance of the whole system. This thesis focuses on an automated design of cache replacement policy optimized to a deployment on particular networks. A genetic algorithm is proposed to automate this process. The genetic algorithm generates and evaluates evolved replacement policies by a simulation on obtained traffic traces. The proposed algorithm is evaluated by designing replacement policies for two variations of the cache management problem. The first variation is an evolution of the replacement policy with an overall low number of state evictions from the flow cache. The second variation represents an evolution of the replacement policy with a low number of evictions belonging to large flows only. Optimized replacement policies for both variations are found while experimenting with various encoding of the replacement policy and genetic operators. The newly evolved replacement policies achieve better results than other tested policies. The evolved replacement policy lowers the overall amount of evictions by ten percent in comparison with the best compared policy. The evolved replacement policy focusing on large flows lowers the amount of their evictions two times. Moreover, no eviction occurs for most of the large flows (over 90%). The evolved replacement policy offers better resilience against flooding the flow cache with large amount of short flows which are typical side effects of scanning or distributed denial of service activities. An extension of the replacement policy is also proposed. The extension complements the replacement policy with an additional information extracted from packet headers. The results show further decrease in the number of evictions when the extension is used.

Computer systems now run drastically different workloads than they did two decades ago. The enormous advances in hardware power, such as processor speed, memory and storage capacity, and network bandwidth, enable them to run new kinds as well as a large number of applications simultaneously. Software technologies, such as garbage collection and multi-threading, also reshape applications and their behaviors, introducing more challenges to system resource management. However, existing general-purpose operating systems do not provide adequate support for these modern applications. These operating systems were designed over two decades ago, when garbage-collected applications were not prevalent and users interacted with systems using consoles and command lines, rather than graphical user interfaces. As a result, they fail to allow necessary coordinations among resource management components to ensure consistent performance guarantees. For example, garbage-collected applications cannot adjust themselves to maintain high throughput under dynamic memory pressure, simply because existing virtual memory managers do not collect and expose enough information to them. Furthermore, despite the increasing demand of supporting co-existing interactive applications in desktop environment, resource managers (especially memory and disk I/O) mostly focus on optimizing throughput. They each work independently, ignoring the response time requirements that the CPU scheduler attempts to satisfy. Consequently, pressure on any of these resources can significantly degrade application responsiveness. In order to deliver robust performance to these modern applications, an operating system has to coordinate its resource managers (e.g., CPU, memory, and disk I/O), as well as cooperate with resource managers in the user space, such as the garbage collector and the thread manger. To support garbage-collected applications, we present CRAMM, a system that enables them to predict an appropriate heap size using information supplied by the underlying operating system, allowing them to maintain high throughput in the face of changing memory pressure. To support highly interactive workloads, we present Redline, a system that manages CPU, memory, and disk I/O in an integrated manner. It uses lightweight specifications to drive CPU scheduling and to coordinate memory and disk I/O management to serve the needs of interactive applications. Such coordination enables it to maintain responsiveness in the face of extreme resource contention, without sacrificing resource utilization. We also show that Redline can be used to support response time sensitive multi-threaded server applications. Our experiences and extensive experiments show that we can coordinate resource managers, both inside and outside the operating system, efficiently without destroying the modularity of the existing system. Such coordination prevents resource managers from working at cross purposes, and dramatically improve the performance of applications when facing heavy resource contention, sometimes by orders of magnitude.

Dans le but d’optimiser la représentation en mémoire des enregistrements Scheme dans le compilateur Gambit, nous avons introduit dans celui-ci un système d’annotations de type et des vecteurs contenant une représentation abrégée des enregistrements. Ces derniers omettent la référence vers le descripteur de type et l’entête habituellement présents sur chaque enregistrement et utilisent plutôt un arbre de typage couvrant toute la mémoire pour retrouver le vecteur contenant une référence. L’implémentation de ces nouvelles fonctionnalités se fait par le biais de changements au runtime de Gambit. Nous introduisons de nouvelles primitives au langage et modifions l’architecture existante pour gérer correctement les nouveaux types de données. On doit modifier le garbage collector pour prendre en compte des enregistrements contenants des valeurs hétérogènes à alignements irréguliers, et l’existence de références contenues dans d’autres objets. La gestion de l’arbre de typage doit aussi être faite automatiquement. Nous conduisons ensuite une série de tests de performance visant à déterminer si des gains sont possibles avec ces nouvelles primitives. On constate une amélioration majeure de performance au niveau de l’allocation et du comportement du gc pour les enregistrements typés de grande taille et des vecteurs d’enregistrements typés ou non. De légers surcoûts sont toutefois encourus lors des accès aux champs et, dans le cas des vecteurs d’enregistrements, au descripteur de type. / In order to optimize the in memory representation of Scheme records in the Gambit compiler, we introduce a type annotation system on record fields. We also introduce flat vector of records containing an abbreviated representation of those records. These vectors omit the header and reference to the type descriptor on contained records and use a type tree spanning the whole memory to recover the type as needed from an internal pointer. The implementation of the new functionnalities is done through changes in the Gambit runtime. We add new primitives to the language and modify the existing architecture to correctly handle the new data types in a way transparent that is transparent to the user. To do so, we modify the garbage collector to account to account for the existance of internal references and of heterogenous records whose fields may not be alligned to a word and need not be boxed. We also have to automatically and systematically update hte type tree to reflect the live vectors. To asses our implementation’s performance, we run a serie of benchmarks. We measure significant gains on allocation time and space with both typed records and contained records. We also measure a minor overhead in access costs on typed fields and major loss on accesses to the type descriptor of contained records.

No contexto da gerência de memória em sistemas operacionais, vários grupos de pesquisa desenvolvem trabalhos na área de algoritmos para gerência de memória virtual e alguns algoritmos para substituição de páginas têm sido propostos na literatura recente. No entanto, essas propostas não chegaram a um algoritmo que resolva satisfatoriamente o problema de desempenho na gerência de memória. Ainda não existe um consenso entre os pesquisadores de como essa questão deve ser tratada de maneira eficiente, e as propostas de algoritmos desenvolvidas possuem grande sobrecarga devido à sua complexidade. O objetivo deste trabalho é propor uma forma eficiente de gerenciar a memória com a composição de técnicas de busca, posicionamento e substituição de páginas. A hipótese aqui adotada é que para tratar o problema da gerência da memória é melhor consumir recursos computacionais determinando quais páginas deveriam estar na memória em um determinado instante de tempo do que gastar recursos determinando qual página será retirada da memória. A tese apresenta uma reanálise dos principais trabalhos que têm como objetivo o desempenho da gerência de memória, tornando possível retirar conclusões e ideias sobre quais fatores influenciam de maneira positiva com relação ao desempenho do sistema. A partir deste estudo, é determinado o conceito de qualidade do conteúdo da memória e criada uma métrica para medi-la. Aplicando tal conceito, formula-se um método sistêmico de construção de algoritmos de gerência de memória. Realiza-se uma aplicação desse método, criando-se então, os algoritmos RR+ng e RRlock+ng. A métrica é aplicada em simulações na fase final do método, mostrando-se adequada para realizar as análises. Os resultados obtidos mostram que a hipótese tratar o problema da gerência da memória, consumindo recursos computacionais determinando quais páginas devem estar na memória ao invés de quais devem deixá-la mostrou-se válida e parece promissora. / When it comes to memory management in operating systems, many research groups have been developing works in the memory management algorithms area and some page replacement algorithms have been proposed in the recent literature. Such proposals were not successful in developing algorithms that worked well as far as the performance in memory management is concerned. There is no consensus among the researches about how this problem can be treated efficiently, and the algorithms proposed have high overhead because of their complexity. The objective of this work is to propose an efficient memory management with the composition of page fetch, placement and replacement techniques. This thesis hypothesis is that to treat the memory management problem it is better to consume computational resources determining which pages must be in the memory in a given time than to waste resources defining which pages would be evicted from the memory. This work presents a reanalysis of the main works whose objective is memory management performance, making it possible to draw different conclusions and ideas about what factors may have a positive influence with respect to system performance. This study develops both the concept of quality of memory contents and a metric to measure it. Besides, a systemic method to create memory management algorithms is devised, applying the concept just created. Then, the method is followed, creating the RR+ng and RRlock+ng algorithms. In the final phase of the method, the metric is applied in simulations, proving to be adequate to perform the analysis. The results show that the idea of treating the memory management problem, consuming computational resources to determine which pages must be in the memory instead of which ones must leave it, hold true and seems to be promising.

La mémoire est considérée comme étant gloutonne en consommation d'énergie, un problème sensible, particulièrement dans les systèmes embarqués. L'optimisation globale de fonctions multimodales est également un problème délicat à résoudre du fait de la grande quantité d'optima locaux de ces fonctions. Dans ce mémoire, je présente différents nouveaux algorithmes hybrides et distribués afin de résoudre ces deux problèmes d'optimisation. Ces algorithmes sont comparés avec les méthodes classiques utilisées dans la littérature et les résultats obtenus sont encourageants. En effet, ces résultats montrent une réduction de la consommation d'énergie en mémoire d'environ 76% jusqu'à plus de 98% sur nos programmes tests, d'une part. D'autre part, dans le cas de l'optimisation globale de fonctions multimodales, nos algorithmes hybrides convergent plus souvent vers la solution optimale globale. Des versions distribuées et coopératives de ces nouveaux algorithmes hybrides sont également proposées. Elles sont, par ailleurs, plus rapides que leurs versions séquentielles respectives. / Résumé en anglais : Memory is considered to be greedy in energy consumption, a sensitive issue, especially in embedded systems. The global optimization of multimodal functions is also a difficult problem because of the large number of local optima of these functions. In this thesis report, I present various new hybrid and distributed algorithms to solve these two optimization problems. These algorithms are compared with conventional methods used in the literature and the results obtained are encouraging. Indeed, these results show a reduction in memory energy consumption by about 76% to more than 98% on our benchmarks on one hand. On the other hand, in the case of global optimization of multimodal functions, our hybrid algorithms converge more often to the global optimum solution. Distributed and cooperative versions of these new hybrid algorithms are also proposed. They are more faster than their respective sequential versions.