Multi-processor/core systems have become ubiquitous but the vast majority of OWL reasoners can process ontologies only sequentially. This observation motivates our work on the design and evaluation of Deslog, a parallel tableau-based description logic reasoner for ALC. A first empirical evaluation for TBox classification demonstrates that Deslog's architecture supports a speedup factor that is linear to the number of utilized processors/cores.
The popularity of multi-processor/core computing facilities makes Description Logic (DL) reasoning feasible that scales w.r.t. the number of available cores.1 Modern manycore architectures together with operating systems implementing symmetric multitasking efficiently support thread-level parallelism (TLP), where smaller subtasks are implemented as threads that are concurrently executed on available cores. In order to utilize such hardware for making DL reasoning scalable to the number of available cores, one has to develop new reasoning architectures efficiently supporting concurrency. Moreover, many well-known tableau optimization techniques need to be revised or adapted in order to be applicable in a parallel context. In this paper we present a new DL reasoning framework that fully utilizes TLP on many-core systems. In principle, standard tableau algorithms are well suited for parallelization because tableau completion rules usually do not depend on a sequential execution but require shared access to common data structures.
We consider the inherent non-determinism of DL tableaux as a feature of DL
reasoning that naturally leads to parallel algorithms which are suitable for a shared-memory
setting. For instance, a source for such a non-determinism are disjunctions and qualified
cardinality restrictions for logics containing at least ALCQ. Many standard DL
reasoning services, e.g. concept satisfiability testing, TBox classification, instance checking,
ABox realization, etc. might be amenable to be implemented in a non-deterministic
way supporting parallelism. However, the use of parallelism in DL reasoning has yet
to be explored systematically. Although it is advantageous to seek scalable solutions
by means of parallelism, little progress has been made in parallel DL reasoning
during the last decade [
Deslog system pre-processing post-processing
reasoning engine service provider
rule applier consistency satisfiability subsumption classification
. infrastr..ucture u t 8 9 ... be researched, e.g., selecting suitable parallel architectures,ltrdl0esi8gnating efficient data structures and memory management, and exploring parallel algorithms.
In the remaining sections we introduce the design of Des⇤log,⇤ discussltrlr1elauted work, operator and present an evalulaitetriaoln demonstrating a mostly (suRper)linear scalability of ⇤ Deslog. ⇤ A
B 2
Architecture⇤ loefft De⇤srilgoht g
Fig. 2: Deslog data struc- Fig. 3: Deslog data structure for The shared-mtuerme oforyr apacroanllceelprte.asoner Deslog consitshtes DofLtherxeperleasyseiorsn: 8 (iR)p.(rAe-puroBc)e.ssing layer, which converts the Web Ontology Language (OWL) representation of ontologies to internal data structures; (ii) reasoning engine layer, which performs the standard DL reasoning services and is composed of two key components, the service provider and the tableau rule applier; (iii) post-processing layer, which collects, caches, and saves reasoning results; (iv) infrastructure layer, which provides core components and utilities, such as structures representing concepts and roles, and the object copy tool. Figure 1 gives an overview of the framework.
First, OWL ontology data is read into the pre-processing layer. Various typical
preprocessing operations, such as transformation into negation normal form (NNF), axiom
re-writing, and axiom absorption, are executed in this layer. The reasoner’s run-time
options, such as service selection, maximum number of threads, and rule application
order, are also set up on this layer. We implemented this layer by using the OWL API
[
The reasoning engine performs primarily inference computation. The first key
component of the reasoning engine is the service provider. As with popular DL reasoning
systems, Deslog provides standard reasoning services, such as testing TBox
consistency, concept satisfiability, etc. As we know, these services may depend on each other.
In Deslog, the classification service depends on subsumption, and the latter depends on
the satisfiability service. The service provider uses a suite of tableau-based algorithms
to perform reasoning. The reasoner adopts tableaux as its primary reasoning method,
which is complemented by another key component, the tableau expansion rule applier.
The main function of this component is to execute tableau rules in some order to build
expansion forests. In Deslog, tableau expansion rules are designed as configurable
plugins, so what rule has to be applied in what application order can be specified flexibly.
At present, Deslog implements the standard ALC tableau expansion rules [
All three layers mentioned above use the facilities provided by the infrastructure layer. All common purpose utilities are part of this layer. For example, the threads manager, global counters, and the globally unique identifier (GUID) generator. In addition, the key data structures representing DL elements and basic operations on them are provided by this layer. 2.2
In contrast to popular DL reasoning systems, Deslog aims to improve reasoning performance by employing parallel computing, while data structures employed by sequential DL reasoners are not always suitable for parallelism.
Tree structures have been adopted by many tableau-based reasoners. However, a naive tree data structure introduces data races in a shared-memory parallel environment and are not well suited in a concurrency setting. Therefore, we need to devise more efficient data structures in order to reduce the amount of shared data as much as possible.
The new data structures facilitating concurrency must support DL tableaux. One important function of trees is to preserve non-deterministic branches generated during tableau expansion. Non-deterministic branches are mainly produced by the disjunction rule and the at-most number restriction rules. To separate non-deterministic branches into independent data vessels, which are suited to be processed in parallel, we adopt a list-based structure, called stage, to maintain a single non-deterministic branch, and a queue-based structure, called stage pool, to buffer all branches in a tableau. Every stage is composed of the essential elements of a DL ontology, concepts and roles.
As with any DL reasoner, the representation of concepts and roles are fundamental design considerations. The core data structure of Deslog is a four-slot list representing a concept. A literal uniquely identifies a distinct concept. An operator indicates the dominant DL constructor applied to a concept. Available constructors cover intersection, disjunction, existential and value restriction, and so on, and this slot can also be empty. The remaining two slots hold pointers to extend nested concept definitions, namely left and right. Figure 2 illustrates a DL concept encoded with the Deslog protocol.
ppoosst-t-pprroocceesssiningg liltieterraall
ooppeerraatotorr ⇤ ⇤ lelefftt ⇤ ⇤ rrigighhtt
ssuubbssuummpptitoionn cclalasssifiificcaatitoionn ..
.. ininffrraasstr.tru.ucctuturree
RR
Roles in Deslog are handled as a special type of concepts and have a similar structure as concepts. For instance, the encoding of the DL expression 8R:(A u B) is shown in Figure 3. Further properties needed for describing a role can be added to the generic structure, e.g., the number restriction quantity. A role data structure is also associated with a list recording instance pairs. With this design, DL concepts can be lined up seamlessly. Instances (i.e., labels in tableau expansions) are lists holding their typing data, concepts. There are also helper facilities, such as a role pool and an instance pool, which are useful to accelerate the indexing of objects.
A notable point on our encoding is how the complement of an atomic concept (i.e., concept name) is expressed (see Figures 4a and 4b).
A
A ⇠ A ⇤ ¬ ((aa)) AAttoommiicc ccoonncceepptt AA
((bb)) AAttoommiicc ccoonncceepptt :¬AA
A principle of Deslog’s design is to model objects and behaviours involved in DL reasoni1n4g as iphnardmaecopgeenonmicds econmptlexabstractions as much as possible in order to facilitate concur13 economy rent pro12cessing. tFranosporrtaitinonstance, branches created during tableau expansion are encapsu11 mbfaoo lated trcoin1t0o standayleoapstlnapnhteetnraooittybpejects. Thus, a whole tableau expansion forest is designed as a list of brafanc89h objects. Tableau expansion rules and even some key optimization techniques p u are aleepso67designed as independent components.
d S 5 4 3 2 1 Fig. 5: Speedup factor for pharmacogenomics complex, economy, transportation, bfo, mao, yeast phenotype, and plant trait.
As aforementioned, multi-processor computers are becoming the main stream, it is expected that idle processors are utilized, and shared-memory TLP is quite suitable for this purpose.
One significant aspect of this research is to investigate how well important DL
reasoning optimization techniques are suited to be implemented in a parallel reasoner and
how they should be adapted if plausible. Deslog has adopted the following optimization
techniques.
1. Lazy-unfolding This technique enables a reasoner to unfold a concept only when
necessary [
Other primary optimization techniques, such as dependency directed backtracking
[4, Chapter 9] [
The current system implements a parallel ALC TBox classifier. It can concurrently
classify an ALC terminology. The parallelized classification service of Deslog
computes subsumptions in a brutal way [
A rather difficult issue in implementing a parallel DL reasoner is managing overhead. This issue is relatively easy for high level parallel reasoning, where multiple threads mainly execute reading operations on some shared data, thus, we implemented the parallel classification service first.
Besides the high-level parallelized service, classification, low level parallelized processing is being developed. In the architecture of Deslog, the classification service uses subsumption, and subsumption uses satisfiability. The low level parallel reasoning focuses on dealing with non-deterministic branches, which are represented as stages in Deslog.
It might seems easy to process stages in parallel, but quite some effort is required to achieve a satisfying scalability via concurrency. The first noticeable fact is that from a root stage every stage may generate new ones. At present, our strategy is using one thread to process one stage. That means the stages buffer, the stage pool, is frequently accessed by multiple threads. That accessing includes both writing and reading shared data frequently. So, designing a high-performance stage buffer and efficient accessing schemes is an essential condition for the enabling a of scalable performance improvement. Otherwise, a parallel approach only causes overhead instead of performance improvement. We are currently working on efficient low-level parallel reasoning.
Although there are robust shared-memory concurrent libraries available, such as the C++ Boost.Thread library and the Java concurrent package, according to our experience, using these libraries immoderately often degrades performance. Therefore, one needs to design sophisticated structures which better avoid shared data, or which do not access shared data frequently. 3
Deslog is implemented in Java 6 in conformity with the aforementioned design. The parallelism of Deslog is based on a multi-threading model and aims at exploiting symmetric multiprocessing (SMP) supported by multi-processor computing facilities. The system is implemented in Java 6 for Java’s relatively mature parallel ecosystem.2 Specifically, the java.util.concurrent package of Java 6 is utilized.
In the following we report on experiments to demonstrate that a shared-memory parallel tableau-based reasoner can achieve a scalable performance improvement. 3.1
The classification service of Deslog can be executed concurrently by multiple threads. We conducted a group of tests, and they show that Deslog has an obvious scalability.
All tests were conducted on a 16-core computer running Solaris OS and Sun Java 6. Many of the test cases were chosen from OWL Reasoner Evaluation Workshop 2012 (ORE 2012) data sets. We manually changed the expressivity of some test cases to ALC so that Deslog could reason about them. Table 1 lists the metrics of the test cases. The results are shown in Figures 5-7. 3.2
The experimental results collected from testing ontologies show a scalable performance improvement. The tests on more difficult ontologies demonstrate a better scalability due to reduced overhead.
Because the computing time of the single thread configuration, T1, is rather small for some ontologies, often smaller than ten seconds, the overhead introduced by maintaining multiple threads can limit the scalability. For some of these ontology tests, the reasoning times are reduced to several milliseconds, i.e., the whole work load assigned to a single thread is around several milliseconds in these settings. According to our empirical results, a small work load w.r.t. the overhead, which is produced by manipulating 2 All components and sources of the system are available at http://code.google.com/p/deslog/. threads as well as accessing shared data, counteracts the benefits gained from parallel processing and the reasoning performance starts to degrade.
When testing ontologies that are big enough, the observed scalability is linear, sometimes even superlinear. These bigger ontologies need longer single thread computing times (T1). The overhead introduced by maintaining a tolerable number of multiple threads is very small and becomes insignificant. A tolerable number, Ni, should always be smaller than or equal to the total number of available processors. In our conducted tests due to the available hardware we have Ni 2 [1; 16] but in order to stress multithreading we conducted all tests with up to 32 threads. In some cases, even though the number of threads exceeds 16, the reasoning performance keeps stable in a rather long run. This clearly supports our hypothesis that a further scalability improvement could be achieved by adding more processors, and we will verify this hypothesis when better experimental hardware becomes available.
Figure 7 shows the standard deviation of thread runtimes measured in the series of tests (in the unit of milliseconds). Overall, the deviations are limited to an acceptable range, i.e., below 140 milliseconds, which is relatively insignificant w.r.t. system overhead. This implies that the work load is well balanced among threads. That is to say, all threads are as much busy as possible. For the most part, when the number of threads is smaller than the tolerable number, 16, deviations are normally close to 0. When threads are added beyond 16, deviations become greater. This is because some processors execute more than one thread, and hereby the thread contexts switching produces a lot of overhead. In our original implementation, we had distributed all subsumption candidates into independent lists, every of which mapped to a thread, but the deviations were sometimes too large. So, the Deslog classification uses now a shared queue to buffer all subsumption candidates, in order keep all threads busy.
We had conducted similar experiments on a high-performance computing cluster, and the results were rather disappointing. The speedup factor gained on the cluster was generally below 3 although we assigned at least 16 processors for each test. The most plausible explanation we can give is that the complex hardware and software environment of the cluster degrades the performance of Deslog. The cluster consists of three types of computing nodes with respect to the built-in processors: 4-core, 8-core, and 16-core. And the same type of computers may have heterogeneous architectures. A job is scheduled on one or more computers randomly. It is normal that a job is assigned to more than one computer, and the communication between computers results in a bottleneck. Another possible reason is that the cluster does not guarantee exclusive usage, which means it is possible that more than one job is running on the same computer at the same time.
Deslog can only deal with ALC ontologies at present, and we expect that more
interesting results will be obtained by implementing more powerful tableau expansion rules
(e.g., see [
Our research investigates the potential contribution of concurrent computing to
tableaubased DL reasoning. Tableau-based DL reasoning has been extensively researched in
sequential contexts. A large amount of literature is available for addressing sequential
DL reasoning (see [
The work in [
The canonical top-search algorithm, as well as its dual bottom-search, can be
executed in parallel, but extra work is needed to preserve completeness. Such an approach
is presented in [
In [
Two hypothesises on parallelized ontology reasoning were proposed in [
The research mentioned above is focusing on a shared-memory multi-threading environment. There is also quite some research proposing distributed solutions, and some of these ideas are also worth being tried in a shared-memory environment.
In [
Recently, some research work focuses on how DL reasoning can be applied to
Resource Description Framework (RDF) and OWL . This trend leads to research on
reasoning about massive web ontologies in a scalable way. MapReduce [
DL has been successfully applied in many domains, amongst which utilizing knowledge on the Internet has become a research focus in recent years. Scalable solutions are required for processing an enormous amount of structured information spreading over the Internet. Meanwhile, multi-processor computing facilities are becoming the main stream. Thus, we consider research on parallelism in DL reasoning as necessary to utilize available processing power..
The objective of this research is to explore how parallelism plays a role in tableaubased DL reasoning. A number of tableau-based DL reasoning optimization techniques have been extensively researched, but most of them are investigated in sequential contexts, so adapting these methods to the parallel context is an important part of this research.
We have partially shown that shared-memory parallel tableau-based DL reasoning can contribute to scalable solutions. This paper introduced our reasoner, Deslog, of which the architecture is devised specially for a shared-memory parallel environment. We presented an aspect of the reasoner’s concurrency performance, and a good scalability could be demonstrated for TBox classification.
In the near future, we will enhance Deslog so that it can reason about more expressive DL languages. More powerful tableau expansion rules will be added. Concurrencysuitable tableau optimization techniques will be implemented. Moreover, we plan to investigate non-determinism more closely, and to design corresponding parallel algorithms.