## 5 Extending to a Parallel Biased-Randomized Algorithm  
The intrinsic characteristics of biased-randomized algorithms make them a good candidate to be parallelized. They could be utilized in a multi-start framework, which is a sequential and iterative approach. In each iteration of this approach, a different solution is generated [58]. In our paper, multi-start methods are composed of two phases: In the first one, a new solution is generated using the biased-randomized heuristic, and in the second one, the algorithm compares the newly generated solution with the best solution obtained so far to update the latter whenever appropriate. Instead of using this sequential approach, multiple instances of the biased-randomized algorithm can be run in parallel (e.g., each using a different computer thread or core) by assigning a different seed of the pseudo-random number generator to each instance (Figure 3). In parallel programming, these types of methods--where the same code is executed using different input parameters without requiring communication or dependency between the processes--are known as _embarrassingly parallel algorithms_[59]. These algorithms are usually easy to adapt for parallel execution, and they are good candidates to be executed using massively parallel processing architectures [60]. In the context of unmanned aerial vehicles or self-driving vehicles, decisions should be made in short times, e.g., seconds or even in milliseconds. Using a distributed computing architecture--such as cloud platforms--is an unsuitable approach in this context due to the relatively high latencies of the network. Thus, high-performance computing architectures on-chip must be employed. These architectures could be multi-core processors or graphics processing units (GPUs). These processor units consist of hundreds of smaller low-energy cores that are divided into groups, streaming multiprocessors [61]. The architecture enables parallel computation with relative energy efficiency compared to traditional processors. Using modern multi-core processors represents another appropriate approach for running embarrassingly parallel algorithms. Multi-core processors have become very popular in the last years, in part because modern computers contain several processing units or cores in a single chip [62]. Moreover, multi-core processors can execute several threads by core simultaneously (hyper-threading), turning these processors into a valuable and inexpensive  
Figure 3: Executing different instances of biased-randomized algorithm in a parallel way. approach to execute parallel programs. The union of biased-randomized algorithms and parallel architectures makes a perfect combination to obtain high-quality solutions in complex systems scenarios in the order of just a few seconds or even milliseconds. In our approach (Algorithm 1), we have used a Multi-core shared memory programming paradigm. Thus, the algorithm executes asynchronous threads that contain as input parameters an independent instance of the BR-heuristic, a seed (pseudo-random number), and a list (\(solutionList\)). The list is a shared variable by all the threads, and each thread saves the best-found solution in one second using its instance of the BR-Algorithm in this list. After creating and running all the threads, the algorithm waits until all threads are executed. Notice that the algorithm ends its parallel execution at this point, and the shared variable \(solutionList\) contains all the solutions found by all the threads. Then, the program executes its last step sorting the list of solutions by reward and selecting the best solution (\(bestSolution\)).