# Tries-Based Parallel Solutions for Generating Perfect Crosswords Grids
## 4 Tries-Based Solutions
### Parallel Implementation
```
procedurePair_Task()(\(L1,L2,Sol\_List,Optimal\_Sol,start\_position\)) if\(L1\) eligible to be placed on \(M3[0,1]\)then  @set the values \(M1[0,1]\), \(M2[0,1]\), \(M3[0,1]\) to correspond to letter \(L1\) else  EXIT if\(L2\) eligible to be placed on \(M3[1,1]\)then  @set the values \(M1[1,1]\), \(M2[1,1]\), \(M3[1,1]\) to correspond to letter \(L2\) else  EXIT @callTries_Crosswords_Seq(\(Sol\_List,Optimal\_Sol,start\_position\))
```

Analysis

The decision to distribute the letters between the processes was based on the fact that we intended to define a parallel algorithm for which the degree of parallelism could be controlled independently on the given word to be placed in the first column. The value of \(M1[0,0]\)._code_ gives, more precisely, the letters that could be placed in the position \(M2[0,1]\), but these are value dependent, and so not appropriate for the MPI process definition. Even if, theoretically, the algorithm allows us to define 26 MPI processes, it is more efficient from the cost point of view to define fewer processes (to decrease the probability of having processes that do not have effective tasks to execute). A good average would be to assign 3-4 letters per process, and also to use a _cyclic distribution_ for assigning letters to processes. The presented solution leads to a multiprocessing parallelisation degree equal to 26, and the hybrid degree of parallelism (through multiprocessing and multiprogramming) is \(26\times 26\). The degree of parallelism could be improved if we consider pairs of letters distributed to the processes instead of simple letters. Using this variant, each process (from \(p\) processes) will receive a list that contains \(676/p\) of pairs of two letters. In this case, a task created by a process will be defined by three letters--the first two are given from a pair distributed to the process and they are used for setting the positions \((0,1)\) and \((1,1)\), and the third is one from the entire alphabet and is supposed to be placed in the position \((2,1)\). This would allow a degree of parallelism bounded by \(676\times 26\). This idea could be generalized to tuples of \(k\) letters, and the obtained degree of parallelism would be bounded by \(26^{k+1}\). So, the number of MPI processes could be increased by defining a more general algorithm that distributes tuples of letters and not just single letters to the processes. The reason for this generalisation is the possible need to engage many more processes in the computation, which is very plausible when using big clusters. ## 5 Analysis and Experiments

In order to evaluate the performance of the proposed solutions, several experiments have been conducted, for both sequential and parallel solutions. For the experiments, a Romanian dictionary with 610767 words was used. The dictionary does not use diacritics. The concrete specification of the initial problem is defined through the following function used for searching the optimal solution:if more than one perfect grid is found, then the one that maximizes the following formula is chosen: \[V=\sum_{i}^{n}V(w_{i}),\] where \(w_{i}\) is a word in a row, and \[V(w_{i})=\sum_{j=1}^{m}code_{ASCII}(c_{i}^{j}),\] with \(c_{i}^{j}\) being the \(j\) letter of the word \(w_{i}\). The experiments were conducted on an HPC cluster--Koty ([[http://hpc.cs.ubbcluj.ro](http://hpc.cs.ubbcluj.ro)]([http://hpc.cs.ubbcluj.ro](http://hpc.cs.ubbcluj.ro)), accessed on 20 November 2021). A node has the following characteristics: two Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60 GHz, each with 10 cores, and 128 GB RAM memory per node. All the cluster nodes are connected using a fast network of 56 Gb/s (Infiniband Mellanox FDR switch SX6512 with 216 ports, 1:1 subscription rate). For the parallel implementation, the tests were conducted using \(P=8\) MPI processes each using \(T=32\) threads, and each process was executed on a different node of the cluster.