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

Bo Yang, Ramesh Karri, David A. McGrew

Research output: Contribution to journalArticle

Abstract

The authors present an architectural optimization technique called divide-and-concatenate for hardware architectures of universal hash functions based on three observations: 1) the area of a multiplier and associated data path decreases quadratically and their speeds increase gradually as their operand size is reduced; 2) multiplication is at the core of universal hash functions and multipliers consume most of the area of universal hash function hardware; and 3) two universal hash functions are equivalent if they have the same collision-probability property. In the proposed approach, the authors divide a 2w-bit data path (with collision probability 2 -2w) into two w-bit data paths (each with collision probability 2 -w), apply one message word to these two w-bit data paths and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2 -2w). The divide-and-concatenate technique is complementary to all circuit-, logic-, and architecture-optimization techniques. The authors applied this technique on a linear congruential universal 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)
Pages (from-to)1740-1746
Number of pages7
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume24
Issue number11
DOIs
StatePublished - Nov 2005

Keywords

  • Collision probabilty
  • Divide-and-concatenate
  • Universal hash functions

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic 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