ScholarSpace will be brought offline for upgrades on Wednesday December 9th at 11AM HST. Service will be disrupted for approximately 2 hours. Please direct any questions to

Item Description

Show full item record

Title: Processor-Time Balanced Reduction With Utilization Maximization And Communication Hiding 
Author: Chindarkar, Gautam R.
Date: 2005-05
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.

Item File(s)

Description Files Size Format View
Restricted for viewing only uhm_ms_3951_r.pdf 3.071Mb PDF View/Open
For UH users only uhm_ms_3951_uh.pdf 3.071Mb PDF View/Open

This item appears in the following Collection(s)


Advanced Search


My Account