Search

Abstract: In this paper, we consider how to optimize I/O server placement in order to improve parallel I/O performance in switch-based clusters. The significant advances in cluster networks in recent years have made it practical to connect tens of thousands of hosts via networks that have enormous and scalable total capacity, and in which communications between a host and any other host incur the same cost. The same cost property frees users from consideration of network contention and allows them to concentrate on load-balancing issues. We formulate the server placement problem on a cluster that has the same cost property as a weighted bipartite matching with the goal of balancing the workload on the I/O nodes. To find an optimal solution to this problem, we propose an algorithm, called Load Balance Matching (LBM), where is the number of compute nodes and is the number of I/O servers. We also investigate server placement for general clusters in which multiple same-cost subclusters are interconnected to form a large cluster. This class of clusters typically adopt irregular topologies that allow the construction of scalable systems with an incremental expansion capability. Also, due to the limited bandwidth on network links between subclusters, network link contention is a major concern when distributing servers over the entire network. We show that finding an optimal placement strategy for general clusters with the goal of minimizing link contention is computationally intractable. To resolve this problem, we propose a hierarchical strategy that places servers in two steps. First, to minimize link contention, we decide which subcluster each server should be assigned to. We propose a tree-based heuristic algorithm, called Load Balance Traversing (LBT), to solve this problem. In the second step, the LBM algorithm decides the location of each server within a subcluster. Our simulation results demonstrate that LBT achieves a significant improvement in parallel I/O performance over four other algorithms, and is near-optimal in some cases. [Copyright &y& Elsevier]

Abstract: This paper presents two new randomized distributed algorithms for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. Both algorithms, called Alg-Neighbors and Alg-Edges, make use of biased and unbiased dice having faces, and are analyzed in terms of correctness, expected time complexity and rate of convergence. First, the Alg-Neighbors algorithm is presented as a generalization of the Calabrese/França algorithm for dice (or coins) with 2 faces. It is proved that a convenient biasing function applied to all dice changes the expected time complexity from sub-exponential, i.e., (for unbiased dice with faces), to , where is the number of the system’s nodes. Next, it is shown that the Alg-Edges algorithm is able to produce acyclic orientations in steps with high probability, where denotes the total number of edges. Finally, a speed of convergence versus quality of acyclic orientation generation (associated number of colors) tradeoff is identified between Alg-Neighbors and Alg-Edges algorithms. Computational experiments were carried out in order to provide a more accurate description of the behavior of both algorithms. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to study multidimensional continued fraction algorithm over the field of formal power series. In the case of the Brun algorithm by using its homogenous version, we prove that it converges. [Copyright &y& Elsevier]

Abstract: This paper investigates both the precision and the model checking efficiency of abstract models designed to preserve branching time logics w.r.t. a 3-valued semantics. Current abstract models use ordinary transitions to over approximate the concrete transitions, while they use hyper transitions to under approximate the concrete transitions. In this work, we refer to precision measured w.r.t. the choice of abstract states, independently of the formalism used to describe abstract models. We show that current abstract models do not allow maximal precision. We suggest a new class of models and a construction of an abstract model which is most precise w.r.t. any choice of abstract states. As before, the construction of such models might involve an exponential blowup, which is inherent by the use of hyper transitions. We therefore suggest an efficient algorithm in which the abstract model is constructed during model checking, by need. Our algorithm achieves maximal precision w.r.t. the given property while remaining quadratic in the number of abstract states. To complete the picture, we incorporate it into an abstraction-refinement framework. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the GPU throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity , and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of , which for a long time was considered to be the fastest for GPU sorting. It is 6 times faster than single CPU quicksort, and 10% faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. [Copyright &y& Elsevier]

Abstract: The Singular Value Decomposition (SVD) is a vital problem that finds a place in numerous application domains in science and engineering. As an example, SVDs are used in processing voluminous datasets. Many sequential and parallel algorithms have been proposed to compute SVDs. The best known sequential algorithms take cubic time. This amount of time may not be acceptable especially when the data size is large. Thus parallel algorithms are desirable. In this paper, we present a novel technique for the parallel computation of SVDs. This technique yields impressive speedups. We discuss implementation of our technique on parallel models of computing such as the mesh and the PRAM. We also present an experimental evaluation of our technique. [Copyright &y& Elsevier]

Abstract: Boosting algorithms are procedures that “boost” low-accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has become a major research topic in computational learning theory. In this paper we study boosting in the presence of random classification noise, giving both positive and negative results. We show that a modified version of a boosting algorithm due to Mansour and McAllester (J. Comput. System Sci. 64(1) (2002) 103) can achieve accuracy arbitrarily close to the noise rate. We also give a matching lower bound by showing that no efficient black-box boosting algorithm can boost accuracy beyond the noise rate (assuming that one-way functions exist). Finally, we consider a variant of the standard scenario for boosting in which the “weak learner” satisfies a slightly stronger condition than the usual weak learning guarantee. We give an efficient algorithm in this framework which can boost to arbitrarily high accuracy in the presence of classification noise. [Copyright &y& Elsevier]

Abstract: In this paper we present a generic algorithm for factoring polynomials over global fields . As efficient implementations of that algorithm for number fields and function fields differ substantially, these cases will be treated separately. Complexity issues and implementations will be discussed in part II which also contains illustrative examples. [Copyright &y& Elsevier]