{'fraction_non_alphanumeric': 0.025881057268722467, 'fraction_numerical': 0.015418502202643172, 'mean_word_length': 4.861290322580645, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Unroll-And-Jam Guided by A Linear-Algebra-Based Data-Reuse Model

Because of the existence of a memory bottleneck in modern microprocessors, idle computational cycles in pipelined multiple functional units slow down the program performance. One solution to this problem is applying loop unroll-and-jam to improve the ratio of memory operations to floating-point operations for loops according to the target machine optimal ratio. In doing so, both enough computation and memory accesses will keep the processor utilization high. Previous work on loop unroll-and-jam implemented data reuse analysis on a data dependence graph [7]. This reuse analysis is used to compute the memory requirement in a loop. Unfortunately the results from this method are neither precise nor efficient. The reuse occurring along the outer loops and the reuse not connected by dependence cannot be fully computed and dependences between uses of the same array element take a large amount of computation space. This thesis applies unroll-and-jam using a linear-algebra-based data reuse model that does not require nearly as much dependence graph space. The model was first developed by Wolf-and-Lam [14]. Based on their model, we developed algorithms to compute cache effects for different unroll choices. This information was in turn used to compute the ratio of memory operations to floatingpoint operations in loops. We then picked unroll amounts for outer loops giving the best ratio and performance. The implementation of our algorithms is efficient in both computation time and computation space. Additionally, through our experiments, we achieved average speed-ups of 44% on the IBM RS6000 model 530, 43% on HP PA_RISC model 712/80 and 41% on SGI Indigo2 with a MIPS R4400 after applying loop unroll-and-jam to 24 scientific kernels.