ACAL Seminar - Nov 16

[Thomas Bartold]

犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖
犖犖牧牧牧�
ADVANCED COMPUTER ARCHITECTURE LABORATORY
Department of Electrical Engineering and Computer Science,
University of Michigan ACAL Seminar
Thursday, November 16, 3:30 - 5:00 PM 1001 EECS
North Campus, University of Michigan

犖犖犖犖漯牧牧牧牧牧牧牧牧牧牧犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖
犖犖犖犖�

"Making Local Search Less Local:
New Techniques for Row-Based Placement"
By
John Lillis
University of Il, Chicago

Abstract: Combinatorial Search mechanisms are among the most successful in
handling NP-hard problems in practice. In this talk, I will give an overview
of work at UIC in this area in the context of row-based placement. The focus
of the work has been on the development of more powerful neighborhood
operators to drive combinatorial search. These operators are distinguished
by their scope: they are designed to enable a more expansive view of the
problem than traditional operators (frequently enabling exponentially large
neighborhoods). Two general techniques for devising such operators are based
on constraint relaxation and on constraint imposition. The general notion of
Relaxation Based Local Search is discussed as representative of the former.
Optimal Interleaving for intra-row optimization and Max-Gain Path
computation for placement legalization are examples of the latter.

These techniques have been incorporated into a prototype standard-cell
placer Mongrel. The techniques and how they fit together in Mongrel as well
as possible generalizations will be discussed.

Anyone wanting to meet with John Lillis please contact Igor Markov
imarkov@eecs

Thursday, November 16, 3:30 - 5:00 PM
Room 1001 EECS
North Campus, University of Michigan

犖犖犖犖犖犖犖犖犖犖犖犖犖漯牧牧牧牧牧牧牧牧的犖犖犖犖犖犖犖犖犖犖犖犖犖犖犖
犖犖犖犖犖