Tiago Carneiro

Loizos Koutsantonis
email: lkoutsantonis@wings-ict-solutions.eu

Nouredine Melab
email: nouredine.melab@univ-lille.fr

Emmanuel Kieffer

Pascal Bouvry
email: pascal.bouvry@uni.lu

A Local Search for Automatic Parameterization of Distributed Tree Search Algorithms

Keywords: Parallel tree-based search, Combinatorial optimization, Parameter configuration, High-productivity languages, Chapel

Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and timeconsuming when solving instances of NP-Hard problems. Due to their parallel nature, algorithms for this class of complexity have been revisited for different architectures over the years. However, parallelization efforts have always been guided by the performance objective setting aside productivity. Using Chapel's high productivity for the design and implementation of distributed tree search algorithms keeps the programmer from lower-level details, such as communication and load balancing. However, the parameterization of such parallel applications is complex, consisting of several parameters, even if a high-productivity language is used in their conception. This work presents a local searchbased heuristic for automatic parameterization of ChapelBB, a distributed tree search application for solving combinatorial optimization problems written in Chapel. The main objective of the proposed heuristic is to overcome the limitation of manual parameterization, which covers a limited feasible space. The reported results show that the heuristic-based parameterization increases up to 30% the performance of ChapelBB on 2048 cores (4096 threads) solving the N-Queens problem and up to 31% solving instances of the Flow-shop scheduling problem to the optimality.

I. INTRODUCTION

Algorithms for solving combinatorial optimization problems (COPs) can be divided into exact (complete) or approximate methods [START_REF] Blum | Metaheuristics in combinatorial optimization: Overview and conceptual comparison[END_REF]. The exact ones guarantee to return a proven optimal solution for any instance of the problem in a finite amount of time. Among the complete algorithms, the treebased enumerative strategies, such as backtracking and branchand-bound (B&B), are the most widely used methods for solving instances of COPs to optimality [START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF].

Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and time-consuming when solving instances of NP-Hard problems. Due to their parallel nature, algorithms for this class of complexity have been revisited for different architectures over the years [START_REF] Melab | Multi-core versus many-core computing for many-task branch-and-bound applied to big optimization problems[END_REF]. However, parallelization efforts have always been guided by the performance objective setting aside productivity. The study of a feasible high-productivity language for the design and implementation of tree-based search led us to the Chapel language [START_REF] Carneiro | Towards ultrascale branch-and-bound using a high-productivity language[END_REF]. In the context of this work, Chapel stands out. It is a compiled language that allows one to hand-optimize data structures for performance and also provides high-level features for dealing with the irregularity of the solution space, such as iterators, which are responsible for load balancing at both distributed and intra-node levels.

Using Chapel for the design and implementation of distributed tree-search algorithms hides from the programmer perspective details, such as lower-level communication messages, load balancing, metrics reduction and distributed coherency of the incumbent solution. However, the parameterization of such parallel applications is complex, consisting of several parameters, even if a high-productivity language is used in their conception. Usually, the parameterization of the productivityaware tree search is performed manually by using parameters from previous experiments. However, it is difficult to improve these parameters manually, as a misconfiguration might lead to poor parallel performance. Moreover, there are cases where the previous experience comes from different problems or different system architectures, which might result in poor parameterization.

This work presents a local search-based heuristic for automatic parameterization of ChapelBB, a distributed tree search application for solving combinatorial optimization problems written in Chapel. The main objective of the proposed heuristic is to overcome the limitation of hand-based parameterization, which strongly relies on executions on different systems and covers a limited solution space. Results show that the heuristicbased parameterization increases up to 30% the performance of ChapelBB on 2048 cores (4096 threads) solving the N-Queens problem and up to 31% solving instances of the Flowshop scheduling problem to the optimality.

The remainder of this document is structured as follows. Section II brings background information introduces ChapelBB, the productivity-aware tree-based search to be parameterized. In turn, Section III presents the heuristic-based approach for parameterization of ChapelBB. The evaluation of the heuristic-based parameterization is shown in Section IV. Finally, conclusions are outlined in Section V. Task 0

(locale 0) 1-2 1 -2 -3 1 -2 -4 1 -2 -5 1-5 1 -5 -2 1 -5 -3 x 1 -5 -4 1 -2 -3 1 -2 -4 1 -2 -5 1

