Constrained via minimization for systolic arrays

Due to progress in VLSI technology, algorithm-oriented array architectures such as systolic arrays or bit-slice structures appear to be effective, feasible, and economic. The constrained-via-minimization problem for circuits composed of arrays of identical cells C is discussed. To guarantee identical electrical behavior of all instances of C and to allow further hierarchical processing, it is desirable to handle all instances of C identically. To this end, layer assignments of circuits needing a minimal number of via holes are sought. It is shown that this problem can be solved by embedding C on the torus, i.e. by identifying the northern boundary of C with the southern boundary, and the eastern one with the western one. The time complexity of the proposed algorithm is O(m³_C), where m_C is the number of routing segments in C