Fault-tolerant distributed shared memory on a broadcast-based architecture

Due to advances in fiber-optics and VLSI technology, interconnection networks that allow multiple simultaneous broadcasts are becoming feasible. Distributed-shared-memory implementations on such networks promise high performance even for applications with small granularity. This paper presents the architecture of one such implementation, called the simultaneous optical multiprocessor exchange bus, and examines the performance of augmented DSM protocols that exploit the natural duplication of data to maintain a recovery memory in each processing node and provide basic fault tolerance. Simulation results show that the additional data duplication necessary to create fault-tolerant DSM causes no reduction in system performance during normal operation and eliminates most of the overhead at checkpoint creation. Under certain conditions, data blocks that are duplicated to maintain the recovery memory are utilized by the underlying DSM protocol, reducing network traffic, and increasing the processor utilization significantly.     

Performance improvement of parallel programs on a broadcast-based distributed shared memory multiprocessor by simulation

Due to advances in fiber optics and VLSI technology, interconnection networks that allow simultaneous broadcasts are becoming feasible. Distributed shared memory (DSM) implementations on such networks promise high performance even for small applications with small granularity. This paper, after summarizing the architecture of one such implementation called the Simultaneous Multiprocessor Optical Exchange Bus (SOME-Bus), presents simple algorithms for improving the performance of parallel programs running on the SOME-Bus multiprocessor implementing cache-coherent DSM. The algorithms are based on run-time data redistribution via dynamic page migration protocol. They use memory access references together with the information of average channel utilization, average channel waiting time, number of messages in the channel queue or short-term average channel waiting time reported by each node and gathered by hardware monitors to make correct decisions related to the placement of shared data. Simulations with four parallel codes on a 64-processor SOME-Bus show that the algorithms yield significant performance improvements such as reduction in the execution times, number of remote memory accesses, average channel waiting times, average network latencies and increase in average channel utilizations.     

Two examples of virtual records

This paper contains an introduction to virtual records. Two examples of virtual record implementations are described in detail, and six other implementations are described briefly. The main purpose of virtual records is to reduce the effect on existing programs of changes in record content and format. The value of virtual records in this context is examined.     

Resolving cyclic dependencies between packages with enriched dependency structural matrix

Dependency structural matrix (DSM) is an approach originally developed for process optimization. It has been successfully applied to identify software dependencies among packages and subsystems. A number of algorithms have been proposed to compute the matrix so that it highlights patterns and problematic dependencies between subsystems. However, existing DSM implementations often miss important information to fully support reengineering effort. For example, they do not clearly qualify and quantify problematic relationships, information that is crucial to support remediation tasks. We propose enriched DSM (eDSM), which provides small‐multiple views and micro–macro‐readings by adding fine‐grained information in each cell of the matrix. Each cell is enriched with contextual information about (i) the type of dependencies (inheritance, class reference, etc.), (ii) the proportion of referencing entities, and (iii) the proportion of referenced entities. We distinguish independent cycles and stress potentially simple fixes for cycles by using coloring information. This work is language independent and has been implemented on top of the Moose software analysis platform. In this paper, we expand our previous work. We improved the cell content information view on the basis of user feedback and performed multiple validations: two different case studies on Moose and Seaside software; one user study for validating eDSM as a usable approach for developers. Solutions to problems identified with eDSM have been performed and retrofitted in analyzed software. Copyright © 2012 John Wiley & Sons, Ltd.     

Supporting flexible data distribution in software DSMs

Page-based software DSM systems suffer from false sharing caused by the large sharing granularity,and only support one-dimension Block or Cyclicblock data distribution schemes,Thus applications running on them will suffer from poor data locality and will be able to exploit parallelism only when using a large number of processors,In this paper.a way towards supporting flexible data distribution(FDD) on software DSM system is presented.Small granularity-tunable blocks,the size of which can be set by compiler or programmer,are used to overlap the working data sets distributed among processors.The FDD was implmented on a software DSM system called JIAJIA.Compared with Block/Cyclic-block distribution schemes used by most DSM systems now,experiments show that the proposed way of flexible data distribution is more effective.The performance of the applications used in the experiments is significantly improved.     

多核处理器中混合分布式共享存储空间的实时划分技术

