Yacine Hakimi
email: y_hakimi@esi.dz

Riyadh Baghdadi
email: baghdadi@nyu.edu

Yacine Challal
email: yacine.challal@udst.edu.qa

A Hybrid Machine Learning Model for Code Optimization

Programming modern heterogeneous systems is becoming increasingly difficult due to their complexity and diversity. As a result, it becomes more difficult for a parallel program to take advantage of all available resources. To achieve high performance on these architectures, developers need to optimize their code to run efficiently on a specific architecture, and this is exceedingly challenging due to the large number of possible optimizations that vary across programs and architectures. Modern compilers attempt to hide this complexity from the developer by using accurate optimization heuristics to optimize code automatically for a diversity of architectures. In the last decade, machine learning has proven to be a game-changer in solving many tasks. While classical machine learning is better when dealing with small data sets, it requires a significant effort to extract useful features from code. On the other hand, deep learning can address this problem by automating the feature extraction process, but it requires a large amount of labeled data, which is scarce in the field of code optimization. We present a novel model for optimizing code that combines classical machine learning and deep learning. It uses deep learning to extract features representing code then it takes these features and uses classical machine learning to map them to a particular output and perform the required task. We evaluate the effectiveness of model on three downstream tasks: device mapping, optimal thread coarsening, and algorithm classification. Our model outperforms all previous models in two tasks (device mapping and optimal thread coarsening) and achieves comparable results in the other task (algorithm classification).The advantages of our model are to get good results only by using a small dataset even without a pre-training phase or complex code representation.

Introduction

The use of heterogeneous systems to perform large-scale computations is becoming an increasingly common practice in both academia and industry [START_REF] Ghazi | Heterogeneous systems testing techniques: An exploratory survey[END_REF], [START_REF] Chen | Lu factorization on heterogeneous systems: an energy-efficient approach towards high performance[END_REF], and [START_REF] Singh | Computing without processors: Heterogeneous systems allow us to target our programming to the appropriate environment[END_REF]. Writing parallel code becomes more challenging when we target such heterogeneous systems which contain different types of hardware accelerators (CPUs, GPUs, etc.) with diverse performance characteristics and behavior.

Many parameters affect the performance of parallel code in a heterogeneous context, ranging from selecting the algorithm and programming model to determining the granularity of parallelism, the communication pattern, scheduling, and mapping strategy. We always have to find the optimal or near-optimal parameters to achieve the better performance gains on a given architecture for a given problem. Some of these parameters may vary between different systems or depend on other parameters, such as input data. To simplify the writing of parallel code in a heterogeneous context and hide the complexity of these architectures, previous research attempted to enable compilers to automatically optimize code and tune the parameters for a given architecture Cummins, Petoumenos, [START_REF] Cummins | End-toend deep learning of optimization heuristics[END_REF]. These compilers automatically decide how the code should be optimized and take decisions such as figuring out whether to map a piece of code (a kernel) to the CPU or GPU [START_REF] Grewe | Portable mapping of data parallel programs to opencl for heterogeneous systems[END_REF], [START_REF] Ashouri | A survey on compiler autotuning using machine learning[END_REF] Ben-Nun, Jakobovits and Hoefler (2018)] and selecting the coarsening factor for a kernel on GPU Cummins et al. (2017), [START_REF] Ben-Nun | Neural code comprehension: A learnable representation of code semantics[END_REF], [START_REF] Magni | Automatic optimization of thread-coarsening for graphics processors[END_REF], VenkataKeerthy, Aggarwal, Jain, Desarkar, [START_REF] Venkatakeerthy | Ir2vec: Llvm ir based scalable program embeddings[END_REF].

Because of the great success of machine learning in recent years, and especially deep learning, machine learning is being increasingly used in compilers and code optimization [START_REF] Cummins | End-toend deep learning of optimization heuristics[END_REF], [START_REF] Ashouri | A survey on compiler autotuning using machine learning[END_REF], [START_REF] Memeti | Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review[END_REF]. Deep learning has previously demonstrated its ability to improve accuracy and solve the problems of feature extraction and selection [START_REF] Cummins | End-toend deep learning of optimization heuristics[END_REF], but it requires large amounts of labeled data which is scarce in the field of compilers and code optimization. Simple models, on the other hand, such as decision trees and SVM, typically require less labeled data than deep learning models, but their performance is heavily influenced by the quality of features. .Generally, a small number of high-quality features is sufficient for these models, but extracting a small number of high-quality features is a nontrivial task.

While feature extraction in traditional machine learning has to be done manually and requires expert developers and domain experts [START_REF] Wang | Machine learning in compiler optimization[END_REF], deep learning has the ability to automatically extract these features from the code, enabling developers to reduce this labor intensive task. Automated feature extraction using deep learning for code has been greatly influenced by Natural Language Processing (NLP) approaches [START_REF] Allamanis | A survey of machine learning for big code and naturalness[END_REF] due to similarities between code and natural language. These approaches, especially pre-trained models such as CodeBERTFeng, Guo, Tang, Duan, [START_REF] Feng | Codebert: A pre-trained model for programming and natural languages[END_REF], have become a feasible way for developers to extract code features and reduce the amount of engineering previously needed. They gave state-of-the-art results in code tasks similar to natural language processing tasks (code completion, code to code translation, code summarization, etc.) [START_REF] Feng | Codebert: A pre-trained model for programming and natural languages[END_REF]. These techniques have also been used in compiler and code optimization [START_REF] Cummins | End-toend deep learning of optimization heuristics[END_REF][START_REF] Ben-Nun | Neural code comprehension: A learnable representation of code semantics[END_REF], however, compiler and code optimization tasks are different from natural language processing tasks and more difficult due to the structural nature of the code and the complexity of interactions between programs and architectures, and the fact that features extracted have to characterize the semantics of the program and its behavior on the target architecture.

We propose a novel approach relying on both traditional machine learning and deep learning to tackle the challenge of code optimization. Our approach is based on the efficiency of the CNN model in extracting high-quality features with a small number of dimensions and the ability of traditional machine learning to deal with small datasets.We use deep learning to extract features representing code to avoid feature engineering and selection then we use these features and classical machine learning to perform the required task relying on the ability of the latter to give good results even with small datasets.

We show that even with a small dataset we can take advantage of deep learning and traditional machine learning together to reach results similar or better than state-of-theart pre-trained models that require a large dataset. Unlike such models, our model requires less training time and less amount of data without a pre-training phase and without the need for a complex code representation. The contributions of this paper can be summarized as follows:

• We propose a new model for code optimization tasks.

This model is a hybrid model that uses deep learning and classical machine learning.

• We evaluate this model on three downstream tasks: device mapping, thread coarsening and algorithm classification.

• The proposed model is the first to match and outperform the performance of state-of-the-art pre-trained models without requiring large amounts of data.

Background

This section outlines the terminology that is used within the paper and provides the necessary background information for the reader about the target research field.

Heterogeneous parallel systems

In general, parallel computing systems can be divided into two main categories based on the type of processors and other resources used by the system. Systems that make use of multiple or many identical processor types are called homogeneous, while systems that make use of multiple or many different processor types are called heterogeneous. Nowadays, parallel computing systems are dominated by heterogeneous systems, which are composed of processors with a variety of different sizes, speeds, and memory types [START_REF] Fang | Parallel programming models for heterogeneous many-cores: a comprehensive survey[END_REF]. The most common systems consist of CPUs combined with specialized processing units or accelerators such as graphics processing units (GPUs) and tensor processing units (TPUs), field programmable gate arrays (FPGAs), etc.

Code and Compiler optimization

