Dissertations / Theses on the topic 'Locality'

In this thesis we consider a number of different aspects of dynamical locality, an axiom on locally covariant theories proposed by Fewster and Verch that is closely related to the question of whether a theory describes the same physics in all spacetimes. After some introductory material, in Chapters 3 and 4 we examine dynamical locality for the nonminimally coupled scalar field and its enlarged algebra of observables. We show that dynamical locality holds at all masses, including non-zero masses, for the nonminimally coupled scalar field theory. We also demonstrate that dynamical locality holds in the massive minimally coupled and massive conformally coupled cases for the enlarged algebra of observables, and fails to hold in the massless minimally coupled case. In Chapter 5, we discuss a number of categorical structures that can be used in the construction of classical theories that may be quantized using canonical anticommutation relations (CAR), and their subsequent quantization. We prove a number of results pertaining to dynamical locality of classical theories and their CAR-quantized counterparts. In Chapters 6 and 7, we give a simplified version of the locally covariant classical and quantum Dirac theories, using the machinery developed in Chapter 5. We also formulate for the first time versions of these theories that are entirely independent of the choice of a global reference frame for the spacetime, and depend only on an equivalence class of these frames. We demonstrate that both the simplified frame-dependent theories and the frame-independent theories are dynamically local.

This dissertation develops a transformational theory of scope which is based not on the position to which an entire quantificational noun phrase (QNP) can move and adjoin but on the position and to which a quantificational determiner can move and adjoin. Following Heim (1982), a tripartite representation for sentences containing QNPs is adopted in which quantificational determiners move out of their containing noun phrases and adjoin to the sentence node at the level of Logical Form (LF). By utilizing this type of representation, asymmetries between the movement possibilities of a phrase and scope possibilities of a phrase can be captured. This dissertation argues that movement of an operator is free but constrained by the operator acquiring the selection index of the phrase which it binds. The selection index is percolated up the tree in a series of local relationships (government, specifier/head and X-Bar). This index percolation is dependent on the ability of a syntactic head to acquire an index. The necessity of this index percolation approach is demonstrated in the first chapter, which investigates the phenomenon of unselective binding between an adverbial operator and indefinite in restrictive 'if/when' clauses. It shows that this relationship is sensitive to some syntactic islands but not others. It demonstrates that the index percolation approach is the best way to capture the selective island sensitivities of this phenomenon. Additional motivation for this account is given in chapter two, which deals with internally headed relative clauses (IHRCs). Several parallels between IHRCs and restrictive 'if/when' clauses are noted. It shows that the binding of the internal head by the determiner associated with the IHRC is similar to the binding of an indefinite by an adverbial operator. The next two chapters treat the phenomenon of partial Wh-movement. These chapters further show the application of the index percolation account because they argue that the relationships noted above between an adverbial operator and indefinite and operator and internal head are analogous to the relationship between a partially moved WH-Phrase and the sentence initial scope marker. In chapter six, the scope of quantified possessive phrases in English is examined. This is a case where movement of a phrase and scope of a phrase sharply differ. The approach where the determiner of the possessive is moved alone, with index percolation from the phrase in the specifier position to the moved determiner, is shown to best handle these cases.

Thesis: S.M. in Computer Science and Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
32
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 43-45).
We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space ... This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By known reductions we obtain a data structure for the Hamming space and ... which is the first improvement over the result of Indyk and Motwani (STOC 1998).
by Ilya Razenshteyn.
S.M. in Computer Science and Engineering

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Linguistics and Philosophy, 1998.
Includes bibliographical references (leaves [219]-229).
In this dissertation, I demonstrate that the feature-based Attract theory of syntactic movement solves several empirical challenges for Relativized Minimality, while incorporating its key insights. Chapter 1 introduces the theory of phrase structure, syntactic movement, and abstract Case to be adopted throughout the dissertation. This chapter also lays out a cross-linguistic typology of possibilities for A-movement to the subject position. Chapter 2 concerns cases of advancing,where the argument generated highest is attracted by the feature (EPP) driving movement to the subject position. Here locality interacts with a condition (Case Identification) preventing an argument from "pied-piping" to check EPP if it checks Case elsewhere. In some instances, advancing is forced jointly by locality and Case Identification. Given two equally local arguments, Case Identification determines which can be attracted to the subject position. However, newly identified "superraising" violations support the view that locality is respected even if the highest argument has already checked Case. In the first part of Chapter 3, I argue for the central empirical proposal of this dissertation, Lethal Ambiguity: an anaphoric dependency cannot be established between two specifiers of the same head. I contend that one argument can A-scramble past another only by entering, or leapfrogging through, a multiple-specifier configuration with it. In either case, no anaphoric dependency can be established between the two arguments. In the second part of Chapter 3, I present cases of leapfrogging in A-movement to the subject position, also subject to Lethal Ambiguity. Chapter 4 extends the empirical coverage of Lethal Ambiguity to answer a long-standing question from the literature-namely, why anaphoric clitics cannot be object clitics, I argue that Lethal Ambiguity rules out the object clitic derivation for anaphors because an anaphoric object checks Case in a multiple-specifier configuration with the would-be antecedent. I adopt a passive-like derivation for the well-formed anaphoric clitic construction, where the clitic is a categorically underspecified external argument. Since this argument cannot be attracted to check Case or EPP, the object can skip over it to the subject position without Lethal Ambiguity arising. The remainder of the chapter is devoted to other potential cases of skipping.
by Martha Jo McGinnis.
Ph.D.

Negli ultimi anni il serverless computing, un nuovo paradigma cloud, ha sperimentato una rapida crescita. Questo modello, chiamato anche Function as a Service (FaaS), permette l’esecuzione di funzioni stateless in risposta ad eventi asincroni. Il suo incremento di popolarità è derivato dalla semplicità di utilizzo. Lo sviluppatore si preoccupa solamente di scrivere il codice delle funzioni e di specificare i requisiti in termini di risorse all’interno della console del provider utilizzato. Tutto il resto, compreso il dimensionamento delle risorse, è gestito in modo automatico dal gestore cloud in base al carico di lavoro richiesto. Inoltre, FaaS offre modalità originali di design e di sviluppo software unite ad una maggior flessibilità nell’uso e nel calcolo dei costi. Questo elaborato è stato inserito in un contesto più ampio, al quale ha partecipato un laureando della Magistrale di Informatica dell’Università di Bologna e due correlatori della University of Southern Denmark. Il progetto, partendo dalla piattaforma serverless open-source Apache OpenWhisk, è volto a dimostrare l’importanza della data locality durante la fase di scheduling delle funzioni. La data locality è importante per ridurre i tempi di esecuzione nel caso in cui le funzioni necessitino di interagire con basi di dati. Come dimostrato in questa tesi, eseguire le cloud functions il più vicino possibile ai dati utilizzati riduce considerevolmente la latenza.

