An Efficient Exact Algorithm for Chip Resource Allocation Problem

In chip resource allocation, assigning blocks into a set of available stages in packet-processing pipeline is a critical problem that will greatly influence the efficiency of chip operation. In this work, we formulate the aforementioned problem as an Integer Programming (IP) model, in which the objective is to minimize the utilized pipeline stages, and the considered constraints involve: i) data dependency and control dependency relationships among the to-be-arranged blocks; ii) switching chip resource constraints. We show the NP-hardness of the studied problem. To boost the solution, we develop a new exact Objective Relaxation Induced Bounding and Variable Fixing driven Branch-and-cut algorithm (ORIBVF -BnC). Numerical experiments over a series of tested instances demonstrate that the proposed ORIBVF-BnC algorithm can significantly boost the solution (achieves a CPU time reduction on average 62.36%) compared to the commercial solver (Gurobi) and obtain the global optimal solution on large-scale problems in a reasonable amount of time.