Erik Saule
Laboratoire d'Informatique de Grenoble (LIG)


"Scheduling Instructions on Processors with Incomplete Bypass"

Florent Blachot, Guillaume Huard, Jonathan Pecero, Erik Saule, Denis Trystram 


  New generation of embedded VLIW processors such as the ST200
  implements a bypass mechanism between functional units. Thanks to
  this mechanism, the result of an arithmetic operation can be
  directly fetched as an operand of another operation. This eliminates
  the usual data dependence latency between the two operations.

  Nevertheless, when production costs enforce strong constraints on
  die area, an incomplete bypass may be implemented to save space. An
  incomplete bypass is a partition of functional units into small
  groups in which the bypass is complete. It implies that, depending
  on the allocation, the latency between dependent operation is either null
  or a fixed number of cycles.

  In this talk, we modelize the problem of scheduling instructions
  for the ST200 processor as a problem of scheduling unitary tasks on
  a hierarchical architecture with communication delays. We propose a
  approximation algorithm based on list scheduling whose factor
  dependent on the number of clusters.  We prove that the
  approximation factor is tight. Experimental results which have run
  on random graphs and on structured graphs demonstrate the
  effectiveness of our approach.