Accession Number : ADA304452

Title :   Analysis of Algorithmic Structures with Heterogeneous Tasks.

Descriptive Note : Contract rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Wilson, Linda F.

PDF Url : ADA304452

Report Date : JAN 1996

Pagination or Media Count : 25

Abstract : Developing efficient programs for distributed systems is difficult because computations must be efficiently distributed and managed on multiple processors. In particular, the programmer must partition functions and data in an attempt to find a reasonable balance between parallelism and overhead. Furthermore, it is very expensive to code an algorithm only to find out that the implementation is not efficient. As a result, it is often necessary to determine and examine those characteristics of an algorithm that can be used to predict its suitability for a distributed computing system. In earlier work, we presented a framework for the study of synchronization and communication effects on the theoretical performance of common homogeneous algorithmic structures. In particular, we examined the synchronous, asynchronous, nearest-neighbor, and asynchronous master-slave structures in terms of expected execution times. In this paper, we examine the effects of synchronization and communication on the expected execution times of heterogeneous algorithmic structures. Specifically, we consider structures containing two different types of tasks, where the execution times of the tasks follow one of two different uniform distributions or one of two different normal distributions. Furthermore, we compare the expected execution times of the heterogeneous algorithmic structures with times for corresponding homogeneous structures. Finally, we develop bounds for the expected execution times of the heterogeneous structures and compare those bounds to simulated execution times.

Descriptors :   *ALGORITHMS, *DISTRIBUTED DATA PROCESSING, *COMPUTER COMMUNICATIONS, COMPUTERIZED SIMULATION, COMPUTATIONS, DATA MANAGEMENT, ASYNCHRONOUS SYSTEMS, PERFORMANCE(ENGINEERING), PROBABILITY DISTRIBUTION FUNCTIONS, COMPARISON, EFFICIENCY, PARALLEL PROCESSING, CONCURRENT ENGINEERING, WORK STATIONS, MULTIPROCESSORS, HETEROGENEITY, SYNCHRONISM, NORMAL DISTRIBUTION.

Subject Categories : Computer Systems
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE