Nfa_Split Documentation

This page contains the Nfa_Split Package documentation.

The nfa_split_det_part Module

class netbench.pattern_match.algorithms.experimental.nfa_split.nfa_split_det_part.nfa_det_part(index=0)

Bases: netbench.pattern_match.b_dfa.b_dfa

Deterministic part of NFA.

Generated VHDL code depends on those modules: det_part.vhd, decoder.vhd, encoder.vhd and memory.vhd. Those modules are located in directory templates/vhdl.

Parameter:index (int) – Number of deterministci part.
decoder_HDL()

Return HDL description of ouput decoder.

Returns:Returns VHDL implementation.
Return type:string
decoder_size()

Return size of output decoder in LUTs.

Returns:Size of output decoder in LUTs.
Return type:int
detunit_HDL()

Return HDL description of deterministic unit.

Returns:Returns VHDL implementation.
Return type:string
encoder_HDL()

Return HDL description of input encoder.

Returns:Returns VHDL implementation.
Return type:string
encoder_size()

Return size of input encoder in LUTs.

Returns:Size of input encoder in LUTs.
Return type:int
getTableByGA(maxSize)

Compute transition table mapping into list by heuristic.

Parameter:maxSize (int) – Maximum size of memory useable for automata implementation.
Returns:Mapping of state id to new state id.
Return type:dict(int->int)
getTableByHeuristic()

Compute transition table mapping into list by heuristic.

Returns:Mapping of state id into new state id and size of memory needed for implementation.
Return type:list[dict(int->int), int]
memory_HDL(wrap=False, bram_size=2048, bram_word=8)

Return HDL description of deterministic unit memory.

Parameters:
  • wrap (boolean) – Defines if memory wraping is used by the mapping..
  • bram_size (int) – Size of BRAM in words
  • bram_word (int) – Size of word in bits
Returns:

Returns VHDL implementation.

Return type:

string

out_states()

Return output states.

Return set of output states. :returns: set of output states. :rtype: set(int)

report_logic(bram_size=2048, bram_word=8)

Reports amount of logic consumed by the deterministic unit of nfa split algorithm.

Parameters:
  • bram_size (int) – Size of BRAM in words
  • bram_word (int) – Size of BRAM word in bits
Returns:

Amount of logic consumed by the algorithm. Returns in (LUT, FF, BRAMS) format.

Return type:

list(int, int, int)

report_memory()

Reports amount of the memory consumed by deterministic part of nfa split algorithm. The returned number is in the bytes.

Returns:Amount of the memory consumed/
Return type:int
split_det_part(k)

Split deterministic part in order to reduce complexity of input encoder. The det part will be split into k parts.

Parameter:k (int) – Defines number of parts.
Returns:Splited parts.
Return type:list(nfa_det_part)
starting_states()
Return set of starting (input) states. :returns: set of starting (input) states. :rtype: set(int)
ttable_min()

Return size of memory (Bytes) which is needed for minimal representation of transition table. Character classes is used to reduce memory utilization.

Returns:Minimal size of transition table in bytes.
Return type:int
ttable_overlap()

Return size of memory (Bytes) for overlapping of tt rows.

Returns:Size of memory in bytes.
Return type:int
ttable_overlap_BRAMS(bram_size=2048, bram_word=8)

Return size of memory (BRAMS) for overlapping of tt rows.

Parameters:
  • bram_size (int) – Size of BRAM in words
  • bram_word (int) – Size of BRAM word in bits
Returns:

Size of memory in BRAMS.

Return type:

int

ttable_size()

Return size of transition table which corresponds to deterministic part.

Returns:Size of transition table.
Return type:int

The nfa_split_nondet_part Module

class netbench.pattern_match.algorithms.experimental.nfa_split.nfa_split_nondet_part.nfa_nondet_part

Bases: netbench.pattern_match.algorithms.clark_nfa.clark_nfa.clark_nfa

NonDeterministic part of NFA. Based on Clark’s NFA implementation. Supports also sharing of char classes if b_Sym_char_class symbols are used.

Generated VHDL code depends on those modules: value_decoder.vhd, state.vhd and final_bitmap.vhd. Those modules are located in directory templates/vhdl.

Supported symbols for this algorithm are sym_char and sym_char_class.

get_HDL(useBram=False)

Return VHDL description of NFA unit implemented in Clark’s approach.

Parameter:useBram (boolean) –

Defines if BRAM implementation of character decoder will be used. (True = BRAM, False = LUT)

NOTE: Only False is currently supported.

Returns:VHDL description of NFA unit implemented in Clark’s approach.
Return type:string

The test_nfa_split Module

netbench.pattern_match.algorithms.experimental.nfa_split.test_nfa_split.create_simulation(alg)

Creates simulation files from templates for object specified by alg parameter.

Parameter:alg (b_ptrn_match) – Object representing pattern matching algorithm.
netbench.pattern_match.algorithms.experimental.nfa_split.test_nfa_split.load_file(name)

Open file specified by name and split content acording to “%$%”.