Parallel computing systems offer potentially high performance while increasing the difficulty of writing and optimizing programs [START_REF] Czarnul | Survey of methodologies, approaches, and challenges in parallel programming using highperformance computing systems[END_REF]. In heterogeneous parallel systems, the problem becomes more complex due to the variety of the processing units in terms of architectures and characteristics. Developers need to optimize their codes to achieve the desired performance, and this must be done every time the architecture changes, making manual software porting and optimization for diverse parallel architectures impractical.

Since manually optimizing codes for diverse parallel architectures is very expensive, researchers are trying to use compilers for automatic code optimization, and this research problem can be divided into two main categories [START_REF] Ashouri | A survey on compiler autotuning using machine learning[END_REF]:

• optimization selection problem: in this category, the goal is to select from among available optimizations the best one and its parameters for a given parallel architecture. The research problems addressed in this paper fall into this category.

• The phase-ordering problem: the goal is to determine the ideal ordering of optimizations and their parameters, considering their interactions. This type of problems is not within the scope of this paper.

Device mapping problem

The goal here is to enable the compiler to decide on which processing unit a particular piece of code should run. The goal is to maximize performance.

Algorithm classification problem

Programs classification by algorithms is beneficial in software engineering tasks [START_REF] Mou | Convolutional neural networks over tree structures for programming language processing[END_REF]. In the context of code parallelization and optimization, this classification can identify what kind of parallel pattern does the code have and thus the thread communication and the data-sharing behaviors [START_REF] Deniz | Using machine learning techniques to detect parallel patterns of multi-threaded applications[END_REF]. This can be used for optimization decisions.

Thread coarsening problem

Thread coarsening is an optimization where the compiler combines the code instructions of several threads into one.

The coarsening factor is the value that determines how many threads are merged together. This code transformation can improve the performance of a particular parallel program in a specific architecture and can yield to slow down on another one. The goal here is deciding whether to apply this optimization depends on the nature of the code being optimized and on the target hardware architecture.

Related work

Machine learning can be used to predict the optimal output for many optimization problems in compiler and code optimization, and interesting results have been observed [START_REF] Wang | Machine learning in compiler optimization[END_REF]. The main idea behind this approach is to train a model on a training dataset generated by compiling a set of programs with every possible parameter of the target optimization problem and then using the program and the optimal parameter as a tuple of x and y in this dataset. This model could then be used to predict the optimal parameter of the target optimization for a new unseen program. Generally, there are two approaches to using machine learning in code and compiler optimization [START_REF] Wang | Machine learning in compiler optimization[END_REF]:

• Using machine learning as a cost function to evaluate a potential solution provided by other search methods: Many previous work use machine learning to build a cost model to estimate speedup and use another optimization method to search for the optimal solution. For example, in Baghdadi, Merouani, Leghettas, Abdous, Arbaoui, Benatchba and Amarasinghe (2021), the authors use deep learning to predict the speedup of a program after applying a sequence of code transformations and use this model to explore the search space.

• Using machine learning to predict the optimal solution directly: For example, in [START_REF] Wang | Integrating profile-driven parallelism detection and machine-learning-based mapping[END_REF], the authors use a machine learning model to predict the optimal number of threads and the scheduling policy for an OpenMP program.

The past two decades have seen an increase in the use of machine learning in compiler and code optimization and one of the most important questions when building machine learning systems in compiler optimization is how the code should be represented to the model. In other words, which features will be able to characterize the program to make accurate predictions about the target task. We, therefore, categorize the literature depending on how previous research attempted to answer this question.

Hand-engineered features

Traditional machine learning algorithms take as input a set of features manually extracted from the program. The earlier work in this field rely on this approach and traditional machine learning algorithms in their work targeting various compiler and code optimizations such as selecting the most beneficial loop unroll factor using SVM and NN (nearestneighbor) [START_REF] Stephenson | Predicting unroll factors using supervised classification[END_REF], scheduling kernels on CPU/GPU heterogeneous platforms using SVM Wen, Wang and O'boyle (2014), decision trees [START_REF] Grewe | Portable mapping of data parallel programs to opencl for heterogeneous systems[END_REF], determining the optimal work distribution between the CPU and GPU using linear regression Luk, Hong and Qilin, determining the best partitioning strategy of irregular applications using KNN Liu, Zhao, Zhong, Liang and Feng (2013) and streaming applications using NN [START_REF] Wang | Using machine learning to partition streaming programs[END_REF] selecting the best value for the coarsening factor on GPU using ANN Magni et al. (2014), determining whether parallelism is beneficial using SVM [START_REF] Wang | Integrating profile-driven parallelism detection and machine-learning-based mapping[END_REF], and many other problems. A comprehensive survey can be found in [START_REF] Memeti | Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review[END_REF].

The performance of these traditional machine learning techniques is greatly affected by the quality of the features. Extracting high-quality features requires expert intervention and a significant amount of time, and these features are not necessarily efficient in solving other optimization problems even for the same code [START_REF] Wang | Machine learning in compiler optimization[END_REF].

Sequence of tokens

Due to the similarities between source code and natural languages and the tremendous success of deep learning in the NLP, using NLP techniques in compilers and code optimization to solve the feature extraction problem has received significant attention in recent years.

The first work in this direction was by [START_REF] Cummins | End-toend deep learning of optimization heuristics[END_REF], where they tried to automatically extract features from OpenCL source code using an End-to-End Deep Learning model with embedding techniques to learn a distributed representation of the code. Their model, DeepTune, succeeded in obtaining better results than manual feature extraction in traditional machine learning methods in device mapping and thread coarsening problems.

Haj-Ali, Ahmed, Willke, Shao, Asanovic and Stoica (2020) have use deep reinforcement learning (RL) in a system called NeuroVectorizer to predict the optimal parameters of vectorization for a given loop in C and C++. The embedding representation is generated by code2vec [START_REF] Alon | code2vec: Learning distributed representations of code[END_REF], which initially decomposes the code into a set of pathways in the AST (Abstract syntax tree) to learn a representation of each of them and finally aggregate them.

Graph representation

In IR2VEC VenkataKeerthy et al. ( 2020), the authors were the first to propose using knowledge graph embedding (KGE) in code optimization to learn code representation using the TransE model. This representation was suitable for use as an input to the XGboost classifier used to do the classification. The model was evaluated in two tasks (device mapping and thread coarsening), and its results are considered the state-of-the-art (SOTA) in these problems. Relying on Graph neural network (GNN), which has recently become a popular area of research Wu, Pan, Chen, Long, Zhang and Yu (2019) and working on the device mapping and thread coarsening problems.Brauckmann, Goens, Ertel and Castrillon (2020) try to use abstract syntax trees (ASTs) and control data flow graphs (CDFGs) as a code representation instead of code sequence to do the classification. In the same direction, Cummins, Fisches, Ben-Nun, Hoefler and Leather (2020) proposed a graph-based program representation called Program Graphs for Machine Learning (PRO-GRAML) that combines the call graph, control-flow graph, and data-flow graph. The authors evaluated their model on device mapping and algorithm classification tasks, and it is considered the state-of-the-art (SOTA) in the algorithm classification problem.

Our approach

Which model is better is a complex question to answer [START_REF] Wang | Machine learning in compiler optimization[END_REF]. On one hand deep learning provides a way to automatically generate program features, it requires large training data to get accurate results (lack of labeled data is well-known problem in this field). On the other hand, traditional machine learning, provides better results in small datasets, but it relies on the quality of features. Extraction and selection of useful features is the main problem here.

