RE: DFA Scheduler and Processor Pipelines

"Naveen Sharma, Noida" <>
4 May 2002 14:22:20 -0400

          From comp.compilers

Related articles
RE: DFA Scheduler and Processor Pipelines (Naveen Sharma, Noida) (2002-05-04)
| List of all articles for this month |

From: "Naveen Sharma, Noida" <>
Newsgroups: comp.compilers
Date: 4 May 2002 14:22:20 -0400
Organization: Compilers Central
Keywords: optimize
Posted-Date: 04 May 2002 14:22:20 EDT


> 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 a scheduling technique based on FINITE AUTOMATA
described in

Efficient Instruction Scheduling using Finite State Automata
by Vasanth Bala and Norman Rubin. (MICRO-28) Nov,95

Broadly speaking GCC had function unit based model for
scheduling in which described characterisitics of
processor unit in the pipeline (multiplicity,simultaneiuty etc).
This is based the other way round. Instruction are described
in terms of functional unit requirements. The scheduler
maintains a collision matrix for resource hazards in processor pipeline
(which corresponds to a DFA state) and updates it as insns are issued.

Incidentally I wrote DFA description for Sh4 processor for GCC and
this method would yield performance improvement of the
order of 10-18 %

You will get lot more detail in the research paper which
is downloadable from the net.

Naveen Sharma.

Post a followup to this message

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