Superposed Parallel Buses: A Systolic Area-Time Optimal VLSI Interconnection

Abstract:

This paper presents a new class of interconnection schemes, based on superposed parallel buses and called systolic grid interconnection. This scheme is optimal both in area and time in terms of VLSI complexity for multi-point networks with prescheduled permutation. This scheme is faster than previously reported
interconnection schemes using linear area. This scheme is especially suitable for utilizing fast but area-limited technology to interconnect a large number of single chip processors using slower technology. Although the primary proposed application is to solve large sparse systems of linear equations, such as those arising from finite element analysis, this interconnection scheme is widely applicable because of its fast permutation capability. The construction of the grid and its VLSI optimality are described as well as some applications.