La mécanique quantique prédit l'existence de corrélations entre particules distantes qui ne peuvent s'expliquer dans le cadre des théories réalistes locales. Suite au développement récent de la théorie de l'information quantique, il a été réalisé que ces corrélations non-locales ont des implications quant aux capacités de traitement de l'information des systèmes quantiques. Outre une signification physique, elles possèdent donc une signification informationnelle. Cette thèse traite de différents aspects de la non-localité liés à ces deux facettes du phénomène.

Nous commençons par un examen de la structure des corrélations locales et non-locales. Nous dérivons dans ce contexte de nouvelles inégalités de Bell, et généralisons ensuite le paradoxe de Greenberger-Horne-Zelinger à des états quantiques de dimension arbitraire et composés de plusieurs sous-systèmes.

Nous abordons par après la non-localité du point de vue de la théorie de l'information. Il est possible de concevoir des théories non-locales consistantes avec le principe de causalité mais offrant des avantages supérieurs à la mécanique quantique en terme de manipulation de l'information. Nous investiguons l'ensemble des corrélations compatibles avec de telles théories afin d'éclairer l'origine des limitations imposées par le formalisme quantique. Nous nous intéressons également à la quantité de communication classique nécessaire pour simuler les corrélations non-locales. Nous montrons que cette mesure naturelle de la non-localité est étroitement liée au degré de violations des inégalités de Bell.

Nous nous tournons ensuite vers des aspects expérimentaux. La faible efficacité des détecteurs utilisés dans les expériences de violation des inégalités de Bell reste un obstacle majeur à une démonstration convaincante de la non-localité, mais aussi à toute utilisation de la non-localité dans des protocoles d'information quantique. Nous dérivons d'une part des bornes quant à l'efficacité minimale requise pour violer les inégalités de Bell, et d'autre part des exemples de corrélations plus résistante à ces imperfections expérimentales.

Finalement, nous clôturons cette thèse en montrant comment la non-localité, principalement étudiée dans le cadre de systèmes décrits par des variables discrètes, telles que les variables de spin, peut également se manifester dans des systèmes à variables continues, telles que les variables de position et d'impulsion.

Doctorat en sciences, Spécialisation physique
info:eu-repo/semantics/nonPublished

This thesis extends techniques from digital circuit interconnect prediction (in particular Rent’s rule) to analyse and predict interconnectedness in software, Chip-Multiprocessors (CMP) and Networks-on-Chip (NoC). In VLSI (Very Large Scale Integrated) circuits, the fractal connectivity of Rent’s rule is a well known predictor of the physical locality of interconnect across many orders of magnitude. It is shown how a generalised Rent’s rule can characterise and model both spatial and temporal locality in software, and it is demonstrated that locality effects can be exploited in Network-on-Chip design for fault tolerance. Evidence of Rentian fractal scaling in software is examined across several benchmarks using multiple methods. Given Rentian scaling, many fundamental results are derived for future many-core CMP architectures that relate number of cores, communication, on-chip memory and the Rent’s exponent, including some surprising scaling requirements towards fine-grain communication. It is also shown that existing models of an algorithm’s asymptotic time and energy cost are inadequate to account for physical communication costs and locality. A new analytical framework that utilises locality and its Rentian characterisation is demonstrated on several example algorithms, and a study is made of the ‘embedding problem’ for composing embeddings of algorithms together. Finally, in examining the interplay of communication and massively parallel computation at larger scales, we look at the mammalian brain as a proof-of-existence. We show that Rent’s rule also appears to apply to neuronal systems, and that this relates to the allometric scaling of communication to computation.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Linguistics and Philosophy, 2012.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 173-179).
This dissertation investigates the constraints on referential dependency relations that can hold between epithets and their antecedents under c-command. The initial observation, presented here in (1), is that epithets can be c-commanded by an antecedent, as long as it is not the closest c-commanding element. (1) a. * Nero, thinks that [the damn traitor] will be invited to the reception. b. OK Nero, thinks that they2 will invite [the damn traitor] to the reception. C.?OK John convinced the panel2 that [the idiot], is smart. Upon closer inspection, the difference between (la) and (lb) seems to involve a subject-object asymmetry in the complement clause of think. Similarly, the contrast between (la) and (lc) suggests that the matrix predicate plays a part in the reduced acceptability of (la). The first part of this dissertation (chapter 2) concerns the syntax of epithets. I argue that epithets are null pronouns modified by a nominal appositive. This argument is based two core pieces of evidence: (i) I will present cross-linguistic evidence illustrating that epithets can be syntactically bound by a quantifier (ii) a series of diagnostics from Den Dikken (2001) and Kayne (2005). Chapter 3 and 4 of this thesis address the semantics of epithets. Following Potts (2005), I argue that epithets must be evaluated from the perspective of a given individual, the evaluator. In chapter 3, I argue that the difference between thinks and convince (cf. Stephenson (2007)) reflects constraints on the judge parameter in an embedded clause that contains an epithet. In chapter 4, I refine my proposal in the spirit of Percus and Sauerland (2003a), (2003b), and argue that cases in which the judge parameter is shifted to the matrix subject have the property of selecting a de se LF. I argue that epithets that adjoin inside such a de se LF cannot refer to the attitude holder, as the nominal appositive would have to adjoin to an uninterpreted anchor. I derive the (la)-(lb) difference by arguing that epithets can undergo LF movement from a position within the embedded object to the antecedent in the matrix clause, but not from a position in the embedded subject. Chapter 5 concludes with a discussion of the role of epithets for general theories of locality.
by Pritty Patel-Grosz.
Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Linguistics and Philosophy, 2008.
Includes bibliographical references (p. 177-185).
This thesis will argue for four broad claims: (1) That local contexts are needed for a descriptively adequate theory of linguistic interpretation, (2) That presupposition accommodation is made with respect to a set of grammatically defined candidates, (3) That the set of accommodation candidates is derived from the same linguistic objects that are used to derive candidates for implicature (the scalar alternatives of the asserted sentence), (4) That scalar implicatures and accommodated propositions are the output of Fox's [31] procedure of innocent exclusion, modified so as to consider implicature candidates and accommodation candidates together. I argue for claim (1) in Chapter 2 by arguing that Heim's principle of Maximize Presupposition! should be checked in local contexts (Local MP). In Chapter 3, I use Local MP to account for an array of blocking effects. We will see that Local MP can help to shed light on the semantics of only, counterfactual conditionals, and focus interpretation, as well as highlighting the importance of dynamically changing assignment functions in a theory of interpretation. I argue for claims (2)-(4) in Chapters 4 and 5 by attempting to address the proviso problem (Geurts [43]), as well as a new puzzle for the theory of implicature that arises in the study of attitude ascriptions.
by Raj Singh.
Ph.D.

