This thesis focuses on range searching data structures, an elementary problem in computational geometry with research spanning decades. These problems often involve very large data sets. Processor speeds increase faster than memory speeds, thus the gap between the rate at which CPUs can process data and the rate at which it can be retrieved is increasing. To bridge this gap, various levels of cache are used. Since cache misses are costly, algorithms should be cache-friendly. The input-output (I/O) model was the first model for constructing cache-efficient algorithms, focusing on a two-level memory hierarchy. Algorithms for this model require manual tuning to determine optimal values for hardware dependent parameters, and are only optimal at a single level of a memory hierarchy. Cache-oblivious (CO) algorithms are built without knowledge of the hierarchy, allowing them to be optimal across all levels at once. There exist strong theoretical and practical results for I/O-efficient range searching. Recently, the CO model has received attention, but range searching remains poorly understood. This thesis explores data structures for CO range counting and reporting. It presents the first space and worst-case query-time optimal approximate range counting structure for a family of related problems, and associated O(N log N)-space query-optimal reporting structures. The approximate counting structure is the first of its kind in internal memory, I/O and CO models. Researchers have been trying to create linear-space query-optimal CO reporting structures. This thesis shows that for a variety of problems, linear space is in fact impossible. Heuristics are also used for building cache-friendly algorithms. Space-filling curves are continuous functions mapping multi-dimensional sets into one-dimensional ones. They are used to build search structures in the hopes that objects that were close in the original space remain close in the resulting ordering. This results in queries incurring fewer page swaps when traversing the structure. The Hilbert curve is notably good at this, but often imposes a space or time penalty. This thesis introduces compact Hilbert indices, which remove the ineffiency inherent for input point sets with bounding boxes smaller than their bounding hypercubes.

La découverte du site Nepress (BiEr-21) en 2004 et les saisons de fouilles subséquentes ont permis de découvrir de nombreux vestiges archéologiques. Ce mémoire a donc pour objectif de déterminer l’identité culturelle des occupants qui ont fréquenté le site, en prenant en considération les activités rituelles et la stratégie d’approvisionnement en matière lithique. Pour y parvenir, une analyse morpho-métrique de l’assemblage lithique a été effectuée. La distribution intra-site des artéfacts a également été prise en considération lors de l’analyse. Une séquence chronologique du Nord-Est américain remontant au Sylvicole inférieur est présentée dans ce mémoire. Une période d’occupation semble dominer sur le site Nepress, soit le Sylvicole inférieur. Cette manifestation est caractérisée par la présence d’artéfacts diagnostiques de la culture Meadowood. Ces objets sont un grattoir triangulaire bifacial Meadowood, ainsi qu’une imitation de pointe de type box-base. / The discovery of the Nepress site (BiEr-21) in 2004 and the subsequent excavations have revealed many archaeological remains. This thesis has seeks to determine the cultural identity of the site’s occupants, taking into account their ritual activities and their lithic procurement strategy. To achieve this, a morpho-metric analysis of the lithic assemblage was undertaken. The intra-site artifact distribution was also taken into account. A chronological sequence for Northeastern North America going back to the Early Woodland is presented. The Early Woodland appears to dominate the occupation of the Nepress site. This is characterised by the presence of diagnostic artifacts of the Meadowood culture. These objects are a triangular bifacial Meadowood scraper, as well as an imitation of a projectile point.

Frontend and backend wearout mechanisms are major reliability concerns for modern microprocessors. In this research, a framework which contains modules for negative bias temperature instability (NBTI), positive bias temperature instability (PBTI), hot carrier injection (HCI), gate-oxide breakdown (GOBD), backend time-dependent dielectric breakdown (BTDDB), electromigration (EM), and stress-induced voiding (SIV) is proposed to analyze the impact of each wearout mechanism on state-of-art microprocessors and to accurately estimate microprocessor lifetimes due to each wearout mechanism. Taking into account the detailed thermal profiles, electrical stress profiles and a variety of use scenarios, composed of a fraction of time in operation, a fraction of time in standby, and a fraction of time when the system is off, this work provides insight into lifetime-limiting wearout mechanisms, along with the reliability-critical microprocessor functional units for a system. This enables circuit designers to know if their designs will achieve an adequate lifetime and further make any updates in the designs to enhance reliability prior to committing the designs to manufacture.