II. THE PRODUCTIVITY-AWARE DISTRIBUTED TREE-BASED SEARCH

This section introduces ChapelBB, a productivity-aware distributed tree search designed and implemented in Chapel. The application solves permutation-based combinatorial optimization problems to the optimality and implements the master-worker scheme detailed in Section II-B.

A. The Chapel High-productivity Language

Chapel is an open-source parallel programming language designed to improve productivity in high-performance computing. In Chapel, the program is started with a single task, and parallelism is added through data or task-parallel features [START_REF] Chamberlain | Chapel comes of age: Making scalable programming productive[END_REF]. Furthermore, as Chapel belongs to the partitioned global address space (PGAS) languages, the application has a global memory addressing space, and each segment of this space is assigned to a different locale [START_REF] Almasi | PGAS (partitioned global address space) languages[END_REF]. In Chapel, a locale is similar to a MPI process, and a computer node can host one or more locale. Due PGAS, a task can refer to any variable lexically visible, whether this variable is placed on the same locale on which the task is running, or on the memory space of another one. Moreover, indexes of data structures can be globally expressed, even in the case where the implementation of such data structures distributes the indexes across several locales.

Iterators in Chapel: are similar to procedures that can be used to isolate iterations from the loop body. Each value yielded by the iterator corresponds to an iteration of the loop. Chapel provides different parallel and distributed iterators that implement load balancing between computer cores and processes. Related works on distributed tree search show that the iterators provided by Chapel are the key feature to achieve a trade-off between productivity and parallel efficiency [START_REF] Carneiro | Towards ultrascale branch-and-bound using a high-productivity language[END_REF], [START_REF] Carneiro | An incremental parallel PGAS-based tree search algorithm[END_REF]. The complex communication pattern of a distributed master-worker algorithm is encapsulated by the iterators. As a consequence, there is no need for explicitly dealing with work distribution, load balancing, termination criteria, or metrics reduction. 1}, where L is the number of locales on which the application runs. This distribution is performed through an attribution operator, which invokes an implicit bulk transfer.

B. The Master Locale and the Initial Search

ChapelBB (Algorithm 1) starts with task 0 running serially on locale 0. As ChapelBB is an algorithm that follows the master-worker load distribution scheme, it is necessary to generate an initial load which should be kept into the distributed pool of nodes P d . As illustrated in Figure 1, this initial load is generated through a partial search (line 5) referred to as the initial search. The latter is partial as it just evaluates sequentially a small portion of the solution space with the sole objective to generate valid, feasible, and incomplete solutions (subproblems) to be kept into P d .

As one can see in Algorithm 1, task 0 initially receives the size N of the problem and the cutoff depth (lines 1 -2). This work focuses on permutation-based combinatorial problems, for which an N -sized permutation represents a valid and complete solution. Therefore, in the partial search, task 0 implicitly enumerates all feasible and valid incomplete solutions containing cutof f elements of the permutation, keeping them into the pool P (line 3), which is local to task 0. Lines 6 to 8 are responsible for defining the PGAS-based pool of nodes P d . In line 9, P d receives via implicit bulk transfer the nodes of P .

The parallel search takes place in line 10, adding parallelism by using the forall statement along with distributed iterators (DistributedIters), which are responsible for the as-Algorithm 1: The Master-worker scheme. In the master-worker scheme followed by ChapelBB, locale 0 (master) is responsible for generating the pool P d and controlling the search, distributing subproblems for the worker locales according to a distributed iterator. In the intra-node level, each worker locale receives nodes from the master and task 0 generates a local pool (P l ). In turn, subproblems are distributed to tasks according to an intra-node iterator. Figure adapted from [START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF]).

1 N ← get problem( ) 2 cutof f ← get cutof f depth( ) 3 P ← {} N ode
signment of nodes in P d to locales in a master-worker manner (distributed load balancing). There is no need for programming a termination criterion or a reduction of the search metrics. The search finishes when the distributed active set P d is empty, and metrics are reduced by using the reduction intents provided by Chapel (+ reduce).

