Queries on spatial data commonly concern a certain range or area, for example, queries related to intersections, containment and nearest neighbors. The Continuous Nearest Neighbor (CNN) query is one kind of the nearest neighbor queries. For example, people may want to know where those gas stations are along the super highway from the starting position to the ending position. Due to that there is no total ordering of spatial proximity among spatial objects, the space filling curve (SFC) approach has proposed to preserve the spatial locality. Chen and Chang have proposed efficient algorithms based on SFC to answer nearest neighbor queries, so we may perform a sequence of individually nearest neighbor queries to answer such a CNN query in the centralized system by one of Chen and Chang's algorithms. However, each searched range of these nearest neighbor queries could be overlapped, and these queries may access several same pages on the disk, resulting in many redundant disk accesses. On the other hand, Zheng et al. have proposed an algorithm based on the Hilbert curve for the CNN query for the wireless broadcast environment, and it contains two phases. In the first phase, Zheng et al.'s algorithm designs a searched range to find candidate objects. In the second phase, it uses some heuristics to filter the candidate objects for the final answer. However, Zheng et al.'s algorithm may check some data blocks twice or some useless data blocks, resulting in some redundant disk accesses. Therefore, in this thesis, to avoid these disadvantages in the first phase of Zheng et al.'s algorithm, we propose a local expansion approach based on the Peano curve for the CNN query in the centralized system. In the first phase, we determine the searched range to obtain all candidate objects. Basically, we first calculate the route between the starting point and the ending point. Then, we move forward one block from the starting point to the ending point, and locally spread the searched range to find the candidate objects. In the second phase, we use heuristics mentioned in Zheng et al.'s algorithm to filter the candidate objects for the final answer. Based on such an approach, we proposed two algorithms: the forward moving (FM) algorithm and the forward moving* (FM*) algorithm. The FM algorithm assumes that each object is in the center of a block, and the FM* algorithm assumes that each object could be in any place of a block. Our local expansion approach can avoid the duplicated check in Zheng et al.'s algorithm, and determine a searched range with higher accuracy than that of Zhenget al.'s algorithm. From our simulation results, we show that the performance of the FM or FM* algorithm is better than that of Zheng et al.'s algorithm, in terms of the accuracy and the processing time.

Στην παρούσα διπλωματική εργασία θα ασχοληθούμε με το πρόβλημα της αξιοπιστίας των κρυφών μνημών δεδομένων και εντολών πρώτου επιπέδου. Η υψηλή πυκνότητα ολοκλήρωσης και η υψηλή συχνότητα λειτουργίας των σύγχρονων ολοκληρωμένων κυκλωμάτων έχει οδηγήσει σε σημαντικά προβλήματα αξιοπιστίας, που οφείλονται είτε στην κατασκευή, είτε στη γήρανση των ολοκληρωμένων κυκλωμάτων. Στην παρούσα εργασία γίνεται αρχικά μια αποτίμηση της μείωσης της απόδοσης των κρυφών μνημών πρώτου επιπέδου όταν εμφανίζονται μόνιμα σφάλματα για διαφορετικές τεχνολογίες ολοκλήρωσης. Στη συνέχεια παρουσιάζεται μια νέα τεχνική αντιμετώπισης της επίδρασης των σφαλμάτων, η οποία βασίζεται στη πρόβλεψη της χωρικής τοπικότητας των μπλοκ μνήμης που εισάγονται στις κρυφές μνήμες πρώτου επιπέδου. Η αξιολόγηση της εν λόγω τεχνικής γίνεται με τη χρήση ενός εξομοιωτή σε επίπεδο αρχιτεκτονικής. / In this thesis we will work on the problem of reliability of first-level data and instruction cache memories. Technology scaling improvement is affecting the reliability of ICs due to increases in static and dynamic variations as well as wear out failures. First of all, in this work we try to estimate the impact of permanent faults in first level faulty caches. Then we propose a methodology to mitigate this negative impact of defective bits. Out methodology based on prediction of spatial locality of the incoming blocks to cache memory. Finally using cycle accurate simulation we showcase that our approach is able to offer significant benefits in cache performance.

No description available.

