Randomized two-process wait-free test-and-set

Summary. We present the first explicit, and currently simplest, randomized algorithm for two-process wait-free test-and-set. It is implemented with two 4-valued single writer single reader atomic variables. A test-and-set takes at most 11 expected elementary steps, while a reset takes exactly 1 elementary step. Based on a finite-state analysis, the proofs of correctness and expected length are compressed into one table. Received: June 1991 / Accepted: March 2002     

Randomized naming using wait-free shared variables

A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For processes and , the protocol uses a name space of size and running time (read/writes to shared bits) with probability at least , and overall expected running time. The protocol is based on the wait-free implementation of a novel -Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least in the face of the strongest possible adaptive adversary. Received: September 1994 / Accepted: January 1998     

Using wait-free synchronization in the design of distributed applications

Wait-free synchronization has been recognized in the literature as an effective concurrent programming technique. The concurrent programming community, however, has been slow to adopt this technique. This paper addresses the practical application of wait-free synchronization in the design of distributed applications. In this paper, we present an implementation of a server that uses wait-free synchronization. The resulting code is more easily seen to be fault tolerant. The performance analysis of the wait-free synchronization server outperformed a server that uses traditional locking techniques. This practical demonstration of the benefits of wait-free synchronization should help foster its adoption in the development of distributed applications.     

On the use of registers in achieving wait-free consensus

Summary.  The computational power of concurrent data types has been the focus of much recent research. Herlihy showed that such power may be measured by the type’s ability to implement wait-free consensus. Jayanti argued that this ability could be measured in different ways, depending, for example, on whether or not read/write registers could be used in an implementation. He demonstrated the significance of this distinction by exhibiting a nondeterministic type whose ability to implement consensus was increased with the availability of registers. We show that registers cannot increase the ability to implement wait-free consensus of any deterministic type or of any type that can, without them, implement consensus for at least two processes. These results significantly impact the study of the wait-free hierarchies of concurrent data types. In particular, the combination of these results with other recent work suggests that Jayanti’s h _m hierarchy is robust for certain classes of deterministic types.     

Using local-spin k-exclusion algorithms to improve wait-free object implementations

Summary.  We present the first shared-memory algorithms for k-exclusion in which all process blocking is achieved through the use of “local-spin” busy waiting. Such algorithms are designed to reduce interconnect traffic, which is important for good performance. Our k-exclusion algorithms are starvation-free, and are designed to be fast in the absence of contention, and to exhibit scalable performance as contention rises. In contrast, all previous starvation-free k-exclusion algorithms require unrealistic operations or generate excessive interconnect traffic under contention. We also show that efficient, starvation-free k-exclusion algorithms can be used to reduce the time and space overhead associated with existing wait-free shared object implementations, while still providing some resilience to delays and failures. The resulting “hybrid” object implementations combine the advantages of local-spin spin locks, which perform well in the absence of process delays (caused, for example, by preemptions), and wait-free algorithms, which effectively tolerate such delays. We present performance results that confirm that this k-exclusion-based technique can improve the performance of existing wait-free shared object implementations. These results also show that lock-based implementations can be susceptible to severe performance degradation under multiprogramming, while our hybrid implementations are not. Received: December 1995 / Accepted: February 1997     

Locality in structured peer-to-peer networks

Distributed hash tables (DHTs), used in a number of structured peer-to-peer (P2P) systems, provide efficient mechanisms for resource placement and location. A key distinguishing feature of current DHT systems, such as Chord, Pastry, CAN and Tapestry, is the way they handle locality in the underlying network. Topology-based node identifier assignment, proximity routing, and proximity neighbor selection are examples of heuristics used to minimize message delays in the underlying network. While these heuristics are sometimes effective, they all rely on a single global overlay that may install the key of a popular object at a node far from most of the nodes accessing it. Furthermore, a response to a lookup message does not contain any locality information about the nodes holding a copy of the object. We address these issues in Plethora, a novel two-level overlay P2P network. A local overlay in Plethora acts as a locality-aware cache for the global overlay, grouping nodes close together in the underlying network. Local overlays are constructed by exploiting the organization of the Internet into autonomous systems (ASs). We present a detailed experimental study that demonstrates performance gains in response time of up to 60% compared to a single global Pastry overlay. We also present efficient distributed algorithms for maintaining local overlays in the presence of node arrivals and departures.     

