This paper describes our progress in developing algorithms for concurrent classification of OWL ontologies. We refactored the architecture of our research prototype and its employed algorithms by integrating lock-free data structures and adopting various optimizations to reduce overhead. In comparison to our earlier work we increased the size of classified ontologies by one order of magnitude, i.e., the size of processed ontologies is now beyond a quarter million of OWL classes. The main focus of this paper is an empirical evaluation with huge ontologies that demonstrates an excellent speedup that almost directly corresponds to the number of used processors or cores.
Parallel algorithms for description logic (DL) reasoning were first explored in the FLEX
system [
Other work has studied concurrency in light-weight ontology languages. There is a
distributed Map Reduce approach algorithm for E L+, however no experiments had been
reported on the proposed algorithms [
The work in this paper is an extension of our work on Parallel TBox classification
[
This section describes the architecture of the implemented system and its underlying
sound and complete algorithm for concurrent classification of DL ontologies. To
compute the hierarchy in parallel, we developed a Java application using a multi-threaded
architecture providing control parameters such as number of threads, number of
concepts (also called partition size) to be inserted per thread, and number of processors. As
thoroughly explained in [
The preprocessing algorithm uses a topological sorting similar to [
In [
The procedure parallel tbox classification is sketched in Algorithm 1. It is called with a list of named concepts and sorts them in topological order with respect to the initial taxonomy created from already known told ancestors and descendants of each concept (using the told subsumer information). The classifier assigns in a round-robin manner partitions with a fixed size from the concept list to idle threads and activates these threads with their assigned partition using the procedure insert partition outlined in Algorithm 2. All threads work in parallel with the goal to construct a global subsumption tree (taxonomy). They also share a global array located concepts indexed by thread Algorithm 1 parallel tbox classification(concept list) topological order list topological order(concept list) repeat wait until an idle thread ti becomes available select a partition pi from topological order list run thread ti with insert partition(pi; ti) until all concepts in topological order list are inserted identifications. Using the Concurrency package in Java, synchronization on the nodes of the global tree as well as the entries in the global array have now been eliminated.
The procedure insert partition inserts all concepts of a given partition into the global taxonomy. We use Concurrent collections from the java.util.concurrent package. This package supplies Collection implementations which are thread-safe and designed for use in multi-threaded contexts. Therefore, for updating a concept or its parents or children, no locking mechanism for the affected nodes of the global tree is needed anymore. Algorithm 2 first performs for each concept new the top-search phase (starting from the top concept (>)) and possibly repeats the top-search phase for new if other threads updated the list of children of its parents. Then, it sets the parents of new. Afterwards the bottom-search phase (starting from the bottom concept (?)) is performed. Analogously to the top-search phase, the bottom search is possibly repeated and sets the children of new. After finishing the top and bottom search for new, the node new is added to the entries in located concepts of all other busy threads; it is also checked whether other threads updated the entry in located concepts for this thread. If this was the case, the top and/or bottom search need to be repeated correspondingly.
To reduce overhead in re-running of top or bottom search, we only re-run twice. If
the concept new is still not ready to be inserted; e.g., there is any interaction between
new and a concept in located concepts; it will be added to the partition list of concepts
(to be located later), and also eliminated from the other busy threads’ located concepts
list, otherwise, new can be inserted into the taxonomy using Algorithm 7. In order to
avoid unnecessary tree traversals and tableau subsumption tests when computing the
subsumption hierarchy, the parallel classifier adapted the enhanced traversal method
[
The possible incompleteness caused by parallel classification [
parents top search(new,>) predecessors(new) parents children bottom search(new,?) while : consistent in bottom search(children,new) do
children bottom search(new,?) successors(new) children for all busy threads ti 6= id do
located concepts (ti ) located concepts (ti ) [ fnew g check check if concept has interaction (new ; located concepts (id )) while (check 6= 0) and : nish rerun do if rerun < 3 then if check = 1 then new predecessors top search(new,>) rerun rerun + 1 predecessors(new) new predecessors if check = 2 then new successors bottom search(new,?) rerun rerun + 1 successors(new) new successors check check if concept has interaction (new ; located concepts (id )) else finish rerun true for all busy threads ti 6= id do
located concepts (ti ) located concepts (ti ) n fnew g if : nish rerun then
insert concept in tbox(new, predecessors(new), successors(new)) placed at least one concept into the hierarchy which the concept new has an interaction with. Again, this might cause missing subsumptions and is analogously also applicable to bottom search.
Both scenarios are properly addressed in Algorithm 2 to ensure completeness. Every time a thread locates a concept in the taxonomy, it notifies the other threads by adding this concept name to their “located concepts” list. Therefore, as soon as a thread finds the parents and children of the concept new by running top search and bottom search; it checks if there is any interaction between concept new and the concepts located in the “located concepts” list. Based on the interaction, top search or bottom search needs to be repeated accordingly. If no possible situations for incompleteness are discovered anymore, Algorithm 7 is called. To resolve the possible incompleteness we utilize AlgoAlgorithm 3 top search(new,current) mark(current,‘visited’) pos-succ ; captured successors(new)(current) for all y 2 successors(current) do if enhanced top subs(y,new) then
pos-succ pos-succ [ fyg if pos-succ = ; then
return fcurrentg else result ; for all y 2 pos-succ do if y not marked as ‘visited’ then
result result [ top search(new,y) return result Algorithm 4 enhanced top subs(current,new) if current marked as ‘positive’ then
return true else if current marked as ‘negative’ then
return false else if for all z 2 predecessors(current)
enhanced top subs(z,new) and found in ancestors(current,new) then mark(current,‘positive’) return true else mark(current,‘negative’) return false rithms 5 and 6.2 The procedure consistent in bottom search is not shown here because it mirrors consistent in top search. 3
In the previous section, we explained the algorithms used in our Concurrent TBox Classifier. In this section, we study the scalability and performance of our prototype. Here, we would like to explain the behavior of our system when we run it in a (i) sequential or (ii) parallel multi-processor environment. We also describe how the prototype performs when we have huge real-world ontologies with different DL complexities. Therefore, in the remaining of this section, we report on the conducted experiments.
We first provide a description of the used platform and the implemented prototype,
then we describe the test cases used to evaluate Concurrent TBox Classifier and provide
2 Algorithm interaction possible(new,concept) uses pseudo model merging [
Algorithm 5 consistent in top search(parents,new) for all pred 2 parents do if successors(pred) 6= captured successors(new)(pred) then diff successors(pred) n captured successors(new)(pred) for all child 2 diff do if found in ancestors(child,new) then
return false return true Algorithm 6 check if concept has interaction(new,located concepts) The return value indicates whether and what type of re-run needs to be done: 0 : No re-run in needed 1 : Re-run TopSearch because a possible parent could have been overlooked 2 : Re-run BottomSearch because a possible child could have been overlooked if located concepts = ; then
return 0 else for all concept 2 located concepts do if interaction possible(new,concept) then if found in ancestors(new,concept) then
return 2 else
return 1 else if interaction possible(concept,new) then if found in ancestors(new,concept) then
return 2 else
return 1 return 0 an overview of the parameters used in the experiments. Finally, we show the results and discuss the performance of the classifier. In addition, the measured runtimes in the figures are shown in seconds using a logarithmic scale.
Platform and implementation All the experiments were conducted on a high performance parallel computing cluster. The nodes in the cluster run an HP-version of RedHat Enterprise Linux for 64 bit processors, with HP’s own XC cluster software stack. To evaluate our approach, Concurrent TBox Classifier has been implemented in Java using lock-free data structures from the java.util.concurrent package with minimal synchronization.
Test cases Table 1 shows a collection of 9 mostly publicly available real-world ontologies. Note that the chosen test cases exhibit different sizes, structure, and DL complexities. The benchmark ontologies are characterized by their name, size in number of named concepts or classes, and used DL.
Parameters used in experiments The parameters used in our empirical evaluation and their meaning are described below (the default parameter value in shown in bold). Algorithm 7 insert concept in tbox(new,predecessors,successors) for all pred 2 predecessors do
successors(pred) successors(pred) [ fnewg for all succ 2 successors do
predecessors(succ) predecessors(succ) [ fnewg
Performance In order to test the effect of these parameters in our system, the benchmarks are run with different parameter values. The performance improvement is measured using the speedup factor which is defined as Speedupp = TT1p , where Speedupp is the speedup factor, and – p is the number of threads. In the cluster environment we always had 8 cores available and never used more than 8 threads in our experiments, so, each thread can be considered as mapped to one core exclusively; – T1 is the CPU time for the sequential run using only one thread and one single partition containing all concept names to be inserted; – Tp is the CPU time for the parallel run with p threads.
Effect of changing only the number of threads To measure the performance of the classifier in this case we selected EClass-51En-1 as our test case and ran the tests with a fixed partition size (5 or 25) but a different number of threads (2 and 4), as shown in Fig. 1. In the following we use Pthreads;partition size to indicate a parallel multi-core setting where the subscripts give the number of cores available, the number of threads 3 For ease of presentation we use the terms core and processor as synonyms here. )) ss dd nn oo cc ee ss n1n100,0,00000 ii (( ee imim tt nn uu RR 11,0,00000 2200 1155 1100 55 00 eecclalasss--5511eenn--11 FFFigiig.g.1.1.1.R.RRuununtnitmtiimmeesessffofororerecclalasss--5511eenn-n-1-11uususisniingngg555ssesete-tt-
eclass-51e titntiingngsgs:s::SSS((s(seseqeququeenntitaial)ll),),,PP2P2,25,;5,5,,PP4P4,45,;5,5,,PP2P2,22,;2525,5,,PP4P4,42,;25255
uentia ((P(PtPhtthrheraeaddss,p,paarrtritttiitiotioinonnsiszieze reads;pa siz)e).).
eecclalasss--5511eenn--11
created, and the partitions size used (from left to right). In the test cases P2;5 and P4;5, we get an ideal speedup proportional to the number of threads, as shown in Fig. 2. As we can see, doubling the number of threads from S to P2;5 and to P4;5, each time doubles the speedup, in other words, decreases the CPU time by the number of threads. This is the ideal speedup that we were expecting to happen.
Comparing thSeS test casesPPS44,,2,25P52;25, and P4;25, we get an even better speedup, also shown in Fig. 1 and 2P.P2I2,n5,5this case, the CPU time decreases almost to 1 the sequential case (S). This speedup is due to a combination of the pPaP2r2,t5,i5t1i0oncPPos4i4m,z2,25ep5aarsewdetlol 110000,0,00000 SS as)s1)st10h0,e0,00c00a0che effect and results from the different memory hierarchies of a cluster with mnondern computers. When we increase the number of threads to 4, the speedup is again dd precoecp11o,0,r00t0i0o0nal to the number of threads and this is wtcotcohat2w200e expected. Here, by doubling oo rr thi(senmei(senmnu11m000b0er of threads, the speedup doubles. fadupfadup Efitftiect of changing only partition sizes The perfeeoeerma11n00ce of the classifier in this case nn pp fouRruREC1l1a00ss-51En-1 is also shown in Fig. 1 with aSfiSxed number of threads (2 or 4) but different partition sizes (5 or 25). When using 2 threads, compared to case S, we get 00 ttthhhreeeiiaddedeeemsmaab,1blla1dascsssopisa-iu2se-2beeggladeewaleuselstsenhpOtn1Oti1nhcfntoeohtolrolsiogtsPpagytamye2wme;b5bhids,i-sau2-atp2asaw,eseicehnclcalcoyawsyocsswc-ste5-hn5r1ee1eienrnne-1w-x1Fpoiegrcd.ts2i,n.dgAetcsorwehaeasepemecmpsbabeantasnhsse.siseeT-ie2TA-ge2egCeasatslg,OetlPOeandnnU1inot1notuol,ttolabtiogcammglymoiybnmebisig-sbp2-e2etacyahaclraleheascsscyda-snyc5-lc5uft1o1.emenTnc-b1-ha1esirseoiSsf if the partiatarigrogeneTTsize is increased to 25, it shows the sameLLasargprgeedup as shown in Fig. 2. In
LL this case, the CPU time decreases almost to 15 compared to the previous case. FFigig..33I.n.RRtuhunentitsmimceeesnsfafororirooonwntotiotlholog4gieiteshsuruessainidngsg,33wsseeettgitniengtgsas::corrFFeisgigp..4o4.n.SdSpipneeegeddsuupppefefoodrruoopnn,totaolsologsgiheieosswffrnroomimnFFFigiig.g.3.3.2. . SSI(n(sseteqhquiuseencntaitaisale)l),,,PtPh22e,5,5C,,PPP4U4,2,25t5.i.me decreases to almost 110 compared to the sequential case. This speedup again is due to a combination of the number of threads as well as the cache effect. When we increase the partition size to 25, the speedup is what we expected. Here, by multiplying the partition size by 5, the speedup is multiplied by five too.
Increasing the partition size, means that more concepts are assigned to one thread; therefore, all the related concepts are inserted into the taxonomy by one thread. Hence, increasing the partition size, reduces the number of corrections.
titninggss:: SS ((sseeqquueenntitaial)l),, PP22,5,5,, PP44,5,5,, PP22,2,255,, PP44,2,255 ((PPththrreeaaddss,p,paarrtittiitoionn ssizizee))..
SS eecclcalcyasycsscs-5-511eenn-1-1
SS
Effect of increasing both the number of threads and the partition size In this scenario, we measured the CPU time when increasing both the number of threads and the partition size. In Fig. 3 and 4, our test suite includes the ontologies Embassi-2, Galen1, LargeTestOntology, Tambis-2a, Cyc, and EClass-51En-1. The CPU time for each test case is shown in Fig. 3 and the speedup factor for each experiment is depicted in Fig. 4. As the results show, in the scenario with 2 threads and partition size 5, the speedup doubles compared to the sequential case and is around 2 and this is what we were expecting. When we increase the number of threads as well as the partition size, for the scenario with 4 threads and partition size 25, the CPU time decreases dramatically and therefore the speedup factor is above 20 for most test cases. This is more than a linear speedup, and it is the result of increasing the thread number as well as partition size together with the cache effect. The highest speedup factor is reported with test case Galen1. Experiment on very large ontologies We selected 3 Snomed variants as very large ontologies with more than 150,000 concepts. Snomed-2 with 182,869 concepts, Snomed-1 with 223,260 concepts, and Snomed with 379,691 concepts were included in our tests. Fig. 7 shows an excellent improvement of CPU time for the parallel over the sequential case. In Fig. 8, the speedup factor is almost 2, which the expected behavior. The best speedup factor is observed for test case Snomed.
Observation on the increase of size of ontologies We chose Cyc, EClass-51en-1, Snomed-1, Snomed-2, and Snomed as test cases. Here, as shown in Fig. 5 and 7, in a parallel setting with 2 threads, the CPU time is divided by 2 compared to the sequential case. The speedup, shown in Fig. 6 and 8, is linear and is consistent for our benchmark ontologies even when the size of the ontologies increases.
Overall, the overhead is mostly determined by the quality of the told subsumers and disjoints information, the imposed order of traversal within a partitioning, the division of the ordered concept list into partitions, and the number of corrections which have been taken place (varied between 0.5% and 3% of the ontology size; depends on the 110000,,000000 )) ss dd nn nn ii (( usus RdRd nn nn ii (( RR
110000 )) ss dd nn oo cc ee ss nn ii (( ee imim tt nn )) SS
PP22,,55
PP44,,2255 eeccllaassss--5511eenn--11 eeccllaassss--5511eenn--11 ccyycc ccyycc
SS
PP22,5,5 SS
PP22,,55 SS
PP22,,55
PP44,,2255 ccyycc ccyycc 2200 1155 1100 225050 110505 1100 55 00 22 11 11..55
eclass-51en-1uuusss--iininnggg333ssseeetttttitininngggsss:::SSS((sseeqquueennnttitiaiaall)l)),,,PPP222,,5;55,,,PPP444,,2;22555..
(seque
FFFiiggig..6.66...SSSpppeeeeededduuupppffofoorrrooonnnttootolloologggiieeisessffrfroroommmFFFiiggig...555..
eedd--22 ssnnoomm ssnnoomm eedd--11 ssnnoomm
eedd SSS((s(seseqeququeuenentnti44iatailal))l,),P,P2P2,25,5;.5.
mm ii tt Figuu. 7. Runtimes for snomed using 2 settings:
nn FFiigg..77..RRuunnttiimmeessffoorrssnnoommeedduussiinngg22sseetttiinnggss::
RR eedd
--22 ssnn oomm ssnn oomm eedd --11 ssnn oomm
eedd top to bottom strategy.
SS ((sseeqquueennttiiaall)),, PP22,,55.. structure of ontology as well as the number of threadsssnn nn and parsstition size). In general, FFiigg..77.. RRuunnttiimmeess ffoorr ssnnoommeedd uussiinngg 22 sseettttiinnggasss::possible to their final order in the tree using a one should try to insert nodes as close
In Concurrent TBox Classifier no optimization techniques for classification have been implemented. For instance, there are well-known optimizations which can avoid subsumption tests or eliminate the bottom search for some DL languages or decrease the number of bottom searches in general. Of course, our system is not competitive at all compared to highly optimized DL reasoners or special-purpose reasoners designed to take advantage of the characteristics of the we can easily classify ontologies that are outside of the fragment.
E L fragment (e.g., see [
In this paper, we have shown an excellent scalable technique for concurrent OWL ontology classification. The explained architecture, which proposes lock-free algorithms with limited synchronization, utilizes concurrency in a multi-core environment. The experimental results show the effectiveness of our algorithms. We can say that this work appears to be the first which documents significant performance improvements in a multi-core environment using real-world benchmarks for ontologies of various DL complexities.