Kaushik Rajan and R. Govindarajan
Packet forwarding is a memory-intensive application requiring
multiple accesses through a trie structure. With the requirement to process
packets at line rates, high performance routers need to forward millions of
packets every second with each packet needing up to 7 memory accesses.
Earlier work shows that a single cache for the nodes of a trie can reduce
the number of external memory accesses.
It is observed that the locality characteristics of the level-one nodes of
a trie are significantly different from those of lower-level nodes. Hence,
we propose a heterogeneously segmented cache architecture (HSCA) which
uses separate caches for level-one and lower-level nodes each with carefully
chosen sizes. Besides reducing misses, segmenting the cache allows us to
focus on optimizing the more frequently accessed level-one node segment.
We find that due to the non uniform distribution of nodes among cache
sets, the level one nodes cache is susceptible to high conflict misses. We
reduce conflict misses by introducing a novel two-level mapping based
cache placement framework. We also propose an elegant way to fit the
modified placement function into the cache organization with minimal
increase in access time. Further, we propose an attribute preserving trace
generation methodology which emulates real traces and can generate traces
with varying locality. Performance results reveal that our HSCA scheme
results in a 32% speedup in average memory access time over a unified
nodes cache. Also, HSCA outperforms IHARC, a cache for lookup results,
with as high as a 10 fold speedup in average memory access time. Twolevel
mapping further enhances the performance of the base HSCA by up
to 13% leading to an overall improvement of up to 40% over the unified
In IEEE Transactions on Computers (IEEE TC)
Publisher Institute of Electrical and Electronics Engineers, Inc.
© 2007 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.