Novel gather and scatter hardware support for microprocessors

Accessing the memory efficiently to keep up with the data processing rate is a well known problem in modern architectures. Regular access patterns, such as constant strides, have been exploited in designing efficient memory systems. The objective of this thesis is to explore the possibilities of using a hardware support to improve memory performance by harnessing the knowledge of access patterns. A novel hardware support called the distTree is proposed to speed up memory accesses whose patterns of access are known at compile time. The distTree facilitates the memory accesses for applications even when the access patterns are irregular.The distTree is implemented and adoptable areas are explored. Two adoptable applications are highlighted in this thesis: Past Fourier Transform (FFT) and Sparse Matrix Vector Multiplication (SpMxV). The performance of the distTree is compared with a state-of-the-art implementation in each application. The experiments have shown a 100% speedup when computing an FIT and a 200% speedup when performing a SpMxV. The speedups are the results of efficient memory access and reduced program overheads. thus allowing the processor to spend the majority of the time on necessary floating point arithmetics. For example, in FIT, 85% of the CPU cycles with the distTree, comparing with 30% without, is devoted to numeric operation executions. In the case of the SpMxV, not only the data structure is simplified but. it also requires 30% less memory space. This thesis shows that identifying memory access patterns in applications and developing hardware support mechanisms based on them improves memory performance. The augmented architecture enables processors to reach their full potentials in data processing capabilities