Another question arises, which representation is better? For example, the work in [START_REF] Barchi | Exploration of convolutional neural network models for source code classification[END_REF] showed CNN's ability to get interesting results with sequence of tokens, even better than many models that relied on pre-trained techniques or complex graph representation, using the small dataset of the device mapping problem only.

In this work, we use a deep learning model composed of an embedding layer to learn the representation of code and a CNN layer to extract low-dimension features vector, then we search for the best classical machine learning algorithm to map these features to a particular output to perform the required task.

The previous work are based on features engineering or end-to-end deep learning model and attempt to address the issue of data scarcity by introducing more complex representations or employing pre-trained techniques. On the contrary, in our approach, the goal is to avoid features engineering by using CNN to extract a small number of highquality features while leveraging the power of traditional methods and techniques developed to deal with small data to to address the issue of data scarcity.

Our work shows that even with a very small dataset and without a pre-trained model trained on a large dataset or the use of complex code representation such as graphbased representation, we can outperform with our model the SOTA models in Device mapping and Thread-coarsening problems, and obtain a well comparable result in the algorithm classification problem.

Proposed approach

In this section, we present our model. Figure 1 shows all the steps needed to build our model. The primary input for the model is the intermediate representation of the LLVM compiler (LLVM-IR) like all the recent work, after the preprocessing, a deep learning model (feature extractor) composed of Embedding, CNN, and Max pooling layers is used to extract features from the LLVM-IR code (we can add auxiliary inputs if needed), then these features are used to train any traditional machine learning algorithm on the downstream tasks, detailed architecture of this model can be seen in Figure 2 (C).To build this model we need the three stages shown in Figure 2

Preprocessing

We preprocessed the LLVM-IR code in order to convert it to a vector of numbers, which can be passed as an input to the deep learning model. The preprocessing is done by following these steps: (1) Tokenizing the code; (2) Atomizing the code. An example of the preprocessing stage is illustrated in Figure 3.

Tokenization

Before identifying the elements or the tokens in the sequence of code, we rewrite the code by:

• Removing the empty line, comments, and unnamed metadata starting with (#,!);

• Rewriting data types as a single tokens.(E.g. <4 * float> → 4_float)

• Rewriting align <Alignment> as a single token.(E.g. align 4 → align_4)

• Replacing the vectors, arrays, and constant (float, integer, double) by a placeholder respecting the types. (E.g. 0x3FD3333340000000 → float_constant, 23 → int-constant, <float 1.000000e+01, float 1.000000e+01>→ vector_float_constant);

• Replacing global and local identifiers, variable, and function names by a placeholder.

• Replacing strings in the declaration of a global variables, functions and string constants by a placeholder (E.g. c"Hello World 0A 00", section "foo" ) This Tokenization is similar to that of [START_REF] Barchi | Exploration of convolutional neural network models for source code classification[END_REF] except in rewriting alignment and replacing strings, our goal is to reduce the number of tokens vocabulary used as much as possible.

Atomization

In this step, first, created a dictionary to convert tokens to integers. All code tokens are converted to their integer indexes using this dictionary. Finally, we get a sequence of integers representing each code. c) GlobalMaxpooling1D A maxpooling layer that selects the maximum value of each output of filters. The output of this layer is a vector of size of 64. d) Dense A fully connected layer with two outputs and "Sigmoid" activation to do the classification.

Training a CNN model

CNN model architecture

2) Training: The training was performed for 40 epochs using the Adam optimizer with its default parameters on the training dataset. 1) Feature extractor we built this model using the Embedding and the Conv1D layers from the previous CNN model. This model consists of these two layers in addition to a GlobalMaxpooling1D layer, and a Concatenation layer that used to add the Auxiliary inputs (optionally) to the output, for example, in the device mapping problem, the result is a vector with 66 values (64 from the output of GlobalMaxpooling1D + 2 Auxiliary inputs). This model is not trained, it is only used as a feature extractor, it takes a sequence of integers and auxiliary inputs as input and produced Features vector as output. 2) Auxiliary Inputs the auxiliary inputs added to feature vectors are values used in the previous work in the device mapping problem to augment the source code input. The code optimization depends on many variables, including the hardware.

Training a Machine Learning model

3) Algorithms Once we get a features vector with a small number of dimensions, we can train any Machine Learning algorithm to do the downstream tasks and take advantage of its ability to deal with a small dataset. In this work, we compare 7 ML algorithms, including an Ensemble learning for every three downstream tasks, and compared their results. The algorithms and their parameters are as follows: Xgboost: max depth = 6, learning rate = 0.1, n estimators = 100, n jobs =10; Random forest: max depth = 5, n estimators = 50; SVM:(C=1.0, ker-nel='linear',degree=7,probability=False, gamma= 'auto') AdaBoostGuassianNB, LR: Default parameters; Section IV shows the results of the comparison and discusses them. 4) Ensemble Learning Ensemble learning is one of the most promising techniques to deal with small and imbalanced datasets [START_REF] Dong | A survey on ensemble learning[END_REF]. This technique uses a set of machine learning algorithms to do the classification and then uses their results to do the final classification. Since we can use traditional ML with our feature extractor, we take advantage of this technique. In our work, we use StackingClassifier, where the output of each ML algorithm (classifier) in the ensemble is stacked, and another classifier (Meta-classifier) computes the final prediction from this stack. Our ensemble learning is a set of the best three algorithms for each task as classifiers and a meta-classifier that takes the results of these algorithms and produces the final result.

Evaluations

We experimentally evaluate the performance of our model on three different downstream tasks (device mapping, optimal thread coarsening and algorithm classification), comparing with state-of-the-art models. In this section, we report the results of our experiments. kernels on CPU and GPU with different workgroups size and byte transfer values. These kernels are from different benchmark suites comprising AMD SDK, NPB, NVIDIA SDK, Parboil, PolybenchGpu, Rodinia, and SHOC. Each data point is composed of a kernel converted to LLVM-IR code, the optimal target device CPU or GPU, parameters (workgroup size, byte transfer).Figure 4 shows the distribution of classes in the AMD and NVIDIA datasets.

Training and metrics

To be able to compare our system to previous work, we use the accuracy metric with 10-fold cross-validation. The data is randomly split into 10 sets and we train 10 classifiers changing the subset used as a test set. We first train the CNN model on the train-set, then we build the Feature extractor model by transfer learning, and finally, we train the ML algorithm on the same train-set using the output of the Feature extractor as input. The prediction is done by the model shown in Figure 2 (C) on the test dataset to compute the accuracy and other metrics.

Machine learning algorithms comparison

We compared the accuracy of the 7 ML algorithms, including Ensemble learning. As shown in Table 1, in contrast to the rest, the ensemble technique tree-based algorithms (Xgboost, Random forest, Adaboost) produced better results. And this was expected since we are dealing with a very small dataset. In addition, the goal of extracting appropriate features for traditional machine learning was to take advantage of these techniques. We built our ensemble learning based on these three algorithms, which produced the best accuracy.

Comparison with previous work

First we compare the accuracy of our system with the previous work. Table 2 shows the results of this comparison. Our model produced almost the same accuracy (92.2%) compared to the state-of-the-art model IR2VEC (92.82%) on the AMD dataset while providing better accuracy (91.0% compared to 89.68%) than it on the Nvidia dataset. Our model outperforms the performances of all the rest models for both datasets, despite the use of only the small dataset of device mapping and without trying to add any other information such as control and data flow. Second we compare our system with previous work on other metrics (Precision, Recall, F1 score). Figure 5 and Figure 6 present the confusion matrix of our system on the two datasets AMD and NVIDIA respectively, used to calculate the previously mentioned metrics. The results of our system and previous models for these metrics (Precision, Recall, F1 score) are presented in Table 3 for AMD dataset and Table 4 for NVIDIA dataset. The values used for previous models in these two tables are taken from [START_REF] Cummins | Programl: Graph-based deep learning for program optimization and analysis[END_REF]. Missing values in Table 3 and Table 4refers to models for which literature results are not present (DeepLLVM [START_REF] Barchi | Exploration of convolutional neural network models for source code classification[END_REF] and IR2VEC VenkataKeerthy et al. ( 2020) ). As we can see in both datasets our system outperforms all previous models by all metrics (accuracy, precision, recall, and F1).

