Distributed, Parallel, and Cluster Computing (cs.DC)

  • PDF
    This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each pair of nodes is able to communicate with each other directly and reliably. We consider the mobile Byzantine fault model proposed by Garay '94 -- in the model, an omniscient adversary can corrupt up to $f$ nodes in each round, and at the beginning of each round, faults may "move" in the system (i.e., different sets of nodes may become faulty in different rounds). Recent work by Bonomi et al. '16 proposed a simple iterative approximate consensus algorithm which requires at least $4f+1$ nodes. This paper proposes a novel technique of using "confession" (a mechanism to allow others to ignore past behavior) and a variant of reliable broadcast to improve the fault-tolerance level. In particular, we present an approximate consensus algorithm that requires only $\lceil 7f/2\rceil + 1$ nodes, an $\lfloor f/2 \rfloor$ improvement over the state-of-the-art algorithms. Moreover, we also show that the proposed algorithm is optimal within a family of round-based algorithms.
  • PDF
    We present a multi-word atomic (1,N) register for multi-core machines exploiting Read-Modify-Write (RMW) instructions to coordinate the writer and the readers in a wait-free manner. Our proposal, called Anonymous Readers Counting (ARC), enables large-scale data sharing by admitting up to $2^{32}-2$ concurrent readers on off-the-shelf 64-bits machines, as opposed to the most advanced RMW-based approach which is limited to 58 readers. Further, ARC avoids multiple copies of the register content when accessing it---this affects classical register's algorithms based on atomic read/write operations on single words. Thus it allows for higher scalability with respect to the register size. Moreover, ARC explicitly reduces improves performance via a proper limitation of RMW instructions in case of read operations, and by supporting constant time for read operations and amortized constant time for write operations. A proof of correctness of our register algorithm is also provided, together with experimental data for a comparison with literature proposals. Beyond assessing ARC on physical platforms, we carry out as well an experimentation on virtualized infrastructures, which shows the resilience of wait-free synchronization as provided by ARC with respect to CPU-steal times, proper of more modern paradigms such as cloud computing.
  • PDF
    The landscape of cloud computing has significantly changed over the last decade. Not only have more providers and service offerings crowded the space, but also cloud infrastructure that was traditionally limited to single provider data centers is now evolving. In this paper, we firstly discuss the changing cloud infrastructure and consider the use of infrastructure from multiple providers and the benefit of decentralising computing away from data centers. These trends have resulted in the need for a variety of new computing architectures that will be offered by future cloud infrastructure. These architectures are anticipated to impact areas, such as connecting people and devices, data-intensive computing, the service space and self-learning systems. Finally, we lay out a roadmap of challenges that will need to be addressed for realising the potential of next generation cloud systems.
  • PDF
    Today's search engines process billions of online user queries a day over huge collections of data. In order to scale, they distribute query processing among many nodes, where each node holds and searches over a subset of the index called shard. Responses from some nodes occasionally fail to arrive within a reasonable time-interval due to various reasons, such as high server load and network congestion. Search engines typically need to respond in a timely manner, and therefore skip such tail latency responses, which causes degradation in search quality. In this paper, we tackle response misses due to high tail latencies with the goal of maximizing search quality. Search providers today use redundancy in the form of Replication for mitigating response misses, by constructing multiple copies of each shard and searching all replicas. This approach is not ideal, as it wastes resources on searching duplicate data. We propose two strategies to reduce this waste. First, we propose rSmartRed, an optimal shard selection scheme for replicated indexes. Second, when feasible, we propose to replace Replication with Repartition, which constructs independent index instances instead of exact copies. We analytically prove that rSmartRed's selection is optimal for Replication, and that Repartition achieves better search quality compared to Replication. We confirm our results with an empirical study using two real-world datasets, showing that rSmartRed improves recall compared to currently used approaches. We additionally show that Repartition improves over Replication in typical scenarios.
  • PDF
    FFT (fast Fourier transform) plays a very important role in many fields, such as digital signal processing, digital image processing and so on. However, in application, FFT becomes a factor of affecting the processing efficiency, especially in remote sensing, which large amounts of data need to be processed with FFT. So shortening the FFT computation time is particularly important. GPU (Graphics Processing Unit) has been used in many common areas and its acceleration effect is very obvious compared with CPU (Central Processing Unit) platform. In this paper, we present a new parallel method to execute FFT on GPU. Based on GPU storage system and hardware processing pipeline, we improve the way of data storage. We divided the data into parts reasonably according the size of data to make full use of the characteristics of the GPU. We propose the memory optimized method based on share memory and texture memory to reduce the number of global memory access to achieve better efficiency. The results show that the GPU-based memory optimized FFT implementation not only can increase over 100% than FFTW library in CPU platform, but also can improve over 30% than CUFFT library in GPU platform.
  • PDF
    OpenMP is a cross-platform API that extends C, C++ and Fortran and provides shared-memory parallelism platform for those languages. The use of many cores and HPC technologies for scientific computing has been spread since the 1990s, and now takes part in many fields of research. The relative ease of implementing OpenMP, along with the development of multi-core shared memory processors (such as Intel Xeon Phi) makes OpenMP a favorable method for parallelization in the process of modernizing a legacy codes. Legacy scientific codes are usually holding large number of physical arrays which being used and updated by the code routines. In most of the cases the parallelization of such code focuses on loop parallelization. A key step in this parallelization is deciding which of the variables in the parallelized scope should be private (so each thread will hold a copy of them), and which variables should be shared across the threads. Other important step is finding which variables should be synchronized after the loop execution. In this work we present an automatic pre-processor that preforms these stages - AutOMP (Automatic OpenMP). AutOMP recognize all the variables assignments inside a loop. These variables will be private unless the assignment is of an array element which depend on the loop index variable. Afterwards, AutOMP finds the places where threads synchronization is needed, and which reduction operator is to be used. At last, the program provides the parallelization command to be used for parallelizing the loop.

Recent comments

Māris Ozols Feb 21 2017 15:35 UTC

I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

Dushyant Vaghela Sep 21 2014 08:30 UTC

We have applied our Research work on various servers, NGIX performs better, VPS Hosting Godadday servers Representative for [explorequotes][1] working fine, finally we have concluded that all the experiments were satisfactory

[1]: http://explorequotes.com/