## 3 Load Distribution and Progressive Decoding on Cell BE
### Galois Field Operation for SIMD  
The random linear network coding uses the Galois field numbers and accompanies computation overhead due to the time-consuming multiplication operations. In this subsection, we propose an optimization technique of Galois field operation which is previously proposed for GPU [34]. Increasing granularity of the Galois multiplication is hard to expand when using a table look-up method [34]. As the size of Galois field increases, memory requirement grows rapidly. In fact, increasing granularity of Galois field by 1 byte means a table size which is 256 times larger. This requires more cache and memory space. Furthermore, the SPEs do not have caches; they only have 256 KB SRAM, referred to as the local store. Therefore, it cannot contain any large sized tables or it can waste a large amount of local memory to hold the tables. To provide sufficient granularity of the multiplications, [PERSON] _et al_. imported a loop-based approach which is based on the actual computations. Although the loop-based approach needs more computations than the table lookup method, it provides a faster computation time with the help of the SIMD instruction sets [34; 35; 28; 36]. In the previous work [34], [PERSON] _et al_. suggested a word length wide multiplication method referred to as Rijndael's finite field [37; 38]. The method can perform four multiplication operations of the numbers in the Galois field at once. The Galois field numbers are as large as one byte and denoted as GF(\(2^{8}\)). They successfully applied the loop-based multiplication on the multiple scalar processors on a GPU which is depicted in Figure 8. The key optimization in the work is to eliminate branch operations by using polynomial mask operations. This helps to improve performance of a division operation with a irreducible polynomial variable. As a result, the execution time has been reduced. Although they highly optimized the loop-based multiplication method by reducing diversity of control flow on branch instructions, there still exists possible reduction of one more branch instruction. Since the branch instruction causes stalls within a pipeline, any branch instruction in a loop crucially degrades performance of the Galois field multiplication; in fact, the speed of the Galois field multiplication highly affects the performance of network coding. For that purpose, we target to removes the remaining branch within the loop represented as (3) in Figure 8. This branch operation also can be replaced with the bitwise operations when the multiplication is optimized into the SIMD instructions. In addition, the replacement only causes less than five instructions to execute. On the other hand, if the branch instruction in line (2) is replaced to the bitwise operations, it requires a significant number of additional instructions to execute in the loop when the factor is zero. For that reason, the branch instruction in line (2) should remain for overall performance. Figure 8: Optimized loop-based multiplication of GF(\(2^{8}\)) for GPU. Figure 9: The loop-based SIMD multiplication in GF(\(2^{8}\)). The proposed Galois field multiplication based on the SIMD instruction set is shown in Figure 9. The main difference compared to the previous code in Figure 8 can be found in (4) to (6). The branch operation is replaced with the masking operation in _ResultMask_ and the execution condition in the branch is calculated with a _vecor_cmpeq_, which is generally included in the SIMD instruction set. A _vector_cmpeq_ operation checks whether each element in a vector is identical to the responsible element of the other vector. With comparing each element in both vectors, the operation set all bits of an element to 1 when the two elements are identical. Therefore, if the condition is true, the result becomes XOR-ed data (Figure 9(a)). Otherwise, the result is not changed (Figure 9(b)). An SPE calculates 80 KB within 211 \(\mu\)s with the original code.