We can conclude that our model achieves similar or better results than state-of-the-art models in this task with less training data and without any additional information or pre-training on a large dataset.

Algorithm classification

dataset

For this task, we use the dataset used in previous work [START_REF] Ben-Nun | Neural code comprehension: A learnable representation of code semantics[END_REF], [START_REF] Cummins | Programl: Graph-based deep learning for program optimization and analysis[END_REF]. This dataset is the POJ-104 [START_REF] Mou | Convolutional neural networks over tree structures for programming language processing[END_REF] dataset converted toLLVM-IR representation. This dataset contains 104 program classes and around 500 samples for each class split in 3:1:1 for training, validation, and testing. Data augmentation was applied

Training and metrics

We train our CNN model with the same parameters we used for the device mapping problem, and like the previous experiments, we build the Feature extractor and train the ML algorithms using it. We use the accuracy metric to compare the performance of different ML algorithms and our model with the previous work.

Machine learning algorithms comparison

For this problem, we tested the same seven ML algorithms, including Ensemble Learning (built based on the best three algorithms), in addition to the End-to-End Deep Learning CNN model. Table 5 summarizes the performance of each algorithm. As we can see in the results, the majority of traditional algorithms (feature extractor + ML), even a simple algorithm like logistic regression outperforms the end-to-end deep learning CNN model. And this was not expected in a relatively large dataset like this one. And unlike the device mapping problem, ensemble learning did not provide the best result. On the contrary, its result was worse than End-to-End deep learning. The support vector machine provided the best accuracy in this problem and was better than the ensemble technique tree-based algorithms (Xgboost, Random Forest, Adaboost), and this shows us that each model can fit a specific dataset or problem, and this is subject to experiment.

Comparison with previous work

We compared our model with the state-of-the-art models in this task, TCNN Mou et al. (2016), inst2vec Ben-Nun et al. (2018), and ProGraML Cummins et al. (2020). The results are shown in Table 6. We can see that our model outperforms the first two models and provides a comparable result (95.47%) to the ProGraML (96.67%), although our model is not based on pre-trained techniques like Inst2vec nor complex graph-based code representation that takes into account the control and data flow information like Pro-graML. Another advantage of our model is that even when we use less data for training, it maintains almost the same accuracy, around 95%, even when we're only using 30% of the training data, or about 86 data points per class. In contrast, any reduction in the amount of training data in an end-to-end deep learning CNN model is accompanied by a decrease in accuracy.

Thread coarsening

In the GPU architecture, increasing the work done by merging multiple parallel threads into a single one is called "Thread-coarsening" in the OpenCL language. The thread coarsening factor controls how many threads to merge. To get the best performance for a kernel in a specific architecture, we need to choose the optimal parameter for the thread coarsening factor. The factor that gives a speedup in one architecture can give a slowdown in another architecture for the same kernel.

dataset

• for this task we use the dataset used in Ben-Nun et al.

( (2020), to determine the best coarsening factor for each kernel on each device. each data is composed of kernel converted to LLVM-IR code, GPU device, and the optimal thread coarsening.

Training and metrics

We train our CNN model with the same parameters as the two previous tasks, except for the input size, which we changed to 2048 because the longest kernel in this data set after preprocessing is 2043. We use leave-one-out crossvalidation to evaluate our models, where a model is trained on 16 kernels from 17 for each device and used to predict the We reproduced all previous work and their results for this task to ensure a fair comparison.

Machine learning algorithms comparison

Like in the previous task (algorithm classification), we have compared the End-to-End deep learning CNN model, the seven ML algorithms, and the ensemble learning (built based on the best three algorithms). As we can see in Figure 7, six ML algorithms from seven perform better than the End-to-End Deep Learning and give a speedup (geometric mean across all platforms) as opposed to the End-to-End DL model, which yields an overall slowdown (speed up of around 0.98). In our experiments, the Random Forest algorithm produced the best results for this task with an overall speedup of 1.05. We note again in this task that another different algorithm gives the best result compared to the first two tasks.

Comparison with previous work

When compared to the other models, we can see in Figure 8 2017) and GNN- AST Brauckmann et al. (2020), yielded an overall slowdown. Figure 9 shows the speedups obtained by all models (geometric mean overall executions) for each platform. As we can see on AMD Radeon, IR2vec obtained a speedup of 1.16x compared to the 1.15 obtained by our model, and this is the only platform where we don't get the best result. GNN-AST and Inst2vec achieved a speedup of 1.06x and 1.04x, while the other models yielded a slowdown. On AMD Tahiti, we achieved a speedup of 1.05 compared to 1.02x and 1.01x that achieved by GNN-AST and Inst2vec, respectively, while the other models result in a slowdown, including IR2vec. On the Nvidia GTX, we are the only ones who get a speedup (1.03x), in contrast to all other models that yielded a slowdown. On NVIDIA Tesla, we achieved a speedup of 1.03x the same get by IR2vec. Inst2vec achieved a speedup of 1.02x, and all other models yielded a slowdown. In summary, for this task, we outperform the state-of-theart models when we aggregate overall executions on all platforms. For each platform, we obtain the best result on 2 of the 4 and match the state-of-the-art IR2vec on another one. IR2vec achieved the best result compared to our model by a difference of 0.01 on one platform. In addition, We are the first ones to achieve a positive speedup on all 4 platforms.

Conclusion and future work

We present a new model for code and compiler optimization problems, which provides better performance compared to state-of-the-art models in two tasks (device mapping and thread coarsening) and provides a comparable result on the algorithm classification task. Our approach outperforms the pre-trained models and models that use a complex graphbased code representation only with small datasets and a simple embedding representation by using the advantages of deep learning and traditional machine learning together. We used a deep learning CNN-based model to build a Features extractor by transfer learning. The features extracted are suitable for use by traditional machine learning algorithms, which allowed us to take advantage of known techniques to deal with the problem of small datasets like ensemble learning and search for the best algorithm for each task. Evaluating the performance of this model on other code optimization problems or even on similar-NLP code classification tasks will be considered in future work. Another direction could be improving the Features extractor to achieve better features and performance.

  Inst2vec Ben-Nun et al. (2018) used the skip-gram model to train an embedding layer analyzing the ConteXtual Flow Graph (XFG) to add more information to the distributed representation. This pre-trained model has shown generally interesting results on device mapping, thread coarsening, and algorithm classification tasks. Using LLVM IR, the intermediate representation (IR) of the LLVM compiler (Low-Level Virtual Machine compiler) Lattner and Adve (2004) instead of OpenCL code, Barchi, Urgese, Macii and Acquaviva (2019) have taken the advantage of the characteristics of this representation to improve the accuracy in the device mapping problem. Barchi, Parisi, Urgese, Ficarra and Acquaviva (2021) introduced the use of Convolutional Neural Network (CNNs) instead of Recurrent Neural Network (RNNs).

  : A) Preprocessing of the LLVM-IR code; B) Training a CNN model; C) Training a ML model using the feature extractor built based on the embedding and CNN layers from the CNN model.

Figure 1 :Figure 2 :

 12 Figure 1: Build_Predictive_Model: Algorithm showing all steps to build our model.

