Re: DFA Scheduler and Processor Pipelines

Christian Parpart <cparpart@surakware.net> wrote:
>well this is a really very unknown part for me.
>Does anyone know what exactly a DFA Scheduler is,
>or even how to implement such a scheduler?
>
>It is mentioned on the gcc.gnu.org site that they'll
>use the DFA scheduler for their processor pipe lines.
>I'd like to get more informations about DFA. Does anyone
>have some usefull urls?
>


The so-called "DFA scheduler" is an instruction scheduler
which uses finite automata to detect resource conflicts (as opposed
to detecing conflicts with some other technique, such as resource
matrices).


Without going into too much detail, the general idea is that
when one is writing an algorithm to re-order instructions ("instruction
scheduling"), a method is needed to detect whether instructions
are competing for the the same resources ("structural hazard detection" or
"resource conflict detection", etc.) so that those conflicts can be
minimized (or eliminated on statically scheduled architectures).


There are numerous ways to implement hazard detection in instruction
schedulers, such as using finite automata. This method is desirable in
that each conflict query can be done with one (or a small number)
of table lookup(s). Other methods are generally not as fast, but
have other benefits. For example, it is cumbersome to use FAs to model
resource conflicts for modulo-scheduling (the standard FA method
isn't directly applicable and requires modifications -- usually requiring
large space requirements). The speed of conflict detection is especially
important in schedulers which do large amounts of backtracking, etc. In
those types of schedulers, conflict detection time can become a significant
fraction of overall scheduling time.


There is a huge body of literature on scheduling and related issues.
You should have no trouble searching with those keywords and developing
matches. However, for one example article to get started on using FAs for
hazard detection, read:
Muller, T. "Employing Finite Automata for Resource Scheduling"
MICRO-26, 1993.


As for gcc. Vladimir Makarov has implemented a FA-based hazard detection
module for the gcc instruction scheduler and an accompanying pipeline
description language (as an extension of the current machine desc. facility).
The code currently is in a development branch at gcc.gnu.org. It is to be
merged into the main sources when the code review process is done. Vlad
and I have both implemented production schedulers with his FA-based code.


Regards, Jason Eckhardt.

Return to the comp.compilers page.
Search the comp.compilers archives again.