In the context of this work, iterators can be considered similar to OpenMP schedulers. Finally, both intra-and interlocale levels of parallelism are exploited by using Chapel parallel iterators. For more details about ChapelBB, the interested reader may refer to [START_REF] Carneiro | Towards ultrascale branch-and-bound using a high-productivity language[END_REF], [START_REF] Carneiro | Productivity-aware design and implementation of distributed tree-based search algorithms[END_REF].

C. Aspects of Implementation

So far, two implementations of ChapelBB have been developed. The first one corresponds to a distributed backtracking for enumerating all complete and valid solutions of the N-Queens problem. This latter consists of placing N non-attacking queens on a N × N chessboard, and it is often used as a benchmark for novel tree-based search algorithms [START_REF] Bell | A survey of known results and research areas for n-queens[END_REF]. The N-Queens is a proof-of-concept that motivates further improvements in solving related combinatorial optimization problems. The second implementation is a distributed branch-and-bound (BB) for solving instances of the Flow-shop scheduling problem (FSP), a classical NP-Hard problem, to the optimality. In short, FSP aims at scheduling N jobs on M machines {m 1 , m 2 , . . . , m M } in that order. For more details, refer to [START_REF] Carneiro | Towards ultrascale branch-and-bound using a high-productivity language[END_REF].

The implementation of ChapelBB is openly available at the Chapel-based Optimization repository [START_REF] Carneiro | Chapel-based optimization[END_REF].

III. A LOCAL SEARCH-BASED APPROACH FOR THE PARAMETERIZATION OF CHAPELBB

A. Challenging Issues

In order to maximize parallel performance and efficiency, on each computer ChapelBB is executed, it is required to provide to the application configuration parameters. These parameters are found manually and based on previous experience. It is important to point out that it is required to find good parameters for each system on which ChapelBB runs, as a good parameters configuration for a given cluster might not work for another one. Additionally, a parameters configuration found for c computer nodes on the same system might not be good for a different number of computer nodes. The same goes for multiple problems: each implementation requires a specific parametrization.

Consider the tuple T = (S, c, π, Π), where S is the system on which ChapelBB is executed, c is a system configuration in terms of computer nodes, and π is the instance of the problem Π to be solved to the optimality. This way, the objective is to find a parameters vector P which minimizes the execution time of ChapelBB(T , P). In this context, the challenge is to find a parameters vector P which minimizes the execution time of ChapelBB(T , P) and also presents good performance for another configuration c ′ and another instance π ′ ∈ I, where I is the set of instances of Π used in the experiments.

Before introducing the algorithm to find by hand feasible and valid parameter configuration for ChapelBB, the parame-

B. Parameters

As one can see in Table I, an implementation ChapelBB for solving to optimality instances of the problem Π receives eight parameters for execution, which are divided into three classes that reflect their importance: Critical, Secondary and T ertiary.

The parameters for which a misconfiguration drastically affects the parallel performance and efficiency of the search are classified as Critical. There are three parameters in this class: c 1 -the initial cutoff depth; c 2 -the second cutoff depth, and c 3 -the distributed load balancing scheme. In turn, the Secondary class consists of the chunk size of the distributed and intra-node load balancing schemes -s 1 and s 2 , respectively, and whether to use hyperthreading for improving intranode parallelism -s 3 . Finally, the least critical parameters, which belong to the T ertiary class are the binary variables t 1 and t 2 , which corresponds to the decision of removing the master locale (id 0) from the search process, using it just to coordinate the search, and whether to distribute or not the centralized pool of nodes P d (See Figure 2), which could improve locality. Therefore,

P = [c 1 , c 2 , c 3 , s 1 , s 2 , t 1 , t 2 ].

C. The Manual Algorithm

An initial parameters configuration P is chosen according to previous experience, from results returned from executions of ChapelBB on another system S ′ . Thus, the initial step of the manual algorithm is to execute ChapelBB(T , P) to get its execution time e. Then, we perturb the critical parameters of P, usually one at a time, generating the neighboring vector P ′ to verify whether this perturbation results in execution time improvement. If P ′ leads to a better performance, a perturbation is performed on P ′ , resulting in P ′′ .

