A divisible load can be arbitrarily divided into independent small load fractions which are assigned to processors in a parallel or distributed computing system for simultaneous processing. The theory and techniques of divisible load distribution have a wide range of aerospace applications, including satellite signal and image processing, radar and infrared tracking, target identification and searching, and data reporting and aggregation and processing in wireless sensor networks. We make new progress on divisible load distribution on tree and pyramid networks. We revisit the classic method for divisible load distribution on partitionable static interconnection networks (including complete tree and pyramid networks) and derive a closed-form expression of the parallel time and speedup. We propose two new methods which employ pipelined communication techniques to distribute divisible loads on tree and pyramid networks. We derive closed-form expressions of the parallel time and speedup for both methods and show that the asymptotic speedup of both methods is bβ+1 for a complete b-ary tree network and 4β+1 for a pyramid network, where β is the ratio of the time for computing a unit load to the time for communicating a unit load. The technique of pipelined communications leads to improved performance of divisible load distribution on tree and pyramid networks. Compared with the classic method, the asymptotic speedup of our new methods is 100% faster on a complete binary tree network and 33% faster on a pyramid network for large β.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    New Divisible Load Distribution Methods using Pipelined Communication Techniques on Tree and Pyramid Networks


    Contributors:
    Keqin Li (author)


    Publication date :

    2011-04-01


    Size :

    1310918 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English