taskq and update times

We have taken a look at the cache update time when using the taskq pragma in the code.
There was a slight decrease in the average update time, 7 milliseconds to 4 milliseconds. However, the worst case for update time increased greatly. The original code had a worst case of the update time around 5-6 seconds, the taskq code had worst cases around 40 seconds with two threads and 50 seconds with 4 threads.

The results are not good. We will try again once we get the hypercuts structure working with the code and see if there is any difference then.

Hypercut

We found the bottleneck of smart rule cache is the data structure we used to store the rules. We use PPDD(Pruned packet decison diagram) which is tree that grows quickly with the number of rules. Thus, besides multi-threading, we looked at other alternative trees.
We found hypercut is a good one. Hypercut is based on a decision tree structure. It has limited memory usage and fast classification speed. I run the source code of hypercut on several rulesets and corresponding trace files. It works file.
I'm now considering rewriting the source code of smart rule cache with hypercut decision tree.

initial results using intel compiler

We tested our smart rule cache program (parallelized with taskq) using a rule set of 102 rules. The results are listed below. It shows that using multithreading can reduce the average update time to roughly half of the original one.



	Num of rules	Num of threads	Avg update time (10^(-6)s)	Cumulative hit ratio (%)
original	102		173	99.98
parallel	102	2	101	99.98
parallel	102	4	104	99.98
parallel	102	8	141	99.95

ICC and taskq works

We successfully installed intel complier(ICC) and it works. We compiled several examples using taskq and they work as expected.
We modified our rulecache program using taskq and it improved average update time. For the case with 1802 rules and 4 threads, we parallelized the bottleneck recursive function and the average updated time reduced from 0.007 to 0.004.
We will run it on Niagara to see the difference. We will also try other number of threads. Another direction could be parallelize other functions as well.

ICC and HyperCuts

We are working on getting the program to run using the taskq pragma but to do this we have to use Intel's C compiler (ICC). We are working on installing the ICC compiler and trying to compile the code with it. Once we are able to compile code we will be able to run it using taskq and compare the results we see.

We are also looking into replacing the tree structure used to store the rules with a HyperCut tree. We noticed that the tree is very large and we think switching to a HyperCut might give a significant performance increase.