Help on instruction scheduling problem

Hi,


I have a query about instruction scheduling which I hope is
appropriate material for posting to comp.compilers.


Background:


The hardware is controlled via binary images that tell the FPGA's what
to do. The hardware "executes" one instruction at a time (there is no
micro-processor, and there are no scratch registers). The registers
are for reading values, setting values and getting conversions to
happen.


All hardware is attached to a "backplane" that acts as a pipe on which
you can place a value (via the registers) to be transmitted to the
outside world.


Each "daughterboard" requires some set of "instructions" for setting
things up etc and another set for getting readings.


The placement of some of these sequences is critical in relation to
others (i.e. "After writing register X you need 4 cycles before you
can read X or Y (but A and B are fine for another 10 cycles)), other
sequences have to occur once in an image but placement is not critical
(i.e. they can be used as "filler", executing when otherwise we would
have to use "nops" to wait anyway).


On top of this there is a overriding requirement of measurement
frequencies (i.e. register A has to be read at least at 10 kHz) and we
aim for an "as short as possible format".


There is no FIFO or anything so if you need to send 10 signals out in
a given time (equidistant) you will need to issue the necessary
"instructions" at those locations on the image, trying to fit all
other "instructions" around it and observing the restrictions on
register usage:-


        x -ra- x -a'- x -r''a''- x - a'''- x - nop - ....


        x == signal that needs to go on the bus at this point.
        a == fillers with unrestricted instructions
        r == restricted instructions, i.e. has to be n cycles before x.
        nop == waits.


Sorry for the lengthy pre-amble. A possible analogy might be a
co-processor in a PC.


Question: Do you know of any literature that discusses how to solve
this "instruction scheduling" problem ? Would the GNU compiler have
any insights ? We can handle all the isolated requirements, but
fitting them together _and_ keeping to the hard time constraints is a
problem.


Any suggestions would be most welcome.


Thanks,


Boris Fennema
&
Declan Cox.


---------------------------------------------------
Declan Cox
Iona Technologies PLC
8-10 Pembroke st. lower
Dublin 2
IRELAND


Tel : +353-1-6625255
Fax : +353-1-6625244
Email: dcox@iona.ie
URL : http://www.iona.com
[This does indeed sound similar to instruction scheduling. You might want
to look at the Stanford MIPS work, which depended on the compiler to
schedule instructions correctly since the chip didn't have hardware
interlocks to enforce correctness. -John]
--

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