In this section, we define a benchmark set for Prolog that contains programs normally used as benchmarks for sequential Prolog systems and other real applications developed in companies or in academia. The applications offer several opportunities for parallelisation, and presents a varied degree of parallelism. To the best of our knowledge, this is the first attempt to define a benchmark set for parallel Prolog systems.
In our benchmark set, we selected programs with predominantly and-parallelism, with predominantly or-parallelism, programs that present both kinds of parallelism in different phases of the computation and applications that have both kinds of parallelism appearing at the same computational phase. We classify them into four main groups depending on whether the parallelism is high or or low, and whether it is mainly and-parallelism or or-parallelism. For brevity, we call these groups: (1) high or, high and, (2) high or, low and, (3) low or, low and, (4) low and, low or, (5) high and, low or, (6) high or, and (7) high and. Group (1) has high degree of or- and and-parallelism, but the amount of or-parallelism is bigger than and-. Group (2) has high degree of or-parallelism with low degree of and-parallelism. Group (3) has low degree of or-parallelism and low degree of and-parallelism, but the amount of or-parallelism is bigger than the amount of and-parallelism. Group (4) has low degree of and- and or-parallelism, but the amount of and-parallelism is bigger than the amount of or-parallelism. Group (5) has high degree of and-parallelism, and low degree of or-parallelism. Group (6) has only or-parallelism. Group (7) includes programs that contain only and-parallelism.
This is a queens program written using a Pandora technique [7]. Its or-parallelism arises when trying to solve the cell predicate. The problem is to place queens in a board (NxN) in order that no queen attacks each other in any column, row or diagonal. For any boardsize, this program has mainly or-parallelism with little amount of and-parallelism. Depending on the boardsize, this program can fall in groups 2 or 3.
This is an example from a natural language question-answering system Chat-80. Chat-80 is a natural language question answering system written at the University of Edinburgh by Pereira and Warren [109]. This version of Chat-80 operates on the domain of world geography. The program makes a query to the Chat-80 database. It contains or-parallelism, and it has been used as one of the or-parallel benchmarks for both the Aurora and Muse systems. This program falls into group 6.
This is a program that solves crossword problems according to the constraint technique used by van Hentenrick in [101]. A crossword generator was written with the purpose of automatically produce different kinds of crosswords. The crossword generator program accepts as an input the crossboard format, horizontal words to be placed in the board and vertical words to be placed in the board. In the program generated by the crossword generator, the crossboard itself is expressed by a clause with a huge body defining the shape of the board in terms of horizontal and vertical blank spaces to be filled in the board. Each word is numbered and defined as a database of facts with as many facts for the same word as the number of letters in the word. Depending on the shape of the crossword, this program can fall into groups 3 or 4.
This is a program that solves a problem described in [64]. The problem is to produce the string 'mu' from a given string, through production rules that can be applied in any order. One example of theorem to prove is that 'miiiii' produces 'mu'. If we replace the letters in the strings by numbers, this puzzle solves some interesting problems in number theory. This program contains only or-parallelism. This program falls into group 6.
This is a program to extract road markings developed by Hluchoweckyj [63] from the vision research group, in the department of Computer Science at the University of Bristol.
This program is part of a Ph.D. project to extract road markings from real world vision pictures that have been processed to identify a set of visible objects. The program fits straight lines or quadratic curves through these objects. The ``best'' set of curves is taken as being the road boundaries, where ``best'' is defined by certain heuristics such as the width between two road boundaries being constant and greater than a vehicle-width apart. This application contains and-parallelism corresponding to parallelising the operations on each pair of objects. We have an example that takes 16 objects as the input data. This program has mainly or-parallelism with little amount of and-parallelism. This program falls into group 5.
This is a version of a naval flying programme generator, initially developed by Software Sciences in the University of Leeds for the Royal Navy. It is an example of a real life resource allocation problem. The program allocates airborne resources (such as aircrafts) whilst taking into account a number of constraints. The problem is solved by using the technique of active constraints as first implemented for Pandora [6]. In this technique, the co-routining inherent to a system such as the Andorra model is used to activate constraints as soon as possible. The program has both or-parallelism, arising from the different possible choices, and and-parallelism, arising from the parallel evaluation of different constraints. The degree of and- and or-parallelism in this program varies according to the queries, but all the queries give rise to more and-parallelism than or-parallelism. Depending on the query, this program falls into groups 4 or 5.
This is a scanner program to reveal the contents of a bitmap. The program is an AKL [66] benchmark developed at SICS. The program reveals the contents of a box (bitmap). The input is the number of dots on each row, column, left diagonal, and right diagonal. The problem was described in [39]. The program contains both and- and or-parallelism corresponding to parallel propagation of determinate bits and evaluation of constraints. This program gives rise to reasonable amounts of both and- and or-parallelism in interleaven phases. This program falls into group 1.
This is a simple substituting decoding system developed by Rong Yang [110]. The system reads an encrypted text and decodes it (assuming the original message is in English). According to the statistics, if one knows about 100 of the most common words, one can respectively understand on average 60% of most text. Now, instead of having an entire English dictionary, we can solve a cipher using only a very small dictionary of common words (about 150 words). Them the program performs a lot of letter matching, first determinately in and-parallel, then when only non-determinate matching is left, the program makes a choice-point (giving rise to or-parallelism). An or-branch fails when the number of unmatchable words exceeds a certain limit. This program falls into group 2.
The length of the ciphertext we have is 56 letters, and the maximum number of unmatchable words is set to 2. This program has mainly or-parallelism with little amount of and-parallelism.
This is another real world application developed by the British Telecom company [78]. It was developed on the scope of the BT contract with the Bristol University. The application involves finding paths through a network from a common source node to several destination nodes in such a way that the overall cost is minimised. The cost of using an individual link may reflect factors such as its length, its capacity, the average level of its demand, or the time of day at which it is demanded. Therefore the shortest route might not always be the cheapest. This program falls into group 4.
This is an application that has several applications, since hardware design till architectural or civil engineering design. The problem consists of placing several components on a surface in order to minimise the total area. Each component can have different shape. Our application deals only with rectangular shapes. The problem is implemented using a branch-and-bound approach with best-first search, and presents a great amount of or-parallelism, that stems from the different branches of the search tree. It belongs to group 6.
This program implements the classical traveling salesperson problem where we need to find a minimum route from a city A to another city B , visiting all cities on the way exactly once. It is also implemented using a branch-and-bound algorithm with best-first search, and presents a great amount of or-parallelism. This program falls into group 6.
This program also implements the classical traveling salesperson problem, but it was implemented in order to have only and-parallelism. This program was developed by the Reform Prolog group, and is used as benchmark in the Reform Prolog system [17]. This program falls into group 7.
As an example and-parallel application, we used the clustering algorithm for network management from British Telecom [35]. The program receives a set of points in a three dimensional space and groups these points into clusters. Basically, three points belong to the same cluster if the distance between them is smaller than a certain limit. We have input data with 400, 500, and 1000 points. This program has very good and-parallelism, and, being completely determinate, no or-parallelism. This program falls into group 7.