Las memorias caché fueron incorporadas en los microprocesadores ya desde los primeros tiempos, y representan la solución más común para tratar la diferencia de velocidad entre el procesador y la memoria. Sin embargo, muchos estudios señalan que la capacidad de almacenamiento de la caché es malgastada muchas veces, lo cual tiene un impacto directo en el rendimiento del procesador. Aunque una caché está diseñada para explotar diferentes tipos de localidad, todas la referencias a memoria son tratadas de la misma forma, ignorando comportamientos particulares de localidad. El uso restringido de la información de localidad para cada acceso a memoria puede limitar la eficiencia de la cache. En esta tesis se demuestra como un análisis de localidad de datos puede ayudar al investigador a entender dónde y porqué ocurren los fallos de caché, y proponer entonces diferentes técnicas que hacen uso de esta información con el objetivo de mejorar el rendimiento de la memoria caché. Proponemos técnicas en las cuales la información de localidad obtenida por el analizador de localidad es pasada desde el compilador al hardware a través del ISA para guiar el manejo de los accesos a memoria.
Hemos desarrollado un análisis estático de localidad de datos. Este análisis está basado en los vectores de reuso y contiene los tres típicos pasos: reuso, volumen y análisis de interferencias. Comparado con trabajos previos, tanto el análisis de volúmenes como el de interferencias ha sido mejorado utilizando información de profiling así como un análisis de interferencias más preciso. El analizador de localidad de datos propuesto ha sido incluido como un paso más en un compilador de investigación. Los resultados demuestran que, para aplicaciones numéricas, el análisis es muy preciso y el overhead de cálculo es bajo. Este análisis es la base para todas las otras partes de la tesis. Además, para algunas propuestas en la última parte de la tesis, hemos usado un análisis de localidad de datos basado en las ecuaciones de fallos de cache. Este análisis, aunque requiere más tiempo de cálculo, es más preciso y más apropiado para cachés asociativas por conjuntos. El uso de dos análisis de localidad diferentes también demuestra que las propuestas arquitectónicas de esta tesis son independientes del análisis de localidad particular utilizado.
Después de mostrar la precisión del análisis, lo hemos utilizado para estudiar el comportamiento de localidad exhibido por los programas SPECfp95. Este tipo de análisis es necesario antes de proponer alguna nueva técnica ya que ayuda al investigador a entender porqué ocurren los fallos de caché. Se muestra que con el análisis propuesto se puede estudiar de forma muy precisa la localidad de un programa y detectar donde estan los "puntos negros" así como la razón de estos fallos en cache. Este estudio del comportamiento de localidad de diferentes programas es la base y motivación para las diferentes técnicas propuestas en esta tesis para mejorar el rendimiento de la memoria.
Así, usando el análisis de localidad de datos y basándonos en los resultados obtenidos después de analizar el comportamiento de localidad de un conjunto de programas, proponemos utilizar este análisis con el objetivo de guiar tres técnicas diferentes: (i) manejo de caches multimódulo, (ii) prebúsqueda software para bucles con planificación módulo, y (iii) planificación de instrucciones de arquitecturas VLIW clusterizadas.
El primer uso del análisis de localidad propuesto es el manejo de una novedosa organización de caché. Esta caché soporta bypass y/o está compuesta por diferentes módulos, cada uno orientado a explotar un tipo particular de localidad. La mayor diferencia de esta caché con respecto propuestas previas es que la decisión de "cachear" o no, o en qué módulo un nuevo bloque es almacenado, está controlado por algunos bits en las instrucciones de memoria ("pistas" de localidad). Estas "pistas" (hints) son fijadas en tiempo de compilación utilizando el análisis de localidad propuesto. Así, la complejidad del manejo de esta caché se mantiene bajo ya que no requiere ningún hardware adicional. Los resultados demuestran que cachés más pequeñas con un manejo más inteligente pueden funcionar tan bien (o mejor) que cachés convencionales más grandes.
Hemos utilizado también el análisis de localidad para estudiar la interacción entre la segmentación software y la prebúsqueda software. La segmentación software es una técnica muy efectiva para la planificación de código en bucles (principalmente en aplicaciones numéricas en procesadores VLIW). El esquema más popular de prebúsqueda software se llama planificación módulo. Muchos trabajos sobre planificación módulo se pueden encontrar en la literatura, pero casi todos ellos consideran una suposición crítica: consideran un comportamiento optimista de la cache (en otras palabras, usan siempre la latencia de acierto cuando planifican instrucciones de memoria). Así, los resultados que presentan ignoran los efectos del bloqueo debido a dependencias con instrucciones de memoria. En esta parte de la tesis mostramos que esta suposición puede llevar a planificaciones cuyo rendimiento es bastante más bajo cuando se considera una memoria real. Nosotros proponemos un algoritmo para planificar instrucciones de memoria en bucles con planificación módulo. Hemos estudiado diferentes estrategias de prebúsqueda software y finalmente hemos propuesto un algoritmo que realiza prebúsqueda basándose en el análisis de localidad y en la forma del grafo de dependencias del bucle. Los resultados obtenidos demuestran que el esquema propuesto mejora el rendimiento de las otras heurísticas ya que obtiene un mejor compromiso entre tiempo de cálculo y de bloqueo.
Finalmente, el último uso del análisis de localidad estudiado en esta tesis es para guiar un planificador de instrucciones para arquitecturas VLIW clusterizadas. Las arquitecturas clusterizadas están siendo una tendencia común en el diseño de procesadores empotrados/DSP. Típicamente, el núcleo de estos procesadores está basado en un diseño VLIW el cual particiona tanto el banco de registros como las unidades funcionales. En este trabajo vamos un paso más allá y también hacemos la partición de la memoria caché. En este caso, tanto las comunicaciones entre registros como entre memorias han de ser consideradas. Nosotros proponemos un algoritmo que realiza la partición del grafo así como la planificación de instrucciones en un único paso en lugar de hacerlo secuencialmente, lo cual se demuestra que es más efectivo. Este algoritmo es mejorado añadiendo una análisis basado en las ecuaciones de fallos de cache con el objetivo de guiar en la planificación de las instrucciones de memoria para reducir no solo comunicaciones entre registros, sino también fallos de cache.
Cache memories were incorporated in microprocessors in the early times and represent the most common
solution to deal with the gap between processor and memory speeds. However, many studies point out that the cache storage capacity is wasted many times, which means a direct impact in processor performance. Although a cache is designed to exploit different types of locality, all memory references are handled in the same way, ignoring particular locality behaviors. The restricted use of the locality information for each memory access can limit the effectivity of the cache. In this thesis we show how a data locality analysis can help the researcher to understand where and why cache misses occur, and then to propose different techniques that make use of this information in order to improve the performance of cache memory. We propose techniques in which locality information obtained by the locality analyzer is passed from the compiler to the hardware through the ISA to guide the management of memory accesses.

