A 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. A mathematical integer programming formulation of the architectural synthesis problem was transformed into the node packing problem. Some integral facets of this polytope were extracted and generalized to produce integral solutions using the simplex algorithm without the need to branch and bound. Execution times are faster by an order of magnitude than previous research which makes use of heuristic techniques. This research breaks ground by simultaneously scheduling and allocating with practical execution times; guaranteeing globally optimal solutions for a specific objective function; and providing a polynomial runtime algorithm for solving this NP-complete problem.<>