Abstract
We present an architecture optimization technique called divide-and-concatenate for universal hash functions. The area of a multiplier increases quadratically and its speed increases gradually with the operand size and two universal hash functions are equivalent if they have the same collision probability property. Based on these observations, the divide-and-concatenate approach divides a 2w-bit data path (with collision probability 2 -2w) into two w-bit data paths (each with collision probability 2 -w), applies one message word to these two w-bit data paths and concatenates their results to construct an equivalent 2w-bit data path (with collision probability 2 -2w). We demonstrate this technique on Linear Congruential Hash (LCH) family. When compared to the 100% overhead associated with duplicating a straightforward 32-bit LCH data path, the divide-and-concatenate approach that uses four equivalent 8-bit data paths yields a 101% increase in throughput with only 52% hardware overhead.
Original language | English (US) |
---|---|
Title of host publication | Proceedings - Design Automation Conference |
Pages | 614-617 |
Number of pages | 4 |
State | Published - 2004 |
Event | Proceedings of the 41st Design Automation Conference - San Diego, CA, United States Duration: Jun 7 2004 → Jun 11 2004 |
Other
Other | Proceedings of the 41st Design Automation Conference |
---|---|
Country/Territory | United States |
City | San Diego, CA |
Period | 6/7/04 → 6/11/04 |
Keywords
- Design
- Experimentation
- Performance
ASJC Scopus subject areas
- Hardware and Architecture
- Control and Systems Engineering