Modeling Communication Locality in Multiprocessors

Locality of reference is an important aspect of many computer operations. It is often exploited to optimize the performance of computer functions. In this paper, we apply the locality concept to the communication patterns of parallel programs operating over an interconnection network with a fixed communication latency between any pair of attached nodes. Unbuffered multistage networks and all-optical networks are examples of these. We quantify the notions of spatial and temporal locality in this context, and combine them in a locality measure. This measure is used as the basis for identifying the communication working sets of a parallel program. We focus on programs with a looping structure and investigate conditions under which each working set consists of the complete set of paths required by a single loop.     

Computationalism and the Locality Principle

Computationalism, a specie of functionalism, posits that a mental state like pain is realized by a ‘core’ computational state within a particular causal network of such states. This entails that what is realized by the core state is contingent on events remote in space and time, which puts computationalism at odds with the locality principle of physics. If computationalism is amended to respect locality, then it posits that a type of phenomenal experience is determined by a single type of computational state. But a computational state, considered by itself, is of no determinate type—it has no particular symbolic content, since it could be embedded in any of an infinite number of algorithms. Hence, if locality is respected, then the type of experience that is realized by a computational state, or whether any experience at all is realized, is under-determined by the computational nature of the state. Accordingly, Block’s absent and inverted qualia arguments against functionalism find support in the locality principle of physics. If computationalism denies locality to avoid this problem, then it cannot be considered a physicalist theory since it would entail a commitment to phenomena, like teleological causation and action-at-a-distance, that have long been rejected by modern science. The remaining theoretical alternative is to accept the locality principle for macro events and deny that formal, computational operations are sufficient to realize a phenomenal mental state.     

Locality Preserving Matching

International Journal of Computer Vision - Seeking reliable correspondences between two feature sets is a fundamental and important task in computer vision. This paper attempts to remove mismatches...     

Locality and Information Transfer in Quantum Operations

We investigate the situation in which no information can be transferred from a quantum system B to a quantum system A, even though both interact with a common system C.PACS:03.67.-a, 03.65.Ud     

Introducing Locality and Softness in Subspace Classification

Subspace classifiers classify a pattern based on its distance from different vector subspaces. Earlier models of subspace classification were based on the assumption that individual classes lie in unique subspaces. In later extensions, locality was introduced into subspace classification allowing for a class to be associated with more than one sub manifold. The local subspace classifier is thus a piecewise linear classifier, and is more powerful when compared to the linear classification performed by global subspace methods. We present extensions to the basic subspace method of classification based on introducing locality and softness in the classification process. Locality is introduced by (subspace) clustering the patterns into clusters, and softness is introduced by allowing a pattern to be associated with more than one cluster. Our motivation for introducing both locality and softness is based on the premise that by introducing locality, it is possible to reduce the bias though at the cost of a possible increase in variance. By introducing softness (or aggregation), the variance can be reduced. Consequently, by introducing both locality and softness, we avoid the possibility of high variance that locality typically introduces. We derive appropriate algorithms to construct a local and soft model of subspace classifiers and present results obtained with the proposed algorithm. Received: 4 November 1998?Received in revised form: 7 December 1998?Accepted: 7 December 1998     

Locality pursuit embedding

Dimensionality reduction techniques are widespread in pattern recognition research. Principal component analysis, as one of the most popular methods used, is optimal when the data points reside on a linear subspace. Nevertheless, it may fail to preserve the local structure if the data reside on some nonlinear manifold, which is indisputably important in many real applications, especially when nearest-neighbor search is involved. In this paper, we propose locality pursuit embedding, a linear algorithm that arises by solving a variational problem. It produces a linear embedding that respects the local geometrical structure described by the Euclidean distances. Some illustrative examples are presented along with applications to real data sets.     

Refactoring for Data Locality

Suggestions for locality optimizations (SLO), a cache profiling tool, analyzes runtime reuse paths to find the root causes of poor data locality, and suggests the most promising code optimizations. Refactoring using the hints of the SLO analyzer doubles the average execution speed of several SPEC2000 benchmark programs.     

