2-2   Cutting Critical Hardware

One of the most promising applications for configurable computing involves pattern matching. Pattern matching is used in tasks such as handwriting recognition, face identification, database retrieval and automatic target recognition. A fundamental operation of pattern matching involves comparing an input set of bits (representing an image, a string of characters or other data) with a set of templates corresponding to the possible patterns to be recognized. The system declares recognition when the number of input bits that match bits in the template exceeds some threshold.[1]

In the case of target recognition—a military application that drove some of our initial work —the greatest challenge is the rapid comparison of an input image to thousands of templates. A template could represent, for example, a front or side view of a specific type of vehicle. Each image typically contains thousands of pixels (picture elements), and a target could appear at any position within an image. To recognize targets fast enough for military applications, a system needs to perform comparisons at the rate of several trillion operations per second, because all the pixels in the input image must be compared with all the pixels in many templates.

With support from the Defense Advanced Research Projects Agency (DARPA), we have built a prototype recognition system with configurable hardware that achieves significant hardware savings by tuning itself to each template in turn. Many of the pixels in a typical template do not contribute to the matching results, and so the configurable computing machine could simply omit them from its calculations. A conventional system could not easily pare itself down in a similar way, because the pixels to be ignored differ from template to template. One can go further in exploiting the flexibility of configurable machines by tuning the hardware to take advantage of similarities among templates. The configurable hardware can process a set of templates in parallel, using only one comparison unit for each pixel whose value is the same for templates in that set. For example, rather than having eight separate hardware circuits consider a certain pixel for eight different templates, a single circuit can consider the pixel and then propagate its outcome to the seven other templates.

Most recently, we have built a prototype encryption system (also funded by DARPA) that takes advantage of configurable hardware. An FPGA implements the Data Encryption Standard (DBS), which uses 56-bit-loftg keys to encrypt 64-bit-long blocks of data. (A key in encryption is a number used to scramble or unscramble a confidential message.) DBS encryption usually proceeds in two steps: subkey scheduling and data processing. In the first step, a set of rotations and permutations translates the 56-bit encryption key into a series of 16 subkeys. Each subkey then processes the data in a separate round; a full set of 16 rounds encrypts or decrypts each 64-bit block. When the computer deals concurrently with multiple users, each dialogue between users must have a distinct key, and the encryption hardware will change keys as parts of messages arrive for different users.

In many applications of DES, the encryption key remains constant while a long block of data passes through the data path. For example, if two people are communicating over a secure network, they exchange a secure encryption key once and then use that key throughout the duration of their dialogue to generate the subkeys for each round of encryption or decryption. Some ASICs are designed to handle only one kind of encryption algorithm, such as DES; others —such as programmable digital signal processors—are capable of implementing many encryption algorithms.

With a configurable chip, the software can calculate the subkey values once, and the data-processing circuitry can be optimized for those specific subkeys. This approach allows the subkey-scheduling hardware to be completely removed from the system. These savings have allowed us to implement the DES algorithm in a 13,000-gate FPGA, instead of the 25,000-gate circuit previously required. When the encryption key must be changed, the user can quickly specify a new circuit, customized to the new key, and download it to the FPGA.

The target-recognition and encryption prototypes we have built help illustrate the enormous flexibility that arises when the hardware in a computer can be customized to a diverse and changing set of external data. There are many other applications that could benefit from the ability to modify the computation hardware in this manner, including digital communications, design automation and digital filtering for radar.

WORDS AND PHRASES

pixel               像素，图素

scramble     扰频，扰乱无线电信号的频率使在无特殊仪器情况下无法接收

schedule         图表，清单，调度表；进度

template 模板，样板，标准框，属性单元

threshold          阈值，门限

NOTES

[1]. A fundamental operation of pattern matching involves comparing an input set of bits (representing an image, a string of characters or other data) with a set of templates corresponding to the possible patterns to be recognized.

模式匹配的基本运算包括把输入的一组比特值(代表一幅图、一串字符或其他数据)与一组对应于可能被识别的模式的模板相比较。