As our computers embed more cores, e cient reasoners are designed with parallelization but also CPU and memory friendliness in mind. These latter contribute to make reasoner tractable in practice despite the computational complexity of logical fragments. However, creating benchmarks to monitor this CPU-friendliness for many reasoners, datasets and logical fragments is a tedious task. In this paper, we present the Universite Saint-Etienne Reasoners Benchmark (USE-RB) that automates the setup and execution of reasoners benchmarks with a particular attention to monitor how reasoners work in harmony with the CPU.
Introduction The number of Web applications relying on a triplestore and a reasoner has seen an exponential growth in the last years. This has resulted in new Web frontends for browsing, searching, and expressing complex queries over online data. As online data has never been as interlinked as today, the emerging challenge is to process these data in a computationaly e cient manner, especially when reasoning.
However, reasoning is a computational expensive task, and there are many logic fragments around, albeit no logic fragments ts all applications. For example, subsumption computation complexity in SHOIN description logic is decidable and exhibit a NEXPTIME time complexity. While such order of complexity may prevent the working ontologist to include a reasoner in their application { although the bene ts to leverage implicit triples { the situation is not so desperate from practical point-of-view. Actually, even when the theoretical complexity seems to be intractable, there are optimized reasoners available [2, 4] that are usable for practical real world cases.
Historically, reasoning scalabilty has been tackled from a distributed computing point-of-view with practical system such as WebPie [1]. While these systems provided an unprecedented scalability, they fall short of scaling linearily ? This work has been supported by the CNRS PEPS-Secu project. with the number of nodes in the cluster. One can observe that the most recent research have shifted towards parallelization on a single node equipped with many cores [2{4]. These approaches focus on designing in-memory, e cient and cache-friendly data structures and algorithms in order to win back otherwise lost CPU cycles as in hardware-unoptimized counterparts. By designing cache-friendly systems, data and code locality are expected to fully exploit CPU subsystems such as the prefetcher, the translation lookaside bu ers and page management, to name a few. Actually, most of reasoning consists in memory I/O rather than raw arithmetic computations { few computations are made but usually data structures are to be traversed several times in di erent ways. For instance, systems such as RDFOx [2] are defying Amdahl law as they exhibit a close-to-linear scalability with respect to the number of threads devoted to the reasoning task. With major chips makers such as Intel running a many cores policy for the next years, one can expect that research e orts combined with technology advances will lead further reasoning performance to the real eld. In order to sustain the research e ort, it is therefore of the utmost practical interest to go deeper in understanding reasoners performance { examinating reasoners from a CPU-friendliness point-of-view is a mandatory e ort.
Through USE-RB { University Saint-Etienne Reasoner Benchmark { we envision a CPU-friendly reasoners benchmark. USE-RB integrate all the facilities to plug any existing / to-be reasoners or datasets, to easily run and evaluate how a reasoner is working in harmony with the CPU. We believe that providing our benchmark to the community will contribute to the research for high performance many-cores reasoners. USE-RB is expected to be con gured with a list of reasoners, a list of datasets and a list of logic fragments. The cartesian product of these sets results in as many benchmark con guration to be run { a benchmark task. The module named USE-RB, the entry point of the execution of the program, is actually responsible for sequentially spawning as many instances of an external program named ReasonersBenchmarked { thus each benchmark task is run in isolation. A Java interface provides functional genericity in order to easily integrate new reasoner to the benchmark. Each execution of ReasonersBenchmarked can be parameterized with the number of warm-up iterations and the number actual iterations for which USE-RB will measure CPU counters. USE-RB track down CPU counters for each execution of a ReasonersBenchmarked instance. The primary counter is the wallclock time taken by the program to run one benchmark con guration { the actual number of CPU cycles, i t l e u p p r e s s e d u e t o x c e s s i v e e n g t h , u s e d b y t h e
C
P
U f o r t h i s p r o c e s s .
O t h e r m e t r i c s f o c u s o n h a r d w a r e s p e c i c c o u n t e r s f o r v a r i o u s
C
P
U c o m p o n e n t , c a t e g o r i z e d a s f o l l o w s .
I n s t r u c t i o n s .
I n s t r u c t i o n s m e t r i c s i n c l u d e s t h e n u m b e r o f b r a n c h m i s p r e d i c t i o n s ( b r a n c h m i s s e s ) b y t h e
C
P
U .
T h i s i s r e l e v a n t f o r r e a s o n e r s g i v e n t h e t r e m e n d o u s a m o u n t o f d a t a s t r u c t u r e s t o t r a v e r s e { t h e s e t r a v e r s a l s a r e t o b e a s m u c h u n i f o r m a s p o s s i b l e , t h e r e f o r e p r e d i c t a b l e f o r e a r l y
C
P
U p i p e l i n e u n i t s .
U
S
E R
B a l s o r e p o r t s t h e t o t a l n u m b e r o f i n s t r u c t i o n s t h e n u m b e r o f i n s t r u c t i o n s p e r
C
P
U c y c l e , a n d t h e n u m b e r o f s t a l l e d
C
P
U c y c l e p e r i n s t r u c t i o n
.
M e m o r y .
M e m o r y m e t r i c s i n c l u d e s t h e n u m b e r o f p a g e f a u l t s t h e n u m b e r o f t r a n s a c t i o n a l l o o k a s i d e b u e r l o a d s a n d m i s s e s ( t o t a l n u m b e r a n d h i t r a t i o ) .
I t a l s o i n c l u d e s t h e n u m b e r o f s t a l l
C
P
U c y c l e s w h e n a c c e s s i n g a n y h i e r a r c h y o f t h e m e m o r y .
C a c h e .
C a c h e m e t r i c s a r e a s u b c a t e g o r y o f
M e m o r y m e t r i c s { a h i g h l y p r o m i n e n t s e t o f m e t r i c s w h e n d e s i g n i n g h i g h p e r f o r m a n c e a p p l i c a t i o n s s o t h a t i t f a l l s i n t o i t s o w n c a t e g o r y i n
U
S
E R
B .
C a c h e m e t r i c s i n c l u d e t h e m i s s r a t e o n a l l l e v e l s o f c a c h e .
I t a l s o p r o v i d e s a p e r c a c h e h i e r a r c h y l e v e l i n f o r m a t i o n o n c a c h e h i t a n d m i s s e s .
A s f o r t h e r s t l e v e l o f c a c h e ( L 1 ) .
I n c a s e o f a h i g h c a c h e m i s s r a t e . 2 . 3
R e s u l t s a n d e x t e n s i b i l i t y U
S
E R
B i s s h i p p e d w i t h v a n i l l a d a t a s e t s , a n d r e a s o n e r s .
I t i s n a t i v e l y a b l e t o r u n b e n c h m a r k s b y c r e a t i n g
B e n c h m a r k c o n g u r a t i o n s ( s e e 2 . 1 ) b y s e l e c t i n g o n e o r s e v e r a l d a t a s e t s , l o g i c a l f r a g m e n t s a n d r e a s o n e r s a m o n g : {
D a t a s e t s : 9 d i e r e n t s i z e s o f a
B
S
B
M d a t a s e t ( f r o m 1 0 0 0 0 0 t r i p l e s u p t o 1 0 0 m i l l i o n t r i p l e s ) ,
W i k i p e d i a
O n t o l o g y ,
Y a g o t a x o n o m y .
W e a l s o s h i p d e d i c a t e d d a t a s e t s f o c u s i n g o n b e n c h m a r k i n g t h e c l o s u r e c o m p u t a t i o n o f t h e s u b s u m p t i o n a x i o m s .
TdLB-loamise arte apge-fults p re 1K
T irples .0 2 02 .0 51
510 .0 1
01 2 05 5 01 − · 0 0 x x x x y x y x y x y x y x y y y y x x x x x x x x
x y y y y y y y y y gao ulbm5 ulbm10 ulbm25 ulbm50 ulbm75 ulbm10 iWk
W rodnet Y gao ulbm5 ulbm10 ulbm25 ulbm50 ulbm75 ulbm10 iWk
W rodnet F i g . 1 .
C a c h e m i s s e s b e n c h m a r k . { Reasoners : JENA [5], OWLIM [6]1, SLIDER [3], SESAME [7], RDFOX [2], and Inferray [4]. { Logical Fragments2 : RDFS default, RDFS-Full, Rho-DF, RDFS+.
One can easily add his/her own dataset, reasoner or logical fragment3. Figure 1 provides an example of gure that can be drawn from the execution of USE-RB. This gure reports data TLB misses and page faults per triple inferred for a RDFS-Full benchmark con guration4. Though the benchmark was run on all vanilla reasoner, we kept the most performant reasoners { omitted reasoners are outperformed by several order of magnitude as reported in [4].
Conclusion In this paper, we presented USE-RB, a system for creating reasoners benchmarks and to observe how reasoners works in harmony with the CPU through the monitoring of CPU counters. USE-RB is publicly available at https://github. com/telecom-se/USE-RB. We believe that the presented benchmark is of the utmost practical interest for the researchers and industries who are willing to provide high performance reasoners. We also think that such frameworks are mandatory for promoting reproducibility of experiments, whenever possible. This framework also includes various popular datasets, reasoners, and implemented logical fragments { while providing the customizable features. 1. Urbani, J., Kotoulas, S., Maassen, J., Van Harmelen, F., Bal, H.: WebPIE: A webscale parallel inference engine using MapReduce. In: Web Semantics: Science, Services and Agents on the World Wide Web, Vol. 10, pp. 59-75 (2012) 2. Motik, B., Nenov, Y., Piro, R., Horrocks, I., Olteanu, D.: Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems. In: AAAI, pp. 129-137 (2014) 3. Chevalier, J., Subercaze, J., Gravier, C., Laforest, F.: Slider: an E cient Incremental
Reasoner. In: SIGMOD, pp. 1081-1086 (2015) 4. Subercaze, J., Gravier, C., Chevalier, J., Laforest, F.: Inferray: fast in-memory RDF inference. In: VLDB, 9(6), pp. 468-479 (2016) 5. McBride, B.: Jena: A semantic web toolkit. In: IEEE Internet computing 6(6) pp.
55 (2002) 6. Bishop, B. et al: OWLIM: A family of scalable semantic repositories. In: Semantic
Web 2(1), pp. 33{42 (2011) 7. Broekstra, J., Arjohn, K., Van Harmelen, F.: Sesame: A generic architecture for storing and querying rdf and rdf schema. In: ISWC, pp. 54{68 (2002) 1 Requires a OWLIM-SE licence 2 Logical fragments description in [4] 3 https://github.com/telecom-se/USE-RB 4 This exlcudes BSBM dataset since it does not support the expressivity of the RDFFull logical fragment.