A. James Clark School of Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/1654

The collections in this community comprise faculty research works, as well as graduate theses and dissertations.

Browse

Subject: search.filters.subject.parallel computing

Search Results

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Empirical Speedup Study of Truly Parallel Data Compression
    (2013-04-20) Edwards, James A.; Vishkin, Uzi
    We present an empirical study of novel work-optimal parallel algorithms for Burrows-Wheeler compression and decompression of strings over a constant alphabet. To validate these theoretical algorithms, we implement them on the experimental XMT computing platform developed especially for supporting parallel algorithms at the University of Maryland. We show speedups of up to 25x for compression, and 13x for decompression, versus bzip2, the de facto standard implementation of Burrows-Wheeler compression. Unlike existing approaches, which assign an entire (e.g., 900KB) block to a processor that processes the block serially, our approach is “truly parallel” as it processes in parallel the entire input. Besides the theoretical interest in solving the “right” problem, the importance of data compression speed for small inputs even at great expense of quality (compressed size of data) is demonstrated by the introduction of Google’s Snappy for MapReduce. Perhaps surprisingly, we show feasibility of holding on to quality, while even beating Snappy on speed. In turn, this work adds new evidence in support of the XMT/PRAM thesis: that an XMT-like many-core hardware/ software platform may be necessary for enabling general-purpose parallel computing. Comparison of our results to recently published work suggests 70x improvement over what current commercial parallel hardware can achieve.
  • Thumbnail Image
    Item
    Using Simple Abstraction to Guide the Reinvention of Computing for Parallelism
    (2009-02-06) Vishkin, Uzi
    The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. CS urgently requires convergence to a robust parallel general-purpose platform that provides good performance and is easy to program. Unfortunately, this same objective has eluded decades of parallel computing research. Now, continued delays and uncertainty could start affecting important sectors of the economy. This paper advocates a minimalist stepping-stone: settle first on a simple abstraction that encapsulates the new interface between programmers, on one hand, and system builders, on the other hand. This paper also makes several concrete suggestions: (i) the Immediate Concurrent Execution (ICE) abstraction as a candidate for the new abstraction, and (ii) the Explicit Multi-Threaded (XMT) general-purpose parallel platform, under development at the University of Maryland, as a possible embodiment of ICE. ICE and XMT build on a formidable body of knowledge, known as PRAM (for parallel random-access machine, or model) algorithmics, and a latent, though not widespread, familiarity with it. Ease-of-programming, strong speedups and other attractive properties of the approach suggest that we may be much better prepared for the challenges ahead than many realize.
  • Thumbnail Image
    Item
    Close Conjunction Detection on Parallel Computer
    (American Institute of Aeronautics and Astronautics, 1995-07) Healy, Liam
    Close conjunction detection is the task of finding which satellites will come within a given distance of other satellites. The algorithms described here are implemented on the Connection Machine (CM) in a program called CM-COMBO. It will find close conjunctions of satellites over a time range for one, a few, or all satellites against the original or another catalog and works with an arbitrary propagator. The problem of comparing an entire catalog against itself is beyond the computing power of current serial machines. This program does not prefilter any orbits and does not make assumptions about the type of orbit (that it be nearly circular, for instance). This paper describes the algorithm for this computation, the implementation on the CM, and resuls of several studies using this program.
  • Thumbnail Image
    Item
    Deterministic Studies of Debris Hazards with Parallel Processors
    (European Space Agency, 1993-04-05) Healy, Liam; Coffey, Shannon
    A new generation of parallel processing computers makes possible the ability to propagate all objects in the space surveillance catalog with simulated objects, and detect close approaches. With this capability, it is possible to test deterministically debris scenarios, without resorting to statistical models. To compare the positions of objects we have developed two methods, an all-to-all comparison and a one-to-all comparison. For the former, a seive significantly reduces computation time; for the latter, direct comparison is possible in parallel. We show results from several simulations, including simulated multiple sources of debris, hazard to the space station, and close contacts amongst the catalog itself, to show potential for debris studies. The techniques described here have potential application the general problem of catalog maintenance.
  • Thumbnail Image
    Item
    Paint by number: Uncovering phase flows of an integrable dynamical system
    (American Institute of Physics, 1991-09) Healy, Liam; Deprit, Etienne
    Given an integrable dynamical system with one degree of freedom, "painting" the integral over phase space proves to be a powerful technique for uncovering both global and local behavior. This graphical technique avoids numerical integration, employing instead a nonlinear method of assigning contrasting colors to the energy values to distinguish subtle details of the flow.