We have developed a static data locality analysis. This analysis is based on reuse vectors and performs the three typical steps: reuse, volume and interfere analysis. Compared with previous works, both volume
and interference analysis have been improved by using profile information as well as a more precise inter-
ference analysis. The proposed data locality analyzer has been inserted as another pass in a research compiler. Results show that for numerical applications the analysis is very accurate and the computing overhead is low. This analysis is the base for all other parts of the thesis. In addition, for some proposals in the last part of the thesis we have used a data locality analysis based on cache miss equations. This analysis, although more time consuming, is more accurate and more appropriate for set-associative caches. The usage of two different locality analyzers also shows that the architectural proposals of this thesis are independent from the particular locality analysis.

After showing the accuracy of the analysis, we have used it to study the locality behavior exhibited by the SPECfp95 programs. This kind of analysis is necessary before proposing any new technique since can help the researcher to understand why cache misses occur. We show that with the proposed analysis we can study very accurately the locality of a program and detect where the hot spots are as well as the reason for these misses. This study of the locality behavior of different programs is the base and motivation for the different techniques proposed in this thesis to improve the memory performance.

Thus, using the data locality analysis and based on the results obtained after analyzing the locality behavior of a set of programs, we propose to use this analysis in order to guide three different techniques: (i) management of multi-module caches, (ii) software prefetching for modulo scheduled loops, and (iii) instruction scheduling for clustered VLIW architectures.

The first use of the proposed data locality analysis is to manage a novel cache organization. This cache supports bypassing and/or is composed of different modules, each one oriented to exploit a particular type of locality. The main difference of this cache with respect to previous proposals is that the decision of caching or not, or in which module a new fetched block is allocated is managed by some bits in memory instructions (locality hints). These hints are set at compile time using the proposed locality analysis. Thus, the management complexity of this cache is kept low since no additional hardware is required. Results show that smaller caches with a smart management can perform as well as (or better than) bigger conventional caches.

We have also used the locality analysis to study the interaction between software pipelining and software prefetching. Software pipelining has been shown to be a very effective scheduling technique for loops (mainly in numerical applications for VLIW processors). The most popular scheme for software pipelining is called modulo scheduling. Many works on modulo scheduling can be found in the literature, but almost all of them make a critical assumption: they consider an optimistic behavior of the cache (in other words, they use the hit latency when a memory instruction is scheduled). Thus, the results they present ignore the effect of stalls due to dependences with memory instructions. In this part of the thesis we show that this assumption can lead to schedules whose performance is rather low when a real memory is considered. Thus, we propose an algorithm to schedule memory instructions in modulo scheduled loops. We have studied different software prefetching strategies and finally proposed an algorithm that performs prefetching based on the locality analysis and the shape of the loop dependence graph. Results obtained shows that the proposed scheme outperforms other heuristic approaches since it achieves a better trade-off between compute and stall time than the others. Finally, the last use of the locality analysis studied in this thesis is to guide an instruction scheduler for a clustered VLIW architecture. Clustered architectures are becoming a common trend in the design of embedded/DSP processors. Typically, the core of these processors is based on a VLIW design which partitionates both register file and functional units. In this work we go a step beyond and also make a partition of the cache memory. Then, both inter-register and inter-memory communications have to be taken into account. We propose an algorithm that performs both graph partition and instruction scheduling in a single step instead of doing it sequentially, which is shown to be more effective. This algorithm is improved by adding an analysis based on the cache miss equations in order to guide the scheduling of memory instructions in clusters with the aim of reducing not only inter-register communications, but also cache misses.

Future multi- and many- core processors are likely to have tens of cores arranged in a tiled architecture where each tile will house a processing core and a bank of the shared last-level cache. The physical distribution of tiles on the processor die gives rise to a Distributed Shared Cache (DSC) architecture where cache access latencies are non-uniform and depend on the physical distance between core and cache bank. In order to maximize cache capacity and favor design simplicity, the address space on a tiled processor is likely to be divided and mapped either statically or dynamically on to the distributed last-level cache such that each cache bank homes certain cache blocks. Given this architecture, an efficient OpenMP 3.0 task scheduler can minimize miss latencies by scheduling tasks on tiles whichare physically closer to the cache banks which home task-relevant data. This master thesis work deals with the design and implementation of a locality-aware user-level runtime OpenMP 3.0 task scheduler for a simulated tiled multicore architecture. Guided by programmer hints, the scheduler extracts locality information pertaining to the data referenced by a task and schedules the task accordingly on the core closest to the L2 slice homing the largest amount of data. Initial results of performance comparison against a work-first randomized work-stealing cilk-like scheduler and a breadth-first randomized work-stealing scheduler have revealed problems with the locality-aware scheduler and have created ground for deeper exploration in the areas of programmer locality characterization and feedback-based extraction of locality information.

The speed of processors increases much faster than the memory access time. This makes memory accesses expensive. To meet this problem, cache hierarchies are introduced to serve the processor with data. However, the effectiveness of caches depends on the amount of locality in the application's memory access pattern. The behavior of various programs differs greatly in terms of cache miss characteristics, access patterns and communication intensity. Therefore a computer built for many different computational tasks potentially benefits from dynamically adapting to the varying needs of the applications. This thesis shows that a cc-NUMA multiprocessor with data migration and replication optimizations efficiently exploits the temporal locality of algorithms. The performance of the self-optimizing system is similar to a system with a perfect initial thread and data placement. Data locality optimizations are not for free. Large cache line coherence protocols improve spatial locality but yield increases in false sharing misses for many applications. Prefetching techniques that reduce the cache misses often lead to increased address and data traffic. Several techniques introduced in this thesis efficiently avoid these drawbacks. The bundling technique reduces the coherence traffic in multiprocessor prefetchers. This is especially important in snoop-based systems where the coherence bandwidth is a scarce resource. Bundled prefetchers manage to reduce both the cache miss rate and the coherence traffic compared with non-prefetching protocols. The most efficient bundled prefetching protocol studied, lowers the cache misses by 27 percent and the address snoops by 24 percent relative to a non-prefetching protocol on average for all examined applications. Another proposed technique, capacity prefetching, avoids false sharing misses by distinguishing between cache lines involved in communication from non-communicating cache lines at run-time.