Hamid Ghasemirahni, et al. have shown that the order of the network packets arrival at a datacenter, equipped with commodity servers, plays a significant role in the latency of processing these packets. The larger the burst of packets that are part of a flow and hence will be processed using the same instructions and data, the greater the utilization of the system’s caches and subsequently the lower the latency of their processing. However, there are many reason for the packets to not arrive in a burst. One of the main reason that is examined in this project is packet interleaving that takes place in the routers and switches along the path that the packets take from a computer to/from the datacenter. This project take a more general look at traffic arriving at a server via a tree of network devices on the uplink path to the server. The focus is to use scripts to create a tree of switches and conduct experiments with them by scripting Mininet. From these experiments we learned that the different algorithms that control the output queues of the network nodes across the network path play a significant role in packet interleaving. Furtheromore, experiments on Mininet host connectivity explained how with the Openflow protocol, Mininet controller set up rules in the switches of the network topology. Finally, experiments in TCP throughput showed the limiting factors of a TCP connection between the server and a host while many provided traffic flows illustrate common behaviors of packet interleaving that occurs due to the switches. / Hamid Ghasemirahni, et al. har visat att ordningen på nätverkspaketens ankomst till ett datacenter, utrustat med varuservrar, spelar en betydande roll i fördröjningen av bearbetningen av dessa paket. Ju större burst av paket som är en del av ett flöde och därför kommer att behandlas med samma instruktioner och data, desto större utnyttjande av systemets cacheminne och därefter desto lägre fördröjning för deras bearbetning. Det finns dock många anledningar till att paketen inte kommer fram i en skur. En av huvudorsakerna som undersöks i detta projekt är paketinterfoliering som sker i routrarna och switcharna längs vägen som paketen tar från en dator till/från datacentret. Detta projekt tar en mer allmän titt på trafik som kommer till en server via ett träd av nätverksenheter på upplänksvägen till servern. Fokus är att använda skript för att skapa ett träd av switchar och utföra experiment med dem genom att skripta Mininet. Från dessa experiment lärde vi oss att de olika algoritmerna som styr utgångsköerna för nätverksnoderna över nätverksvägen spelar en betydande roll i paketinterfoliering. Dessutom förklarade experiment på Mininet-värdanslutning hur med Openflow-protokollet, Mininet-styrenheten satte upp regler i switcharna i nätverkstopologin. Slutligen visade experiment i TCP-genomströmning de begränsande faktorerna för en TCP-anslutning mellan servern och en värd medan många tillhandahållna trafikflöden illustrerar vanliga beteenden för paketinterfoliering som uppstår på grund av switcharna.

Recent years have witnessed the emergence of microprocessors that are embedded within a plethora of devices used in everyday life. Embedded architectures are customized through a meticulous and time consuming design process to satisfy stringent constraints with respect to performance, area, power, and cost. In embedded systems, the cost of the memory hierarchy limits its ability to play as central a role. This is due to stringent constraints that fundamentally limit the physical size and complexity of the memory system. Ultimately, application developers and system engineers are charged with the heavy burden of reducing the memory requirements of an application. This thesis offers the intriguing possibility that compilers can play a significant role in the automatic design space exploration and optimization of embedded memory systems. This insight is founded upon a new analytical model and novel compiler optimizations that are specifically designed to increase the synergy between the processor and the memory system. The analytical models serve to characterize intrinsic program properties, quantify the impact of compiler optimizations on the memory systems, and provide deep insight into the trade-offs that affect memory system design.

The gap between processor speed and memory latency has led to the use of caches in the memory systems of modern computers. Programs must use the caches efficiently and exploit data locality for maximum performance. Multiprocessors, built from many processing units, are becoming commonplace not only in large servers but also in smaller systems such as personal computers. Multiprocessors require careful data locality optimizations since accesses from other processors can lead to invalidations and false sharing cache misses. This thesis explores hardware and software approaches for creating and exploiting temporal and spatial locality in multiprocessors. We propose the capacity prefetching technique, which efficiently reduces the number of cache misses but avoids false sharing by distinguishing between cache lines involved in communication from non-communicating cache lines at run-time. Prefetching techniques often lead to increased coherence and data traffic. The new bundling technique avoids one of these drawbacks and reduces the coherence traffic in multiprocessor prefetchers. This is especially important in snoop-based systems where the coherence bandwidth is a scarce resource. Most of the studies have been performed on advanced scientific algorithms. This thesis demonstrates that a cc-NUMA multiprocessor, with hardware data migration and replication optimizations, efficiently exploits the temporal locality in such codes. We further present a method of parallelizing a multigrid Gauss-Seidel partial differential equation solver, which creates temporal locality at the expense of increased communication. Our conclusion is that on modern chip multiprocessors, it is more important to optimize algorithms for data locality than to avoid communication, since communication can take place using a shared cache.

