• LarkcProject
• WP5
• docs
• platform
• ApiAnytimeModels

Anytime Behaviour - Discussion of Potential Programming Models

1. Introduction

This article is intended to be a discussion of programming models that could be used by LarKC to achieve 'anytime' behaviour. As such, it will first try to define anytime behaviour and then present a set of potential design solutions (programming models). Each solution will have its own advantages and disadvantages. Through discussion, it is hoped that the consortium will choose the approach most suitable for LarKC and this model will become the de facto standard that all writers of software components must adhere to.

2. Terminology

The following terminology is used in this article:

3. Definition

In essence, LarKC hopes to achieve fast search/reasoning by using a combination of:

• approximate techniques
• novel techniques (borrowed from other disciplines), and
• parallel execution

Parallel execution involves the simultaneous execution of more than one execution context, or thread. For a single (hardware) processor system, this can sometimes allow for a simpler and more efficient design. However, it is on multi-processor systems that software designed for parallel execution can expect to achieve its scalability goals, i.e. more processors => faster execution OR more data processed.

In the context of LarKC and a multi-processor (and therefore a multi-threaded) environment, it naturally follows that a desired behaviour of a LarKC platform would be that the 'user' could terminate a search/reasoning task at anytime and still have some meaningful answer (or set of results). Such a behaviour is called 'anytime'. The principal advantage, is that it allows the user to decide how best to trade response times with accuracy/quantity of results.

Barry's comment: There seem to be two 'sub-models', that might be worth defining here. That is, for a search activity, a user would expect to get any results as quickly as possible (asynchronously), whereas for some activity where the result is a convergence towards a solution (analogy - numerical approximation) the user might only be interested in the final result. Of course, this latter case doesn't forbid intermediate solutions being returned and this might be advantageous to the user anyway. - Maybe delete this comment?

Further, a LarKC platform is constructed from many components that work together (under the guidance of a 'Decide' component) to deliver results to the user. These components will in turn need to communicate and will likely also pass 'intermediate results' between themselves.

This article first considers the case of anytime behaviour that exists at the boundary of LarKC, i.e. between the user and platform. It may well be that one solution fits all, so that we can use a single anytime model throughout LarKC as a whole. However, after considering the user-LarKC interface, this article will be further expanded with an analysis of the communication requirements between LarKC components.

4. Interface between LarKC and User

The goals:

1. The LarKC interface should be as simple as possible to give the user maximum flexibility to integrate with LarKC
2. The user should not be forced to use unacceptably complex synchronisation mechanisms (preferably none at all)
3. The user thread should not block indefinitely when making a request to a LarKC platform

4.1. Callback

In some ways, this is the simplest model of all. The basic idea is similar to the java swing listener concept, i.e. to get notifications of events, one must create a class that supports a particular listener interface and pass an instance of this class to the 'thing' doing the notifying.

The sequence of events in the LarKC case would be:

1. User creates an object to receive asynchronous results (a receiver)
2. User passes this receiver object with a request (sparql query) to LarKC (and returns immediately)
3. LarKC does some processing and starts to return results by calling methods on the receiver object (LarKC thread, not user thread)
4. The receiving object does whatever it needs with the results

4.1.1. Advantages

1. Very simple model
2. Well understood and similar to existing java paradigms (although swing is single-threaded)
3. User thread is at no time blocked in LarKC components (either waiting for a LarKC response or polling an object for a response)
4. User has complete control over synchronisation mechanism used

4.1.2. Disadvantages

1. LarKC callback thread executes user code (potentially blocking for unacceptable time)
2. The user is required to implement all synchronisation mechanisms when processing results
3. Terminating a search/reasoning task early requires some mechanism to 'de-register' the receiver object (with possibly complicated synchronisation issues)
4. Results are returned one-at-a-time, although there is the possibility for batching results, i.e. passing many results in one call to resultEvent()

4.2. Queue

A common technique for passing messages between communicating threads is to use some form of synchronised queue. In this model, a queue exists at the boundary between the components (or the system and a user). As messages are generated by one component, they are put on to the queue for the target component. Whenever the target component thread is available for processing messages, it 'takes' messages from its dedicated queue.

All synchronisation in this model is handled by the queue itself. The queue manages contention between threads putting and taking from the queue simultaneously. Also, attempting to take from an an empty queue can either block until there is something in the queue (take) or return immediately if the queue is empty (poll).

For LarKC, the messages passed between the platform and the user will be query results. The sequence of events would go something like this:

1. User submits a query to the platform - this call returns immediately with a (handle or reference to a) result queue (or this could be provided by the user)
2. The platform starts putting results in to the queue as they are generated and continues until there are no more results or it is told to stop
3. User enters a loop removing from the queue until there are enough results or there are no more results

4.2.1. Advantages

1. Very simple model
2. Very loose coupling between components
3. LarKC thread executes only LarKC code and user thread executes only user code
4. No explicit synchronisation mechanisms are required - all handled by the queue
5. User code can be essentially single threaded
6. Suitable standard queue implementations already exist (java.util.concurrent)

4.2.2. Disadvantages

1. Care must be taken to avoid queue explosion - when the user processes results slower than LarKC generates them (can be avoided with a bounded queue, but with the possibility of losing results)
2. User thread must either block on the queue when there are no results, or poll the queue in a loop

4.3. Synchronise on ResultSet

4.4. Synchronise on Task