Green computing techniques aim to reduce the power foot print of modern embedded devices with particular emphasis on processors, the power hot-spots of these devices. In this thesis we propose compiler-driven and profile-driven optimizations that reduce power consumption in a modern embedded processor. We show that these optimizations reduce power consumption in functional units and memory subsystems with very low performance loss. We present three new techniques to reduce power consumption in processors, namely, transition aware scheduling, leakage reduction in data caches using criticality analysis, and dynamic power reduction in data caches using locality analysis of data regions. A novel instruction scheduling technique to address leakage power consumption in functional units is proposed. This scheduling technique, transition aware scheduling, is motivated by idle periods that arise in the utilization of functional units during program execution. A continuously large idle period in a functional unit can be exploited to place the unit in low power state. This novel scheduling algorithm increases the duration of idle periods without hampering performance and drives power gating in these periods. A power model defined with idle cycles as a parameter shows that this technique saves up to 25% of leakage power with very low performance impact. In modern embedded programs, data regions can be classified as critical and non-critical. Critical data regions significantly impact the performance. A new technique to identify such data regions through profiling is proposed. This technique along with a new criticality based cache policy is used to control the power state of the data cache. This scheme allocates non-critical data regions to low-power cache regions, thereby reducing leakage power consumption by up to 40% without compromising on the performance. This profiling technique is extended to identify data regions that have low locality. Some data regions have high data reuse. A locality based cache policy based on cache parameters like size and associativity is proposed. This scheme reduces dynamic as well as static power consumption in the cache subsystem. This optimization reduces 25% of the total power consumption in the data caches without hampering the execution time. In this thesis, the problem of power consumption of a program is decoupled from the number of processor cores. The underlying architecture model is simplified to abstract away a variety of processor scenarios. This simplified model can be scaled up to be implemented in various multi-core architecture models like Chip Multi-Processors, Simultaneous Multi-Threaded Processors, Chip Multi-Threaded Processors, to name a few. The three techniques proposed in this thesis leverage underlying hardware features like low power functional units, drowsy caches and split data caches. These techniques reduce power consumption of a wide range of benchmarks with low performance loss.

The current popular, distributed, n-tiered, object-oriented application architecture pro- vokes many design debates. Designs of such applications are often divided into logical layer (or tiers) - usually user interface, business logic and domain object (or data) layer, each with their own design issues. In particular, the latter contains data that needs to be stored and retrieved from permanent storage. Decisions need to be made as to the most appropriate way of doing this - the choices are usually whether to use an object database, to communicate directly with a relational database, or to use object-relational mapping (ORM) tools to allow objects to be translated to and from their relational form. Most often, depending on the perceived profile of the application, software architects make these decisions using rules of thumb derived from particular experience or the design patterns literature. Although helpful, these rules are often highly context-dependent and are of- ten misapplied. Research into the nature and magnitude of 'design forces' in this area has resulted in a series of benchmarks, intended to allow architects to understand more clearly the implications of design decisions concerning persistence. This study provides some results to help guide the architect's decisions. The study investigated and focused on the <i.performance of object persistence and com- pared ORM tools to object databases. ORM tools provide an extra layer between the business logic layer and the data layer. This study began with the hypothesis that this extra layer and mapping that happens at that point, slows down the performance of object persistence. The aim was to investigate the influence of this extra layer against the use of object databases that remove the need for this extra mapping layer. The study also investigated the impact of certain optimisation techniques on performance. A benchmark was used to compare ORM tools to object databases. The benchmark provided criteria that were used to compare them with each other. The particular benchmark chosen for this study was OO7, widely used to comprehensively test object persistence performance. Part of the study was to investigate the OO7 benchmark in greater detail to get a clearer understanding of the OO7 benchmark code and inside workings thereof. Included in this study was a comparison of the performance of an open source object database, db4o, against a proprietary object database, Versant. These representatives of object databases were compared against one another as well as against Hibernate, a popular open source representative of the ORM stable. It is important to note that these applications were initially used in their default modes (out of the box). Later some optimisation techniques were incorporated into the study, based on feedback obtained from the application developers. There is a common perception that an extra layer as introduced by Hibernate nega- tively impacts on performance. This study showed that such a layer has minimal impact on the performance. With the use of caching and other optimisation techniques, Hibernate compared well against object databases. Versant, a proprietary object database, was faster than Hibernate and the db4o open source object database. Copyright / Dissertation (MSc)--University of Pretoria, 2010. / Computer Science / unrestricted