Locality of Reference in Hierarchical Database Systems

Localized information referencing is a long-known and much-exploited facet of program behavior. The existence of such behavior in the data accessing patterns produced by database management systems is not currently supported by empirical results. We present experimental results which demonstrate that in certain environments and under certain important applications, locality of reference is an undeniable characteristic of the information accessing behavior of a hierarchical database management system. Furthermore, database locality of reference is in a sense more regular, predictable, and hence, more exploitable than the localized reference activity found in programs in general. The implications of these results for the performance enhancement and workload characterization of database management systems are discussed.     

FORALL实现过程中的局部性优化

FORALL结构是FORTRAN 95的一种语法,在编译器中高效地实现FORALL结构是一项富有挑战性的工作,局部性优化对其高效实现尤其重要。本文介绍作者在G95编译器中实现FOR ALL结构时用到的两种局部性优化方法--临时空间合并和嵌套循环排序。实验结果表明,局部性优化对提高FORALL结构的性能非常有效。对某类FORALL结构,与Intel的EFC 编译器相比,我们的实现方法能提高30％的性能。     

无参数局部保持投影及人脸识别

局部保持投影(LPP)通过构造近邻图来保持样本的局部结构,在构图过程中,LPP面临复杂的参数选择问题.为解决此问题,提出无参数局部保持投影(PLPP)算法.首先设计一种无参数的构图方法,能够动态地获取样本的近邻点并配置相应的边权.其次,利用该构图方法,PLPP通过寻求最佳投影矩阵,用于保持样本在低维空间的局部结构.由于PLPP在构图过程中并未设置任何参数且采用余弦距离设置边权,因此PLPP计算更加方便快捷且对离群样本更具鲁棒性.另外,为进一步提升PLPP的识别性能,在PLPP的基础上通过加入样本的类别信息,提出监督的无参数局部保持投影算法(SPLPP).最后,在ORL、FERET及AR人脸库上的实验验证了PLPP与SPLPP的有效性.     

网格局部性及其优化研究

数据网格已逐步在科学研究领域得到应用.提高数据网格的性能以适应分布式数据管理已经成为研究数据网格的一个热点.提出了网格局部性的概念,分析了网格局部性对数据网格性能的影响,并从增强网格局部性的角度对数据网格的性能进行优化,提出了综合跳一扩散副本替换策略(jump-DRP)和参考生物外激素的任务调度策略(JARIP).实验结果表明,考虑了网格局部性因素的jump-DRP与JARIP的策略组合提高了网格平台的任务处理性能,并对各类应用背景及任务的复杂程度具有鲁棒性.     

Data-Centric Transformations for Locality Enhancement

On modern computers, the performance of programs is often limited by memory latency rather than by processor cycle time. To reduce the impact of memory latency, the restructuring compiler community has developed locality-enhancing program transformations such as loop permutation and tiling. These transformations work well for perfectly nested loops (loops in which all assignment statements are contained in the innermost loop), but their performance on codes such as matrix factorizations that contain imperfectly nested loops leaves much to be desired. In this paper, we propose an alternative approach called data-centric transformation. Instead of reasoning directly about the control structure of the program, a compiler using the data-centric approach chooses an order for the arrival of data elements in the cache, determines what computations should be performed when that data arrives, and generates the appropriate code. At runtime, program execution will automatically pull data into the cache in an order that corresponds approximately to the order chosen by the compiler; since statements that touch a data structure element are scheduled close together, locality is improved. The idea of data-centric transformation is very general, and in this paper, we discuss a particular transformation called data-shackling. We have implemented shackling in the SGI MIPSPro compiler which already has a sophisticated implementation of control-centric transformations for locality enhancement. We present experimental results on the SGI Octane comparing the performance of the two approaches, and show that for dense numerical linear algebra codes, data-shackling does better by factors of two to five.     

程序局部性的量化分析

给出与平台无关的局部性量化方法,从空间局部性和时间局部性2个角度,量化SPEC2000测试基准程序,以及这些程序的数据段、代码段和堆栈段。时间和空间局部性组成的二维局部性分布直观地展示了基准测试程序的局部性。实验结果表明,程序数据局部性主要由堆段的局部性决定,堆段的局部性最差,栈的局部性最优。