DC7-Rochester 94

DC7--A Cheap, Superfast Data Comparator Chip

C. H. Ting, June, 1994

Summary

I have designed and produced a new, low cost, superfast Data Comparator chip DC7 which could be used to search data patterns in very large databases. The current design puts 490 bit-comparator cells on a small 0.1"x0.1" silicon die, organized in 7 rows of 70 bit-comparator cells. Its clock rate is greater than 50 MHz. In volume production, this chip will cost $2.00 a piece.

Main features of this chip include the following:

1. 7 simultaneous 70-bit comparisons, 490 bit-comparator cells

2. Each bit-comparator cell has a shift register, a pattern register and a mask register

3. Matured 1.2 micron, single poly double metal, CMOS process

4. Serial chaining for longer data and pattern words

5. Parallel expansion for wider data words

6. 50 million comparisons per second

7. Global compare output to facilitate interrupts to host computer

8. Small silicon die, 2.4x2.4 mm²

9. Popular 40 pin DIP package

10. Modular and scalable design suitable for bigger and faster production chips

The design was prototyped at the Orbit Semiconductor, Inc., and the prototype chips works beautifully. I am designing a PC plug-in board with this chip so that the performance of the chip can be tested more realistically in a computer system. I am exploring its applications in data and pattern searching in CD-ROM's and in Genebank databases.

1. Design of the Data Comparator Chip

The basic structure of this Data comparator Chip is shown in Figure 1. It contains a large Shift Register, a Data Register, and a Mask Register. All three registers have the same length of 70 bits. Every clock cycle, a new bit is shifted into the Shift Register and the oldest bit is shifted out. The bit pattern in the Shift Register is compared with that in the Data Register. If all the bits in the Shift Register not masked of by the Mask Register bits agree with the corresponding bits in the Data Register, a Compare bit is set. This Compare bit is brought to an output pin. The Mask Register allows patterns to be selectively compared, thus greatly increase the flexibility of pattern matching or data comparing. There are 7 such Shift-Data-Mask Register sets in a DC7 chip. The 7 Compare bit from the 7 register sets are OR'ed together. The resulting bit is the Global Compare bit. This bit is also brought to an output pin. The Global Compare bit is very useful in interrupting the host computer when any of the register sets detects a particular data pattern.

Binary data are fed into a Shift Register serially by a positive-going pulse on the CLOCK input pin. Since the other end of the Shift Register is also brought to an output pin, many DC7 chips can be connected in series to increase the depth of the binary bit pattern to be searched. When a DC7 chip is wired serially, one can search a binary pattern of 490 bits long. DC7 has 7 Shift Register sets, and it can handle 7 bit ASCII data very conveniently in search text data bases. The length of data pattern to be search is then 70 bytes. If the chip is used to search more complicated data patterns more than 7 bits in width, many DC7 chip can be arranged in parallel to handle words of larger width.

The Data Register is loaded from the Shift Register with a positive-going pulse on the DataLoad input pin. The Mask Register is loaded from the Shift Register with a positive-going pulse on the MaskLoad input pin. To initialize a chip to search for a particular binary pattern, the target pattern is first loaded serially into the Shift Register. The DataLoad pin is raised to 5 volts and then lowered to ground quickly. It causes the data in the Shift Register to be loaded into the Data Register. Similarly the Mask Register must be loaded with a mask pattern, which determines which bits are to be ignored in the comparison. When DC7 chip is powered up, all the registers are cleared.

The logic circuitry of this DC7 chip is shown in Figure 2. Each bit is handle by a shift register, two latches, and two gates. This group of logic forms a cell which can be replicated to form a complete chip. The current implementation of DC7 puts 7x70 of these cells on a single chip.

Although the design of this chip is optimized for data comparing, its application is not limited to data comparing alone. Any application in which pattern matching is needed can use this chip. Some application which come immediately to mind are: data encryption and decryption, sync separation in disk drive controller, packet switching in telecommunication, file maintenance, image processing and understanding, etc.

This DC7 chip is designed for expandability. Many of them can be connected to form arrays of two or more dimensions to handle two dimensional data and data of even higher dimensions.

Since the logic in each cell is very simple and not many gates are involved, this chip can run at very high speed. The pulse width of the CLOCK, DataLoad and MaskLoad should be greater than 10 ns. The loading and shifting rate is 50 MHz. As all 470 bits in the Shift Registers are compared with the bit patterns in the Data Register, the comparison rate can be sustained at about 23 GBits/sec. Apparently, the actual comparison rate is more likely to be limited by the data bandwidth by the host computer or the source of the data stream.

2. Layout of DC7

