QUADRATIC ZERO-ONE PROGRAMMING-BASED SYNTHESIS OF APPLICATION-SPECIFIC DATA PATHS

In this paper, a novel technique for the synthesis of complex multifun ctional units is presented. Given a set of functions, the goal is to m inimize the area cast of a unit that can execute these functions. A se t of primitive functional units is allocated and shared between operat ions which belong to different functions. In the presented approach, a bipartite matching-based technique is extended with a quadratic cost function which allows for a much more accurate modeling of interconnec t cost compared to previous approaches. In the optimization process, f unctional unit type selection, instance allocation, and instance assig nment are performed simultaneously. As an extension of the technique, a set of constraints which exclude solutions with false combinatorial cycles will also be presented. The technique finds its main applicabil ity in the synthesis of custom accelerator data paths in high throughp ut signal processing applications, as required in video, image process ing, front end speech processing, and user-end telecom. In addition, i t can be applied in the synthesis of the data path of domain-specific instruction set processors. Experiments show that highly optimized res ults can be obtained within acceptable CPU times.