A SOLUTION METHODOLOGY FOR EXACT DESIGN SPACE EXPLORATION IN A 3-DIMENSIONAL DESIGN SPACE

This paper describes an exact solution methodology, implemented in Ren sselaer's Voyager design space exploration system, for solving the sch eduling problem in a three-dimensional (3-D) design space: the usual t wo-dimensional (2-D) design space (which trades off area and schedule length), plus a third dimension representing clock length, Unlike desi gn space exploration methodologies which rely on bounds or estimates,t his methodology is guaranteed to find the globally optimal solution to a 3-D scheduling problem, Furthermore, this methodology efficiently p runes the search space, eliminating provably inferior design points th rough the following: 1) a careful selection of candidate clock lengths and 2) tight hounds-on the number of functional units or on the sched ule length, Both chaining and multicycle operations are supported.