Since the beginning of the 20th century, much time and effort has been invested in the search for a theory of quantum gravity. While this provided a myriad of possibilities, it has so far failed to find a definitive answer. Here we take an alternative approach: instead of constructing a theory of quantum gravity and examining its low energy limit, we start with the conventional theory and ask what are the first deviations induced by a possible quantization of gravity. It is proposed that in this limit quantum gravity, whatever the ultimate theory might be, manifests itself as non-locality. In this thesis are explored two different approaches to effective theories. In the first, it is demonstrated how combining quantum field theory with general relativity naturally gives rise to non-locality. This is explored in the context of inflation, a natural place to look for high energy phenomena. By considering a simple scalar field theory, it is shown how non-locality results in higher dimensional operators and what the effects are on inflationary models. The second approach looks at a theory which naturally incorporates a minimal scale. Noncommutative geometry parallels the phase space or deformation quantization approach of quantum mechanics. It supposes that at short scales, the structure of spacetime is algebraic rather than geometric. In the first instance, we follow the first section and look at cosmological implications by replacing normal scalar theory with its noncommutative counterpart. In the second, we take a step back and examine the implications of quantization on the differential geometry. The formalism is developed and applied to generic spherically symmetric spacetimes where it is shown that to first order in deformation, the quantization is unique.

Thesis: Ph. D. in Cognitive Science, Massachusetts Institute of Technology, Department of Brain and Cognitive Sciences, 2017.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 189-211).
I explore the hypothesis that the universal properties of human languages can be explained in terms of efficient communication given fixed human information processing constraints. I argue that under short-term memory constraints, optimal languages should exhibit information locality: words that depend on each other, both in their interpretation and in their statistical distribution, should be close to each other in linear order. The informationtheoretic approach to natural language motivates a study of quantitative syntax in Chapter 2, focusing on word order flexibility. In Chapter 3, I show comprehensive corpus evidence from over 40 languages that word order in grammar and usage is shaped by working memory constraints in the form of dependency locality: a pressure for syntactically linked words to be close. In Chapter 4, I develop a new formal model of language processing cost, called noisy-context surprisal, based on rational inference over noisy memory representations. This model unifies surprisal and memory effects and derives dependency locality effects as a subset of information locality effects. I show that the new processing model also resolves a long-standing paradox in the psycholinguistic literature, structural forgetting, where the effects of memory appear to be language-dependent. In the conclusion I discuss connections to probabilistic grammars, endocentricity, duality of patterning, incremental planning, and deep reinforcement learning.
by Richard Landy Jones Futrell.
Ph. D. in Cognitive Science

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.B.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 18).
We obtain improved running times for two algorithms for clustering data: the expectation-maximization (EM) algorithm and Lloyd's algorithm. The EM algorithm is a heuristic for finding a mixture of k normal distributions in Rd that maximizes the probability of drawing n given data points. Lloyd's algorithm is a special case of this algorithm in which the covariance matrix of each normally-distributed component is required to be the identity. We consider versions of these algorithms where the number of mixture components is inferred by assuming a Dirichlet process as a generative model. The separation probability of this process, [alpha], is typically a small constant. We speed up each iteration of the EM algorithm from O(nd2k) to O(ndk log 3(k/a))+nd 2 ) time and each iteration of Lloyd's algorithm from O(ndk) to O(nd(k/a). 39) time.
by Shaunak Kishore.
S.B.
M.Eng.

This thesis considers the extent to which the BBC, arguably the nation’s most important cultural institution, attempted to meet its commitment to regional and local broadcasting in one English region, Yorkshire, between 1945 and 1990. The study focuses specifically on the extent to which a distinctive regional culture can be identified within the BBC in Yorkshire and how this changed over time while also considering how BBC programme makers both engaged with and represented the audience and the extent to which they attempted to foster place-related identity. The years 1945 to 1990 included the relaunching of English regional broadcasting at the end of World War Two, the arrival of television in the North and a redefinition of the BBC’s non-metropolitan broadcasting at the end of the 1960s with the creation of a new BBC television region based at Leeds and the launch of BBC local radio. Prior to, and then alongside, the establishment of these new services, Leeds-based producers working for the BBC North Region were bringing new voices in drama and entertainment to the attention of the nation. But by 1990 this period of relative regional autonomy and expansion had come to an end and producers of regional programmes had been told they were to focus on news and current affairs. An oral history approach has been employed alongside an analysis of programme material that concentrates on day-to-day local and regional broadcasting - programmes made in the region for the regional audience - going beyond the ‘texts’ to ask why these programmes were made and how they were made. Different aspects of programming are considered (regional television news and features, the early years of local radio) together with BBC cultures and practices.

With the increasing gap between the speeds of the processor and memory system, memory access has become a major performance bottleneck in modern computer systems. Recently, Symmetric Multi-Processor (SMP) systems have emerged as a major class of high-performance platforms. Improving the memory performance of Parallel applications with dynamic memory-access patterns on Symmetric Multi-Processors (SMP) is a hard problem. The solution to this problem is critical to the successful use of the SMP systems because dynamic memory-access patterns occur in many real-world applications. This dissertation is aimed at solving this problem.;Based on a rigorous analysis of cache-locality optimization, we propose a memory-layout oriented run-time technique to exploit the cache locality of parallel loops. Our technique have been implemented in a run-time system. Using simulation and measurement, we have shown our run-time approach can achieve comparable performance with compiler optimizations for those regular applications, whose load balance and cache locality can be well optimized by tiling and other program transformations. However, our approach was shown to improve significantly the memory performance for applications with dynamic memory-access patterns. Such applications are usually hard to optimize with static compiler optimizations.;Several contributions are made in this dissertation. We present models to characterize the complexity and present a solution framework for optimizing cache locality. We present an effective estimation technique for memory-access patterns to support efficient locality optimizations and information integration. We present a memory-layout oriented run-time technique for locality optimization. We present efficient scheduling algorithms to trade off locality and load imbalance. We provide a detailed performance evaluation of the run-time technique.

The path search problem considers a simple model of communication networks as channel graphs: directed acyclic graphs with a single source and sink. We consider each vertex to represent a switching point, and each edge a single communication line. Under a probabilistic model where each edge may independently be free (available for use) or blocked (already in use) with some constant probability, we seek to efficiently search the graph: examine (on average) as few edges as possible before determining if a path of free edges exists from source to sink. We consider the difficulty of searching various graphs under different search models, and examine the computational complexity of calculating the search cost of arbitrary graphs.

