Protocol Knowledge in Slack Matching
Tuesday October 31, 2006
Hamerschlag Hall D-210
Carnegie Mellon University
Stalls, due to mis-matches in communication rates, are a major performance
obstacle in pipelined circuits. If the rate of data production is faster
than the rate of consumption, the resulting design performs slower than when
the communication rate is matched. This can be remedied by inserting pipeline
buffers (to temporarily hold data), allowing the producer to proceed if the
consumer is not ready to accept data. The problem of deciding which channels
need these buffers (and how many) for an arbitrary communication profile is
called the slack matching problem; the optimal solution to this problem has
been shown to be NP-complete.
In this talk, I will present a heuristic that uses knowledge of the
communication protocol to explicitly model these bottlenecks, and an iterative
algorithm to progressively remove these bottlenecks by inserting buffers. I
will show how this approach naturally handles large designs with arbitrarily
cyclic and acyclic topologies, and which exhibit various types of control choice.
The heuristic is efficient, achieving linear time complexity in practice, and
produces solutions that (a) achieve up to 60% performance speedup on large
media processing kernels, and (b) can either be verified to be optimal, or the
approximation margin can be bounded. I will be presenting this paper at ICCAD 2006.
Girish is an n-th year Phd student, who has spent the last few years
understanding the nature of asynchronous circuits, hardware compilation, and
large, coarse-grained reconfigurable fabrics. He is part of the Phoenix team
supervised by his adviser, Seth Goldstein.