Some Issues in General-Purpose Shared Memory Multiprocessing: Parallelism Exploitation and Memory Access Combining

摘要

The use of automatic program restructuring and memory access combining for ''general-purpose'' large scale shared memory machine is investigated. The effects of unpredictable control flows and data accesses on the effectiveness of automatic program restructuring are considered through the experiments of several basic nonnumerical programs. Various loop structures found are classified, and their effects are investigated. Also, the importance of algorithm change is considered. In addition, a way of parallelizing loops with conditional branching is studied. Several schemes of memory access combining are investigated. Inherent limit in the idea of memory access combining is revealed, and the effectiveness of those schemes is studied. An approximate formula to provide bounds on the best possible performance of memory access combining is developed, and a practical scheme to achieve performance close to such bounds in modest sized machines is proposed. 78 refs., 28 figs. 9 tabs. (ERA citation 13:013840)