Irregular applications span a broad range of applications with unpredictable
memory access patterns, control structures, and/or network transfers. They
typically use pointer-based data structures such as graphs and trees, often
present fine-grained synchronization and communication, and generally
operate on very large data sets. They have a significant degree of latent
parallelism, which however is difficult to exploit due to their complex
behavior. Current high performance architectures rely on data locality and
regular computation to tolerate access latencies, and often do not cope
well with the requirements of these applications. Furthermore, irregular
applications are difficult to scale on current supercomputing machines,
due to their limits in fine-grained synchronization and small data transfers.