Allocation of dual-stacks in data path synthesis

A general purpose storage structure called dual-stack, which is practically implementable, is explored for data path synthesis. Dual-stack is an extension of the conventional single-stack. Dual-stacks maintain an effective access separation among variables whose lifetime intervals overlap which is not possible in single-stacks. Utilizing this structure can lead to a better performance in the final implementation of the algorithm. The problem of allocating variables to stacks and interconnection allocation has been modeled as a 0-1 integer linear programming (ILP) formulation with the objective to design a data path with a minimum number of stacks, registers and interconnects. The effectiveness of the proposed storage structure is demonstrated with the elliptical wave filter benchmark example