## 5 Methodology
### Initial Construction of Solutions
For every examination indexed \(i\) in the input, only the conflicts with examinations indexed \(j\geq i+1\) need to be considered. At this point, two independent processes are detected in order to be parallelized: the calculation of the cost of a whole chromosome and the calculation of the cost of a single examination. Both approaches were implemented. From now on, the first approach will be referred to as the chromosome-threaded approach, while the second will be referred to as the examination-threaded approach. In the chromosome-threaded approach, each thread calculates the sum of a whole chromosome; thus \(pop\) threads are executed, where \(pop\) is the population size, and no synchronization is needed. Every thread computes the cost of the chromosome in a local variable, and at the end, it stores it in the global memory. The pseudocode for the chromosome-threaded approach is given in Algorithm 2. ```
\(chromosome\gets blockDim.x*blockIdx.x+threadIdx.x\); \(small\_sum\gets 0\); \(\_shared\_\)\(int\_w\_shared[]\); if\(threadIdx.x<n\_slots\)then \(w\_shared[threadIdx.x]\gets w\_d[threadIdx.x]\); end \(\_syncthreads()\); for\(i\gets 1\)to\(n\_courses\)do for\(k\gets i+1\)to\(n\_courses\)do \(distance\gets abs(slot[i]-slot[k])\); \(small\_sum+=w\_shared[distance]*students\_in\_conflict[i][k]\);  end for end \(cost\_d[chromosome]\gets small\_sum\);
```
**Algorithm 2**Evaluation, chromosome-threaded approach: each thread evaluates one chromosome of the population. In the examination-threaded approach, each thread calculates the cost of one examination only and places the result in an array in the shared memory. After the calculation of the cost of each examination, the total cost of the chromosome should be computed. The total cost of each chromosome can be computed with a reduction operation, keeping as many threads as possible active [59]. After examining the characteristics of the datasets that are used in this paper, a problem occurs with the _pur-s-93_ dataset. The number of examinations in this dataset is 2419, which means that 2419 threads are needed for the calculation of a single chromosome. However, due to the limitations of the CUDA programming model,each block can have up to 1024 threads, thus needing three blocks of threads if each block is configured to contain the most available threads. However, having a block with 1024 threads means that in that multiprocessor, only one block can be executed at the same time, since a multiprocessor can have up to 1536 threads, and therefore, the multiprocessor is not fully utilized. Taking these into consideration, our approach for the number of threads per block and the number of blocks is:

\[tpb.x=\left\{ \begin{array}{ll}E&E<512\\ 512&\text{otherwise}\end{array} \right.\]

\[blocks.x=\left\{ \begin{array}{ll}1&E<512\\ 1+\lfloor E/512\rfloor&\text{otherwise}\end{array} \right.\]

\[blocks.y=pop\]
```
\(chromosome\gets blockIdx.y\); \(course\_id\gets threadIdx.x+blockIdx.x*blockDim.x\); \(shared\_lcost[]\); \(shared\_w\_shared[]\); \(lcost[threadIdx.x]\gets 0\); if\(threadIdx.x<n\_slots\)then \(w\_shared[threadIdx.x]\gets w\_d[threadIdx.x]\);  end if \(\_syncthreads()\); if\(course\_id<n\_courses\)then for\(j\gets course\_id+1\)to\(n\_courses\)do \(distance\gets abs(slot[course\_id]-slot[j])\); \(lcost[threadIdx.x]+=w\_shared[distance]*students\_in\_ conflict[course\_id][j]\);  end if  end for \(\_syncthreads()\); \(lcost[0]\gets total\ sum\ of\ local\ array\ with\ reduce\ sum\ operation\); if\(threadIdx.x=0\)and\(n\_courses<512\)then \(cost\_d[chromosome]\gets lcost[0]\);  end if if\(threadIdx.x=0\)and\(n\_courses>=512\)then \(atomicAdd(\&cost\_d[chromosome],lcost[0])\);  end if
```
**Algorithm 3**Evaluation, examination-threaded approach: each thread evaluates one gene of the population. In the above equations, \(tpb.x\) is the number of threads per block in the \(x\) direction, \(blocks.x\) and \(blocks.y\) are the number of blocks in the \(x\) and \(y\) direction, \(E\) is the number of examinations and \(pop\)is the population size.