在多核处理器芯片中,分布式共享存储DSM虽然提供了统一的全局寻址的存储空间,但却引入了虚地址向实地址转换的开销,这对性能产生了负面的影响。我们注意到,在并行程序的执行过程中,被处理的数据属性(私有或共享)并不是一成不变的。并行程序中不同的数据具有不同的属性,即使同一数据在程序的不同执行阶段也可能具有不同的属性。本文首先详细地阐述了一种混合式的分布式共享存储空间,支持对共享数据采用全局寻址的虚地址访问而对私有数据采用快速寻址的实地址访问;进而提出了一种针对混合式的分布式共享存储空间的实时划分技术。该技术根据并行程序中数据的属性,在程序运行时,实时地调整和划分分布式共享存储空间。当数据为私有时,通过实地址访问加快数据的访问速度,当数据为共享时则维持虚地址访问,从而减少整个并行程序运行过程中的地址转换开销,提高系统的性能。实际应用程序的实验结果表明,与传统的分布式共享存储空间相比,实时划分的混合式的分布式共享存储空间具有性能优势,性能的提升比例与具体的网络规模、计算规模、并行程序映射方式等有关。在我们的实验中,性能的提升比例最高为13.14%,最低为6.98%。     

Formalization of a test experiment-II

The paper develops the approach to testing considered in [1]. A formal model of test interaction of the most general type and reduction-type conformance are proposed for which there is hardly any dependence between errors. It is shown that many known types of conformance in various interaction semantics are particular cases of this general model. The paper is devoted to the problem of dependence between errors defined by specification and to the related problem of optimization of tests. There is dependence between errors if there exists a strict subset of errors such that any nonconformal implementation (i.e., implementation that contains some error) contains an error from this subset. Accordingly, it is sufficient that the tests detect errors only from this subset. In the general model proposed, the dependence between errors may arise when one chooses, as a class of implementations under test, some strict subset of the class of all implementations. Partial interaction semantics and/or various implementation hypotheses (in particular, a safety hypothesis) precisely suggest that an implementation under test is not arbitrary but belongs to some subclass of (safe) implementations.     

大规模同步测压系统的集成与应用

建筑外形的复杂化要求在风洞试验中能够实现更大规模的同步测压;为达到这一目标,将多台DSM3400电子扫描测压系统组建为局域网,由远程主机利用Telnet协议对多台主机进行控制;采用互相关分析技术对多台主机采集的数据进行相位修正,以保证数据的同步性;通过设置不同的控制压力稳定时间,实现了多台主机的并行校准;由此构建了多达1280点的大规模同步测压系统,该系统理论上可无限扩容,其可靠性和准确性已在试验工作中得到验证;该同步测压系统的集成方案可在相关领域推广应用。     

Adaptive mapped least squares SVM-based smooth fitting method for DSM generation of LIDAR data

This paper presents an adaptive mapped least squares support vector machine (LS-SVM)-based smooth fitting method for DSM generation of airborne light detection and ranging (LIDAR) data. The LS-SVM is introduced to generate DSM for the sub-region in the original LIDAR data, and the generated DSM for this region is optimized using the points located within this region and additional points from its neighbourhood. The basic principles of differential geometry are applied to derive the general equations (such as gradients and curvatures) for topographic analysis of the generated DSM. The smooth fitting results on simulated and actual LIDAR datasets demonstrate that the proposed smooth fitting method performs well in terms of the quality evaluation indexes obtained, and is superior to the radial basis function (fastRBF) and triangulation methods in computation efficiency, noise suppression and accurate DSM generation.     

Employing AVX vectorization to improve the performance of random number generators

By the example of the RNGAVXLIB random number generator library, this paper considers some approaches to employing AVX vectorization for calculation speedup. The RNGAVXLIB library contains AVX implementations of modern generators and the routines allowing one to initialize up to 10¹⁹ independent random number streams. The AVX implementations yield exactly the same pseudorandom sequences as the original algorithms do, while being up to 40 times faster than the ANSI C implementations.     

一种分布式共享存储系统的线程分配算法

讨论了软件实现了多线程ＤＳＭ 的通信开销和线程分配问题,给出了一种基于线程关系图的调度模型,并在此基础上提出了一种基于迭代的线程分配算法,通过大量的线程关系图对算法进行了评价,并且在一个软件ＤＳＭ系统中实现了该算法,同时给出了算法的评价结果和应用程序的性能数据。     

分布共享存储系统中的数据预送技术

远程数据访问的延迟已成有分布共享存储系统发展的最大障碍。它直接影响到ＤＳＭ系统的效率,尤其是对用软件实现的ＤＳＭ系统。为理解和分析ＤＳＭ系统中的数据行为,论文提出了一种新的分布共享存储结构模型,并在此基础上提出了一种叫做“数据预送”技术,旨在从缩小数据在系统不同层次间的语义差别入手,减少ＤＳＭ中的通信次数,提高对远程访问延迟的容忍力。文中对数据预送技术的原理和实现进行了描述。经对对原形系统的测试,     

