VLSI Design of Sorting Networks in CMOS Technology

VÍCTOR M. JIMÉNEZ-FERNÁNDEZ, ANA D. MARTÍNEZ, JOEL RAMÍREZ, JESÚS S. OREA, OMAR ALBA, PEDRO JULIÁN, JUAN A. RODRÍGUEZ, OSVALDO AGAMENNONI AND OMAR D. LIFSCHITZ

VLSI Design

INTECH

Año: 2012; p. 93 - 110

Although sorting networks have extensively been reported in literature (Batcher, 1962), there are a few references that cover a detailed explanation about their VLSI (Very Large Scale of Integration)realization in CMOS (Complementary Metal-Oxide-Semiconductor)technology (Turan et al., 2003). From an algorithmic point of view, a sorting network is defined as a sequence of compare and interchange operations depending only on the number of elements to be sorted. From a hardware perspective, sorting networks can be visualized as combinatorial circuits where a set of denoted compare-swap (CS) circuits can be connected in accordance to a specific network topology (Knuth, 1997). In this chapter, the design of sorting networks in CMOS technology with applicability to VLSI design is approached at block, transistor, and layout levels. Special attention has been placed to show the hierarchical structure observed in sorting schemes where the so called CS circuit constitutes the fundamental standard cell. The CS circuit is characterized through SPICE simulation making a particular emphasis in the silicon area and delay time parameters. In order to illustrate the inclusion of sorting networks into specific applications, like signal processing and nonlinear function evaluation, two already reported examples of integrated circuit designs are provided (Agustin et al., 2011; Jimenez et al., 2011).