Scalability of Irregular Problems

Many modern architectures have been designed with increasing core counts and simultaneous multi-threading in an effort to drive performance and efficiency ever higher. Unfortunately many of these systems are used to conduct computation on real world problems which are dynamic and highly irregular in nature. While regular applications can be developed into highly optimized implementations such that they benefit from traditional architecture design, irregular problems often achieve a mere fraction of a systems computational power even when optimized.

In this work we evaluate and analyze the performance of irregular problems on a range of modern architectures commonly used in high performance computing, as well as a novel migrating thread architecture. The sparse problems we focus on in the following studies exhibit both control-flow and memory access irregularities which makes them excellent benchmarks for the greater class of irregular problems. We show the apparent inability for sparse problems to scale well on traditional architectures often experiencing speedup far below 1 even when optimized for hardware design features.

Analyzing the design features of traditional and migrating thread architectures which prohibit or promote scalability of irregular problems, we propose a future architecture for use on irregular applications.