[Next] [Previous] [Up] [Top] [Contents]
6 Performance
6.1 Benchmarks
Four benchmarks are presented here. The first two are designed to measure the raw speed of firing rules using forward chaining.
- cycle1000. Firing 1000 instances of the same rule in a cycle. This is done by firing the rule in figure 11 after the clause forwardKeyword 0 has been asserted to the database.
- nocycle1000. Firing 1000 instances of a rule, without a cycle. This is done by firing the rule in figure 12 after 1000 clauses with the keyword forwardKeyword have been asserted.
However, the rules used in the above benchmarks are artificial and much simpler than those used to solve real problems. Therefore, two further benchmarks which solve specific problems are also used.
- tourney. Scheduling a bridge tournament of 16 players, so that every player partners every other player once, and plays against every other player twice.
- rubik. Scrambles a rubik's cube and solves it, by rotating faces until every block on the same face is the same colour.*1
The latter benchmarks were previously implemented in OPS5*2, and have been used to compare the efficiency of different OPS5 implementations (in [1] for example). OPS5 is an imperative rule-based language, and most of the rules used in the OPS5 benchmarks retract or modify information already on the database, often immediately making the antecedents false. Nevertheless, the SDML implementations use the same algorithms and there is a one-to-one correspondence between most of the rules in both languages.
The SDML versions of the benchmarks use some facilities that are not present in OPS5, such as arbitraryChoice (to arbitrarily choose who plays together or which block to move into position next) and lists (particularly useful for the efficient representation and manipulation of rubik's cubes). Subdatabases can be used for different stages in the problems' solutions, since backtracking is not used (in either OPS5 or SDML) after scheduling any bridge hands or rotating the cube. Backward chaining, which is not available in OPS5, is used for some of the SDML rules.*3
Efficient Forward Chaining for Declarative Rules in a Multi-Agent Modelling Language - 16 FEB 95
[Next] [Previous] [Up] [Top] [Contents]
Generated with CERN WebMaker