Figure 2 (

 2 Figure 2 (B) shows the architecture of our CNN model used in this stage, we use the same architecture of language model in[START_REF] Barchi | Exploration of convolutional neural network models for source code classification[END_REF].

  This model consists of four layers: a) Embedding layer An embedding layer that takes a sequence of integers as input and learn a useful distributed representation of it by translating each integer (index of token) into a vector in the distributed representation. We use an Embedding size = 64 and we choose an input size = 4096 in device mapping and algorithm classification problems and 512 in thread coarsening problem. b) One-dimensional convolutional neural network A CNN that takes the distributed representation as input and apply 1D convolution over it using several filters. Each filter has a kernel size that defines the number of tokens to consider as the convolution passed across the input. We use 64 filters with kernel size = 32 and LeakyReLU as an activation function..

Figure 3 :

 3 Figure 3: Example of transformation of an intermediate representation to a sequence of numbers.

Figure 2 (

 2 Figure 2 (C) shows the architecture of our classifier, we build another CNN model as a Feature extractor with the transfer learning technique, the output of this model concatenated with auxiliary inputs (optionally) is used as inputs to train a ML algorithm.

•Figure 4 :

 4 Figure 4: Classes distribution in the AMD and NVIDIA datasets.

Figure 5 :

 5 Figure 5: The confusion matrix on the AMD dataset (device mapping problem using the Ensemble learning).

Figure 6 :

 6 Figure 6: The confusion matrix on the NVIDIA dataset.(device mapping problem using the Ensemble learning)

  ) and VenkataKeerthy et al. (2020), this dataset is the dataset used in the previous work on the thread coarsening problem including Cummins et al. (2017) converted from OpenCL code to LLVM-IR code. • The dataset is composed of 68 data points obtained by executing 17 OpenCL kernels (taken from AMD SDK, NVIDIA SDK, and Parboil benchmarks suites) on 4 different GPU devices AMD Radeon 5900, AMD Tahiti 7970, NVIDIA GTX 480, and NVIDIA Tesla K20c, with all the 6 classes of possible coarsening factors Cummins et al. (2017), Wen et al. (2014), Cummins et al. (2020), Feng et al. (2020) Dong et al.

