Tuesday, January 10, 2012

New Features in MADARA KaRL

The MADARA Knowledge and Reasoning Language (KaRL) has undergone some major changes recently that should provide developers with a faster, more flexible reasoning engine. In this post, we’ll outline features like explicit compilation of KaRL logics and implicit compilation of variable references, and the timed wait operation. Along the way, we'll show how to use the atomic pre- and post- prints for evaluations or wait statements.

Originally, the KaRL engine created an expression tree and then cached the expression tree in an STL string to expression tree map. This feature still exists, but we noticed that the string lookups were taking quite a bit of time. In the worst case, such string lookups can take O(m log n), where m is the length of the string and n is the number of compiled logics. This is quite a long time to grab a cached tree.

The same search complexity was limiting the execution of our KaRL interpreter logic as well. With each variable lookup, we perform a lookup in an STL string to long long tree map. Depending on the length of the variable and the number of variables, this could again take a while.

Not anymore.

Developers may now compile KaRL logics directly with a call to the compile function, the result of which can be used to directly reference the expression tree. Additionally, underneath the hood, we have rewritten the variable node in the expression tree so that it directly manipulates the underlying Knowledge Record in the Thread Safe Context (and does so without entering or leaving the mutex). This resulted in increasing the speed of the engine by a factor of 3-4x, depending on how the logics were being processed. Keep in mind that this speed up factor was achieved on an already state-of-the-art reasoned that was capable of 2 million knowledge operations per second (~500 ns per operation).

When using a C++ for loop to call the reasoning engine, these changes improved our performance from ~1us per operation to ~250ns. Larger logics, where internal optimizations are possible, have been improved from ~500ns per operation to ~190ns. This means that the KaRL engine can now processes knowledge operations at over 5mhz—5 million operations per second.

The implicit compilation is included in all knowledge calls, but the explicit compilation can be done via the following:


// Initiate knowledge base with no transport
Madara::Knowledge_Engine::Knowledge_Base knowledge;

// new classes for evaluation settings and compiled expressions
Madara::Knowledge_Engine::Eval_Settings settings;
Madara::Knowledge_Engine::Compiled_Expression compiled;

// compile the expression and save it into compiled
compiled = knowledge.compile ("invariant => (++.count ; someother.condition => status = 5)");

// evaluate the expression with the default settings
knowledge.evaluate (compiled, settings);



You can see other examples of using these new features in the test for reasoning throughput.

We’ve also added the ability to do timed waits instead of indefinite blocking waits on knowledge expressions. This allows for a calling C++ program to wait for a specific time interval for the knowledge expression or KaRL logic to become non-zero, and if the time interval passes, returning control back to the caller. The underlying mechanisms are similar. The KaRL engine aggregates any changes to variables within the logic evaluation and sends updates to other interested network entities over the DDS transport.

You can find examples of how to use this in the timed wait tests. I include an example below:


// Initiate knowledge base with no transport
Madara::Knowledge_Engine::Knowledge_Base knowledge;

// new classes for wait settings and compiled expressions
Madara::Knowledge_Engine::Compiled_Expression compiled;
Madara::Knowledge_Engine::Wait_Settings wait_settings;

// simple expression that will always evaluate to zero
std::string logic = "++.count && 0";

// set the wait settings to a polling frequency of once
// a millisecond and a maximum wait time of 10 seconds
wait_settings.poll_frequency = .001;
wait_settings.max_wait_time = 10.0;

// create atomic pre and post print statement
wait_settings.pre_print_statement =
"WAIT STARTED: Waiting for 10 seconds.\n";
wait_settings.post_print_statement =
"WAIT ENDED: Number of executed waits was {.count}.\n";

// compile the simple zero logic
compiled= knowledge.compile (logic);

// wait on the expression with the timed wait semantics
knowledge.wait (compiled, wait_settings);


The implications of the time-based waiting mechanism are pretty big, and these changes will eventually make their way into the KATS framework to allow for even more flexibility with automated tests and deployments in the form of fail and success condition executions of deployment elements. Combined with the new redeployment framework changes, the MADARA suite of tools should help a lot of distributed, real-time and embedded developers better reach their project goals. If you have any questions or comments about the implementations of these features or how you can use them in your projects, please let me know. MADARA is completely open source under a BSD license.

No comments:

Post a Comment