Hashing strategies for the Cray XMT

Author

Goodman, Eric L. ; Haglin, David J. ; Scherrer, Chad ; Chavarria-Miranda, D. ; Mogill, Jace ; Feo, John

Author_Institution

Sandia Nat. Labs., Albuquerque, NM, USA

fYear

2010

fDate

19-23 April 2010

Firstpage

1

Lastpage

8

Abstract

Two of the most commonly used hashing strategies-linear probing and hashing with chaining-are adapted for efficient execution on a Cray XMT. These strategies are designed to minimize memory contention. Datasets that follow a power law distribution cause significant performance challenges to shared memory parallel hashing implementations. Experimental results show good scalability up to 128 processors on two power law datasets with different data types: integer and string. These implementations can be used in a wide range of applications.

Keywords

Cray computers; data structures; parallel databases; program processors; shared memory systems; 128 processors; cray XMT; hashing strategies; hashing with chaining; integer data types; linear probing; memory contention; power law datasets; power law distribution; scalability; shared memory parallel hashing; string data types; Concurrent computing; Cost function; Data structures; Dictionaries; Frequency; Laboratories; Magnetic heads; Parallel machines; Peer to peer computing; Scalability;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on

Conference_Location

Atlanta, GA

Print_ISBN

978-1-4244-6533-0

Type

conf

DOI

10.1109/IPDPSW.2010.5470688

Filename

5470688