Figure 7 :

 7 Figure 7: Speedups (geometric mean across all platforms) comparison between different ML algorithms(Thread coarsening)

  that our model (features extractor + random forest) obtained the best speedup of 1.05x (geometric mean overall executions on all platforms) compared to 1.02x obtained by IR2vec VenkataKeerthy et al. (2020) and 1.01x obtained by Inst2vec Ben-Nun et al. (2018). The other models, Magni et al. (2014) and DeepTune Cummins et al. (

Figure 8 :

 8 Figure 8: Speedup (geometric mean overall platforms) compared to state-of-the-art models (Thread coarsening)

Figure 9 :

 9 Figure 9: Speedup (geometric mean for each platforms) compared to state-of-the-art models (Thread coarsening)

Table 1

 1 Comparison of ML algorithms accuracy using the Feature extractor(Device mapping) Comparison of the accuracy with the state-of-the-art models(Device mapping)

	dataset	XG boost Random forest Ada Boost	Algorithm SVM	Gaussian NB	Logistic Regression	Ensemble Learning
	AMD Tahiti	90.58%	89.53%	89.83%	70.85%	64.12%	40.95%	92.2%
	Nvidia	88.19%	82.81%	85.20%	58.59%	53.36%	57.24%	91.0%
	Average	89.38%	86.17%	87.51%	64.72%	58.74%	49.10%	91.6%
	Table 2
	dataset	Model Grewe et al. DeepTune Inst2vec (NCC) ProGraML DeepLLVM IR2VEC Our System
	AMD Tahiti	73.38%	83.67%	82.79%	86.6%	85.60%	92.82%	92.2%
	Nvidia	72.94%	80.29%	81.76%	80.0%	85.32%	89.68%	91.0%
	Average	73.16%	81.98%	82.27%	83.3%	85.46%	91.25%	91.6%

Table 3

 3 Comparison of Precision,Recall,and F1 score, with the stateof-the-art models(Device mapping problem on AMD dataset).

	Metrics
		Precision Recall	F1
	Models
	DeepTune	0.72	0.72	0.72
	Inst2vec (NCC)	0.81	0.80	0.80
	ProGraML	0.89	0.87	0.88
	DeepLLVM	-	-	-
	IR2VEC	-	-	-
	Our System	0,92	0,88	0,90

Table 4

 4 Comparison of Precision,Recall,and F1 score, with the state-ofthe-art models(Device mapping problem on NVIDIA dataset).

	Metrics
		Precision Recall	F1
	Models
	DeepTune	0.69	0.61	0.65
	Inst2vec (NCC)	0.79	0.79	0.79
	ProGraML	0.81	0.80	0.80
	DeepLLVM	-	-	-
	IR2VEC	-	-	-
	Our System	0,90	0,93	0,92

Table 5

 5 Comparison of ML algorithms accuracy using the Feature extractor (Algorithm classification)

	Metric	Algorithms	End to End DL	XG boost	Random forest		Ada Boost	SVM		Gaussian NB	Logistic Regression	Ensemble Learning
		Accuracy		93.32% 93.92%	90.69%	93.61% 95.47%	86.92%	93.89%	92.27%
	Table 6
	Comparison of the accuracy with the state-of-the-art models (Algorithm classification)
		Metric	Models TBCNN NCC (inst2vec)	ProGraML GGN	ProGraML Transformer	Our model
		Accuracy	94.00 %	94.83%		96.32%	96.67%	95.47 %
	by the authors of Ben-Nun et al. (2018) on the training set,
	by compiling each program with different flags. The dataset
	(after the data augmentation) is composed of around 220K
	training data and around 10k data for each validation and test
	data.


Sarra Khaber

Ryma Boussaha
email: rboussaha@esi.dz

Yacine Challal
email: yacine.challal@udst.edu.qa

Service orchestration in Autonomous Vehicle Networks: Leveraging Vehicular Fog and Edge Computing

Keywords: Autonomous vehicles, Intelligent Transportation Systems, Edge computing, Vehicular for computing, QoS

The presence of connected and autonomous vehicles is transforming the transportation landscape, improving safety, efficiency, accessibility, and sustainability. However, the disparity between the computational capabilities of autonomous vehicles and their embedded computations requires offloading computation tasks. To address this issue, RoadSide Units (RSUs) have been introduced, bringing computing units closer to the vehicles. By performing real-time computation tasks at the network edge, RSUs enable faster decision-making and reduce reliance on remote cloud servers. Another solution that enhances the capabilities of smart transportation systems is the collaboration of neighboring vehicles within the framework of vehicular fog computing. However, existing research in task placement for vehicular networks often overlooks the quality of service (QoS) in terms of vehicle-service connectivity, focusing primarily on load balancing and latency reduction. To tackle this problem, our work proposes a task orchestration solution that leverages vehicle mobility factors to strike a balance between minimizing latency and improving QoS. The objective is to minimize disconnection and avoid waiting times for service relocation. We evaluated the effectiveness of our proposed solution through a comparative evaluation, which demonstrated that our approach offers the best tradeoff between average service latency and QoS improvement in terms of vehicle connectivity. These results indicate that our solution effectively enhances both performance and reliability.

I. INTRODUCTION

In recent years, there has been significant research and development in the field of smart cities transportation and Connected Autonomous Vehicles (CAV). These areas aim to leverage advanced technologies and data-driven approaches to enhance transportation systems, improve efficiency, and promote sustainable urban mobility. However, autonomous vehicles rely on sophisticated algorithms and real-time processing of various sensor data to perceive their environment and to make decisions. The complexity and volume of these computations can be significant, especially in highly autonomous vehicles that operate in complex and dynamic environments. Various solutions have been proposed to offload certain computational tasks to external servers. Two such emerging solutions are edge computing and vehicular fog computing. Edge computing involves deploying computing resources, such as Roadside Units (RSUs), closer to the users or at the network edge. These RSUs provide computational power, storage, and communication capabilities and minimizes the required bandwidth for communication with cloud servers. Vehicular fog computing, on the other hand, leverages the computing units within vehicles in close proximity to collaborate and execute services in a distributed manner. While load balancing and minimizing latency are typically prioritized, the Quality of Service (QoS) aspect, particularly the number of connection cuts when a vehicle leaves the range of a node hosting its service, is often overlooked. In [START_REF] Sami | Vehicular-OBUs-As-On-Demand-Fogs: Resource and Context Aware Deployment of Containerized Micro-Services[END_REF], the authors propose a framework for deploying containerized micro-services in a vehicular context, referred to as Vehicular-OBus-as-on-DemandFOGs (VODFs). They propose leveraging the concept of Fog Computing, where resources are distributed at the edge of the network, to enable efficient and dynamic deployment of containerized micro-services. They compare their solution with existing deployment approaches and demonstrate its superiority in terms of resource utilization, latency reduction, and adaptability to changing conditions. In [START_REF] Lee | Resource Allocation for Vehicular Fog Computing Using Reinforcement Learning Combined With Heuristic Information[END_REF], the authors propose a resource allocation approach for vehicular fog computing that combines reinforcement learning with heuristic method. The authors formulate the resource allocation problem as a Markov decision process and employ the Q-learning algorithm to train a reinforcement learning agent. Through simulations, the proposed approach is shown to outperform existing schemes by achieving improved resource allocation efficiency. The study conducted by [START_REF] Daoud | Communication-wise Comparison of the Online Resource Allocation Methods in CAV Fleets[END_REF] explores the comparison of online resource allocation methods in connected and autonomous vehicle (CAV) fleets. The research examines different approaches such as centralized, decentralized, auctionbased, and reinforcement learning methods, focusing on their communication aspects. The study provides insights into the advantages and challenges of each method, considering factors like efficiency, scalability, resilience, and the communication infrastructure available.

In fact, the mobility of a node, especially in a dynamic network, is inherently stochastic and not perfectly predictable in advance. However, there are certain factors that can help facilitate the prediction of node mobility, including: the current position of the vehicle, the destination of the vehicle, the routes that the vehicle will take, the Vehicle speed and acceleration. Most of existing solutions misuse vehicles mobility information in the process of resource allocation and services location. In this work, we address this problem and we aim to improve existing solutions. We propose en effective solution of placing tasks in vehicular fog and edge computing networks while minimizing service latency and improving vehicle connectivity. Our proposal involves a multi-objective optimization model and a service orchestration algorithm, that considers different factors related to vehicle mobility in order to enhance the quality of service. Additionally, our solution addresses potential interruptions and constraints such as connection cuts and latency violations. We conducted tests and we made comparison against a position-based heuristic, and an edgeonly approach. The results demonstrated that our solution achieved the best tradeoff between minimizing average service latency and improving QoS in terms of vehicle connectivity with its service.

The remainder of this paper is organized as follows. In Section 2, we describe the vehicular fog and edge computing based solution for task orchestration that we propose. In Section 3, we present performance evaluation as well as experiments of our proposed scheme. Finally, conclusions are made in Section 4.

II. SERVICE ORCHESTRATION IN VEHICULAR FOG AND

EDGE COMPUTING BASED CAV NETWORK Our solution enables vehicles to request hardware resources from neighboring vehicles when their local resources are insufficient for hosting a service. Neighboring vehicles are grouped into clusters, each managed by a master vehicle responsible for orchestrating services within the cluster. The master vehicle considers factors like vehicle mobility (speed, destination, position) to select the most suitable node within the cluster for each service request. If no neighboring vehicle can meet the request, the vehicle in need will request the closest edge server to deploy the service. This approach optimizes resource allocation by leveraging proximity and mobility, utilizing peerto-peer sharing within clusters, and resorting to edge servers when local resources are insufficient.

A. Network architecture

Our solution seeks to optimize the use of hardware resources in vehicular networks to effectively meet the vehicles service requirements. Our architecture consists of three layers, as depicted in figure 1. The Vehicular Fog Layer consists of vehicles that can act as resource requesters or hosts, providing their available resources to other vehicles in exchange for privileges, such as reduced motorway toll rates. Communication within this layer is facilitated through wireless connections of ad hoc nature, using technologies like DSCR. The main role of the Edge Server Layer is to provide virtual resources for hosting vehicle services. These edge servers possess a much larger pool of physical resources compared to the resources available at the vehicle's edge, known as the On-Board Unit. The primary function of the Access Points/Base Stations Layer is to facilitate the establishment of connectivity between vehicles and edge servers. Vehicles within the coverage range of an access point are linked to it using WiFi or LTE connections. Furthermore, the access points are interconnected with the edge servers through wired connections. The access points themselves are interconnected via highly reliable and fast network to ensure seamless communication within the network.

B. Clustered vehicle organization

The vehicular Fog consists of clusters, which are groups of neighboring vehicles communicating through V2V connections. Each cluster within the vehicular Fog includes two distinct types of vehicles.

1) Master: The master, also referred to as the cluster orchestrator, undertakes the following set of tasks:

• Receive service accommodation requests (requests) from seeking vehicles. • Gather information from other vehicles within its cluster.

• Identify the most suitable node within the cluster to host the service for each requesting vehicle. • Allocate and reserve the requested resources in the selected vehicle. • Notify the requesting vehicle of the decision made by transmitting the required information for establishing communication, such as the IP address of the hosting vehicle. Two methods are employed for selecting the master vehicle within a cluster. The first method involves choosing the vehicle with the highest available resources, considering the resourceintensive nature of tasks performed by the master vehicle. The second method involves selecting the vehicle that tends to be centrally located within the cluster over time, which facilitates communication with other vehicles.

2) Worker: A vehicle within the cluster can act as a requester, a host, or fulfill both roles simultaneously. When a worker vehicle requires additional resources to perform its service, it sends a request to the cluster's master and awaits a response from the host vehicle, containing the necessary information to establish a connection. When a vehicle needs to perform a computer vision service, it starts by formulating a request containing all the necessary information to host the service. This information typically includes the model reference used for image processing, the maximum acceptable latency, and the expected service duration. Additionally, it is vital for the vehicle to provide the average CPU and memory usage rates for the service.

C. Multi-objective optimization model

Consider vehicle v i as the requester of service s, and let C be the cluster (if available) such that v i ∈ C. We define a host H as a node satisfying H ∈ (C -{v i , v m } ∪ E S ), where v m represents another vehicle in the cluster and E S represents the edge servers. Lat H,i,s represents the average latency of service s for v i when it is executed on host H. Disc H,i,s represents the probability of a connection being interrupted between v i and H, which may occur before v i reaches its destination or no longer requires the service s. The parameters and their corresponding definitions are summarized in Table I. Our problem can be formulated as follows:

min Lat H,i,s (1)
min Disc H,i,s subject to (2)

