Divide-and-concatenate: An architecture level optimization technique for universal hash functions

Bo Yang, Ramesh Karri, David A. McGrew

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
Pages614-617
Number of pages4
StatePublished - 2004
EventProceedings of the 41st Design Automation Conference - San Diego, CA, United States
Duration: Jun 7 2004Jun 11 2004

Other

OtherProceedings of the 41st Design Automation Conference
CountryUnited States
CitySan Diego, CA
Period6/7/046/11/04

Keywords

  • Design
  • Experimentation
  • Performance

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Divide-and-concatenate: An architecture level optimization technique for universal hash functions'. Together they form a unique fingerprint.

Cite this