GLOBAL OPTIMIZATION APPROACH FOR ARCHITECTURAL SYNTHESIS

A relaxed LP model, which simultaneously schedules and allocates functional units and registers, is presented for synthesizing cost-constrained globally optimal architectures. This research is important for industry by providing exploration of optimal synthesized architectures since it is well known that early architectural decisions have the greatest impact on the final design. A mathematical integer programming formulation of the architectural synthesis problem was transformed into the node packing problem. Polyhedral theory was used to formulate constraints that decreased the size of the search space, thus improving integer programming solution efficiency. Execution times are an order-of-magnitude faster than previous research that uses heuristic techniques. This research breaks new ground by 1) simultaneously scheduling and allocating in practical execution times, 2) guaranteeing globally optimal solutions for a specific objective function, and 3) providing a polynomial run-time algorithm for solving some instances of this NP-complete problem.