Data-centers increasingly deploy commodity servers with high-speed network interfaces to enable low-latency communication. However, achieving low latency at high data rates crucially depends on how the incoming traffic interacts with the system's caches. When packets that need to be processed in the same way are consecutive, i.e., exhibit high temporal and spatial locality, CPU caches deliver great benefits. This licentiate thesis systematically studies the impact of temporal and spatial traffic locality on the performance of commodity servers equipped with high-speed network interfaces. The results are that (i) the performance of a variety of widely deployed applications degrade substantially with even the slightest lack of traffic locality, and (ii) a traffic trace from our organization's link to/from its upstream provider reveals poor traffic locality as networking protocols, drivers, and the underlying switching/routing fabric spread packets out in time (reducing locality).  To address these issues, we built Reframer, a software solution that deliberately delays packets and reorders them to increase traffic locality. Despite introducing µs-scale delays of some packets, Reframer increases the throughput of a network service chain by up to 84% and reduces the flow completion time of a web server by 11% while improving its throughput by 20%. / Datacenter distribuerar alltmer rå varuservrar med höghastighets-nätverksgränssnitt för att möjliggöra kommunikation med låg latens. Att uppnå låg latens vid höga datahastigheter beror dock mycket på hur den inkommande trafiken interagerar med systemets cacheminnen. När paket som behöver bearbetas på samma sätt är konsekutiva, dvs. uppvisar hög tids- och rumslig lokalitet, ger cacher stora fördelar. I denna licentiatuppsats studerar vi systematiskt effekterna av tidsmässig och rumslig trafikplats på  prestanda för rå varuservrar utrustade med höghastighetsnätgränssnitt.Vå ra resultat visar att (i) prestandan för en mängd allmänt distribuerade applikationer försämras avsevärt med till och med den minsta bristen på trafikplats, och (ii) visar ett trafikspår från vår organisation dålig trafikplats som nätverksprotokoll, drivrutiner och den underliggande omkopplingen/dirigera tygspridningspaket i tid (minska lokaliteten). För att ta itu med dessa problem byggde vi Reframer, en mjukvarulösning som medvetet fördröjer paket och ordnar dem för att öka trafikplatsen. Trots införandet av µs-skalafördröjningar för vissa paket visar vi att Reframer ökar genomströmningen för en nätverkstjänstkedja med upp till 84% och minskar flödet för en webbserver med 11% samtidigt som dess genomströmning förbättras med 20%. / <p>QC 20210512</p> / ULTRA

The astronomical increase in the number of wireless devices such as smart phones in 21th century has revolutionized the way people communicate with one another and share information. The new wireless technologies have also enabled researchers to collect real data about how people move and meet one another in different social settings. Understanding human mobility has many applications in different areas such as traffic planning in cities and public health studies of epidemic diseases. In this thesis, we study the fundamental properties of human contact graphs in order to characterize how people meet one another in different social environments. Understanding human contact patterns in return allows us to propose a cost-effective routing algorithm for spreading information in Delay Tolerant Networks. Furthermore, we propose several contact predictors to predict the unobserved parts of contact graphs when only partial observations are available. Our results show that we are able to infer hidden contacts of real contact traces by exploiting the underlying properties of contact graphs. In the last few years, we have also witnessed an explosion in the number of people who use social media to share information with their friends. In the last part of this thesis, we study the running times of several information spreading algorithms in social networks in order to find the fastest strategy. Fast information spreading has an obvious application in advertising a product to a large number of people in a short amount of time. We prove that a fast information spreading algorithm should efficiently identify communication bottlenecks in order to speed up the running time. Finally, we show that sparsifying large social graphs by exploiting the edge-betweenness centrality measure can also speed up the information spreading rate. / Graduate