Graphics Processing Units (GPUs) run thousands of parallel threads and achieve high Memory Level Parallelism (MLP). To support high MLP, a structure called a Miss-Status Holding Register (MSHR) handles multiple in-flight miss requests. When multiple cores send requests to the same cache line, the requests are merged into one last level cache MSHR entry and only one memory request is sent to the Dynamic Random-Access Memory (DRAM). We call this inter-core locality. The main reason for inter-core locality is that multiple cores access shared read-only data within the same cache line. By prioritizing memory requests that have high inter-core locality, more threads resume execution. Many memory access scheduling policies have been proposed for general-purpose multi-core processors and GPUs. However, some of these policies do not consider the characteristic of GPUs and others do not utilize inter-core locality information. In this thesis, we analyze the reasons that inter-core locality exists and show that requests with more inter-core locality have a higher impact performance. To exploit inter-core locality, we enable the GPU DRAM controller to be aware of inter-core locality by using Level 2 (L2) cache MSHR information. We propose a memory scheduling policy to coordinate the last level cache MSHR and the DRAM controller. 1) We introduce a structure to enable the DRAM to be aware of L2 cache MSHR information. 2) We propose a memory scheduling policy to use L2 cache MSHR information. 3) To prevent starvation, we introduce age information to the scheduling policy. Our evaluation shows a 28% memory request latency reduction and an 11% performance improvement on the average for high inter-core locality benchmarks.
Applied Science, Faculty of
Electrical and Computer Engineering, Department of
Graduate

Value prediction is a speculative technique to break true data dependencies by predicting uncomputed values based on history. Previous research focused on exploiting two types of value locality (computation-based and context-based) in the local value history, which is the value sequence produced by the same instruction that is being predicted. Besides local value history, value locality also exists in global value history, which is the value sequence produced by all dynamic instructions according to their execution order. In this thesis, a new type of value locality, computational locality in global value history is studied. A prediction scheme, called gDiff, is designed to exploit one special and most common case of this computational model, the stride-based computation, in global value history. Experiments show that there exists very strong stride type of locality in global value sequences and ideally the gDiff predictor can achieve 73% prediction accuracy for all value producing instructions without any hybrid scheme, much higher than local stride and local context prediction schemes. However, the ability to realistically exploit locality in global value history is greatly challenged by the value delay issue, i.e., the correlated value may not be available when the prediction is being made. The value delay issue is studied in an out-of-order (OOO) execution pipeline model and the gDiff predictor is improved by maintaining an order in the value queue and utilizing local stride predictions when global values are unavailable to avoid the value delay problem. This improved predictor, called hgDiff, demonstrates 88% accuracy and 69% prediction coverage on average, outperforming a local stride predictor by 2% higher accuracy and 13% higher coverage.

In this dissertation, motivated both by our incomplete physical understanding, and by quantum information theory, we investigate quantum non-locality. In Chapter 2, we ask the question, which quantum states are non-local? We show that any entangled pure state is non-local, but that things are complicated with mixed states. In particular, following Werner’s local hidden variable model for projective measurements on a class of entangled states, we write down an extended model that works for arbitrary positive operator valued measurements performed by the separated observers. We also show that the existence of such a model for one particular quantum state implies the existence of a similar model for a wide class of other quantum states. Finally, we discuss the fact that some quantum states display a hidden non-locality, and describe a general classification scheme for the non-locality of quantum states. In Chapter 3, we turn to a particular protocol of quantum information theory, namely, quantum teleportation. We discuss the connections between quantum teleportation and non-locality. We drive a Bell-type inequality pertaining to the teleportation scenario and investigate when it is violated. We give an example of a situation in which a teleportation fidelity of ¾ is achieved without non-locality, even though this is greater than the classical limit of 2/3. In Chapter 4, we describe the experiments that have been performed as tests of quantum non-locality and the associated loopholes. We point out an assumption, the no-memory assumption that is common to nearly all analyses of Bell-type experiments, yet is not implied by locality. We remove the assumption and give a new analysis of the ideal case.

Non-local forces exist in nature for two reasons. First that the recent experiments on locality are supposed to be accurate enough. Second that there is no local theory that can reproduce all the predictions of orthodox quantum theory which, almost for about a century, have been proved to be correct experimentally again and again. This thesis concerns both of these. A brief discussion of the measurement in quantum theory is followed by two comments which show that the quantum description is frame dependent and that the collapse of the wave-function of a system may occur without the relevant measurement being performed. After this the Bohm model and a modified version of the Bohm model are described. Next we introduce a new method for obtaining the Bell-type inequalities which can be used for testing locality. We derive more inequalities by this method than obtained by other existing procedures. Using Projection Valued(PV) and Positive Operator Valued Measures(POVM) measurements we have designed experiments which violates one of the Bell inequalities by a larger factor than existing violations which in turn could increase the accuracy of experiments to test for non-locality. This is our first result. After discussing the non-locality and non-Lorentz invariant features of the Bohm model, its retarded version, namely Squires' model - which is local and Lorentz invariant - is introduced. A problem with this model, that is the ambiguity in the cases where the wave-function depends on time, is removed by using the multiple-time wave-function. Finally, we apply the model to one of the experiments of locality and prove that it is in good agreement with the orthodox quantum theory.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Linguistics and Philosophy, 1988.
M.I.T. copy lacks leaves 67, 105, 106, 107, 204, 206, 209, 218, 240, 241, and 245. Vita.
Includes bibliographical references (leaves 296-306).
by Amy Sara Weinberg.
Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Linguistics and Philosophy, 2004.
Includes bibliographical references (p. 155-158).
In this thesis I demonstrate that a simplified theory of locality \ has greater success in accounting for locality in movement than more complicated alternatives that have been suggested. In particular, I argue that closeness should not be relativized to minimal domains, and that locality in movement follows from restrictions on Agree, but not on Move itself. Data is drawn from Locative Inversion in English, passivization in ditransitive verb phrases and constructions which involve movement to multiple specifiers of a single head. I show that the constructions that have previously been claimed to necessitate the notion of equidistance do not in fact provide motivation for this concept. Instead, further investigation of these constructions actually provides evidence for the elimination of equidistance from the grammar. I further argue that movement past a existing specifier to a higher specifier of the same head is grammatical, and that data which has been argued to show that this movement is prohibited can be given another analysis. This follows if Move, in contrast to Agree, is not subject to locality constraints. The streamlined theory of locality proposed here therefore ultimately accounts for a wider body of data than any of the more complicated alternatives.
by Teal Bissell Doggett.
Ph.D.

