45504051
Horizons of Parallel Computation
This paper considers the ultimate impact of fundamental physical limitations—notably, speed of light and device size—on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, we take here the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency-hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.
930169
Sequencing-by-hybridization at the information-theory bound: an optimal algorithm
In a recent paper [PFU99) we have introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a well defined periodic pattern. It was shown in [PFU99] that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given library size of probes) is significantly better than the standard scheme based on oligomer probes.
In this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. We prove that the new algorithm exploits the full potential of the SBH technology with high-confidence performance, that comes within a small constant factor (about 2) of the information-theory bound. Moreover, this performance is achieved while maintaining running time linear in the target sequence length.
1765683
The Role of Arithmetic in Fast Parallel Matrix Inversion
Abstract. In the last two decades several NC algorithms for solving basic linear algebraic problems have appeared in the literature. This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the concrete feasibility of many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the ``Engineering of Algorithms.'' We perform a comparative analysis of several well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic setting no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach.
18686062
Sequencing-by-hybridization revisited: the analog-spectrum proposal
All published approaches to DNA sequencing by hybridization (SBH) consist of the biochemical acquisition of the spectrum of a target sequence (the set of its subsequences conforming to a given probing pattern) followed by the algorithmic reconstruction of the sequence from its spectrum. In the "standard" or "uniform" approach, the probing pattern is a string of length L and the length of reliably reconstructible sequences is known to be m/sub len/ = O(2/sup L/). For a fixed microarray area, higher sequencing performance can be achieved by inserting nonprobing gaps ("wild-cards") in the probing pattern. The reconstruction, however, must cope with the emergence of fooling probes due to the gaps and algorithmic failure occurs when the spectrum becomes too densely populated, although we can achieve m/sub comp/ = O(4/sup L/). Despite the combinatorial success of gapped probing, all current approaches are based on a biochemically unrealistic spectrum-acquisition model (digital-spectrum). The reality of hybridization is much more complex. Departing from the conventional model, in this paper, we propose an alternative, called the analog-spectrum model, which more closely reflects the biochemical process. This novel modeling reestablishes probe length as the performance-governing factor, adopting "semidegenerate bases" as suitable emulators of currently inadequate universal bases. One important conclusion is that accurate biochemical measurements are pivotal to the success of SBH. The theoretical proposal presented in this paper should be a convincing stimulus for the needed biotechnological work.
1952504
Data structures and algorithms for the string statistics problem
Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log2n) and spaceO(n logn), off-line on a RAM.
206394014
Holographic dispersal and recovery of information
A simple scheme for dispersal and recovery of digital information based on the discrete Fourier transform is discussed. The author presents a different implementation of M.O. Rabin's (J. ACM, vol.36, no.2, p.335-48, Apr. 1989) scheme, whose recovery cost is O(log m+k) operations per character, assuming m= Theta (n); for example, when k= Theta (log n), this cost drops from O(m) to O(log m) per character. Since the implementation is based on the Fourier transform, it is termed holographic. >
17687657
Work-Preserving Speed-Up of Parallel Matrix Computations
Brent's scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm. Such a scheme preserves, under slow-down, the actual number of executed operations, also called work. In this paper we take the complementary viewpoint, and rather than consider the work-preserving slow-down of some fast parallel algorithm, we investigate the problem of the achievable speed-ups of computation while preserving the work of the best-known sequential algorithm for the same problem. The proposed technique, eminently applicable to problems of matrix-computational flavor, achieves its result through the interplay of two algorithms with significantly different features. Analogous but structurally different "interplays" have been used previously to improve the algorithmic efficiency of graph computations, selection, and list ranking. We demonstrate the efficacy of our technique for the computation of path algebras in graphs and digraphs and various fundamental computations in linear algebra. Some of the fundamental new algorithms may have practical value; for instance, we substantially improve the algorithmic performance of the parallel solution of triangular and Toeplitz linear systems of equations and the computation of the transitive closure of digraphs.
27244492
A time-optimal parallel algorithm for three-dimensional convex hulls
In this paper we present an O(1/α logn)-time parallel algorithm for computing the convex hull ofn points in ℜ3. This algorithm usesO(@#@ n1+a) processors on a CREW PRAM, for any constant 0 < α ≤1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log2n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.
43888320
Triangulating a Simple Polygon
9347410
Supereffective slow-down of parallel computations
Brent’s scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm. Such a scheme preserves the actual number of executed operations, and when applicable, it provides a processor balancing technique that significantly reduces the work, expressed as the number of ezecutcdde operators. In this paper we discuss a new technique, called supereffective slow-down, that yields quite fast an algorithm with work significantly smaller than that of the fastest algorithm for the same problem. This technique can be viewed as a work-preserving acceleration of an existing recursive sequential algorithm for the considered problem. The presented examples include the computation of path algebras in graphs and digraphs and various computations in linear albegra. Some of the new algorithms may have practical value; for instance, we substantially improve the performance of the known parallel algorithms for triangular linear systems of equations.