A design methodology for optimally folded, pipelined architectures in VLSI applications using projective space lattices

Semi-parallel, or folded, VLSI architectures are used whenever hardware resources need to be saved. Most recent applications that are based on Projective Geometry (PG) based balanced bipartite graphs also fall in this category. Many of these applications are actively being researched upon, especially in the area of coding theory and matrix computations. Almost all these applications need bipartite graphs of the order of tens of thousands in practice, whose nodes represent parallel processing. To reduce its implementation cost, reducing amount of hardware resources is an important engineering objective. In this paper, we provide a high-level, top-down design methodology to design optimal semi-parallel architectures for applications, whose Data Flow Graph (DFG) is based on PG bipartite graph. Unlike many other folding schemes, the topology of connections between physical elements nodesdoes not change at runtime in this methodology. Hence the folding scheme achieves the best possible throughput, in lack of any overhead of shuffling data across memories while scheduling another computation on the same processing unit. Another advantage is the ease of implementation. To lessen the throughput loss due to folding, we also incorporate a multi-tier pipelining strategy in the design methodology. A C++-based synthesis tool has been developed and tested for automatic generation of RTL models, and is publicly available. A specific high-performance design of a low-density parity check (LDPC) decoder based on this methodology was worked out in past, and has been patent pending.