Localization of an unmanned ground vehicle based on hybrid 3D registration of 360 degree range data and DSM

A computer vision technique to identify the location of an outdoor unmanned ground vehicle (UGV) is presented. The proposed technique is based on hybrid 3D registration of 360 degree laser range data to a digital surface model (DSM). Range frames obtained from 48 laser detectors are aligned with the reference coordinate system of the DSM. Three novel approaches are proposed for accurate and fast 3D registration of range data and the DSM. First, a two-step hybrid 3D registration technique is proposed. A pair-wise registration step of two consecutive range frames is followed by a refinement step using a layered DSM. Second, a fast projection-based pair-wise registration is proposed by employing rasterized 360 degree range frames. Third, a high elevation DSM is divided into several elevation layers and correspondence search is done near the vehicle’s current elevation. This reduces the number of matching outliers and facilitates fast localization. Experimental results show that the proposed approaches yield better performance in 3D localization compared to conventional 3D registration techniques. Error analysis on five outdoor paths is presented with respect to ground truth.     

Data race avoidance and replay scheme for developing and debugging parallel programs on distributed shared memory systems

Distributed shared memory (DSM) allows parallel programs to run on distributed computers by simulating a global virtual shared memory, but data racing bugs may easily occur when the threads of a multi-threaded process concurrently access the physically distributed memory. Earlier tools to help programmers locate data racing bugs in non-DSM parallel programs are not easily applied to DSM systems. This study presents the data race avoidance and replay scheme (DRARS) to assist debugging parallel programs on DSM or multi-core systems. DRARS is a novel tool which controls the consistency protocol of the target program, automatically preventing a large class of data racing bugs when the parallel program is subsequently run, obviating much of the need for manual debugging. For data racing bugs that cannot be avoided automatically, DRARS performs a deterministic replay-type function on DSM systems, faithfully reproducing the behavior of the parallel program during run time. Because one class of data racing bugs has already been eliminated, the remaining manual debugging task is greatly simplified. Unlike previous debugging methods, DRARS does not require that the parallel program be written in a specific style or programming language. Moreover, DRARS can be implemented in most consistency protocols. In this paper, DRARS is realized and verified in real experiments using the eager release consistency protocol on a DSM system with various applications.     

A comparative evaluation of hybrid distributed shared-memory systems

Distributed Shared-Memory (DSM) systems are shared-memory multiprocessor architectures in which each processor node contains a partition of the shared memory. In hybrid DSM systems coherence among caches is maintained by a software-implemented coherence protocol relying on some hardware support. Hardware support is provided to satisfy every node hit (the common case) and software is invoked only for accesses to remote nodes.In this paper we compare the design and performance of four hybrid distributed shared memory (DSM) organizations by detailed simulation of the same hardware platform. We have implemented the software protocol handlers for the four architectures. The handlers are written in C and assembly code. Coherence transactions are executed in trap and interrupt handlers. Together with the application, the handlers are executed in full detail in execution-driven simulations of six complete benchmarks with coarse-grain and fine-grain sharing. We relate our experience implementing and simulating the software protocols for the four architectures.Because the overhead of remote accesses is very high in hybrid systems, the system of choice is different than for purely hardware systems.     

基于LIDAR数据的城市数字表面模型生成技术

激光雷达(LIDAR)数据是一种新型数据源,它产生的是高密度点云数据。为了更加方便地应用这些数据,首先要生成数字表面模型(DSM)。采用传统的方法生成城市DSM,对城市区域复杂性的考虑不足,也没有对数据存在的缺值情况进行相应处理,故无法生成高质量的城市DSM。该文阐述了一种新颖的生成高质量城市DSM的方法,兼顾城市的复杂性和LIDAR传感器本身的特点。试验证明,该方法生成的DSM与传统方法相比,具备更好的效果。     

TreadMarks: shared memory computing on networks of workstations

Shared memory facilitates the transition from sequential to parallel processing. Since most data structures can be retained, simply adding synchronization achieves correct, efficient programs for many applications. We discuss our experience with parallel computing on networks of workstations using the TreadMarks distributed shared memory system. DSM allows processes to assume a globally shared virtual memory even though they execute on nodes that do not physically share memory. We illustrate a DSM system consisting of N networked workstations, each with its own memory. The DSM software provides the abstraction of a globally shared memory, in which each processor can access any data item without the programmer having to worry about where the data is or how to obtain its value