Parameter:name (string) – Name of the file.
Returns:Loaded and splited content of the file.
Return type:list(string)
netbench.pattern_match.algorithms.experimental.nfa_split.test_nfa_split.run_simulation(test)

Runs the simulation and compare the results.

Parameter:test – Object representing the test.
Returns:True when simulation is OK, False otherwise.
Return type:boolean
netbench.pattern_match.algorithms.experimental.nfa_split.test_nfa_split.save_file(name, content)

Save the content stored in parameter content into file named by parameter name.

Parameters:
  • name (string) – Name of the file.
  • content (string) – Content to write.
class netbench.pattern_match.algorithms.experimental.nfa_split.test_nfa_split.test_nfa_split(methodName='runTest')

Bases: unittest.TestCase

A base test class for NFA Split architecture.

test_ns()
Tests the NFA Split architecture.

The example_of_use Module

netbench.pattern_match.algorithms.experimental.nfa_split.example_of_use.save_file(name, content)

Save the content stored in parameter content into file named by parameter name.

Parameters:
  • name (string) – Name of the file.
  • content (string) – Content to write.

The nfa_split Module

class netbench.pattern_match.algorithms.experimental.nfa_split.nfa_split.nfa_split

Bases: netbench.pattern_match.b_nfa.b_nfa

The NFA split class implements NFA split architecture. This architecture consists from nondeterministic part and from one ore more deterministic parts. Construction algorithm determinates which states can be active together and then the states which can’t be active together are mapped into DFA parts as more than one set of nonactive states is possible - each set coresponds to one deterministic part. States which can be active together are implemented in the nondeterministic part.

This class is based on:

Korenek Jan, Kosar Vlastimil: NFA Split Architecture for Fast Regular Expression Matching, In: Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, La Jolla, US, ACM, 2010, p. 2, ISBN 978-1-4503-0379-8

Korenek Jan, Kosar Vlastimil: Efficient Mapping of Nondeterministic Automata to FPGA for Fast Regular Expression Matching, In: Proceedings of the 13th IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems DDECS 2010, Vienna, AT, IEEE CS, 2010, s. 6, ISBN 978-1-4244-6610-8

concurrently_reachable()

Compute set of state’s tuples, which can ba active in same time.

Returns:Set of concurrently active states.
Return type:set(tuple(int, int))
create_det_parts(number_of_parts=1, table_mapping_method=0, useCharClasses=False, concurrency_method=0)

Create deterministic parts of NFA. Number of parts, table mapping algorithm, usage of charclasses and mathod of determinating state concurrecy can be specified.

Parameters:
  • number_of_parts (int) – Number of deterministic parts to create. Less number parts can be generated if requested number of parts is higher than number of parts which can be generated.
  • table_mapping_method (int) – Specifies transition table mapping algorithm. Use 0 for heuristic and 1 for genetic algorithm. Usage of 0 is recommended.
  • useCharClasses (boolean) – Specifies if character class are used in DFA parts.
  • concurrency_method (int) – Specifies algorithm which is used to determinate state concurrecy. Use 0 for determinisation and 1 for concurrently_reachable() method. The concurrently_reachable() method has time complexity O(n^2).
Returns:

State of DFA parts construction. True means that all is OK and False indicate error during construction.

Return type:

boolean

get_HDL()

Generate VHDL code representing whole nfa split architecture.

Returns:File names and VHDL code for all nfa split units.
Return type:dict(string -> string)
load(file)

Load nfa_split object using cPickle.

Parameter:file (string) – File name.
Returns:Loaded nfa_split object
Return type:nfa_split
report_dfa_logic(bram_size=2048, bram_word=8)

Return estimation of LUTs, FFs and BRAMs consumed by all deterministic parts.

Parameters:
  • bram_size (int) – Size of BRAM in words
  • bram_word (int) – Size of BRAM word in bits
Returns:

Amount of logic consumed by the algorithm. Returns in (LUT, FF, BRAMS) format.

Return type:

list(int, int, int)

report_logic(bram_size=2048, bram_word=8)

Return estimation of LUTs, FFs and BRAMs consumed by whole nfa_spli architecture.

Parameters:
  • bram_size (int) – Size of BRAM in words
  • bram_word (int) – Size of BRAM word in bits
Returns:

Amount of logic consumed by the algorithm. Returns in (LUT, FF, BRAMS) format.

Return type:

list(int, int, int)

report_memory()

Return estimation of consumed memory (in Bytes).

Returns:Estimation of consumed memory in bytes.
Return type:int
report_nfa_logic()

Return estimation of LUTs, FFs and BRAMs consumed by nondeterministic parts.

Returns:Amount of logic consumed by the algorithm. Returns in (LUT, FF, BRAMS) format.
Return type:list(int, int, int)
save(file)

Save nfa_split object using cPickle.

Parameter:file (string) – File name.
split_det_parts(k)

Split deterministic parts in order to reduce complexity of input encoder. Each part is split to k-parts.

Parameter:k (int) – Each deterministic part is split into k-parts.