If a local optimum is found in the region of the critical parameter, the next step is to explore less critical parameters. However, in the manual algorithm, the search for better secondary and tertiary parameters can be neglected, as a wrong configuration might not degrade considerably the parallel performance and efficiency of ChapelBB. The last step of the manual algorithm is to run experiments on different system configurations and for a reduced set of instances. The parameters configuration which returns the best overall results is then chosen.

D. The Hill-climbing Algorithm

Explicit enumeration of all possible configurations for a given T corresponds to 16, 200 possibilities, and this parameter choice would only be the proven best for T . Based on the manual algorithm, we propose a hill climbing approach for automatic parallelization of ChapelBB. Our objective is not to rely only on previous experience and overcome the limitation of manual parameterization, which neglects the secondary and tertiary parameters.

As it can be observed in Algorithm 2, the hill climber starts with an arbitrary parameters vector P hill and executes ChapelBB(T, P hill ), to get its cost hill cost in terms of execution time. Then, the algorithm performs a local search on P hill , returning the best parameters configuration that can be found in its neighborhood. In case an improvement is found, P and best cost are updated and the local search is called until no further improvement is possible.

E. The Local Search

Due to the huge amount of time required for the search to complete when bad parameters are chosen, the local search does not evaluate a large solutions space, only neighbors with distance one from P hill . For each parameter p of P hill , the search generates the neighboring vectors P lef t and P right . For instance, if c 3 (See Table I) in P hill is dynamic, P lef t has all elements equal to the ones of P hill but c 3 , which is Algorithm 2: A hill climbing algorithm for automatic parameterization of ChapelBB.

Input: The tuple T . Output: A parameters vector P and the cost of ChapelBB(T , P).

F. Aspects of Implementation

As parallelism is added in Chapel, it is possible to call the ChapelBB itself as the cost function of the parameterization heuristic, as shown in both pseudocodes previously presented. Moreover, the heuristic can be used also as an initial parameters generation, so the search can be started without parameters, only receiving T . In the current implementation, the parameterization is only performed for a given tuple T . If the user wants to get a parameter for another system configuration or instance, it is required to start the search receiving a different T .

IV. EVALUATION A. Experimental Protocol

In this evaluation, the hill climbing algorithm detailed in Section III-D is used to find feasible parameters for two implementations of ChapelBB: the first one solves instances of the FSP to the optimality, whereas the second one enumerates all feasible and complete solutions of the N-Queens problem. We compare the results obtained by the hill climber to the ones obtained manually, based on previous executions on another system, which has a different processor architecture and highperformance network.

As pointed out in Section III-C, in the manual parameterization, we run a set of experiments, for a reduced set of instances, on a number of nodes smaller than the one we want to run the final experiments. The reason for such a choice is that a reservation containing several nodes is usually difficult to get. Moreover, good parameters for a high number of computer nodes differ considerably from the parameters for a small number of nodes and single-node execution. In this way, both the manual and the heuristic-based parameterization are performed on 20 computer nodes. Then, we compare the execution times for 32 computer nodes.

In the experiments, N-Queens problems of size (N ) ranging from 17 to 21 are considered. The instance chosen for parameterization is the N-Queens of size N = 19, which can be considered as a big instance. In turn, the FSP benchmark instances used in our experiments are the FSP instances defined by Taillard [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF]. We use 9 instances where M = N = 20. For most instances where M = 5 or 10, the bounding operator gives such good lower bounds that it is possible to solve them in few seconds using a sequential B&B. Instances with M = 20 and N = 50, 100, 200 or 500 are very hard to solve. For example, the resolution of the instance Ta056 (N = 50, M = 20), performed in [START_REF] Mezmaz | A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems[END_REF], lasted 25 days with an average of 328 processors and a cumulative computation time of about 22 years. For the parameterization, the instance chosen is ta28, which, among the 9 selected instances for the experiments, is a medium-sized one.

To compare the performance of two tree-based search algorithms, both should explore the same search space. When an instance is solved twice using a parallel tree search algorithm, the number of explored nodes varies between two resolutions. Therefore, for all FSP instances, the initial upper bound (cost of the best found solution) is set to the optimal value, and the search proves the optimality of this solution. This initialization ensures that precisely the critical sub-tree is explored, i.e., the nodes visited are exactly those nodes which have a lower bound smaller than the optimal solution [START_REF] Karypis | Unstructured tree search on SIMD parallel computers[END_REF].

