Algorithmic Study on Systolic Array Structures

摘要

Computation bound problems impose a severe burden on the CPU. In order to speed up computation, specific problems that are identified as the main burden can be done using parallel processing. In this way, the time consuming tasks can be executed on specially tailored hardware. This hardware is designed to implement an algorithm-oriented parallel-processing structure that works more efficiently than the CPU for these specific tasks. This thesis is a study of the mapping of the algorithms onto a kind of structure called systolic array. The development and utilization of a software tool designed to assist on such analysis is presented here. This tool, named Systolic Array Graphics Simulator (SYSGRAS), has the capability to represent any type of systolic array, no matter how complex the cells and structure are. Because of the capability of SYSGRAS, an interactive computer program simulator, the study of systolic arrays is simplified. The complexity of the time-space relationships is analyzed with the help of some color-graphics techniques. The visualization of the data interaction is thus enhanced and the user is alleviated from the burden of keeping track of partial results and can dedicate attention to the processing algorithm.