ASAP: Automatic speculative acyclic parallelization for clusters

摘要: While clusters of commodity servers and switches are the most popular form large-scale parallel computers, many programs not easily parallelized for due to high internode communication cost lack globally shared memory. Speculative Decoupled Software Pipelining (Spec-DSWP) is a promising automatic parallelization technique that speculatively partitions loop into multiple threads communicate in pipelined manner. Speculation can complement conservative static analysis, making more robust applicable. allows Spec-DSWP speculate only rarely occurring dependences while respecting other through among threads. Acyclic patterns pipelining make tolerant latency clusters. However, since iteration (a transaction) sub-transactions across according pipeline stages, special runtime system required supports multi-threaded transactions (MTXs). This dissertation proposes Automatic Parallelization (ASAP) enables without any hardware modification. The ASAP various speculation techniques require different validation costs, automatically parallelizes sequential loops using SpecDSWP transformation with optimal application techniques. efficiently MTXs correctly execute transformed on With synergistic combination speculation, acyclic communication, support, this approach achieves or demonstrates path achieve scalable performance speedup up 109× wide range applications