Adaptive Content Distribution Networks (A-CDNs) sind anwendungsübergreifende, verteilte Infrastrukturen, die auf Grundlage verteilter Replikation von Inhalten und Inhaltsadaption eine skalierbare Auslieferung von adaptierbaren multimedialen Inhalten an heterogene Clients ermöglichen. Die Platzierung der Replikate in den Surrogaten eines A-CDN wird durch den Platzierungsmechanismus des A-CDN gesteuert. Anders als in herkömmlichen CDNs, die keine Inhaltsadaption berücksichtigen, muss ein Platzierungsmechanismus in einem A-CDN nicht nur entscheiden, welches Inhaltsobjekt in welchem Surrogat repliziert werden soll, sondern darüber hinaus, in welcher Repräsentation bzw. in welchen Repräsentationen das Inhaltsobjekt zu replizieren ist. Herkömmliche Platzierungsmechanismen sind nicht in der Lage, verschiedene Repräsentationen eines Inhaltsobjektes zu berücksichtigen. Beim Einsatz herkömmlicher Platzierungsmechanismen in A-CDNs können deshalb entweder nur statisch voradaptierte Repräsentationen oder ausschließlich generische Repräsentationen repliziert werden. Während bei der Replikation von statisch voradaptierten Repräsentationen die Wiederverwendbarkeit der Replikate eingeschränkt ist, führt die Replikation der generischen Repräsentationen zu erhöhten Kosten und Verzögerungen für die dynamische Adaption der Inhalte bei jeder Anfrage. Deshalb werden in der Arbeit adaptivitätssensitive Platzierungsmechanismen zur Platzierung von Replikaten in A-CDNs vorgeschlagen. Durch die Berücksichtigung der Adaptierbarkeit der Inhalte bei der Ermittlung einer Platzierung von Replikaten in den Surrogaten des A-CDNs können adaptivitätssensitive Platzierungsmechanismen sowohl generische und statisch voradaptierte als auch teilweise adaptierte Repräsentationen replizieren. Somit sind sie in der Lage statische und dynamische Inhaltsadaption flexibel miteinander zu kombinieren. Das Ziel der vorliegenden Arbeit ist zu evaluieren, welche Vorteile sich durch die Berücksichtigung der Inhaltsadaption bei Platzierung von adaptierbaren Inhalten in A-CDNs realisieren lassen. Hierzu wird das Problem der adaptivitätssensitiven Platzierung von Replikaten in A-CDNs als Optimierungsproblem formalisiert, Algorithmen zur Lösung des Optimierungsproblems vorgeschlagen und diese in einem Simulator implementiert. Das zugrunde liegende Simulationsmodell beschreibt ein im Internet verteiltes A-CDN, welches zur Auslieferung von JPEG-Bildern an heterogene mobile und stationäre Clients verwendet wird. Anhand dieses Simulationsmodells wird die Leistungsfähigkeit der adaptivitätssensitiven Platzierungsmechanismen evaluiert und mit der von herkömmlichen Platzierungsmechanismen verglichen. Die Simulationen zeigen, dass der adaptivitätssensitive Ansatz in Abhängigkeit vom System- und Lastmodell sowie von der Speicherkapazität der Surrogate im A-CDN in vielen Fällen Vorteile gegenüber dem Einsatz herkömmlicher Platzierungsmechanismen mit sich bringt. Wenn sich die Anfragelasten verschiedener Typen von Clients jedoch nur wenig oder gar nicht überlappen oder bei hinreichend großer Speicherkapazität der Surrogate hat der adaptivitätssensitive Ansatz keine signifikanten Vorteile gegenüber dem Einsatz eines herkömmlichen Platzierungsmechanismus. / Adaptive Content Distribution Networks (A-CDNs) are application independent, distributed infrastructures using content adaptation and distributed replication of contents to allow the scalable delivery of adaptable multimedia contents to heterogeneous clients. The replica placement in an A-CDN is controlled by the placement mechanisms of the A-CDN. As opposed to traditional CDNs, which do not take content adaptation into consideration, a replica placement mechanism in an A-CDN has to decide not only which object shall be stored in which surrogate but also which representation or which representations of the object to replicate. Traditional replica placement mechanisms are incapable of taking different representations of the same object into consideration. That is why A-CDNs that use traditional replica placement mechanisms may only replicate generic or statically adapted representations. The replication of statically adapted representations reduces the sharing of the replicas. The replication of generic representations results in adaptation costs and delays with every request. That is why the dissertation thesis proposes the application of adaptation-aware replica placement mechanisms. By taking the adaptability of the contents into account, adaptation-aware replica placement mechanisms may replicate generic, statically adapted and even partially adapted representations of an object. Thus, they are able to balance between static and dynamic content adaptation. The dissertation is targeted at the evaluation of the performance advantages of taking knowledge about the adaptability of contents into consideration when calculating a placement of replicas in an A-CDN. Therefore the problem of adaptation-aware replica placement is formalized as an optimization problem; algorithms for solving the optimization problem are proposed and implemented in a simulator. The underlying simulation model describes an Internet-wide distributed A-CDN that is used for the delivery of JPEG images to heterogeneous mobile and stationary clients. Based on the simulation model, the performance of the adaptation-aware replica placement mechanisms are evaluated and compared to traditional replica placement mechanisms. The simulations prove that the adaptation-aware approach is superior to the traditional replica placement mechanisms in many cases depending on the system and load model as well as the storage capacity of the surrogates of the A-CDN. However, if the load of different types of clients do hardly overlap or with sufficient storage capacity within the surrogates, the adaptation-aware approach has no significant advantages over the application of traditional replica-placement mechanisms.

