VLSI Computations

The Future

Computers to be used in the 1990s may be the next generation. Very large-scale integrated (VLSI) chips will be used along with high-density modular design. Multiprocessors like the 16 processors in the S-1 project at Lawrence Livermore National Laboratory and in the Denelcor’s HEP will be required. Cray-2 is expected to have four processors, to be delivered in 1985. More than 1000 mega float-point operations per second (megaflops) are expected in these future supercomputers.

Mapping Algorithms Into Vlsi Arrays

Procedures to map cyclic loop algorithms into special-purpose VLSI arrays are described below.  The method is based on mathematical transformation of the index sets and the data-dependence vectors associated with a given algorithm.  After the algorithmic transformation, one can devise a more efficient array structure that can better exploit parallelism and pipelining by removing unnecessary data dependencies.

Need For Parallel Processing

Achieving high performance depends not only on using faster and more reliable hardware devices, but also on major improvements in computer architecture and processing techniques. State – of – the art parallel computer systems can be characterized into three structural classes: pipelined computers, array processors and multi-processor systems. Parallel processing computers provide a cost-effective means to achieve high system performance through concurrent activities.

The Systolic Array Architecture

The choice of an appropriate architecture for any electronic system is very closely related to the implementation technology.  This is especially true in VLSI.  The constraints of power dissipation, I/O pin count, relatively long communication delays, difficulty in design and layout, etc., all important problems in VLSI, are much less critical in other technologies.  As a compensation, however, VLSI offers very fast and inexpensive computational elements with some unique and exciting properties.  For example, bi-directional transmission gates (Pass transistors) enable a full barrel shifter to be configured in a very compact NMOS array.

VlSI Computing Structures

Highly parallel computing structures promise to be a major application area for the million-transistor chips that will be possible in just a few years.  Such computing system has structural properties that are suitable for VLSI implementation.  Almost by definition, parallel structures imply a basic computational element repeated perhaps hundreds or thousands of times.  This architectural style immediately reduces the design problem by similar orders of magnitude.  In this section, we examine some VLSI computing structures that have been suggested by computer researchers.  We begin with a characterization of the systolic architecture.  Then we describe methodologies for mapping parallel algorithms into processor arrays.  Finally, we present the reconfigurable processor arrays for designing algorithmically presented below.  Modularly structured VLSI computing structures will be presented. Described below are key attributes of VLSI computing structures.

Reconfigurable Processor Array

Algorithmically specialized processors often use different interconnection structures.  As demonstrated in Figure 10.30, five array structures have been suggested for implementing different algorithms.  The mesh is used for dynamic programming.  The hexagonally connected mesh was shown in the previous section for L-U decomposition.  The torus is used for transitive closure.  The binary tree is used for sorting.  The double-rooted tree is used for searching.  The matching of the structure to the right algorithm has a fundamental influence on performance and cost effectiveness.

Conclusion

The applications of VLSI computations appear in real-time image processing as well as real-time signal processing. The VLSI feature extraction introduced by Foley and Sammon in 1975 enables signal and image processing computations effectively and speedily.Pattern embedding by wafer-scale integration (WSI) method introduced by Hedlum is another application of VLSI computing structures. Modular VLSI architectures for implementing large scale matrix arithmetic processors have been introduced.