B. Experimental Testbed

The experiments were executed on the new Aion Cluster, hosted at the University of Luxembourg. All computer nodes are symmetric and operate under Red Hat Enterprise Linux 8.3, 64 bits. The nodes are equipped with two AMD Epyc The number of locales (Chapel processes) is passed to the application using Chapel's built-in command line parameter -nl L, where L is the number of locales on which the application is executed. In these experiments, each computer node hosts one Chapel locale. Both the hill climber and ChapelBB implementations were programmed for Chapel version 1.25.0, and the default task layer (qthreads) is the one employed. Chapel's multi-locale code runs on top of GASNet, and several environment variables should be set with the characteristics of the system the multi-locale code is supposed to run. One can see in Table II a summary of the runtime configurations for multi-locale execution. The Infiniband GASNet implementation is the one used for communication (CHPL_COMM_SUBSTRATE) along with SSH, which is responsible for getting the executables running on different locales (GASNET_PSM_SPAWNER).

C. Experimental Results

One can see in Table III parameters found manually and via the hill climbing heuristic for the N-Queens and the FSP problems. A first detail that is it worth to mention concerns the parameters found by the heuristic for the N-Queens problem. The previous experience shows us that the dynamic distributed load balancing scheme presents the best performance for both the N-Queens and the FSP problems [START_REF] Carneiro | Towards ultrascale branch-and-bound using a high-productivity language[END_REF], [START_REF] Carneiro | Productivity-aware design and implementation of distributed tree-based search algorithms[END_REF]. In turn, on the Aion cluster, which is AMD-based, ChapelBB shows the best performance enumerating the solutions of the N-Queens using guided as the load balancing scheme. For all other scenarios, the best configuration uses the dynamic iterator. It is important to point out the limitation of relying on previous experience without proper evaluation of all classes of parameters. Without using the heuristic, we would continue to use the dynamic iterator instead of exploring other configurations for the load distribution scheme.

For the manual parameters choice, the best initial and secondary cutoff depths found are 4 and 8, respectively. In turn, the use of a heuristic made it possible to find a initial cutoff depth deeper for the N-Queens and a shallower depth for the FSP. A deeper initial cutoff might result in finegrained subproblems, and a shallower depth might result in subproblems with a coarser granularity, which might result in load imbalance. First, sub-tress that would became unfeasible in deeper depths are not pruned yet in the enumeration process. Second, with coarse-grained subproblems, computer nodes might starve more easily, as the pool gets empty while other computer nodes did not finish their enumeration.

For the N-Queens, the size of the centralized pool using the heuristic, for N = 18, is 8.6× bigger than the one using the manual parameters. On the other hand, there is no time spent in distributing the active set as the P GAS flag is set to false. The time is only spent when the master sends tree nodes to other locales. However, in the current implementation of Chapel, this data transfer for the distribution of the active set is residual.

Concerning the parameters in the Tertiary class, for the manual parameterization, it is not worth to make several experiments with the P GAS flag as it did not affect significantly the performance of the application. Only the heuristically chosen parameters for the FSP problem are using the P GAS flag set to true. Furthermore, the heuristic found the same intranode chunk size for both problems -128. The choice of such parameter was not performed manually. The value of 128 is based on previous experience.

Performance Results: One can see in Figure 4 the comparison of ChapelBB's parallel performance configured with the manually and heuristically chosen parameters. Concerning the N-Queens problem, and for the smaller size (N = 17), ChapelBB with the heuristically chosen parameters can be almost twice as slow as its counterpart using the manually chosen parameters. As the solution space grows, it is possible to improve the performance of ChapelBB solving the N-Queens from 24% (N = 19) to 30% (N = 21) on 32 computer nodes (2048 cores). The main reason for this big difference can be explained by primary parameters. Using the deeper initial depth allied to the guided distributed iterator made the search more efficient. Using the dynamic iterator with the handchosen parameters results in load imbalance. For N = 21, the biggest load processed by a locale is 1, 47× higher than the smallest load. In turn, the heuristic-based parameters, which use the guided iterator and a deeper initial depth, show the biggest tree processed by a locale only 5% bigger than the smallest tree.