DC7 was laidout by Chuck Moore of the Computer Cowboys, using the OKAD chip design system built by Mr. Moore. The diffusion areas, transistors, and interconnections are laid out in a grid of tiles. Each tile is 4 microns on a side, and the chip contains 600x600 tiles. The size of the silicon die is 2.4x2.4 mm². 40-pin DIP packages are used to bond the dies. The chip was prototyped by Orbit Semiconductor, on its N-well, single poly, double metal, 1.2 micron CMOS process. This is the smallest and the cheapest die size Orbit supports.

The chip pinout is shown in Figure 3.

Some samples of the layout is shown at the end of this volume where I discuss how to use the Deskjet 550C to make color prints of the layout.

3. Discussions

To make use of the DC7 chip, it has to be integrated into a computer system so that the Data Registers and the Mask Registers can be loaded from a host computer, the data stream is piped through the DC7 chip, and the Compare and Global Compare outputs are constantly monitored. To test the chips and also to demonstrate the performance of DC7, a PC plug-in board was built to interface a DC7 chip to the ISA bus in the PC. The schematics of this board is shown in Figure 5.

On this test DC7 board, a parallel I/O chip Intel 8255A is used to ship data into DC7 and also monitor the compare outputs from DC7. Port A of 8255A is used to supply 7-bit data to the seven Shift Register in DC7. Port B is used to monitor the compare outputs from DC7. Port C provides the clocking signals to the CLOCK, DataLoad, and MaskLoad pins on DC7.

A demonstration program was developed to exercise all the circuitry in DC7 and to tests its text searching capability. The program is shown in Listing 1.

4. Conclusion

It is very satisfying to design a chip and actually build it successfully. The DC7 chip is very fast and very cheap to build. It will find many applications in data searching and pattern matching. Having a set of long shift registers by itself can be of values in many signal processing applications. Now that the computers are get bigger and more powerful, the data to be handled by the computers grow even more rapidly. Specialized chips like DC7 will greatly ease the task of data searching and greatly speed up the search process when it is integrated into a system.

Figure 1. The architecture of the Data Comparator Chip.

Figure 2. The logic design of the Data Comparator Chip.

Figure 3. The Pinout of DC7

D0-6 Data input

Q0-6 Data output - delayed 70 cycles

C0-6 Data compare output, low if data match pattern

C Low if some match, (AND of C0-6)

Kd Data clock. Latch data on rising edge, output data on falling edge

Kp Latch pattern from data when high

Km Latch mask from data when high

Ti Test input

T Test output

Figure 3. Chip layout in DC7.

( See Page 113 and 114 for samples of DC7 layout )

Figure 4. The Schematics of a DC7 Plug-in Board.

Listing 1. Testing Code for DC7

\ Test BC7 data comparator chip, 10dec93cht

empty

hex

3bc constant portBase

\ 378 constant portBase \ alternate printer port

portBase constant outPort

portBase 1+ constant inPort

portBase 2+ constant controlPort

: delay 4 0 do loop ;

comment:

: Kd ( b -- , shift data )

dup 7f and outPort pc!

dup 80 or outPort pc!

7f and outPort pc!

;

comment;

code Kd ( b -- ) \ latch data into shift register

pop ax

mov dx, # outPort

and al, # 1f

out dx, al \ out data

or al, # 80

out dx, al \ raise Kd

and al, # 1f

out dx, al

end-code

comment:

: Kp ( -- , latch data )

4 controlPort pc! delay

3 controlPort pc! delay

;

: Km ( -- , latch mask )

2 controlPort pc! delay

3 controlPort pc! delay

;

comment;

code Kp ( -- ) \ latch data into data register

mov dx, # outPort

mov al, # 0

out dx, al \ out Kp

or al, # 40

out dx, al

and al, # 0

out dx, al

end-code

code Km ( -- ) \ latch data into mask register

mov dx, # outPort

and al, # 0

out dx, al \ out mask

or al, # 20

out dx, al

and al, # 0

out dx, al

end-code

: shiftData ( b -- )

;

: reset 0 outPort pc! \ clear data and mask

\ enable all bits to compare

3 controlPort pc!

80 0 do 0 kd loop \ shift in 0's

kp km

;

: disable \ load 1 to mask, disable data

\ compare will all become 0 active

3 controlPort pc!

80 0 do 7F kd loop \ shift in 1's

km km

;

decimal

: cc ( -- )

-1 0

DO I

LOOP

;

: ccc begin cc key? until ;

: tt 0 begin 1+ dup kd kp km key? until ;

: aa ( -- )

-1 0 DO

0 Kd -1 Kd

LOOP

;

: aaa begin aa key? until ;

: bb ( b -- b )

-1 0 DO

0 Kd dup Kd

LOOP

;

: bbb ( b -- )

begin bb key? until drop ;