Processor-Time Balanced Reduction With Utilization Maximization And Communication Hiding
Date
2005-05
Authors
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Narrator
Transcriber
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
University of Hawaii at Manoa
Volume
Number/Issue
Starting Page
Ending Page
Alternative Title
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.
Description
Keywords
Citation
Extent
Format
Geographic Location
Time Period
Related To
Theses for the degree of Master of Science (University of Hawaii at Manoa). Electrical Engineering; no. 3951
Related To (URI)
Table of Contents
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.
Rights Holder
Local Contexts
Collections
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.