The rampant success of quantum theory is the result of applications of the 'new' quantum mechanics of Schrödinger and Heisenberg (1926-7), the Feynman-Schwinger-Tomonaga Quantum Electrodynamics (1946-51), the electro-weak theory of Salaam, Weinberg, and Glashow (1967-9), and Quantum Chromodynamics (1973-); in fact, this success of `the' quantum theory has depended on a continuous stream of brilliant and quite disparate mathematical formulations. In this carefully concealed ferment there lie plenty of unresolved difficulties, simply because in churning out fabulously accurate calculational tools there has been no sensible explanation of all that is going on. It is even argued that such an understanding is nothing to do with physics. A long-standing and famous illustration of this is the paradoxical thought-experiment of Einstein, Podolsky and Rosen (1935). Fundamental to all quantum theories, and also their paradoxes, is the location of sub-microscopic objects; or, rather, that the specification of such a location is fraught with mathematical inconsistency. This project encompasses a detailed, critical survey of the tangled history of Position within quantum theories. The first step is to show that, contrary to appearances, canonical quantum mechanics has only a vague notion of locality. After analysing a number of previous attempts at a `relativistic quantum mechanics', two lines of thought are considered in detail. The first is the work of Wan and students, which is shown to be no real improvement on the usual `nonrelativistic' theory. The second is based on an idea of Dirac's - using backwards-in-time light-cones as the hypersurface in space-time. There remain considerable difficulties in the way of producing a consistent scheme here. To keep things nicely stirred up, the author then proposes his own approach - an adaptation of Feynman's QED propagators. This new approach is distinguished from Feynman's since the propagator or Green's function is not obtained by Feynman's rule. The type of equation solved is also different: instead of an initial-value problem, a solution that obeys a time-symmetric causality criterion is found for an inhomogeneous partial differential equation with homogeneous boundary conditions. To make the consideration of locality more precise, some results of Fourier transform theory are presented in a form that is directly applicable. Somewhat away from the main thrust of the thesis, there is also an attempt to explain the manner in which quantum effects disappear as the number of particles increases in such things as experimental realisations of the EPR and de Broglie thought experiments.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-06-29T11:57:33Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) template.pdf: 1023711 bytes, checksum: bb469b82eb53b63f6e13f942f61ae867 (MD5)
Made available in DSpace on 2016-06-29T11:57:33Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) template.pdf: 1023711 bytes, checksum: bb469b82eb53b63f6e13f942f61ae867 (MD5) Previous issue date: 2014-08-14
CNPq
As fun c~oes de Bell s~ao conhecidas pelo papel central desempenhado na caracteriza c~ao da n~ao localidade da teoria qu^antica. Usualmente s~ao empregadas na quanti ca c~ao do grau de n~ao localidade de sistemas qu^anticos espec cos atrav es do calculo do seu valor m aximo entre todos os poss veis estados e con gura c~oes associadas aos detectores. No entanto, embora dois estados qu^anticos tenham diferentes \densidades de con gura c~ao n~ao local"( Estados com diferentes contribui c~oes de con gura c~oes associadas aos detectores que geram n~ao localidade), se eles possuem o mesmo valor do m aximo da fun c~ao de Bell, ent~ao s~ao considerados igualmente n~ao locais. Usando este crit erio, Ac n et al. (Phys. Rev. A 65, 052325, 2002) encontraram que para qunits (Estados de sistemas qu^anticos conjuntos d-dimensionais), o estado maximamente emaranhado n~ao corresponde ao estado maximamente n~ao local, fato que e considerado como uma anomalia da n~ao localidade da teoria qu^antica (M ethot & Scarani; Quant. Inf. Comput. 7, 157, 2008). A m de resolver o problema da anomalia, nesta disserta c~ao e proposta uma medida do grau de n~ao localidade, na qual s~ao tomadas em conta todas as contribui c~oes de con- gura c~oes dos detectores que geram n~ao localidade do estado. Tal medida e proporcional a integral da fun c~ao de Bell na regi~ao de viola c~ao, no espa co dos par^ametros que caracterizam as con gura c~oes (Em geral ^angulos relativos entre orienta c~oes dos detectores). Foi calculado o grau de n~ao localidade de v arios sistemas de dois e tr^es n veis, com e sem uma contribui c~ao de ru do qu^antico ao estado, usando tr^es tipos de desigualdades de Bell: A desigualdade na vers~ao original, a desigualdade CHSH e a desigualdade GCLMP (Ac n et al. 2002). Em todos os casos estudados foi observada concond^ancia entre o estado maximamente emaranhado e o estado maximamente n~ao local, resolvendo assim o problema da anomalia da n~ao localidade.
Bell functions are known by the central role played on the characterization of non-locality in quantum theory. They are often used in the quanti cation of the non-locality strength for speci c quantum systems by calculating their maximum among all possible states and detector's con gurations. However, even if two quantum states present di erent \nonlocal density con gurations"(States with di erent contributions of detector con gurations that generate non-locality), if these display the same value for the maximum of Bell function, then they are considered equally non-local. Making use of this criteria, Ac n et al. (Phys. Rev. A 65, 052325, 2002) found that for qunits (Joint states of d-dimensional quantum systems), the maximally entangled state does not match with the maximally non-local state, this is known as an anomaly of quantum non-locality (M ethot & Scarani; Quant. Inf. Comput. 7, 157, 2008). In order to solve the anomaly problem, in this dissertation it is proposed a nonlocality strength measure in which the whole contributions of detector's con gurations that give rise to non-locality are taken into account. Such a measure is proportional to the Bell function integration over the violation region on the space of the parameters that characterize the detector's con guration (Usually, relative angles between orientations of detectors). The non-locality strength was calculated for several two and three-level bipartite systems, with and without a contribution of white noise to the whole state of the system, by using three kinds of Bell inequalities: Bell inequality in its original version, CHSH inequality and GCLMP inequality (Ac n et al. 2002). In all the cases, it was observed agreement between maximally entangled states and maximally non-local ones, thus solving the problem of anomaly of non-locality.