Finding a good parameters configuration is easier for the N-Queens: a bigger problem keeps the characteristics of the smaller ones. Thus, the results are similar for N > 18. However, when it comes to the FSP, the parameterization is much more difficult, even though the instances belong to the class for which N = M = 20. Each instance has its characteristic in terms of solution space size and irregularity. Despite these challenging issues, ChapelBB configured with the heuristically-chosen parameters shows performance inferior to its manually-configured one only for the instances ta22 (-22%), ta28 (-30%) and ta30 (-33%). It is important to point out that ta22 and ta30 are the smallest instances. This way, this performance difference, which might look big in percent, corresponds to about one second of execution time.

Equivalent performance is observed for both parameteriza- tion strategies for three instances: ta23, ta27 and ta29. By using the heuristic, it is possible to improve the performance of ChapelBB for the three biggest instances ta24, ta25 and ta26 in 31%, 20% and 11%, respectively. As these instances are the biggest, e.g., solving ta24 to the optimality takes 110 seconds on 2048 cores -4096 threads and using the heuristicallychosen parameters, the average execution time of ChapelBB using the heuristically-chosen parameters is 13% lower than its version initialized with the hand-chosen parameters.

V. CONCLUSIONS AND FUTURE RESEARCH DIRECTIONS

This work presented a heuristic-based approach for the parameterization of ChapelBB, a productivity-aware tree-based search for solving combinatorial problems. The proposed heuristic is a hill-climbing approach based on the manual algorithm previously used for the parameterization of ChapelBB. A first concluding remark is to point out the limitation of manual parameterization. For instance, relying on previous experience and performing a poor search for new secondary and tertiary parameters limited the performance of ChapelBB, mainly when solving the N-Queens or bigger FSP instances.

The reported results show that the heuristic-based approach improves the performance of ChapelBB in around 30% for N > 18 solving the N-Queens. Solving instances of the FSP is a more complex scenario. It is valid to mention that both ways of parameterization result in equivalent results for the small and medium cases. In turn, the heuristic-based parameterization is more efficient for the biggest instances, for which improvements result in significant execution time gains. In such a scenario, it was possible to decrease the execution time of ChapelBB from 13% to 31%.

A first improvement to the hill-climbing search implementation is to use a solution found by hand as the initial solution. This way, it would be possible to overcome the main flaw of the hand-made parameterization, which is the limited search of better secondary and tertiary parameters. Finally, ChapelBB also is implemented to harness all GPUs and CPUs of the system altogether. The parameterization of such a scenario is more challenging, as parameters from different architectures need to be taken into account. Therefore, we also consider implementing a version of the hill-climber for the parameterization of this complex scenario.

Fig. 1 .

 1 Fig. 1. Schematic representation of an initial search on locale 0 -task 0 that generates the pool P for a permutation combinatorial problem size N = 4 and cutof f = 3. The figure depicts the branch that has the element 1 of the permutation as the root and generated 4 valid and feasible incomplete solutions at depth cutof f = 3.

Fig. 2 .

 2 Fig.2. The distributed pool P d consists of several sets P i d , i ∈ {0, ..., L -1}, where L is the number of locales on which the application runs. This distribution is performed through an attribution operator, which invokes an implicit bulk transfer.

  4 metrics ← (0, 0) 5 metrics + = initial search(N, cutof f, P ) 6 Size ← {0..(|P | -1)} // Domain 7 D ← Size mapped onto locales to a standard distribution 8 P d ← [D] : N ode 9 P d = P // Using implicit bulk-transfer 10 forall node in P d following a distributed iterator with(+ reduce metrics) do 11 metrics + = Search(N, node, cutof f )

Fig. 3 .

 3 Fig.3. In the master-worker scheme followed by ChapelBB, locale 0 (master) is responsible for generating the pool P d and controlling the search, distributing subproblems for the worker locales according to a distributed iterator. In the intra-node level, each worker locale receives nodes from the master and task 0 generates a local pool (P l ). In turn, subproblems are distributed to tasks according to an intra-node iterator. Figure adapted from[START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF]).

Fig. 4 .

 4 Fig. 4. Relative execution time achieved by ChapelBB configured with the heuristically-chosen parameters compared to its manually configured counterpart (a) enumerating all feasible and valid solutions of the N-Queens problem and (b) solving instances of the FSP to the optimality. The FSP instances are ordered according to their tree sizes. Results are shown for 32 computer nodes -2048 cores (4096 threads).