Lat H,i,s < trl s (3) dem cpu s < avail cpu H,t < max cpu H t ∈ T (4) dem mem s < avail mem H,t < max mem H t ∈ T (5)
The optimal host selection must carefully balance the objectives of minimizing latency, minimizing the occurrence of connection disruptions, and ensuring an adequate allocation of CPU and memory resources. Furthermore, it is essential for the chosen host to meet the maximum acceptable latency requirement for the given service. To address this problem, we propose an iterative process that incorporates both proactive and reactive measures in response to connection disruptions between the requesting vehicle and its host. The proactive aspect involves selecting a node to host the service during orchestration that minimizes connection outages. Meanwhile, reactive mechanisms are employed to handle such disruptions when they occur.

D. Service orchestration

Upon receiving a request from a requesting vehicle, the master vehicle must determine the relevance of each worker vehicle to the request, based on multiple criteria. To do so, it must calculate a score for each candidate and select the candidate with the highest score. If a vehicle does not possess the requested amount of CPU and memory, it is removed from the list of potential vehicles, and the master vehicle does not compute its score. The master vehicle determines the score for each vehicle by considering the mobility factors of the worker vehicles in relation to the requesting vehicle, which are : the vehicle's destination, speed and position. In order to minimize the loss of connection between the requesting vehicle and its service, it is essential to consider the destination of each candidate. The speed of the vehicle is also a factor in optimizing communication duration and reducing connection disruptions. If the selected vehicle is considerably slower or faster than the requesting vehicle, they will quickly diverge from each other, even if they are following the same route. Moreover, the vehicle's position is considered in order to minimize latency.

1) Score Calculation: Let v i and v j ∈ C represent the requesting vehicle and a candidate vehicle, respectively. The score of v j at time t is determined by the following formula:

score(v j , t) = α 1 .φ 1 + α 2 .φ 2 + α 3 .φ 3 (6)
Such that :

φ 1 = 1 D(desi,desj ) , φ 2 =
1 D(p vi,t,p vj,t) and φ 3 = 1 |si,t-sj,t| α 1 denotes the weight assigned to the destination parameter (0 ≤ α 1 ≤ 1). α 2 denotes the weight assigned to the position parameter, (0 ≤ α 2 ≤ 1). α 3 denotes the weight assigned to the speed parameter, (0 ≤ α 3 ≤ 1).

We define φ1 as follows :

φ1 = 1 D(desi,desj ) if D(des i , des j ) > 1m 1 otherwise (7)
The same procedure applies to the speed parameter, as it is possible for multiple vehicles to be traveling at the same speed. Therefore, we define the following value:

φ3 = 1 |si,t-sj,t| if |s i,t -s j,t | > 0.5m 2 otherwise (8)
The modification does not apply to the position parameter because the distance between any two vehicles at any given moment cannot reach zero. Therefore, the new formula for the score is as follows:

score(v j , t) = α 1 . φ1 + α 2 .φ 2 + α 3 . φ3 (9)
In our final step, we made the decision to incorporate the service usage time into our score calculation. When the requesting vehicle is expected to utilize the service for a brief period (such as a few minutes or seconds), the influence of the destination parameter on the score calculation should be reduced. In such a short time span, the probability of connection dropout is minimal, so the focus should be on latency and ensuring that the distance between vehicles does not increase over time. If, by the end of the service usage time, the vehicle v i reaches its destination, then the score is calculated using equation (9). We define the remaining time for vehicle v i to reach its destination from the current moment t as res i,t . Therefore, the final formula for the score is: 9) otherwise (10) The cluster master executes Algorithm 1 each time it receives a request from a vehicle. The master processes each request individually without directly affecting the orchestration of other requests. Indeed, the arrival of requests from vehicles is not deterministic. There is no guarantee that all requests will arrive at the cluster master simultaneously, and it is crucial that any request received by the master is processed promptly. There is no time for waiting, as computer vision services are highly critical and time-sensitive.

score(v j , t) =    α 1 . tus resi,t . φ1 + α 2 .[1 -tus resi,t ].φ 2 + α 3 . φ3 if tu s ̸ = res i,t equation(
The initial step of the algorithm executed by the master upon receiving a request is to gather the "dynamic" information of the workers and combine it with the existing "static" information in the set V . The resulting data is stored in a matrix called list vehicle. Subsequently, list vehicle is filtered to retain only the vehicles that possess available computing capacities greater than the requested ones, which are identified as the candidates. There are three possible scenarios: if there are no candidates in the cluster, the master informs the requesting vehicle by returning "NULL"; if there is only one candidate, the master directly reserves the requested resources in that vehicle; if there are multiple candidates, we proceed with the following steps:

• The master calculates the score of each candidate using formula (9). • The master sorts the list of candidates, in descending order based on the candidates' scores. • The master chooses the first two candidate vehicles from the sorted list, Ranked, and if the requested image is present in the second vehicle but not in the first vehicle, and the scores of the vehicles are close enough, their order is reversed. • The master sends a resource reservation message to the selected vehicle (the first one in the sorted list), and in return, it receives the port number associated with the service. • The master then provides the requesting vehicle with the IP address of the chosen vehicle and the corresponding port number. These two pieces of information are all that the requesting vehicle needs to establish communication with its service. if Ranked [START_REF] Sami | Vehicular-OBUs-As-On-Demand-Fogs: Resource and Context Aware Deployment of Containerized Micro-Services[END_REF] does not have the image of the service and Ranked [START_REF] Lee | Resource Allocation for Vehicular Fog Computing Using Reinforcement Learning Combined With Heuristic Information[END_REF] has the image of the service and (score 1score 2 < β) then 12:

Algorithm 1 Orchestration algorithm within the cluster

Input: V = {(v i , max cpu i , max mam i , des i )/v i ∈ C vi ̸ = v m } 1: β ← 0
Swap the positions of Ranked [START_REF] Sami | Vehicular-OBUs-As-On-Demand-Fogs: Resource and Context Aware Deployment of Containerized Micro-Services[END_REF] and Ranked [START_REF] Lee | Resource Allocation for Vehicular Fog Computing Using Reinforcement Learning Combined With Heuristic Information[END_REF];

III. EVALUATION RESULTS

The architecture described in this work was implemented using the integration of Containernet1 and Mininet-WiFi2 to model the vehicles (and edge servers), and the "AP" class of Mininet-WiFi to model the access points.

Since our solution combines service orchestration at the cluster level and edge solicitation, we compared our solution with two baseline methods.

• Edge-only: In this solution, the neighboring vehicles cannot host the service requested by the vehicle and the only option is the edge [START_REF] Sami | Vehicular-OBUs-As-On-Demand-Fogs: Resource and Context Aware Deployment of Containerized Micro-Services[END_REF]. • First-Fit: The problem of service orchestration or resource allocation is often reduced to the Bin-Packing problem. By analogy, the objects and their volumes represent the services and their demands, respectively. The bins and their capacities represent the nodes (vehicles in a cluster) and their hardware capabilities, respectively [START_REF] Sami | Vehicular-OBUs-As-On-Demand-Fogs: Resource and Context Aware Deployment of Containerized Micro-Services[END_REF].

A. Evluation metrics

We evaluate our solution based on two metrics:

• Latency: As a first step, we calculate the average latency of each requesting vehicle's service from the beginning In this work, we adopted a microservice for high-level image processing: h2non/imaginary. In order to use the service, it is necessary to perform a profiling step to determine the resource requirements, including CPU and RAM. Several tests were carried out on a container named "imaginary" with a maximum CPU allocation of one core and a memory limit of 500MB. The results of these tests are summarized in the table II.

In order to ensure unbiased testing, we decided to randomly generate the hardware resources for the vehicles. The generation process follows a uniform distribution. In the initial step, we generated a random list of 'fit' and 'blur' tasks permuting them. Next, we assigned CPU and memory demands to each task in the generated list. To introduce variability while aligning with the results obtained in the profiling phase, we utilized the normal distribution to generate the demands for each task. To simulate the arrival of requests, we use a Poisson process. In a Poisson process, the time between two consecutive requests follows an exponential distribution with parameter λ [START_REF] Ross | Stochastic processes[END_REF], which represents the average number of requests per unit of time. In our experiments, we set λ = 10 req/min to test our system's response to a high load (frequent arrival of requests) [START_REF] Lin | Resource Allocation in Vehicular Cloud Computing Systems With Heterogeneous Vehicles and Roadside Units[END_REF], [START_REF] Zheng | An SMDP-Based Resource Allocation in Vehicular Cloud Computing Systems[END_REF]. The reason for selecting the Toccoa map in Georgia, United States was its complexity. As depicted in the figure 2, the map highlights the chosen source and destination points. To maximize the range of scenarios, we

B. Empirical study

The scoring function relies on the weights α 1 , α 2 , and α 3 , which determine the importance of each component (destination, current position, velocity). We selected 13 different combinations to represent a wide range of scenarios. Additionally, we chose a scenario with a cluster of 8 vehicles and 6 requesting vehicles. For each combination, we conducted multiple test runs and obtained the average results for latency and connection disruption. The summarized results are presented in the table IV.

The number of connection disruptions has an inverse relationship with the first weight (associated with the destination). This can be observed in combinations [START_REF] Sami | Vehicular-OBUs-As-On-Demand-Fogs: Resource and Context Aware Deployment of Containerized Micro-Services[END_REF][START_REF] Lee | Resource Allocation for Vehicular Fog Computing Using Reinforcement Learning Combined With Heuristic Information[END_REF][START_REF] Ross | Stochastic processes[END_REF][START_REF] Zheng | An SMDP-Based Resource Allocation in Vehicular Cloud Computing Systems[END_REF]10,13). This result is logical because if we assign high importance to the destination in the scoring calculation, we choose a candidate whose route is more similar to that of the requesting vehicle. As a result, the candidate accompanies the vehicle for a longer duration, leading to a lower chance of connection loss to the service. The combination (0.6, 0.2, 0.2) yields the best performance. This combination will be used in the comparative study.

