Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/10452

Files

File Description SizeFormat 
uhm_ms_3951_r.pdfRestricted for viewing only3.15 MBAdobe PDFView/Open
uhm_ms_3951_uh.pdfFor UH users only3.15 MBAdobe PDFView/Open

Item Summary

Title: Processor-Time Balanced Reduction With Utilization Maximization And Communication Hiding
Authors: Chindarkar, Gautam R.
Issue Date: 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.
URI: http://hdl.handle.net/10125/10452
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



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