| Presentation | 2007-12-14 An Improvement of Concurrent Extensible Hash Tables to Reduce Contension Costs Naoya SUEDA, Yoko KAMIDOI, Shin'ichi WAKABAYASHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We improve the split-ordered list hash algorithm (SOL) proposed by Shalev and Nir that can process multiple operations concurently and can extend table size on asynchronous shared memory systems. In general hashing algorithm, lists bucket are longer as the number of items inserted in the hash table is larger. Consequently, it is problem that time of searching item is larger. SOL algorithm, maintains constant length of bucket lists by extending table size. Time of find operation is faster when SOL algorthm executed by multiple operation. On concurrent execution, however, SOL algorithm might have significant performance degradation when many instructions for insertion and deletion areissued concurrently. We consider that the performance degradation is introduced by concurrent accessing one shared variable. We focus on contention for one shared variable. We propose an improvement of SOL algorithm to avoid access contention and aim high-performance hashing algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | asynchronous shared memory system / shared variable / concurrent execution / extensible hash tables / compare-and-swap instruction |
| Paper # | COMP2007-54 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2007/12/7(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Improvement of Concurrent Extensible Hash Tables to Reduce Contension Costs |
| Sub Title (in English) | |
| Keyword(1) | asynchronous shared memory system |
| Keyword(2) | shared variable |
| Keyword(3) | concurrent execution |
| Keyword(4) | extensible hash tables |
| Keyword(5) | compare-and-swap instruction |
| 1st Author's Name | Naoya SUEDA |
| 1st Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University() |
| 2nd Author's Name | Yoko KAMIDOI |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University |
| 3rd Author's Name | Shin'ichi WAKABAYASHI |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University |
| Date | 2007-12-14 |
| Paper # | COMP2007-54 |
| Volume (vol) | vol.107 |
| Number (no) | 390 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |