Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changes between Initial Version and Version 1 of ConcurrentHashTable


Ignore:
Timestamp:
2012-08-08T10:57:14Z (9 years ago)
Author:
Adam Hraska
Comment:

short description, how to run tests and benchmarks

Legend:

Unmodified
Added
Removed
Modified
  • ConcurrentHashTable

    v1 v1  
     1= Scalable Concurrent Hash Table =
     2* GSoC 2012, ticket #398
     3* mentor: Jakub Jermar
     4* student: Adam Hraska
     5* repository: lp:~adam-hraska+lp/helenos/rcu/
     6* benchmarking repository: lp:~adam-hraska+lp/helenos/cht-bench/
     7
     8The goal of the project is to create a scalable concurrent resizable hash table (CHT):
     9* scalable = performance improves with added cpus
     10* concurrent = the table allows parallel access from multiple threads/cpus preferably without blocking
     11* resizable = the table grows and shrinks automatically as item are added or removed from it
     12Moreover, the table must be suitable to replace the current global page hash table in the kernel.
     13Optionally, it may be ported to user space as well.
     14
     15== Current Status ==
     16{{{#!comment
     17
     18supported platforms, what needs to be implemented in others (atomics, ipis vs config_smp)
     19NMI safe or not
     20todos
     21}}}
     22
     23Todos:
     24*
     25
     26== Implementation ==
     27=== CHT Algorithm ===
     28=== RCU Algorithms ===
     29
     30== Testing ==
     31The CHT replies on working atomic operations, SMP calls (ie IPIs), RCU and the system work queue.
     32In order to test these out, pull and build the source code (eg on x86-64 machines):
     33{{{
     34bzr checkout lp:~adam-hraska+lp/helenos/rcu/
     35make PROFILE=amd64
     36}}}
     37Boot HelenOS with eg 4 CPUs in QEMU:
     38{{{
     39qemu-system-x86_64 -cdrom image.iso -smp4
     40}}}
     41Once fully operational, switch to the kernel console by pressing F12
     42(or typing kcon in the shell). You can then finally run the following
     43relevant tests:
     44{{{
     45test atomic1
     46test smpcall1
     47test workqueue
     48test rcu1
     49test cht
     50}}}
     51Neither of the tests should panic, crash, leak memory, loop infinitely, or report errors.
     52The only test //workqueue// reports an error which is however expected and marked appropriately
     53with line //Stress testing a custom queue. Stops prematurely. Errors are expected.//
     54
     55You may be interested in runtime statistics gathered by RCU or the system work queue.
     56Run these commands in the kernel console:
     57{{{
     58rcu
     59workq
     60}}}
     61
     62== Benchmarks ==
     63In order to benchmark the CHT or RCU implementation, pull sources of the benchmarking
     64branch and build the code in a release build (ie clear the debug build option):
     65{{{
     66bzr checkout lp:~adam-hraska+lp/helenos/cht-bench/
     67make PROFILE=amd64
     68make config # this is where you have to clear the debug build option
     69make
     70}}}
     71Boot HelenOS in QEMU with eq 4 CPUS and list the available benchmarks in the kernel console with the
     72//chtbench// command:
     73{{{
     74qemu-system-x86_64 -cdrom image.iso -smp 4
     75
     76/ # kcon
     77kconsole> chtbench 0 0 0
     78}}}
     79
     80=== Results ===
     81The following results were obtained by benchmarking [http://bazaar.launchpad.net/~adam-hraska+lp/helenos/cht-bench/revision/1589 r1589]
     82on Core(TM) i7 CPU 920 @ 2.67GHz (4 cores, each with 2 !HyperThreads), running
     83a release build (with networking):
     84{{{contrib/conf/net-qe.sh e1k -smp 4 }}}
     85Each benchmark run consists of repeating a certain operation in a loop for 10 seconds
     86on the specified number of cpus (ie individual threads wired to these cpus).
     87Benchmarks were repeated as many times as needed (between 10 and 20 consecutive
     88runs) in order to obtain a confidence interval of the number of completed operations
     89within about 1% of the average number of completed operations of the runs. The following
     90figures include error bars depicting a single standard deviation of the completed number
     91of operations in a single run (ie it is //not// the SD of the mean, aka standard error).
     92However the estimated SD is typically below 1-2% of the mean (ie tiny) and therefore not
     93visible in the figures without zooming ;-).