Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Distributed Parallelism Considered Harmful

    Thumbnail
    View/Open
    TR_92-37.pdf (1.321Mb)
    No. of downloads: 362

    Date
    1992
    Author
    Makowski, Armand M.
    Nelson, R.
    Metadata
    Show full item record
    Abstract
    We consider a model of a distributed parallel processing system that shows that parallel versus sequential processing is beneficial only under conditions of light load. Our results are valid under general assumptions on the number of processors, task service times and the information used to schedule jobs. Our model of a parallel processing system consists of a set of homogeneous processors each with private memory in which tasks queue before being served. Jobs arriving to the system consist of a random number of tasks which can be executed independently each other and we consider a job to be completed only after all of its component tasks have finished execution. a central dispatcher schedules the tasks on the processors at job arrival instants using information on the number of tasks currently scheduled on each processor. We model this system as a distributed fork/join queueing system and derive the structure of the individually optimal scheduling policy. Our results show that the individually optimal is a mixture of policies corresponding to sequential job execution (all tasks are scheduled on a single processor) and parallel scheduling (tasks are distributed among several processors in a manner that tends to equalize queue lengths). We show that, under conditions that include the case of moderate to heavy loads, the individually optimal scheduler schedules tasks according to the sequential policy which runs counter to the intuition that parallel processing is desirable. Because we do not include certain overheads associated with executing jobs in parallel in our model, our results are biased towards parallel rather than sequential processing. since we believe that systems are not typically underutilized, our results strongly suggest that it can be harmful to have parallel execution in distributed processing systems. Response time properties of the individually optimal scheduler are derived and compared to other scheduling policies.
    URI
    http://hdl.handle.net/1903/5219
    Collections
    • Institute for Systems Research Technical Reports

    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