TABLE I PARAMETERS

 I USED TO CONFIGURE THE DISTRIBUTED SEARCHES AND THE VALUES THEY CAN RECEIVE.

	Parameter	Alias	Description	Possible values
	c1	F irst Cutof f	Initial cutoff depth	3,4,5
	c2	Second Cutof f	Second cutoff depth	6,7,8
	c3	Load balancing	Distributed load balancing	static, dynamic, guided
	s1	Distributed chunk	Distributed load balancing chunk size	1,4,8,16,32
	s2	Intra -node Chunk Intra-node load balancing (dynamic) chunk size	8,16,32,64,128
	s3	Hyperthreading	Use hyper-threading?	true, f alse
	t1	Coordinated	Locale 0 acts only as the coordinator?	true, f alse
	t2	P GAS	PGAS-based active set?	true, f alse
	ters used to configure the distributed search are introduced as
	follows.

  The local search used by the hill climber. The tuple T , the parameters vector P hill , and hill cost. Output: A tuple < P best , search cost >, which corresponds to the best parameters found by the local search and the cost of ChapelBB(T , P best ), search cost. P best , search cost > equals to static. In turn, P right has c 3 equals to guided. The concepts of lef t and right are similar to the next and the previous elements of a circular doubly linked. If the local search finds a cost improvement, the search returns the best parameters vector P best and the cost of ChapelBB(T , P best ), search cost.

	11	best cost ← min(lef t cost, right cost)
	12	if best cost < search cost then
	13	search cost ← best cost
	14	if lef t cost < right cost then
	15	P best ← P lef t
	16	else
	17	P best ← P right
	18	end
	19
	20	end
	21 end
	22 return <
		1 P hill ← get random parameters( )
		2 P ← ∅
		3 best cost ← 0
		4 hill cost ← ChapelBB(T , P hill )
		5 while hill cost < best cost do

6 best cost ← hill cost 7 P ← P hill 8 < P hill , hill cost > ← local search(T , P hill , hill cost) 9 end 10 return < P, hill cost> Algorithm 3: Input: 1 P lef t ← ∅, P right ← ∅ 2 P best ← P hill 3 lef t cost ← 0, right cost ← 0 4 best cost ← 0 5 search cost ← hill cost 6 forall parameter p in P hill do 7 P lef t ← get lef t neighbor(P hill , p) 8 P right ← get right neighbor(P hill , p) 9 lef t cost ← ChapelBB(T , P lef t ) 10 right cost ← ChapelBB(T , P right )

  GHz, a total of 64 cores (128 threads) per node, and 256 GB ram. In the experiments, up to 32 nodes have been reserved, total of 2048 cores, hosting 4096 threads. All computer nodes are interconnected through a InfiniBand (IB) HDR100 network, configured over a Fat-Tree Topology.

	ROME 7H12 @ 2.6
	TABLE II
	SUMMARY OF THE ENVIRONMENT CONFIGURATION FOR MULTI-LOCALE
	EXECUTION AND COMPILATION.
	Variable	Value
	CHPL_RT_NUM_THREADS_PER_LOCALE	128
	CHPL_TARGET_CPU	native
	CHPL_HOST_PLATFORM	linux64
	CHPL_LLVM	none
	CHPL_COMM	gasnet
	CHPL_GASNET_SEGMENT	everything
	CHPL_COMM_SUBSTRATE	ibv
	GASNET_PSM_SPAWNER	ssh

TABLE III PARAMETERS

 III FOUND MANUALLY AND VIA HEURISTIC TO EXECUTE CHAPELBB. THE ORDER OF THE PARAMETERS FOLLOWS TABLE I.

		Parameters
	Heuristic-Queens	(guided, 5, 8, 1, 8, 128, f alse, f alse)
	Manual-Queens	(dynamic, 4, 8, 16, 32, 128, f alse, f alse)
	Heuristic-FSP	(dynamic, 3, 7, 8, 8, 128, true, f alse)
	Manual-FSP	(dynamic, 4, 8, 64, 32, 128, f alse, f alse)

present results(metrics)