% {\lb Research Contributions}


%%\noindent {\lb Section A: An Outline of Research Contributions}

\vspace{0.25 cm}
After I joined McGill University in 1987,
I established the Advanced Computer Architecture and
Program Structures Group (ACAPS).
The following is a summary of the research contributions.
Also, please  refer to Section B below for a list of
related references.
%I have made, together with the graduate students in ACAPS.

\vspace{0.25 cm}
\noindent {\bf I. Computer Architectures and Systems}

\vspace{0.25 cm}
\noindent I.1.  The McGill Dataflow Architecture Model (MDFA)

\vspace{0.25 cm}
Dataflow architectures have promised
solutions addressing the two fundamental problems
of von Neumann computers in multiprocessing : memory latency and
synchronization overhead.
However, we must not ignore the efficiency and simplicity
of the instruction sequencing mechanism in von Neumann architecture
models, as well as over 40 years of optimization of instruction execution
mechanisms.

The McGill Dataflow Architecture Model
%(\cite{GaoHumMon91,GaoHumWon90,GaoHumWon90.2,Gao91.2,Gao91.12})
presents an efficient hybrid architecture model
which employs
(1)
conventional architecture
techniques to achieve fast pipelined
instruction execution, while
exploiting fine-grain parallelism by data-driven instruction
scheduling;
(2) a mechanism which
supports concurrent operation of multiple instruction threads
on the hybrid architecture model;
(3) a compiling paradigm for {\sl dataflow software pipelining}
which efficiently exploits loop parallelism through
{\sl balancing} techniques.
MDFA  utilizes the so-called {\em argument-fetching} dataflow principle
%%originated from joint research with Prof. Dennis at MIT
%\cite{DennisGao88.2}, 
and is one of the first architecture model
which has been substantially developed based on this principle.
The MDFA has been simulated on a dataflow architecture testbed developed
at McGill,
and experimental results
have demonstrated the effectiveness of
features
of the proposed hybrid architecture, as well as
contributing to its improvement.

\vspace{0.25 cm}
\noindent I.2.  The Super-Actor Architecture Model (SAM)

\vspace{0.25 cm}
Based on our experience with MDFA, we have proposed
the Super-Actor Machine (SAM) --- a multi-threaded architecture
based on an hybrid dataflow and von Neumann evaluation model.
%\cite{HumGao91,HumGao91.3,HumGao91.4}.
We presented a novel
organization of high-speed memories, known as the {\em register-cache},
for a multi-threaded architecture.
As the term suggests, it is
organized both as a register file and a cache.
Viewed from the execution unit, its contents are addressable
similar to ordinary CPU registers using relatively
short addresses.
From the main memory perspective,
it is content addressable, i.e., its contents are tagged just
as in conventional caches.
The register allocation for the register-cache is adaptively performed at
runtime, resulting in a dynamically allocated register file.
The SAM has been simulated on a dataflow architecture testbed developed
at McGill/CRIM,
and experimental results
have demonstrated the effectiveness of
features
of the proposed architecture, as well as contributing to its improvement.
%SAM has gained some international interest, and
%the GMD FIRST (a prestigious  computer science research institution
%in the field of high-performance computer architecture in Germany) in Berlin has
%proposed to
%work with my group to jointly implement the full SAM model in hardware.

\vspace{0.25 cm}
\noindent I.3. The Multithreaded Architecture Model (MTA)

\vspace{0.25 cm}

Most recently, we have proposed the MTA (Multi-Threaded Architecture) model.
Multithreaded node architectures have been proposed for future multiprocessor
systems.  However,
some open issues remain: can efficient multithreading support
be provided in a multiprocessor machine
such that
it is capable of tolerating the synchronization and communication
latencies, without intruding on the
performance of sequentially-executed code?
And how much
(quantitatively) does such non-intrusive multithreading support
contribute to the scalable parallel performance in the presence
of increasing interprocessor communication and synchronization demands?

Funded by an NSERC Strategic Grant, the MTA project
attempts to address
the above issues.
We have implemented the MTA model on
an experimental high-performance multiprocessor testbed called MANNA 2.0.
The MTA-MANNA platform has for each processing node, an
Execution Unit (EU) for performing the computations and is programmed as a
standard superscalar processor,
and a Synchronization Unit (SU)
supporting dataflow-like thread synchronizations
and scheduling, as well as processing remote
memory requests.
We intend to demonstrate that multithreading support can be efficiently
implemented into a multiprocessor without a major impact on uniprocessor
performance.
Preliminary results gave first encouraging quantitative indications of how much the basic
multithreading support can help in tolerating increasing
communication/synchronization 