C. Comparative study

In order to test the effectiveness of our solution compared to basic techniques (First Fit and Edge-only), we conducted a series of tests. In terms of service relocations, we observe that hosting services on edge servers yield better results. This is justified by the fact that the vehicle maintains its connection with the edge server hosting its service, even when transitioning from one access point to another. However, there are cases where the latency constraint is violated when the number of hops (access points) between the vehicle and the edge server increases, triggering a service migration. In terms of latency (figure 3), we notice that the average latency of services hosted only on edge servers is significantly higher compared to other methods. This is consistent with the fact that vehicle-edge communications are slower than vehicle-tovehicle communications. When comparing scenarios in which the First Fit method experiences more connection disruptions than our solution, it becomes apparent that latency increases as the number of disruptions rises. This can be attributed to the higher probability of task allocation to the edge server, which subsequently impacts latency.

IV. CONCLUSION

The on-board units of vehicles may not always be able to execute resource-intensive services locally without performance degradation. As a result, vehicles need to leverage their environment to carry out tasks. We have proposed a solution for service orchestration in networks of connected autonomous vehicles based on vehicular fog and edge computing. The orchestration algorithm within a cluster utilizes vehicle mo-bility factors such as speed, current position, and destination to enhance the quality of service (QoS) for the requesting vehicle. To validate our solution, we conducted several tests and compared it to traditional methods such as first fit and edge only. The results demonstrated that our solution strikes the best balance between minimizing average service latency and improving QoS in terms of vehicle connectivity with its service.

Fig. 1 .

 1 Fig. 1. Network architecture.

Fig. 2 .

 2 Fig. 2. Source and destinations of vehicles on the Toccoa map.

Fig. 3 .

 3 Fig. 3. Average latency of the service obtained using different methods.

  Estimated time of usage of s by v i .

		TABLE I
		INPUT PARAMETERS.
	Parameter	Meaning
	v i	A vehicle which belongs to the set of vehicles, V.
	max cpu i	Amount of CPU resources available in the OBU of
		vehicle v i .
	max mem i	Amount of memory resources available in the OBU
		of vehicle v i .
	des i	Destination of v i .
	avail cpu i,t	The amount of CPU resources available in v i at time t.
	avail mem i,t	The amount of memory resources available in vehicle
		v i at a specific time t.
	s i,t	Speed of vehicle v i at time t.
	p v i,t	Position of vehicle v i at time t.
	D(a, b)	Distance between a and b.
	C	Cluster whose master is vm.
	s	Service of the set of services S.
	dem cpus	Amount of CPU resources requested by service s.
	dem mems	Amount of memory resources requested by service s.
	trls	Maximum latency tolerated by service s.
	tu s,i

  .1; 2: list vehicle ← collect info(V); 3: candidates ← filter(list vehicle,dem cpu s ,dem mem s ); 4: if size(candidates) = 0 then

	5:	return NULL;
	6: else if size(candidates)=1 then
	7:	best ← candidates[1];
	8: else
	9:	Calculate the score of each candidate in candidates;
	10:	Ranked ← Sort(candidates,desc,score)
	11:

TABLE II SUMMARY

 II OF THE PROFILING PHASE OF THE "imaginary" SERVICE.

	Service	Request	Number of re-	CPU (cores)	Memory (MB)
		latency (s)	questss
	fit	0.019	52	0.62	< 30M B
		0.03	33	0.5	< 20M B
	blur	0.019	52	0.88	< 30M B
		0.03	33	0.7	< 20M B

TABLE III NUMBER

 III OF VEHICLES AND REQUESTS.

		3 requests	4 requests	5 requests	6 requests
	cluster of 5	X
	cluster of 6	X	X
	cluster of 7		X		X
	cluster of 8			X	X
	cluster of 9		X	X

TABLE IV RESULTS

 IV OF THE EMPIRICAL STUDY.

		Combination	Latency (s)	Relocation
	1	0.33|0.33|0.33	0.0949	5.75
	2	0.4|0.3|0.3	0.09	5
	3	0.3|0.4|0.3	0.0993	5.75
	4	0.3|0.3|0.4	0.091	4.75
	5	0.45|0.2|0.35	0.0865	4.75
	6	0.45|0.35|0.2	0.0772	5
	7	0.5|0.25|0.25	0.0825	4.25
	8	0.25|0.5|0.25	0.0856	4.25
	9	0.25|0.25|0.5	0.0838	4.5
	10	0.6|0.2|0.2	0.0745	4.25
	11	0.6|0.3|0.1	0.0854	4.5
	12	0.6|0.1|0.3	0.0856	4.5
	13	0.7|0.15|0.15	0.094	4

explored various combinations of number of vehicles in a cluster and number of service requests, which are succinctly presented in the table III.

  Table V summarizes the obtained results.

	cluster	request	Our Solution	First-Fit	Edge Only
			Latency (s)	Relocation	Latency (s)	Relocation	Latency (s)	Relocation
	5 V	3	0.073	2.2	0.0955	3	0.134	1
	6 V	3	0.094	1	0.096	1	0.1383	0
		4	0.057	0	0.0954	3	0.1307	2
	7 V	4	0.045	1	0.045	1	0.121	2
		6	0.0693	3	0.121	5	0.1333	2.6
	8 V	5	0.0623	2.6	0.0673	3	0.142	0
	9 V	5	0.099	3	0.0983	3	0.1312	2
		4	0.0425	0	0.0512	1.2	0.1277	1

https://containernet.github.io/

https://mininet-wifi.github.io/