• Number 326  |
• December 6, 2010

New and improved “hash” for the Cray XMT

“Hashing strategies” are methods for slicing and dicing data to assign it to locations within a computer. Now, scientists at DOE’s Pacific Northwest National Laboratory and Sandia National Laboratories have improved hashing strategies for multithreaded machines.  They adapted two of the most commonly used variations of hashing strategies to run efficiently on the Cray XMT.  As a result, they decreased computing time for the same problem from 536 to 77 seconds. The new strategies can be scaled efficiently from 2 to 128 processors.

Hashing strategies speed up computing tasks by assigning an identifier to a certain piece of data so it can be found quickly.  An identifier will always be placed into a particular location – or bucket – in the computer’s memory. When multiple identifiers need to be stored in the same bucket, a collision occurs. Even though collisions are almost inevitable, hashing strategies must still compute accurately.

Hashing strategies for the Cray XMT are challenging to adapt because of its multithreaded architecture.  Unlike massively parallel machines, which typically use around 64 computing threads per cluster node at one time, the Cray XMT could use 16,000 computing threads all accessing its 1 terabyte of shared memory. If all 16,000 threads want to use the same information at the same time, the computer slows down.  The researchers adapted the “linear probing” and “hashing with chaining” strategies to minimize memory contention during data processing in the multithreaded environment. 

Advances in multithreaded computing could improve analyses of irregular, data-intensive applications in a variety of scientific domains.

[Kristin Manke, 509.372.6011,
kristin.manke@pnl.gov]