## 3 Our Parallel Strategies
### Parallel Initialization on GPU
#### 3.2.2. Bay Divisions Generation  
To generate bay divisions, the conventional method and the improved method are both proposed in this subsection. The conventional method (INI_BD1) is firstly to generate a random integer _rand_ for each facility on bay divisions, and then use _rand_1%2 to get an integer of value equal to 0 or 1. Consequently, (\(p-1\)) random integers are required for \(p\) facilities. In INI_BD1, \(p\) facilities require (\(p-1\)) modulo operations for the representation of bay divisions. If there are \(n\) individuals, we need  
Figure 6. Performance ratio between INI_FS2 and INI_FS1 for facility sequence generation.  
to perform the modulo operation (\(n*(p-1)\)) times in total, thus resulting in a high time complexity even in parallel computing. In order to reduce such calculations in parallel, we propose the other method (INI_BD2) to improve the performance of generating bay divisions. The new method uses bitwise operators instead of modulo operators. Assume the value of an integer generated randomly is \(x\) (\(x\geq 1\)), we calculate \(x\)\(AND\) 1 to generate a value of either 0 or 1 for the first facility in the bay divisions. Then a one-bit right arithmetic shift is adopted to change the value of \(x\), and the new \(x\) is used in next iteration. Repeat the above procedure for \((p-1)\) times, the whole bay divisions are generated. INI_BD2 algorithm is of O(1) time complexity, which is much smaller than O(\(p\)) time complexity required by INI_BD1. Moreover, INI_BD2 uses arithmetic shift operations to replace modulo operators in INI_BD1.  
\[x\ AND\ 1=\sum_{i=0}^{\lfloor\log_{2}(x)\rfloor}2^{i}\Big{(}\Big{\lfloor}\frac{ x}{2^{i}}\Big{\rfloor}\bmod 2\Big{)}\bigg{(}\Big{\lfloor}\frac{1}{2^{i}}\Big{\rfloor} \bmod 2\bigg{)} \tag{5}\]  
\[x_{new}\ =x*2^{b} \tag{6}\]  
Kernel Algorithm 2 is the pseudocode of the improved method INI_BD2 for facility bay divisions. Each thread is responsible for producing one bay divisions. Firstly, we generate a random integer, and then bitwise operators, instead of modulo operators, are used to obtain a value of either 0 or 1 for every facility except the last one (Lines 2-5).
```
Data:  decimal: Variable for a random integer value  baydarr: Boolean array containing flexible bay divisions for each individual Operator:  '>': Bitwise operation SHR (shift right)  '&': Bitwise operation AND Input:  baydarr Result:  All of facility divisions generated randomly Kernel function:  _global_ void genB (Array baydarr) {  1: decimal <- Random()  2: foreach i \(\in\) {0,...,length - 1} do  3: baydarr[blockID][threadID][i] <- (decimal & 1)  4: decimal <- (decimal >> 1)  5: end  }
```
**Algorithm 2**Parallel Bay Divisions Generation  
Figure 7 is the performance ratio between INI_BD2 and INI_BD1 for generation of bay divisions. The INI_BD2 uses bitwise operators instead of a lot of mod operators of INI_BD1, yet GPU is not good at such mod calculations due to hardware limitations. So the performance ratio of INI_BD2 is much better than INI_BD1, and with the increase in the number of facilities, the more obvious the performance improvement.