The development and optimisation of programs through search is a growing application area for computational intelligence techniques. Evolution-inspired search heuristics, such as genetic programming, provide methods for autonomously generating programs within the constraints of a program representation. Genetic programming is a machine learning approach to producing programs represented using executable or interpreted structures. However, despite theoretical advances, choosing a suitable representation remains a basic concern for designers. Choice of representation affects search space size, structure and accessible solutions, as well as engineering considerations such as ease of implementation. Locality is a property of evolutionary search spaces derived from the representation and search operators, that relates genotype and phenotype distances. The interaction between search space locality and search performance under different representations is not well understood. The objective of this thesis is to broaden the present understanding of locality to encompass more complex representations, for example graphs and grammars, as well as non-traditional coevolutionary approaches. This thesis presents four main original contributions. Firstly, a statistical approach to measuring locality is defined that incorporates the Mantel test, a method adapted from numerical ecology. The method is assessed empirically in a series of case studies over two established forms of genetic programming, Grammatical Evolution and Cartesian Genetic Programming. Secondly, a new approach to visualising locality is provided. The technique uses force-layout algorithms derived from the field of graph-drawing to construct fitness landscapes in genetic programming. The technique is applied to produce visualisations that demonstrate structural characteristics across regions of the search space. Thirdly, the effect of locality on performance is assessed in model coevolutionary problems. A framework to analyse performance in a coevolutionary context is provided, followed by an examination of the response to locality and coupled algorithm parameters. The final contribution explores the interaction between locality and two `pathological' dynamics in coevolutionary algorithms, disengagement and cycling. The analysis demonstrates that locality can influence the likelihood of coevolutionary pathologies, when using executable representations. Results are provided for new constructed problems and a coevolutionary pursuit and evasion task. In the conclusions, directions for future analysis of the role of locality in evolutionary search are considered, as well as the relationship between these findings and other outstanding general issues in the field of genetic programming.

Designing on-premise hardware platforms to deal with big data analytics should be done in a way in which the available resources can be scaled both up and down depending on future needs. Two of the main components of an analytics cluster is the data storage and computational part. Separating those two components yields great value but can come with the price of performance loss if not set up properly. The objective of this thesis is to examine how much the performance gets impacted when the computational and storage part gets divided into different hardware nodes. To get data on how well this separation could be done, several tests were conducted on different hardware setups. These tests included real-world workloads run on configurations where both the storage and the computation took place on the same nodes and on configurations where these components were separated. While those tests were done on a smaller scale with only three compute nodes parallel, tests with similar workloads were also conducted on a larger scale with up to 32 computational nodes. The tests revealed that separating compute from storage on a smaller scale could be done without any significant performance drawbacks. However,when the computational components grew large enough,bottlenecks in the storage cluster surfaced. While the results on a smaller scale were satisfactory,further improvements could be made for the larger-scale tests.

Today's processors commonly use caches to help overcome the disparity between processor and main memory speeds. Due to the principle of locality, most of the processor's requests for data are satisfied by the fast cache memory, resulting in a signficant performance improvement. Methods for evaluating workloads and caches in terms of locality are valuable for cache design. In this dissertation, we present a locality surface which displays both temporal and spatial locality on one three-dimensional graph. We provide a solid, mathematical description of locality data and equations for visualization. We then use the locality surface to examine the locality of a variety of workloads from the SPEC CPU 2000 benchmark suite. These surfaces contain a number of features that represent sequential runs, loops, temporal locality, striding, and other patterns from the input trace. The locality surface can also be used to evaluate methodologies that involve locality. For example, we evaluate six synthetic trace generation methods and find that none of them accurately reproduce an original trace's locality. We then combine a mathematical description of caches with our locality definition to create cache characterization surfaces. These new surfaces visually relate how references with varying degrees of locality function in a given cache. We examine how varying the cache size, line size, and associativity affect a cache's response to different types of locality. We formally prove that the locality surface can predict the miss rate in some types of caches. Our locality surface matches well with cache simulation results, particularly caches with large associativities. We can qualitatively choose prudent values for cache and line size. Further, the locality surface can predict the miss rate with 100% accuracy for some fully associative caches and with some error for set associative caches. One drawback to the locality surface is the time intensity of the stack-based algorithm. We provide a new parallel algorithm that reduces the computation time significantly. With this improvement, the locality surface becomes a viable and valuable tool for characterizing workloads and caches, predicting cache simulation results, and evaluating any procedure involving locality.

Thesis (Ph. D.) -- University of Maryland, College Park, 2004.
Thesis research directed by: Linguistics. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Massively parallel processing devices, like Graphics Processing Units (GPUs), have the ability to accelerate highly parallel workloads in an energy-efficient manner. However, executing irregular or less tuned workloads poses performance and energy-efficiency challenges on contemporary GPUs. These inefficiencies come from two primary sources: ineffective management of locality and decreased functional unit utilization. To decrease these effects, GPU programmers are encouraged to restructure their code to fit the underlying hardware architecture which affects the portability of their code and complicates the GPU programming process. This dissertation proposes three novel GPU microarchitecture enhancements for mitigating both the locality and utilization problems on an important class of irregular GPU applications. The first mechanism, Cache-Conscious Warp Scheduling (CCWS), is an adaptive hardware mechanism that makes use of a novel locality detector to capture memory reference locality that is lost by other schedulers due to excessive contention for cache capacity. On cache-sensitive, irregular GPU workloads, CCWS provides a 63% speedup over previous scheduling techniques. This dissertation uses CCWS to demonstrate that improvements to the hardware thread scheduling policy in massively multithreaded systems offer a promising new design space to explore in locality management. The second mechanism, Divergence-Aware Warp Scheduling (DAWS), introduces a divergence-based cache footprint predictor to estimate how much L1 data cache capacity is needed to capture locality in loops. We demonstrate that the predictive, pre-emptive nature of DAWS can provide an additional 26% performance improvement over CCWS. This dissertation also demonstrates that DAWS can effectively shift the burden of locality management from software to hardware by increasing the performance of simpler and more portable code on the GPU. Finally, this dissertation details a Variable Warp-Size Architecture (VWS) which improves the performance of irregular applications by 35%. VWS improves irregular code by using a smaller warp size while maintaining the performance and energy-efficiency of regular code by ganging the execution of these smaller warps together in the warp scheduler.
Applied Science, Faculty of
Electrical and Computer Engineering, Department of
Graduate

The growing gap between processor clock speed and DRAM access time puts new demands on software and development tools. Deep memory hierarchies and high cache miss penalties in present and emerging computer systems make execution time sensitive to data locality. Therefore, developers of performance-critical applications and optimizing compilers must be aware of data locality and maximize cache utilization to produce fast code. To aid the optimization process and help understanding data locality, we need methods to analyze programs and pinpoint poor cache utilization and possible optimization opportunities. Current methods for run-time analysis of data locality and cache behavior include functional cache simulation, often combined with set sampling or time sampling, other regularity metrics based on strides and data streams, and hardware monitoring. However, they all share the trade-off between run-time overhead, accuracy and explanatory power. This thesis presents methods to efficiently analyze data locality at run time based on cache modeling. It suggests source-interdependence profiling as a technique for examining the cache behavior of applications and locating source code statements and/or data structures that cause poor cache utilization. The thesis also introduces a novel statistical cache-modeling technique, StatCache. Rather than implementing a functional cache simulator, StatCache estimates the miss ratios of fully-associative caches using probability theory. A major advantage of the method is that the miss ratio estimates can be based on very sparse sampling. Further, a single run of an application is enough to estimate the miss ratio of caches of arbitrary sizes and line sizes and to study both spatial and temporal data locality.