Search results for "ARCHITECTURE"
showing 10 items of 3706 documents
Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs
2017
Parity RAIDs are used to protect storage systems against disk failures. The idea is to add redundancy to the system by storing the parity of subsets of disks on extra parity disks. A simple two-dimensional scheme is the one in which the data disks are arranged in a rectangular grid, and every row and column is extended by one disk which stores the parity of it.In this paper we describe several two-dimensional parity RAIDs and analyse, for each of them, the probability for dataloss given that f random disks fail. This probability can be used to determine the overall probability using the model of Hafner and Rao. We reduce subsets of the forest counting problem to the different cases and show…
Balls into non-uniform bins
2014
Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…
A loopless algorithm for generating the permutations of a multiset
2003
AbstractMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.
Burrows-Wheeler transform and Run-Length Enconding
2017
In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-…
Randomized renaming in shared memory systems.
2021
Abstract Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m . The problem is called tight if m = n , and loose if m > n . In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O ( log n ) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = ( 1 + ϵ ) ⋅ n and constant ϵ , they achieve a step complexity of O ( log log n ) . In this paper we consider tight as well as loos…
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
172 REAL TIME EDGES DETECTION USING WAVELET TRANSFORM
2000
One of the way to extract edges uses the fast wavelet transform algorithm. This technique allows the detection of multiscale edges and is used to detect all the details, which are in a picture by modifying the scale. The real time application for edge detection involves the implementation of the algorithm on an integrated circuit like a FPGA and the development of an appropriated board. This article deals about the implementation of a wavelet transform algorithm onto a FPGA and development of an electronic board to detect multiscale edges.
ADI schemes for valuing European options under the Bates model
2018
Abstract This paper is concerned with the adaptation of alternating direction implicit (ADI) time discretization schemes for the numerical solution of partial integro-differential equations (PIDEs) with application to the Bates model in finance. Three different adaptations are formulated and their (von Neumann) stability is analyzed. Ample numerical experiments are provided for the Bates PIDE, illustrating the actual stability and convergence behaviour of the three adaptations.
A Metric for Automatic Word categorization
2008
This paper presents a metric to be used by the working prototype WIH (Web Intelligent Handler). This metric (referred here as po) is designed to reflect main topic words and discriminate certain text profiles through word weightings. The actual version is designed only for Spanish web texts. Statistical analyses show that it is possible to differentiate text profiles upon po behavior. A poll is presented also, showing that it is a good main words discriminator. This paper is posted here as a new algorithm useful for Spanish text processing.
A Probabilistic Approach to the Count-To-Infinity Problem in Distance-Vector Routing Algorithms
2013
Count-to-infinity problem is characteristic for routing algorithms based on the distributed implementation of the classical Bellman-Ford algorithm. In this paper a probabilistic solution to this problem is proposed. It is argued that by the use of a Bloom Filter added to the routing message the routing loops will with high probability not form. An experimental analysis of this solution for use in Wireless Sensor Networks in practice is also included.