Gilbert C. Sih

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M91/29
April 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/ERL-91-29.pdf

Interprocessor communication (PC) overheads have emerged as the major performance limitation in parallel processing systems, due to the transmission delays, synchronization overheads, and conflicts for shared communication resources created by data exchange. Accounting for these overheads is essential for attaining efficient hardware utilization. This thesis introduces two new compile-time heuristics for scheduling precedence graphs onto multiprocessor architectures, which account for interprocessor communication overheads and interconnection constraints in the architecture. These algorithms perform scheduling and routing simultaneously to account for irregular interprocessor interconnections, and schedule all communications as well as all computations to eliminate shared resource contention.

The first technique, called dynamic-level scheduling, modifies the classical HLFET list scheduling strategy to account for IPC and synchronization overheads. By using dynamically changing priorities to match nodes and processors at each step, this technique attains an equitable tradeoff between load balancing and interprocessor communication cost. This method is fast, flexible, widely targetable, and displays promising perforrnance.

The second technique, called declustering, establishes a parallelism hierarchy upon the precedence graph using graph-analysis techniques which explicitly address the tradeoff between exploiting parallelism and incurring communication cost. By systematically decomposing this hierarchy, the declustering process exposes parallelism instances in order of importance, assuring efficient use of the available processing resources. In contrast with traditional clustering schemes, this technique can adjust the level of cluster granularity to suit the characteristics of the specified architecture, leading to a more effective solution.

Advisor: Edward A. Lee

BibTeX citation:

@phdthesis{Sih:M91/29,
    Author = {Sih, Gilbert C.},
    Title = {Multiprocessor Scheduling to Account for Interprocessor Communication},
    School = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/1729.html},
    Number = {UCB/ERL M91/29},
    Abstract = {Interprocessor communication (PC) overheads have emerged as the major
performance limitation in parallel processing systems, due to the
transmission delays, synchronization overheads, and conflicts for
shared communication resources created by data exchange. Accounting
for these overheads is essential for attaining efficient hardware
utilization. This thesis introduces two new compile-time heuristics
for scheduling precedence graphs onto multiprocessor architectures,
which account for interprocessor communication overheads and
interconnection constraints in the architecture. These algorithms
perform scheduling and routing simultaneously to account for
irregular interprocessor interconnections, and schedule all
communications as well as all computations to eliminate shared
resource contention.

The first technique, called dynamic-level scheduling, modifies the
classical HLFET list scheduling strategy to account for IPC and
synchronization overheads.  By using dynamically changing priorities
to match nodes and processors at each step, this technique attains
an equitable tradeoff between load balancing and interprocessor
communication cost. This method is fast, flexible, widely targetable,
and displays promising perforrnance.

The second technique, called declustering, establishes a parallelism
hierarchy upon the precedence graph using graph-analysis techniques
which explicitly address the tradeoff between exploiting parallelism
and incurring communication cost. By systematically decomposing this
hierarchy, the declustering process exposes parallelism instances
in order of importance, assuring efficient use of the available
processing resources. In contrast with traditional clustering
schemes, this technique can adjust the level of cluster granularity
to suit the characteristics of the specified architecture, leading
to a more effective solution.}
}

EndNote citation:

%0 Thesis
%A Sih, Gilbert C.
%T Multiprocessor Scheduling to Account for Interprocessor Communication
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/ERL M91/29
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/1729.html
%F Sih:M91/29