Two dimensional folding strategies for improved layouts of cyclic shifters

Our work aims at improving the layouts of cyclic shifters, especially regarding the wire length on the critical path. Like in P.-M. Seidel et al. (2001) we are considering the placement of basic gates and we target improving the layout and routing properties through the placement choices. In our approach we do not only allow to optimize the placement of muxes within the layers, but we generally abstract from the constraint that shifter layouts are organized in fixed layers. We allow the MUXes to be placed more liberally within the shifter, our structured approach is to consider decomposing an n-bit cyclic shift into two disjoint cyclic subshifts and implementing the two subshifts in orthogonal orientations. This organization allows to make the layout of cyclic shifters more squared and have either gate or interconnection constraints determine both height and width of the shifter layout. The decomposition of the n-bit shift into two cyclic subshift requires small modifications to the selection signals within the shifter, but the modifications can be incorporated into the shifter design without affecting the critical path of the implementation.