Quadratic zero-one programming based synthesis of application specific data paths

In this paper, a novel technique for the synthesis of complex multi-functional units is presented. Given a set of functions or instructions, the goal is to minimize the area cost of a unit that can execute these functions. A common set of primitive functional units is allocated and shared between operations which belong to different functions. In the present approach, a bipartite matching based technique is extended with a quadratic cost function which allows for a much more accurate modeling of interconnect cost compared to previous approaches. In the optimization process, functional unit type selection, instance allocation and instance assignment are performed simultaneously. As an extension of the technique, a set of constraints which exclude solutions with false combinatorial cycles are also presented. Experiments show that highly optimized results can be obtained with acceptable CPU times.