High-Level Constructors for Solution Searching in Or-Parallel Prolog Systems

High-Level Constructors for Solution Searching in Or-Parallel Prolog Systems João André Martins da Silva Mestrado Integrado em Engenharia de Redes e Sistemas Informáticos Departamento de Ciência de Computadores 2014 Orientador Ricardo Jorge Gomes Lopes da Rocha, Professor Auxiliar, Faculdade de Ciências insira uma figura alusiva ao tema Todas as correções determinadas pelo júri, e só essas, foram efetuadas. O Presidente do Júri, Porto, ______/______/_________ Jo˜ao Andr´e Martins da Silva High-Level Constructors for Solution Searching in Or-Parallel Prolog Systems Tese submetida `a Faculdade de Ciˆencias da Universidade do Porto para obten¸c˜ao do grau de Mestre em Engenharia de Redes e Sistemas Inform´aticos Advisor: Prof. Ricardo Jorge Gomes Lopes da Rocha Departamento de Ciˆencia de Computadores Faculdade de Ciˆencias Setembro de 2014 2 Dedicado aos meus pais e irm˜a. 3 4 Abstract 0 This aim of this work is to design and implement strategies that can improve the performance of logic programs when searching for particular solutions in an Or-Parallel Prolog system. Prolog is a first-order logic predicate language that belongs to the declarative family of programming languages, emphasizing data declaration and use. Or-Parallelism is a form of implicit parallelism that can be applied to Prolog programs, in order to allow the parallel execution of several clauses that match a Prolog goal. With the availability of specific strategies that can improve the system’s performance when searching for solutions in parallel, we expect to: (i) allow for long-running programs, such as those used for simulations, to take less time to execute; (ii) make it possible to execute new programs that deal with larger amounts of data, that would otherwise be too slow to run; (iii) generate more interest in Prolog, which might lead to further research. In particular, our implementation was done on top of the YAP Prolog system, a well-known and established system which makes it possible for users to get all of these benefits. The strategies proposed in this work have a very important concept at the core: make relatively small changes to the YAP’s engine codebase in order to allow them to be easily ported to other implementations of Prolog, and make them available to the user, by using high-level constructors that transparently increase the speedups obtained without forcing the user to make complex source code changes. 5 3 Implementation of Constructors 33 3.1 Methodology ................................ 33 3.2 SolutionSearching ............................. 36 3.2.1 Strategy W - Wait Before Starting . . . . . . . . . . . . . . . . 38 3.2.2 Strategy B - Get Work Below Before Taking the Next Alternative 39 3.2.3 Strategy L1 - Get Work to the Left Before Taking the Next Alternative ............................. 40 3.2.4 Strategy L2 - Get Work to the Left, with Fallback . . . . . . . . 42 3.2.5 Strategy L3 - Get Work to the Left, in Sorted Order . . . . . . 43 3.2.6 Strategy F1 - Descend the Tree, Start Sharing After Failing the FirstTime.............................. 43 3.2.7 Strategy F2 - Descend the Tree, Share Less After Failing the FirstTime.............................. 45 3.2.8 Strategy S - Freeze the Or-Frames, Allowing Voluntary Suspension 46 3.2.9 Summary .............................. 47 4 Experimental Results 49 5 Conclusions and Future Work 55 5.1 MainContributions............................. 55 5.2 FurtherWork ................................ 55 References 57 A Benchmarking Code 59 12 List of Tables 0 4.1 Execution times and speedups obtained with 4 workers and problem size 30,forallstrategies. .............................. 50 4.2 Execution times and speedups obtained with 8 workers and problem size 34. 51 4.3 Execution times and speedups obtained with 12 workers and problem size 38......................................... 51 4.4 Execution times and speedups obtained with 16 workers and problem size 42......................................... 52 4.5 Execution times and speedups obtained with 20 workers and problem size 45......................................... 53 4.6 Execution times and speedups obtained with 24 workers and problem size 49......................................... 53 13 14 List of Figures 0 2.1 A Prolog example where several color-related predicates are defined. . . . . 25 2.2 Implicit search tree generated for the query ?- color(C). ......... 26 2.3 YAP’s memory area layout. . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4 The relationship between choice points and Or-Frames (courtesy of Ricardo Rocha,from[Roc01]). ............................. 31 3.1 A benchmark that takes exponential time to find a list. . . . . . . . . . . . 34 3.2 A predicate that generates an unbalanced search tree. . . . . . . . . . . . . 35 3.3 Search tree for a call to find/2 when given a list of length 2. . . . . . . . . 36 3.4 A clause used to generate lists that produce pathological behaviour. . . . . 36 3.5 YapOr search tree after worker 0 shares work with worker 1. . . . . . . . . 37 3.6 Expected YapOr worker distribution, using 4 workers. . . . . . . . . . . . . 37 3.7 Expected worker distribution with strategy W, using 4 workers. . . . . . . 39 3.8 Intermediate worker distribution with strategy B, using 4 workers. . . . . . 40 3.9 Expected worker distribution with strategy B, using 4 workers. . . . . . . . 40 3.10 Expected worker distribution with strategies L1 to L3, using 4 workers. . . 41 3.11 Worker 0, immediately before failing..................... 44 3.12 Expected worker distribution with strategy F1, using 4 workers. . . . . . . 44 3.13 Expected worker distribution with strategy F2, using 4 workers. . . . . . . 45 3.14 Expected worker distribution with strategy S, using 4 workers, before suspendingwork................................... 46 3.15 Expected worker distribution with strategy S, using 4 workers, after suspendingwork................................... 47 4.1 Relative speedups obtained with 4 workers. . . . . . . . . . . . . . . . . . . 50 4.2 Relative speedups obtained with 8 workers. . . . . . . . . . . . . . . . . . . 51 4.3 Relative speedups obtained with 12 workers. . . . . . . . . . . . . . . . . . 52 4.4 Relative speedups obtained with 16 workers. . . . . . . . . . . . . . . . . . 52 4.5 Relative speedups obtained with 20 workers. . . . . . . . . . . . . . . . . . 53 15 4.6 Relative speedups obtained with 24 workers. . . . . . . . . . . . . . . . . . 54 A.1 A test designed to stress the parallel findfirst/3 implementation. . . . 59 A.2 Calculates the speedup of the parallel execution of A.1. . . . . . . . . . . . 60 A.3 A wrapper that calls A.2 for each problem size passed as an argument. . . 60 16 List of Acronyms 0 CLP Constraint Logic Programming. DCG Definite Clause Grammar. LP Logic Programming. SLD resolution Selective Linear Definite clause resolution. WAM Warren’s Abstract Machine. YAP YAP Prolog system. 17 18 Introduction 1 Nowadays, immense amounts of data are generated every day. Even though humans have the ability to detect patterns, we are unable to keep up with this increase of information. We did, however, create machines that are able to process this data and give us the big picture in a way that is simpler to understand. The problem is that only a few people have the knowledge needed to control its execution and develop new programs even if they only perform slightly different tasks on tiny variations of the same problems. One tool that makes this process easier is Logic Programming (LP). LP belongs to the class of declarative programming languages, which means that programmers expose the problem they are trying to solve in a straightforward manner with the added benefit that the results they get back also use the same language. Arguably, an important language that belongs to this class is Prolog. This language presents features that make complex tasks such as machine learning and language processing easy to program due to its high-level declarative style. Users do not simply want an expressive language, though. They also want to be able to perform their tasks in a manner that is as fast as possible. For a few years now, being fast implies the use of the multiprocessing features of modern CPUs. Explicit parallelism is, however, a road that is full of challenges that programmers used to writing sequential programs do not want to think about. Once again, Prolog simplifies the task for the programmer: due to its non-determinism, tasks can be run in a partially arbitrary order that can be implicitly parallelized by the runtime system, without altering their semantics. Another important advantage of using Prolog when compared to other languages is that, having deep roots in mathematical concepts, it is possible to prove the correctness of the programs written in it. 19 CHAPTER 1. INTRODUCTION 20 1.1 Motivation Throughout the last decade multicore computers became standard, with their inclusion in x86, the most widely used PC architecture. For this reason, powerful multicore machines are widely available and are becoming increasingly affordable. Researchers and scientists make use of these machines for studies, experiments and developing models in fields that can go from physics to medicine. Taking into account the previously mentioned features of Prolog and the availability of powerful multicore computers, it was natural for researchers to make use of a combination of Prolog and multicore computers. In applications with very large data sets, such as those that often arise in the previously mentioned fields, any decrease in the execution times can not only save users time but also allow them to solve bigger problems. This thesis’ objective is to improve performance of the YapOr Or-Parallel Engine, namely by increasing the speedups of parallel constructors that find specific solutions to a query. Our contribution is a set of strategies designed to reduce the time and resources used to solve problems in parallel Prolog and their implementation in the YAP Prolog system [CRD12], a state-of-the-art implementation of Prolog, including several extensions and developed at the University of Porto. We explain the rationale for the changes and how they alter the overall execution of a Prolog program, presenting the modules where these changes take place. These strategies are particularly useful for long-running programs where a reduction of a few percent of the overall time may translate into minutes, hours or even days. The implementation of each of these strategies changes a relatively small portion of the source code, on purpose, in order to make them easy to understand and be re-implemented in other systems and also to simplify the process of combining several of them together. We hope that this work makes LP a more viable and attractive alternative to other languages for the processing of tasks where large amounts of data must be processed. 1.2 Thesis Outline This document is structured in 6 chapters and a brief description of each is provided next. •Chapter 1: Introduction. The current chapter. 21 1.2. THESIS OUTLINE •Chapter 2: Background. This chapter presents relevant background information on logic programming and the Prolog language. Initially, we provide a comparison of LP with other programming paradigms and introduce the reader to the Prolog programming language. The next sections are dedicated to the Warren’s Abstract Machine (WAM), a virtual machine used by several modern Prolog implementations, and to the YAAM, YAP’s version of the WAM. Finally, we present the YapOr Or-Parallel Engine. •Chapter 3: The Implementation of Or-Parallel Solution Searching Constructors. This chapter describes the methods we used to optimize the YapOr Or-Parallel Engine and describes the several strategies that we have implemented to improve the performance of YapOr. •Chapter 4: Experimental Results. This chapter presents measurements made to assess the system’s performance and discusses the results obtained. •Chapter 5: Conclusions and Future Work. This chapter concludes the thesis and presents suggestions for further work. •Annex A: Benchmarking Code. Contains the code used for benchmarking. CHAPTER 2. BACKGROUND 28 •E, a pointer to the current environment; •B, a pointer to the most recent choice point; •A1, ..., An, the argument registers; •X1, ..., Xn, the temporary variable registers. 2.3.3 Instructions The WAM defines an instructions set that can be divided into four groups: •Choice point instructions which allocate and deallocate memory for choice points, making backtracking possible; •Control instructions that are responsible for managing the calls of subgoals in predicates and manage the environments; •Indexing instructions that, based on the type and value of the first argument of a call, jump to specialized code for that call. •Unification instructions which perform the matching and unification of variables and other types. The instructions that deal with Prolog data structures operate using the notion of modes, of which there are two: •Write mode, the mode where data structures representing Prolog terms are created; •Read mode, where these data structures are matched. 2.4 YAAM The YAAM is YAP’s optimized version of the WAM. It is based on many of the same ideas of WAM’s design, but makes a considerable number of changes, mainly to the memory layout of the WAM. One of the key insights made by the YAP developers is that memory allocated on the heap is long-lived, which means that a compact representation of terms is ideal. As such, the YAAM uses tag bits to represent the five main types of data presented in 29 2.4. YAAM [AK91]: integers, atoms, applications, pairs and references. It additionally supports one more type introduced by YAP: extensions, which allow the use of additional data types not present in strictly-standard Prolog implementations. Examples of additional data types currently available in YAP are multiple-precison integers and arrays of floats and integers. The WAM does not specify the layout of the memory areas. A naive, but obvious, way would be to allocate memory for each area independently of the others, dynamically adjusting each one as needed. The YAAM, leaves the code area independent but compresses the other memory areas into the following scheme: Heap PDLTrail Stack Code Figure 2.3: YAP’s memory area layout. This scheme presents a some advantages: •Allocation of a single large memory area, which is faster than the allocation of several small memory areas; •The layout allows allocation operations to be pointer movements, rather than reallocating and copying memory as in the naive way; •Detecting overflow of the memory areas can be done by a simple pointer comparison. A problem with this scheme is that, when the memory needs to be expanded, all of the memory areas must be copied rather than just the area that needs more memory. 2.4.1 Just-in-Time Indexing Traditionally, Prolog implementations that make use of the WAM index terms by the first argument, making unification faster by only trying alternatives where the type of CHAPTER 2. BACKGROUND 30 the first argument of the query is compatible with the first argument of the matching predicate. For very large datasets, the developers of YAP tested the difference in performance caused by reordering the arguments and reached the conclusion that it could change performance significantly [CRD12]. The solution developed was a dynamic indexing mechanism, called just-in-time indexing (or JITI). This mechanism adds an instruction to the WAM, index pred, that performs the task of indexing the predicate. Although this mechanism may generate a large amount of indexing code, it generally does not do so [CRD12]. 2.5 The YapOr Or-Parallel Engine With the advent of multicore computers, programs need to be able to divide tasks into smaller subtasks that are executed by each core, in parallel. There are two main ways in which one can parallelize the execution of a Prolog program implicitly. These are known as And-Parallelism, where several subgoals in a clause are executed simultaneously and the failure of any of them results in failure of the goal, and Or-Parallelism, where several clauses that match a goal run in parallel in order to find multiple solutions faster. YapOr is an extension of the YAP system that enables it to make use of the multiple cores that are available on current CPUs. As the name suggests, it exploits the OrParallelism inherent to Prolog programs to make solution discovery faster. Similarly to the Muse system [AK90], the YapOr system uses environment copying, where a worker that makes a work request copies the environment of the worker that accepts that request. This is done incrementally, that is, the receiver positions itself above the sender and only copies the portion of memory that is different from its own. Unlike standard Yap, YapOr disallows resizing of the memory areas, which may be a problem for long-running applications that use large amounts of memory. To alleviate this problem, the user can change the size of the areas at compile and/or startup-time. Since YapOr deals with Or-Parallelism, it needs to track which alternatives of a choice point were given to each worker. To do so, each YapOr worker maintains a linked list of Or-Frames to store that information. 31 2.5. THE YAPOR OR-PARALLEL ENGINE Sharing TR H B CP ENV LUB P & Q getwork OrFr_members OrFr_node OrFr_nearest_livenode OrFr_next ALT OrFr_alt Unlocked OrFr_lock Choice Point Or-Frame CP_TR CP_H CP_B CP_CP CP_ALT CP_ENV CP_OR_FR CP_LUB TR H B CP ALT ENV --- LUB Choice Point Figure 2.4: The relationship between choice points and Or-Frames (courtesy of Ricardo Rocha, from [Roc01]). As shown in Figure 2.4, choice points are coupled with Or-Frames; choice points store information relative to the different alternatives that may be taken, mainly in the CP ALT,CP CP,CP TR,CP H,CP B and CP ENV, while Or-Frames maintain information about the different workers that may search for solutions within their associated choice point, mediating access to the choice point with the OrFr lock field and maintaining a bitmap of workers, OrFr members. In this manner, the control of the choice of the next alternative to explorer is moved from the choice point, which is private, to the shared Or-Frames. Or-Frames are only allocated when a worker shares a choice point to which the Or-Frame then becomes associated. Private choice points do not have associated Or-Frames since there is no need to keep information about other workers. An additional change made by YapOr to the YAP system is the introduction of a new WAM instruction called get work that implements the scheduling strategy and is ultimately responsible for the work sharing process [Roc96]. The strategy can be summarized as follows: •Ask for work to the worker that simultaneously has the highest load and is nearest. •When a worker shares work, share all its private nodes. •When unable to get work, backtrack to a point where it is able to. CHAPTER 2. BACKGROUND 32 More precisely, when a worker backtracks to a shared choice point, it first tries to get the next available alternative. Failing that, i.e. if there is no work left in the shared choice point, a worker will move up in the tree until there are other workers below it in order to ask them for work. If, after this process, no work has been shared, the worker moves up to a better position to be able to get work. The execution ends if all workers reach the top root choice point and are unable to get work from each other. Implementation of Constructors 3 In this chapter, we present the different strategies we tested to improve the execution of Or-Parallel computations in YapOr. We firstly present the method used to determine what portions of YapOr would benefit the most from optimization. Then, we explain the changes made and the reasoning behind each. 3.1 Methodology YapOr enables a Prolog programmer to use Or-Parallelism within an application in two main ways: •parallel findall/3, which runs a query in parallel, retrieving a list of all solutions to that query •parallel findfirst/3, which executes a query and stops after finding the first, leftmost solution to that query. Our goal is to increase the speedups we obtain using these parallel primitives, relative to the current version of YapOr. In order to do that, we must first be able to determine where the potential for improvement is. With that in mind, we created a simple synthetic benchmark to test YapOr’s parallel findall/3. The benchmark, presented in Figure 3.1, receives a list of 0s and 1s as input (first argument of find/4), and creates all possible lists of 0s and 1s with size smaller or equal to that of the input list until it recreates that list (second argument of find/4). This generates a balanced search tree, and takes an exponentially increasing amount of time as the size of the list increases. The choice of a benchmark that takes an exponential amount of time was made in order to be able to very easily test different time scales, from milliseconds to several seconds. 33 CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 34 1append([], X,X). 2append([X|Y], Z, [X|W]) :- append(Y,Z,W). 3 4options(0). 5options(1). 6 7find(In,Out):-length(In,Len), find(In, [], Len,Out). 8 9find(ToFind,SoFar,Left, [Item|End]) :- 10 Left >0,options(Item), append(SoFar, [Item], Next), 11 NextLeft is Left -1,find(ToFind,Next,NextLeft,End). 12 find(ToFind,ToFind,_, []). 13 14 % A couple of list examples 15 lists(List,Len):-mkList(Len,0,List). 16 lists([0,0,0|End], Len):-mkList(Len -3,1,End). 17 18 mkList(0,_, []) :- !. 19 mkList(Len,Num, [Num|End]) :- Left is Len -1,mkList(Left,Num,End). 20 21 go(Len) :- 22 lists(List,Len), 23 time(parallel_findall(Var,find(List,Var), Solutions)), 24 fail. Figure 3.1: A benchmark that takes exponential time to find a list. The results obtained with our experiments for this benchmark showed that, on the 24-core machine we used for them, YapOr with 24 workers is able to achieve close to linear speedups, of approximately 21. These results show that the implementation is already very optimized and that in order to get better performance we might need a completely different algorithm. We therefore moved our efforts to the implementation of the parallel findfirst/3 constructor. By making a small change to this benchmark, consisting of changing the use of parallel findall/3 to parallel findfirst/3, we tested the implementation of the parallel findfirst/3 constructor. For an efficient implementation of this predicate, we expect that the execution takes an increasing amount of time as the position of the first solution moves to the right in the search tree. This time should also be proportional to the number of nodes of the search tree that we must traverse until find the solution. Our experiments for this benchmark, which we performed with varying numbers of workers, showed that the existing implementation of parallel findfirst/3 reaches the result in a fast manner - that is, it is faster than parallel findall/3 35 3.1. METHODOLOGY and the execution time does depend on the number of nodes traversed. The time that parallel findfirst/3 took to find a solution at the rightmost path of the tree was also similar to that of parallel findall/3, as expected. We thus turned our attention to different cases of execution. Because of the SLD resolution, the tree search is performed from left to right. Additionally, as parallel findfirst/3 stops after finding the first match, a Prolog programmer that is interested in improving the performance of a program that makes use of parallel findfirst/3 will try to make sure that whenever a predicate is executed, its first alternative is the least resource-intensive, then the second and so on, generating a skewered tree that is heavier on the right. This problem has been subject to research and there are algorithms that have good performance in this case, such as [MLAP11] and [PA10] but, because they use work stealing rather than work sharing and we want to make few changes to YAP, we didn’t explore these options. To simulate this use case, we changed the benchmark presented above in a way that generates a tree where its right half side is twice as deep as the left half, thus we have an unbalanced tree to search. This is done by adding the following predicate to the benchmark and changing find/2 as shown next: 1find(In,Out):-length(In,Len), unbalancedFind(In, [], Len,Out). 2 3unbalancedFind(ToFind, [], Left,End) :- 4options(First), NextLeft is Left *(1+First)-1, 5find(ToFind, [First], NextLeft,End). Figure 3.2: A predicate that generates an unbalanced search tree. Due to the exponential growth of this algorithm, the difference in size between the left and right half sides of the tree increases quickly, with the right side having the vast majority of the search space. This can be easily observed even with a small example such as the one presented in Figure 3.3. We then performed some tests with this program using YapOr. Once again, searching the leftmost path of the tree, where the lists are composed of zeros only, can not obtain any speedup due to the semantics of Prolog, that require moving left-to-right, top-to-bottom. Queries with a solution on the large, right side of the tree obtained reasonable speedups, considering the large number of nodes that must be searched. Queries on the left side of the tree, however, had small speedups. In particular, CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 36 [] [1] [1, 1] [1, 1, 1] [1, 1, 1, 1][1, 1, 1, 0] [1, 1, 0] [1, 1, 0, 1][1, 1, 0, 0] [1, 0] [1, 0, 1] [1, 0, 1, 1][1, 0, 1, 0] [1, 0, 0] [1, 0, 0, 1][1, 0, 0, 0] [0] [0, 1][0, 0] Figure 3.3: Search tree for a call to find/2 when given a list of length 2. given a list composed of as many zeros as the number of YapOr workers, followed by ones, produces pathological behavior, in that YapOr achieves speedups that are much smaller than expected. For these cases,the speedup reached a maximum of 2 as we increased the number of workers up to the number of cores of the machine, which is 24 in this case. In order to make these cases easier to reproduce, we add a new clause to the lists/1 predicate that generates lists that, given the number of workers and the size of the list, produce the pathological behavior that we expect: 1lists(Pathological,FullLen,Cpus) :- 2Len is FullLen -Cpus,mkList(Cpus,0,Left), 3mkList(Size,1,Right), append(Left,Right,Pathological). Figure 3.4: A clause used to generate lists that produce pathological behaviour. 3.2 Solution Searching In order to improve the performance for queries that produce the pathological behavior we have presented, we must first be able to understand why this behavior occurs. When YapOr executes a program in parallel, each worker gets a work slice. The heuristics used by YapOr try to divide the available work in a way that: •It avoids discarding data that the sender/receiver of work have in common; •The worker that makes a request receives a large slice of work; •Each worker does all the work it has before making another request. 37 3.2. SOLUTION SEARCHING Our experiments show that these heuristics work very well for parallel findall/3 because they spread the workers throughout the work tree, generating a work distribution such as the one presented in Figure 3.6. For simplicity, we assume that moving one from a branch to another, adjacent to it, takes one time unit. Initially, only worker 0 can search the tree. After sharing work with worker 1, the appearance of the tree is that of Figure 3.5. In the next time unit, worker 0 shares work with worker 2 and worker 1 shares work with worker 3, resulting in the distribution of Figure 3.6. This way, if the tree is balanced, each of the workers takes the same time, allowing the Prolog compiler to achieve linear speedups. If the tree is not balanced, the number of times that work has to be shared is relatively small because every time it happens, the amount of work shared is as large as possible. Figure 3.5: YapOr search tree after worker 0 shares work with worker 1. Figure 3.6: Expected YapOr worker distribution, using 4 workers. For the parallel findfirst/3 predicate this strategy can be improved. First of all, because we do not need all the solutions, we should not make the Or-Parallel Engine spread the workers too much. In this case, we should in fact keep them as much to CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 44 The implementation first creates a memory mapped variable is work sharing enabled during the initialization of YapOr that is used to keep track of whether or not work sharing is enabled. Then, once again between steps 1 and 2, every worker except for the first waits for the variable to be true and keeps yielding the processor in order to avoid wasting CPU time. The first worker starts execution as normal. When the variable becomes true, after the first fail/0, the other workers start making work requests. Using this strategy the worker distribution presents the pattern shown in Figure 3.12. Notice that what always happens is that worker 0 fails at the position shown in Figure 3.11. Afterwards, all the workers can start sharing work, leading to the somewhat random positioning of Figure 3.12, where the workers are all close together. Figure 3.11: Worker 0, immediately before failing. Figure 3.12: Expected worker distribution with strategy F1, using 4 workers. Unlike the previous strategies, this strategy deals with a major problem detected early on: workers that start by moving to the right, become lost forever because they are never able to complete the search of the big subtree before the other workers complete the small one. This strategy tries to force every worker to start at the bottom left of the search tree and then move up and to the right as needed, minimizing this problem. 45 3.2. SOLUTION SEARCHING This strategy still has a couple of flaws - one of them is that the waiting time before the process of work sharing starts can be a considerable slice of the total runtime; the other is that the first time that work is shared, each worker might copy a huge amount of memory, because it has none in common with the sender, which might be at a very deep level of the tree. 3.2.7 Strategy F2 - Descend the Tree, Share Less After Failing the First Time This strategy intends to improve upon the previous one by diminishing the amount of work that must be shared overall during the first time each worker receives work. It does not do changes to any additional modules of Yap besides the ones changed by the previous strategy. We first change the is work sharing enabled variable to be an integer instead of a boolean, changing its name in the process to maximum sharing worker. When maximum sharing worker is 0, sharing is disabled. After the first fail/1, the value is set to 1 and worker 1 gets work from worker 0 and then moves to 2/3 of the depth of worker 0, setting maximum sharing worker to 2. Then worker 2 does the same, relative to worker 1 and so on until every worker has work. This strategy produces a different worker distribution from the previous strategy; the expected worker distribution is presented in Figure 3.13. The difference is that the state of Figure 3.11 is reached, the work sharing is done sequentially, with each worker moving up one node, forming the distribution of Figure 3.13. Figure 3.13: Expected worker distribution with strategy F2, using 4 workers. This strategy would considerably decrease the amount of sharing and spread the workers enough to avoid having too many work requests, except that in practice, we observed that this initial work sharing process fails most of the time, delaying CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 46 considerably the initialization of all workers. As discussed in Chapter 4, we can observe that this strategy is unable to improve over the previous one, when implemented in YapOr. 3.2.8 Strategy S - Freeze the Or-Frames, Allowing Voluntary Suspension This strategy makes use of functions of OPTYAP, the Or-Parallel tabling engine of Yap, that are capable of freezing and unfreezing a complete execution sub-branch of the search tree. It should also be the strategy that causes the biggest variations in terms of execution, producing the most nondeterministic behavior of all the strategies presented. We make changes to the Or-Frame data structure and to the get work function. The first change we have done was to add a new field to the Or-Frame, or fr continuation which keeps a pointer to a frozen Or-Frame that is immediately below - or the continuation of - the current Or-Frame. We also slightly altered the suspend branch() and resume suspension frame() functions to freeze and unfreeze the Or-Frames, respectively. Using the doubly-linked list of strategy 3.2.5, we keep track of the order of workers. If the worker that tries to get work is the rightmost, it suspends all frames that are not common to any other worker, essentially creating a linked list of suspended Or-Frames, and asks all workers from the leftmost for work until it gets work or, failing that, resumes execution of the suspended Or-Frames. Assuming that we have the worker distribution presented in Figure 3.14 and that worker 1 suspends work to move to the left, we arrive at the distribution presented in Figure 3.15. Figure 3.14: Expected worker distribution with strategy S, using 4 workers, before suspending work. 47 3.2. SOLUTION SEARCHING Figure 3.15: Expected worker distribution with strategy S, using 4 workers, after suspending work. Although preliminary experiments based on voluntary movement that discards OrFrames presented good performance - when the workers did not discard the Or-Frame with the solution, which could happen because the algorithm was incorrect - we were unable to implement voluntary suspension in practice due to severe runtime errors whenever we attempted to do so. 3.2.9 Summary We presented different strategies that make different decisions regarding how to schedule work. We saw that we may: •Wait a certain amount of time; •Try to always move down the tree; •Move back to be able to move left; •Wait until failing the first time; •Suspend work to move to left. We also saw that we should avoid sharing too little which leads to trampling, or too much because sharing is a slow operation. Additional possibilities are presented in Chapter 5. 48 Experimental Results 4 In this chapter, we present experimental results for the strategies proposed in the previous chapter, showing the speedups that each stategy was able to achieve and how they vary based on the size of the problem we want to address. Our results were obtained using two NUMA machines, which were used independently from each other. Both have the same technical specifications: four six-core AMD Opteron 8425 HE processors, totaling 24 cores, each with a clock speed of 2.1 GHz, with 128 GB RAM and using Fedora Core 20 in 64-bit mode. Since the parallel findfirst/3 predicate is not available for Yap’s sequential version, all the speedups measured with a certain number of workers are relative to running that same version of YapOr with a single worker. We ran tests used the different strategies we presented with different problem sizes. As expected of the exponential benchmark we used, we verified that the execution times doubled when the size of the problem increased by 1. Therefore, for simplicity, we always chose a size that took as close to 200 seconds as possible, when using a single worker, for all the results presented in this section. In the tables we present next, that are accompanied by a graphical representation, there are 4 rows: 1. The execution time using 1 worker; 2. The execution time using the number of workers indicated in the caption; 3. The speedup obtained; 4. The speedup relative to the default YapOr strategy. To measure the speedups, we ran the benchmark presented in Appendix A 12 times for each pair of strategy and problem size and then we discarded the fastest and the 49 CHAPTER 4. EXPERIMENTAL RESULTS 50 slowest runs, presenting the average of the remaining 10 runs. We do not present results for parallel findall/3 because our tests revealed that these strategies do not improve its execution. Strategy: YapOr W B L1 L2 L3 F1 F2 1 worker: 174.142 174.621 174.271 174.923 174.612 175.232 173.965 174.672 4 workers: 96.121 96.138 114.961 96.662 75.284 77.770 92.224 86.589 Speedup: 1.81 1.82 1.52 1.81 2.32 2.25 1.89 2.02 Relative: 1.00 1.01 0.84 1.00 1.28 1.24 1.04 1.12 Table 4.1: Execution times and speedups obtained with 4 workers and problem size 30, for all strategies. 0 0,2 0,4 0,6 0,8 1 1,2 1,4 YapOr W B L1 L2 L3 F1 F2 Figure 4.1: Relative speedups obtained with 4 workers. Looking at table 4.1 we immediately notice that: •Strategy B significantly decreases the speedup comparatively to standard YapOr; •Strategies W and L1 do not produce considerable changes; •Strategies L2 and L3 increase speedups a little bit, where strategy L2 performs better; •Strategies F1 and F2 increase speedups slightly and, out of the two, strategy F2 is better. An interesting observation that is not immediately obvious is that strategies F1 and F2 generally have similar runtimes to YapOr’s strategy but sporadically produce results 51 in about a half of YapOr’s time, that is, they have speedups close to 4. Out of these strategies, strategy F2 appears to have a higher likelihood of producing the solutions with a relatively good speedup. In our tests, the results obtained when using 4 workers are very similar to those obtained for other numbers of workers, in terms of the speedup that is achieved. For brevity the remaining tables only show results for standard YapOr, strategy L2 and strategy F2. Strategy: YapOr L2 F2 1 worker: 203.044 204.957 203.002 8 workers: 102.534 88.121 95.424 Speedup: 1.98 2.33 2.12 Relative: 1.00 1.18 1.07 Table 4.2: Execution times and speedups obtained with 8 workers and problem size 34. 0,9 0,95 1 1,05 1,1 1,15 1,2 YapOr L2 F2 Figure 4.2: Relative speedups obtained with 8 workers. Strategy: YapOr L2 F2 1 worker: 226.521 227.110 227.029 12 workers: 118.145 96.612 112.103 Speedup: 1.92 2.35 2.03 Relative: 1.00 1.22 1.06 Table 4.3: Execution times and speedups obtained with 12 workers and problem size 38. After analyzing these tables side-by-side we can notice a pattern in the execution of YapOr: in general, when using a number a + n of workers and using a list that has b CHAPTER 4. EXPERIMENTAL RESULTS 52 0 0,2 0,4 0,6 0,8 1 1,2 1,4 YapOr L2 F2 Figure 4.3: Relative speedups obtained with 12 workers. Strategy: YapOr L2 F2 1 worker: 250.255 251.978 252.001 16 workers: 126.344 101.563 118.524 Speedup: 1.98 2.48 2.12 Relative: 1.00 1.25 1.08 Table 4.4: Execution times and speedups obtained with 16 workers and problem size 42. 0 0,2 0,4 0,6 0,8 1 1,2 1,4 YapOr L2 F2 Figure 4.4: Relative speedups obtained with 16 workers. + n zeros at the beginning and cones following, the execution takes a similar amount of time to that of aworkers, with a list of bzeros and cones. This is to be expected, assuming that all the nadditional workers take the right side of each of the first n choice points and, as such, reduce the problem to the version without those nworkers and the smaller list. 53 Strategy: YapOr L2 F2 1 worker: 142.813 143.122 144.672 20 workers: 71.324 58.556 66.890 Speedup: 2.00 2.44 2.16 Relative: 1.00 1.22 1.08 Table 4.5: Execution times and speedups obtained with 20 workers and problem size 45. 0 0,2 0,4 0,6 0,8 1 1,2 1,4 YapOr L2 F2 Figure 4.5: Relative speedups obtained with 20 workers. Strategy: YapOr L2 F2 1 worker: 148.312 149.216 150.275 24 workers: 74.142 60.922 70.443 Speedup: 2.00 2.45 2.13 Relative: 1.00 1.23 1.07 Table 4.6: Execution times and speedups obtained with 24 workers and problem size 49. We can also see that, despite our efforts, the speedups do not increase in any considerable manner with the addition of workers, although the speedups tend to stabilize at a speedup of 2, with the standard YapOr strategy. APPENDIX A. BENCHMARKING CODE 60 1#!/bin/bash 2pushd $(dirname $0)2>&1>/dev/null 3DIR=$(pwd) 4 5for VERSION in "yap1" "yap2";do 6cd $DIR/../$VERSION 2>&1>/dev/null 7echo "Size = $2" 8 9TIME1=$(echo "go($1,$2)." | 10 ./yap -l $DIR/bench.pro 2>&1>/dev/null | 11 head -n3 | tail -n1) 12 13 TIMEN=$(echo "go($1,$2)." | 14 ./yap -l $DIR/bench.pro -w $CPUS 2>&1>/dev/null | 15 head -n3 | tail -n1) 16 17 echo $TIME1 18 echo $TIMEN 19 20 if ["$TIMEN"== "0.000" ];then 21 TIMEN="0.001" 22 fi 23 24 TIME1=$(echo "$TIME1"| awk ’{print $6}’) 25 TIMEN=$(echo "$TIMEN"| awk ’{print $6}’) 26 27 echo | awk ’{res=’"$TIME1 /$TIMEN"’; printf "Speedup = %.2f\n", res}’ 28 done; 29 30 popd 2>&1> /dev/null Figure A.2: Calculates the speedup of the parallel execution of A.1. 1#!/bin/bash 2LEFT=$# 3CPUS=$(lscpu | grep "CPU(s):" | awk ’{print $2;}’ | head -n1) 4echo $(hostname)"(1 worker VS" $CPUS "workers):" 5 6while [$LEFT -gt 0];do 7echo 8bash runbench.sh $CPUS $1 9shift 10 LEFT=$(echo "$LEFT -1"| bc) 11 done Figure A.3: A wrapper that calls A.2 for each problem size passed as an argument.