Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Can Parallel Algorithms Enhance Serial Implementation?

    Thumbnail
    View/Open
    CS-TR-2784.1.ps (199.4Kb)
    No. of downloads: 121

    Auto-generated copy of CS-TR-2784.1.ps (223.6Kb)
    No. of downloads: 933

    Date
    1998-10-15
    Author
    Vishkin, Uzi
    Metadata
    Show full item record
    Abstract
    Consider the serial emulation of a parallel algorithm. The thesis presented in this paper is rather broad. It suggests that such a serial emulation has the potential advantage of running on a serial machine faster than a standard serial algorithm for the same problem. The main concrete observation is very simple: just before the serial emulation of a round of the parallel algorithm begins, the whole list of memory addresses needed during this round is readily available; and, we can start fetching all these addresses from secondary memories at this time. This permits prefetching the data that will be needed in the next "time window", perhaps by means of pipelining; these data will then be ready at the fast memories when requested by the CPU. The possibility of distributing memory addresses (or memory fetch units) at random over memory modules, as has been proposed in the context of implementing the parallel-random-access machine (PRAM) design space, is discussed. This work also suggests that a multi-stage effort to build a parallel machine may start with "parallel memories" and serial processing, deferring parallel processing to a later stage. The general approach has the following advantage: a user-friendly parallel programming language can be used already in its first stage. This is in contrast to a practice of compromising user-friendliness of parallel computer interfaces (i.e., parallel programming languages), and may offer a way for alleviating a so-called "parallel software crisis". It is too early to reach conclusions regarding the significance of the thesis of this paper. Preliminary experimental results with respect to the fundamental and practical problem of constructing suffix trees indicate that drastic improvements in running time might be possible. Serious attempts to follow it up are needed to determine its usefulness. Parts of this paper are intentionally written in an informal way, suppressing issues that will have to be resolved in the context of a concrete implementation. The intention is to stimulate debate and provoke suggestions and other specific approaches. Validity of our thesis would imply that a standard computer science curriculum, which prepares young graduates for a professional career of over forty years, will have to include the topic of parallel algorithms irrespective of whether (or when) parallel processing will succeed serial processing in the general purpose computing market. (Also cross-referenced as UMIACS-TR-91-145.1)
    URI
    http://hdl.handle.net/1903/559
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility