Seminário de Teoria da Computação

The datapath meging problem in the design of reconfigurable systems

                 Cid Carvalho de Souza

            Sexta-feira, 12 de setembro de 2003

               Auditório do IC (IC1), 13:00hs


Resumo:

In this  talk we discuss the  problem of merging  circuit datapaths in
the design of reconfigurable systems.

We  show that  this problem  can  be formulated  in terms  of a  graph
optimization problem and belongs to NP-hard.

The focus of our work is  on the development of an Integer Programming
model  capable  to provide  good  dual  bounds  for the  problem  and,
hopefully,  to  prove  optimality  of some  solutions  for  real-world
instances.

To this end, we propose an Integer Programming  model and present some
valid inequalities that can be  added to tighten the linear relaxation
and used as cutting planes in a branch-and-cut type algorithm.

Preliminary  computational  results  on  real instances  arising  from
multimidea applications are reported.

These results give an indication that, under certain circumstances, it
might be  reasonable to try to  solve the problem  exactly via Integer
Programming techniques.

This is a  joint work with André Lima, Nahri  Moreano and Guido Araújo
from IC--UNICAMP.