PFAC implementation on CPU

[Shakya]

Hi all,

I am studying on Aho-Corasick algorithm for my final year project.Our
effort currently, is on implementing an enhanced version of the
Algorithm on CPU.I really appreciate your help on this.Can I have
algorithm pseudo code of PFAC if available ?

Waiting for a quick reply.

[Cheng-Hung Lin]

We have released the PFAC algorithm on Google code(http://code.google.com/p/pfac/). 

--
Sincerely,
Cheng-Hung Lin

[Lung-Sheng Chien]

If you have a GPU, then you can just install PFAC library and compare
it to your CPU version.
Theoretically speaking, complexity of AC is better than complexity of
PFAC.
However on GPU, PFAC can be better than AC in average.
Of course, we don't have a AC-GPU version, so it is not an apple-to-
apple comparison.

I would suggest that you focus on AC algorithm first because
If you don't run PFAC on many-core system, I don't see any benefits.

Lung-
Sheng

[Shakya]

Thank you for the quick reply.
quoting,

"I would suggest that you focus on AC algorithm first because
If you don't run PFAC on many-core system, I don't see any benefits".

That's some thing I wanted to clarify.Thanks.

I would like to try an implementation of PFAC on CPU.May I know
whether it is available?

Shakya

[Lung-Sheng Chien]

PFAC library contains CPU version.

You can check src/PFAC_CPU.cpp, the code is very simple. You can also
check doc/PFAC_algorithm.pdf to know the PFAC state machine.
Besids, you can run CPU version of PFAC library by setting parameter
platform as PFAC_PLATFORM_CPU (please check doc/PFAC_userGuide.pdf as
well).

Again, you can say PFAC is a simplified version of AC and is easy to
implement on many-core system.
However it has load imbalance issue, you can easily create a testcase
that PFAC cannot perform well.

Lung-Sheng

[suejb memeti]

Hi

I tried to compile the simple_example.cpp on a cpu with no GPU card installed, using this command:

gcc -fopenmp -O3 -I/pfac/include -o test simple_example.cpp -c

But it seems to generate a binary file that can not be executed on my machine. Do you have any suggestion on how to compile it for a system that has no GPU?

Regards