\vspace{0.25 cm}
\noindent I.4. Parallelism Limit Studies

\vspace{0.25 cm}
We have designed and developed the SITA testbed which
provides a powerful set of object-code analysis techniques for
the study of algorithmic parallelism, compiler optimization strategies,
and parallel architecture structures.
With SITA,
we can conduct
studies on the {\em limits of parallelism} and the {\em smoothability}
of the parallelism on a wide variety of applications.
%\cite{TheobaldGaoHen93}.
%\cite{TheobaldGaoHen92.2,TheobaldGaoHen93}.
This tool has already shown a high-level of potential parallelism for
both scientific and non-scientific applications.
The results indicate that high amounts of parallelism 
can be exploited
smoothly---delayed without affecting the overall execution time---under
various combinations of conventional architecture features and
multithreading, as well as compiler optimization techniques.

\vspace{0.25 cm}
\noindent I.5. International Interaction and Recognition

\vspace{0.25 cm}
The work carried out MDFA has received substantial international recognition.
The applicant
was invited to present his research results to
several important international workshops\/conferences\/panels
to present these results.
% entitled: "Dataflow: a status report" in conjunction
%with the 16th ACM Symposium on Computer Architecture held
%in Jerusalem, Israel, May, 1989.
For example, he 
has been a co-chair of the International Workshop on Multithreaded
Computers in conjunction with IEEE Supercomputing'91 held
at Albuquerque, New Mexico --- the first such meeting in this field.
He has also been a co-chair of
%% the organizing committee of
the Second International Workshop on Dataflow and multithreaded Computers
in conjunction with The 19th ACM Symposium on Computer Architecture,
held in Queesland, Australia, May 1992.
He also served as the Program Chairman of the International Conference
on Parallel Architectures and Compilation Techniques (PACT '94)
held in Aug. 1994 in Montreal,
co-sponsored by IFIP and ACM 
SIGARCH,
in association with ACM SIGPLAN, IEEE TCCA (Technical Committee
on Computer Architecture) and IEEE TCPP (Technical Committee on
Parallel Processing).


%The ACAPS research group at McGill has also been in constant interaction with
%prominent researchers in the field of multithreaded
%computing.  The applicant is a co-chair of the organizing/program committee
%of the International Workshop on Multithreaded Computers --- one of the first in
%this field ---
%in conjunction with the IEEE and ACM SIGARCH Supercomputing'91  Conference
%$to be held at Albuquerque, New Mexico, 1991.

\vspace{0.25 cm}
\noindent {\bf II. Optimizing and Parallelizing Compilers}

\vspace{0.25 cm}
In the design of high-performance architectures today
new compiler concepts and techniques are needed to
cope with rapidly advancing hardware technology.  In fact, recent 
architectural breakthroughs have been directly related to innovative 
compiler optimizations.
%---whether it be for reduced instruction set 
%computers (RISC), complex instruction set computers (CISC),
%multiprocessing, or vector processing.
My main contributions are listed below.

\vspace{0.25 cm}
\noindent  II.1.  Compiling for Instruction-Level Parallelism (ILP)

\vspace{0.25 cm}

\noindent II.1.1  {\em Dataflow Software Pipelining}

\vspace{0.25 cm}
Dataflow {\sl software pipelining} was originated
from my dissertation work as
an efficient code mapping methodology for pipelining array operations embedded
in loops for static dataflow computers.
%% \cite{Gao86,Gao90}.
Under this methodology, fully pipelined array (vector) operations
can be supported by a data flow computer in a fine-grain manner.

\vspace{0.25 cm}
One important contribution is to the balancing techniques
for fully pipelined data flow code.
In \cite{Gao89.2}, I have formulated and studied  the
optimal balancing  problem (i.e. to introduce a minimum amount
of buffering into data flow
graphs for fully balancing)
and show that efficient polynomial time  solutions
exist for acyclic static dataflow graphs.
%%In \cite{GaoHumWon91,GaoHumWon90.4},
We have introduced the
concept of {\em limited balancing} --- a
method to reduce and minimize the token storage required for static dataflow graphs and
an extension of our original balancing method.
%%In \cite{GaoNin91.1},
Later we further extend the theoretical framework, and
for the first time, prove that the limited balancing problem
can be solved using efficient polynomial time algorithms.
The significance of
this work is to demonstrate that such solution methods can be applied to
a class of dataflow graphs beyond  the static dataflow model, and our method can be applied
to
dataflow graphs with cycles.
We consider these results are important and original.
These developments have laid the foundations of a theoretical framework
for dataflow software pipelining
and demonstrated the feasibility of the application of
such methods in real compilers.

We have applied the methodology of dataflow software pipelining
to MDFA and SAM at McGill, and studied the effects using
simulation.
%%  Some results have been reported in
%%\cite{GaoHumWon90,GaoPar90,HumGao91.4}.

\vspace{0.25 cm}
\noindent II.1.2.  {\em A Timed-Petri Net Model of Loop Scheduling}

\vspace{0.25 cm}
Efficient execution of loops is one of the most important
challenges for high-performance computer architectures.
Loop scheduling involves
handling a partially ordered set of operations which are to be
performed repetitively over a sequence of iterations.
Our original contribution is the proposal
of applying the theory and methods in timed Petri net
%%and the {\em behavior graph}
to fine-grain loop scheduling
due to their unique power in modeling both the partial order
and the cyclic nature of the loop execution sequence
in a unified fashion.
The behavior of a Petri net
can be modeled by constructing its {\em behavior graph} (at compile-time),
which contains a repetitive
pattern in its firing sequence
known as the {\em cyclic frustum}.


%%In \cite{GaoWonNin91.2},
A Petri net model has been
developed to model a class of loop programs.
We have proven the following results: (1) when the net is operated under the
{\em earliest firing rule},
a cyclic frustum will appear in its behavior graph within a bounded number
of steps.
(2) a polynomial time bound can be established
for such cyclic frustum to occur
running under the earliest firing rule.
This resolves a known problem in Petri net theory by itself.
More importantly, it shows the feasibility
for a compiler to
determine, at compile-time, the cyclic frustum;
(3) from a cyclic frustum we can derive
a time-optimal schedule for the corresponding loop, and
a method is given to compute the optimal computation rate as well as
the critical cycles in the program graph which dominate the rate.
(4) we demonstrated that it is possible to integrate
resource limitations into the proposed model, e.g., machines
with single or multiple pipelined execution units.
These results are important and original.
The mechanism of detecting
cyclic frustums has been implemented in a prototype compiler testbed.
Simulation results
have demonstrated that the cyclic frustum
can be detected very quickly for real loops.

We have extended our work
%% in \cite{GaoWonNin91.2}, 
and studied
the problem of minimum storage 
allocation to loops
under rate-optimal scheduling.
We have shown that, at least for a class
of dataflow loops, the optimal storage problem
can also be solved in polynomial time.
%% \cite{GaoNin91.1}.


\vspace{0.25 cm}
%%\noindent II.1.4. Register Allocation and Instruction Scheduling
\noindent II.1.3. {\em Advanced Software Pipelining and Scheduling Techniques}

\vspace{0.25 cm}
We have studied the use of periodic schedules in
software pipelining for single and nested loops.
%%\cite{VandongenGaoNin92,GaoNinVan93.2}.
We have extend our methods to handle scheduling and register allocation
simultaneously based on an integer linear programming
(ILP) based framework as described in Ning's Ph.D thesis.
%%\cite{Ning93,NingGao93}.
A key intuition leading to our surprisingly simple formulation and
its efficient solution is the association of maximum computation rate
of a program graph with its
{\em critical cycles} due to Reiter's pioneering work
on Karp-Miller computation graphs.
%% \cite{Reiter68}.
In particular, our method generalizes the work
by Callahan, Carr and Kennedy on
{\em scalar expansion},
%%\cite{CallahanCarKen90},
the work
by Lam on {\em modular variable expansion}
for software pipelined loops,
%% \cite{Lam88},
and the work by Rau et al on
register allocation for modulo scheduled loops.
%% \cite{RauEtAl92}.
We have also proposed the ``interval graph'' based register
allocation algorithms which appear to provide a good representation
to study combined instruction scheduling and
register allocation methods.

Most recently, we have utilized such
ILP based framework to find {\em rate-optimal} periodic schedules
under both resource and register
constraints.
For example,
we would like to address the following software pipelining problem:
given a loop and a machine architecture with a fixed number
of processor resources (e.g. function units), how can one
construct a software-pipelined schedule
which runs on the given architecture at the maximum possible iteration
rate (so called {\em rate-optimal})
while minimizing the number of registers?
Our main contributions of this paper are listed below.
First, we demonstrate that such problem can be described
by a simple mathematical
formulation with precise optimization objectives under
periodic linear scheduling framework.
The mathematical formulation provides a clear picture which permits one
to visualize the overall solution space (for rate-optimal schedules)
under different sets of constraints.
Secondly, we show that a precise mathematical formulation
and its solution {\em does} make a significant performance
difference!  We evaluated the performance of our method
against three other leading contemporary heuristic methods and demonstrated
%Huff's Slack
%        Scheduling~\cite{Huff93}, Wang, Eisenbeis, Jourdan and Su's
%        FRLC~\cite{WangEtAl93}, and Gasperoni and Schwiegelshohn's modified
%        list scheduling~\cite{GasperoniSch91}.
that        Experimental results show that 
our method often
performed significantly better than these methods.
Research along this line 
%% ~\cite{GovindarajanAltGao94,GovindarajanAltGao94.2}
is now leading to another Ph.D thesis by Erik Altman.
%% \cite{Altman94}.

The impact of dynamic scheduling mechanisms --- such as the
reorder buffer (or completion buffer) and renaming mechanisms --
on scheduling and register allocation have been studied in
Luis Lozano's MSc thesis.

\vspace{0.25 cm}

\noindent II.1.4.  {\em A Methodology for Collective Loop Optimization}

\vspace{0.25 cm}
Traditionally, the methodology of
loop optimization and parallelization is to perform optimization on a single
loop (or loop nest), one at a time.
%%In \cite{Gao86.4,Gao90},
% have pointed out the importance of performing
%optimization for a collection of loops simultaneously.
%In \cite{SarkarGao91},
We have developed a methodology of
%% such
collective loop optimization.
%% is formulated and developed.
Such methodology has been applied to a collection of loops
to perform
a novel
optimization called {\it array contraction}, that saves space and time
by converting an array variable
into a scalar variable or a buffer containing a small number of scalar
variables.  We show that the array contraction problem can
be solved efficiently for a class of loops.
These results are original.

\vspace{0.25 cm}
\noindent  II.2. Compiling for Distributerd Machines


\vspace{0.25 cm}
We have been working on enabling compiling methodology and techniques for
distributed memory machines.
%in the following areas.
We have proposed and implemented
%an integer linear programming based framework
a parallelizing technique
which automatically computes computation and data decompositions
for sequentially written applications.
Under our decomposition algorithms, a program is divided
into collections (called clusters) of loop
nests. Within each cluster of nests,
the data locality constraints are formulated as a system of
homogeneous linear equations which is solved by
polynomial time algorithms.
Our algorithms also attempt to minimize data redistribution communications between
loop clusters.
The data locality constraints within a cluster may need to be relaxed
to trade locality
for parallelism. Such relaxations are guided by exploiting the
hierarchical program nesting structures from outer to inner nesting levels.
Our method can handle complex programs containing perfect and
non-perfectly
nested loops with
or without
loop-carried dependences.
%%\cite{NingVanGao94.5,NingVanGao95}.
To apply our method, we have extended the {\em array dataflow analysis}
technique by P. Feautrier
%% \cite{Feautrier91}
and performed an initial implementation and experimentation
on benchmark programs such as Perfect Club Benchmarks.
This leads to  R. Wen's SM thesis preparation.
%%\cite{Wen's Thesis in Preparation}.
%\cite{Wen94}

This technique has been tested in a research High-Performance C
(HPC) compiler 
and preliminary results are very encouraging.
%% \cite{NingVanGao95}.
We have also proposed a novel technique for
computation and data decomposition
based on collective loop optimization.
%% \cite{GaoSar90,GaoSarVaz93}.


%\vspace{0.25 cm}
%\noindent II.1.5. Languages for Parallel Programming
%
%\vspace{0.25 cm}
%Despite their importance in scientific computation,
%arrays have posed a  challenge to the efficient
%implementation of functional languages.
%%%In \cite{GaoEtAl90.1}, 
%We have proposed a monolithic array constructor
%which provides a solution to two
%major problems arising in the implementation of monolithic arrays:
%(1) the overhead of scheduling and synchronization for
%recursively defined arrays;
%(2) the copying of
%the intermediate arrays during array construction.
%Our array constructor allows an index domain to be constructed from
%a set of rectangular {\em index regions} and combinations of these.
%%An ordered sequence of regions may be specified in
%a fashion which can be checked by a compiler using simple subscript
%analysis techniques.
%An array is also allowed to be monotonically defined by iteration
%without using incremental array update operations.

\vspace{0.25 cm}
\noindent II.3. Efficient Algorithms for Flowgraph Analysis

\vspace{0.25 cm}
Dataflow  analysis framework based on
Static Single 
Assignment (SSA) form,
Sparse Evaluation Graphs (SEG),
Dependence  Flow Graphs (DFG), etc.,
demand fast computation of  program points where data flow
information must be merged, the so-called   {\bf $\phi$-nodes}.
To the best of our knowledge, the problem of finding
an algorithm for computing {\bf $\phi$-nodes} for an
arbitrary SEG in linear time remains 
open.

We have present a
surprisingly simple algorithm for computing $\phi$-nodes
for  arbitrary flowgraphs (reducible or irreducible) that
runs in  {\em  linear} time.
We employ
a novel program representation,
called the {\bf DJ-graph}.
%%% (Section~\ref{Djg}).
The skeleton of the DJ-graph of a program is the dominator tree of
its flowgraph.
The tree skeleton is augmented with
{\em join edges} (called J-edges)
from the original flowgraph which   potentially lead to
join nodes where data flow information are merged.
Based on DJ-graphs, we have developed other novel and efficient algorithms to
solve a series problems in flowgraph analysis such as
multiple-node immediate dominator analysis, identification of reducible and irreducible graphs,
and incremental algorithm for maintaining dominator trees.
This research leads the preparation of V.C. Sreedhar's Ph.D thesis.

\vspace{0.25 cm}
\noindent  II.4. International Interaction and Recognition

\vspace{0.25 cm}
The work at McGill in compiling has been in constant interaction with
the international
research community of this field, and the applicant has
been an invited to present papers on the 2nd, 3rd, 4th, 5th and 6th Workshop
on Languages and Compilers for Parallel Computing (1989,90,91,92,93).
This workshop series
is a very important and well-known international event in this research area,
and has been a forum for
invited speakers to present most recent and new significant research results.
The applicant (and his co-authors) has been the few invited speaker from
a Canadian institution.
Most work presented was refereed rigorously by at least three expert referees.
The applicant has been elected into program committees of many
international conferences in this field.


\vspace{0.25 cm}
\noindent \noindent {\bf III. Other Contributions}

\vspace{0.25 cm}

For other research contributions, please see the publication list
in the next section.

%Outside the mainstream of my research, I am also interested in
%parallel algorithms.  One important contribution
%I made is to a parallel algorithm for
%the All Pairs Examination Problem (APE), which appears in
%many applications.


%%In \cite{GaoTho88}, I introduced a new algorithm which is
%%ideal for hypercube configurations,
%%and showed that it can achieve the lower bounds of both computation and
%%communication steps under the restriction that each processor is able to
%%hold one pair of the elements at each step.
%%In \cite{TheobaldGao91.1},
%%we have generalized the algorithm beyond the restriction, and
%5proposed a new parallel APE  algorithm which uses processor time optimally
%%and requires fewer communication steps than previous algorithms,
%%with minimal
%%network traffic and low run-time overhead.
%%These results are important and original.




%\noindent {\bf References}
%
%\bibliographystyle{plain}
%\bibliography{/labs/acaps/doc/bib/main,submitted}
%\newpage

%\noindent {\lb Section I.B: A List of Research Publications}

%\section*{Rerefeed Journal Papers}
%\input{journal-bib.bbl}
%\section*{Refereed Conference Papers}
%\input{conf-bib.bbl}
%\section*{Monographs and Books}
%\input{books-bib.bbl}

%\newpage{16}

%\noindent {\lb Section C: Professional Contributions}
%\vspace{0.2 cm}

%
%\input{profession}