No description available.

Aujourd’hui, le renforcement de la sécurité des systèmes de communications devient une nécessité, par anticipation du développement des ordinateurs quantiques et des nouvelles attaques qui en découleront. Cette thèse explore deux techniques complémentaires permettant d’assurer la confidentialité des données transmises sur des liens sans-fils. Dans la première partie de ce travail, nous nous intéressons au schéma de cryptographie à clé publique basée sur des réseaux de points, qui représente une des techniques les plus prometteuses pour la cryptographie post-quantique. En particulier, nous considérons le cryptosystème Goldreich-Goldwasser-Halevi (GGH), pour lequel nous proposons un nouveau schéma utilisant les GLD. Dans la seconde partie de ce travail, nous étudions la sécurité des canaux de diffusion multi-utilisateur, ayant accès à des mémoires de caches, en présence d'un espion. Nous considérons deux contraintes de sécurité: la contrainte de sécurité individuelle et la contrainte de sécurité jointe. Nous dérivons des bornes supérieure et inférieure pour le compromis sécurisé capacité-mémoire en considérant différentes distributions de cache. Afin d'obtenir la borne inférieure, nous proposons plusieurs schémas de codage combinant codage wiretap, codage basé sur la superposition et codage piggyback. Nous prouvons qu'il est plus avantageux d'allouer la mémoire de cache aux récepteurs les plus faibles. / Today, there is a real need to strengthen the communication security to anticipate the development of quantum computing and the eventual attacks arising from it. This work explores two complementary techniques that provide confidentiality to data transmitted over wireless networks. In the first part, we focus on lattice-based public-key cryptography, which is one of the most promising techniques for the post-quantum cryptography systems. In particular, we focus on the Goldreich-Goldwasser-Halevi (GGH) cryptosystem, for which we propose a new scheme using GLD lattices. In the second part of this work, we study the security of multi-user cache-aided wiretap broadcast channels (BCs) against an external eavesdropper under two secrecy constraints: individual secrecy constraint and joint secrecy constraint. We compute upper and lower bounds on secure capacity-memory tradeoff considering different cache distributions. To obtain the lower bound, we propose different coding schemes that combine wiretap coding, superposition coding and piggyback coding. We prove that allocation of the cache memory to the weaker receivers is the most beneficial cache distribution scenario.

This thesis describes process of RedirFS portation to FreeBSD operating system. Source operating system is Linux. Those two operating systems are described from VFS view to determine differences and needed modifications. Then follows implementation of port.

Model checking problems suffer from state space explosion. State space explosion is the number of states in the graph increases exponentially with the number of variables in the state description. Searching the large graphs required in model checking requires an efficient algorithm. This dissertation explores several methods to improve an externalmemory search algorithm for model checking problems. A tool implementing these methods is built on top of the Murphi model checker. One improvement is a state cache for immediate detection leveraging the properties of state locality. A novel type of locality, intralayer locality is explained and shown to exist in a variety of search spaces. Another improvement, partial delayed duplicate detection, exploits interlayer locality to reduce search times. An automatic partitioning function is described that allows hash-based delayed duplicate detection to be used without domain knowledge of the state space. A phased delayed duplicate detection algorithm combining features of hash-based delayed duplicate detection and sorting-based delayed duplicate detection is explained and compared to the other methods.