Changes between Initial Version and Version 1 of ConcurrentHashTable

Timestamp:

2012-08-08T10:57:14Z (12 years ago)

Author:

Adam Hraska

Comment:

short description, how to run tests and benchmarks

ConcurrentHashTable

@@ +1 @@
+= Scalable Concurrent Hash Table =
+* GSoC 2012, ticket #398
+* mentor: Jakub Jermar
+* student: Adam Hraska
+* repository: lp:~adam-hraska+lp/helenos/rcu/
+* benchmarking repository: lp:~adam-hraska+lp/helenos/cht-bench/
+
+The goal of the project is to create a scalable concurrent resizable hash table (CHT):
+* scalable = performance improves with added cpus
+* concurrent = the table allows parallel access from multiple threads/cpus preferably without blocking
+* resizable = the table grows and shrinks automatically as item are added or removed from it
+Moreover, the table must be suitable to replace the current global page hash table in the kernel. 
+Optionally, it may be ported to user space as well.
+
+== Current Status ==
+{{{#!comment
+
+supported platforms, what needs to be implemented in others (atomics, ipis vs config_smp)
+NMI safe or not
+todos
+}}}
+
+Todos:
+*
+
+== Implementation ==
+=== CHT Algorithm ===
+=== RCU Algorithms ===
+
+== Testing ==
+The CHT replies on working atomic operations, SMP calls (ie IPIs), RCU and the system work queue.
+In order to test these out, pull and build the source code (eg on x86-64 machines):
+{{{
+bzr checkout lp:~adam-hraska+lp/helenos/rcu/
+make PROFILE=amd64
+}}}
+Boot HelenOS with eg 4 CPUs in QEMU:
+{{{
+qemu-system-x86_64 -cdrom image.iso -smp4
+}}}
+Once fully operational, switch to the kernel console by pressing F12 
+(or typing kcon in the shell). You can then finally run the following 
+relevant tests:
+{{{
+test atomic1
+test smpcall1
+test workqueue
+test rcu1
+test cht
+}}}
+Neither of the tests should panic, crash, leak memory, loop infinitely, or report errors. 
+The only test //workqueue// reports an error which is however expected and marked appropriately
+with line //Stress testing a custom queue. Stops prematurely. Errors are expected.//
+
+You may be interested in runtime statistics gathered by RCU or the system work queue. 
+Run these commands in the kernel console:
+{{{
+rcu
+workq
+}}}
+
+== Benchmarks ==
+In order to benchmark the CHT or RCU implementation, pull sources of the benchmarking 
+branch and build the code in a release build (ie clear the debug build option):
+{{{
+bzr checkout lp:~adam-hraska+lp/helenos/cht-bench/
+make PROFILE=amd64
+make config # this is where you have to clear the debug build option
+make
+}}}
+Boot HelenOS in QEMU with eq 4 CPUS and list the available benchmarks in the kernel console with the 
+//chtbench// command:
+{{{
+qemu-system-x86_64 -cdrom image.iso -smp 4
+
+/ # kcon
+kconsole> chtbench 0 0 0
+}}}
+
+=== Results ===
+The following results were obtained by benchmarking [http://bazaar.launchpad.net/~adam-hraska+lp/helenos/cht-bench/revision/1589 r1589] 
+on Core(TM) i7 CPU 920 @ 2.67GHz (4 cores, each with 2 !HyperThreads), running 
+a release build (with networking):
+{{{contrib/conf/net-qe.sh e1k -smp 4 }}}
+Each benchmark run consists of repeating a certain operation in a loop for 10 seconds 
+on the specified number of cpus (ie individual threads wired to these cpus).
+Benchmarks were repeated as many times as needed (between 10 and 20 consecutive
+runs) in order to obtain a confidence interval of the number of completed operations 
+within about 1% of the average number of completed operations of the runs. The following
+figures include error bars depicting a single standard deviation of the completed number
+of operations in a single run (ie it is //not// the SD of the mean, aka standard error). 
+However the estimated SD is typically below 1-2% of the mean (ie tiny) and therefore not
+visible in the figures without zooming ;-).