Speeding Up the Evaluation of a Mathematical Model for VANETs Using OpenMP - Simulation and Modeling Methodologies, Technologies and Application - page 26

different technology penetration ratios. This assumption implies that we have to calcu-
late the number of collisions once for each of the possible combinations in the chain of
vehicles equipped with and without CCA technology, that is,
N
m

N !
( N − m )! m !

= ,

(7)

where N is the total number of vehicles in the chain and m is the number of vehicles
equipped with the CCA technology. It is worth to notice that the number of combina-
tions for m vehicles set with CCA technology and N − m without it is the same that
for N − m vehicles with CCA and m without it. Therefore, in order to analyze the
computation time, we solve the model varying the CCA penetration rate between 0%
and 50% , since the rest of cases are computationally (but not numerically) identical. As
we can see in Table 1, the number of combinations grows quickly by an increase on the
CCA penetration rate as well as by an increase on the number of vehicles.

Ta b l e 1 . Number of combinations of N = { 10 , 20 , 30 } vehicles with and without CCA

technology

CCA% 10 veh. 20 veh. 30 veh.

0% 1 1 1

10% 10 190 4060

20% 45 4845 593775

120 38760 14307150

30%

40% 210 125970 86493225

50% 252 184756 155117520

In addition to that, we also aim at evaluating the impact on the number of accidents
of the inter-vehicle distance d , varying this parameter in a wide range.

5 Implementation

In this section we firstly introduce the algorithm for the model implementation (Algo-
rithm 1) and then, we explain the method we have used to parallelize it.
Examining the algorithm we can make the following observations:
1. The iterations of the for loop that covers the number of Combinations resulting from
the CCA technology penetration rate are independent for each other, so they can be
executed in parallel by different threads.
2. The same occurs with the for loop that covers the RangeOfDistances (for the inter-
vehicle spacing) to be evaluated.
3. Since the collision probabilities of the vehicles in the platoon is computed recur-
sively, each iteration of the for loop that considers each vehicle in the chain needs
the results of the preceding iteration, so this loop should be executed sequentially.
4. To obtain the first row of matrix P N we have to multiply N times a vector of di-
mension ( N +1)( N +2)
2

by a matrix of dimension ( N +1)( N +2)
2

× ( N +1)( N +2)
2

.The
vector-matrix multiplication can be also parallelized so that each thread executes the
multiplication of the vector by part of the matrix columns. However, the N multipli-
cations should be done one after the other, that is, sequentially.