Please use this identifier to cite or link to this item:

Processor-Time Balanced Reduction With Utilization Maximization And Communication Hiding

File Description Size Format  
uhm ms 3951 r.pdf Version for non-UH users. Copying/Printing is not permitted 3.15 MB Adobe PDF View/Open
uhm ms 3951 uh.pdf Version for UH users 3.15 MB Adobe PDF View/Open

Item Summary

Title:Processor-Time Balanced Reduction With Utilization Maximization And Communication Hiding
Authors:Chindarkar, Gautam R.
Date Issued:May 2005
Abstract:Work efficiency cannot guarantee utilization maximization due to its susceptibility to biases toward either deployed processors P or execution time T, resulting in an imbalanced work distribution. To enhance the overall parallelization effectiveness, balancing work consisting of both computation and communication is critical to equitably optimize both P and T and therefore satisfy the needs of both the user and the resource manager. A "BUCH" measure is introduced to include P-T balancing, maximizing utilization of computations, and communication hiding as important components of truly effective parallelization. PRAM reduction, flawed by the imbalance of O(lg n) for T and O(n/(lg n)) for P, is clearly biased towards minimizing T at the expense of P and it also completely ignores communication. A new reduction technique called "BUCH-R" conforming to BUCH measure requirements is developed to produce effective schedules, assuming communication costs are bounded by the uniform computation cost. BUCH-R balances work distribution to achieve O(√n) for both P and T. By minimizing communications and overlapping them with computations, BUCH-R completely hides communication to eliminate all delays. Comparative analyses show and experimental data further buttress that PRAM utilization asymptotically decreases to 1/2 as n increases, while BUCH-R utilization asymptotically increases to approach the optimal theoretical bound of 1. Consequently, the validation of truly effective balanced parallel reduction achieving an appropriate compromise between user and resource manager needs via BUCH-R is complete. This makes a case for the recognition of BUCH-R as a new theoretical benchmark for effective parallel reduction.
Rights:All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.
Appears in Collections: M.S. - Electrical Engineering

Please email if you need this content in ADA-compliant format.

Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.