Irregular computations on fine-grain multithreaded architecture

Engineering and other elds require high performance parallel computing. When the problem at hand presents a structure regular enough to be dealt with automatically, it is sufficient to leave the parallelization and optimization to compiling tools. However, most of the important applications possess structures that lack regularity, and consequently, performance enhancement by exploitation of high performance computing requires new design techniques and tools. In these cases, issues such as data layout, data dependencies,locality, workload, load balance and minimization of communication which impact performance need to be carefully assessed for the client parallel implementation. Memory and synchronization latencies are serious bottlenecks in parallel computing. In the SPMD (Single Instruction Multiple Data Model), von Neumann style of programming is used and hence irregular computations are hard to program. On the other hand, in negrained multithreading models, the program is divided into many small threads and the threads interleaved to achieve maximum parallelism.