Engineering Commons^™

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent …

Nesting System With Quantization And Knowledge Base Applied, Leszek Koszalka, Grzegorz Chmaj

Electrical & Computer Engineering Faculty Research

Nesting algorithms deal with placing two dimensional shapes on the given canvas. In this paper a binary way of solving the nesting problem is proposed. Geometric shapes are quantized into binary form, which is used to operate on them. After finishing nesting they are converted back into original geometrical form. Investigations showed, that there is a big influence of quantization accuracy for the nesting effect. However, greater accuracy results with longer time of computation. The proposed knowledge base system is able to strongly reduce the computational time.