ELIMINATING BARRIER SYNCHRONIZATION FOR COMPILER-PARALLELIZED CODES ON SOFTWARE DSMS

Software distributed-shared-memory (DSM) systems provide an appealing target for parallelizing compilers due to their flexibility. Previous studies demonstrate such systems can provide performance comparable to message-passing compilers for dense-matrix kernels. However, synchron ization and load imbalance are significant sources of overhead. In thi s paper, we investigate the impact of compilation techniques for elimi nating barrier synchronization overhead in software DSMs. Our compile- time barrier elimination algorithm extends previous techniques in thre e ways: (1) we perform inexpensive communication analysis through loca l subscript analysis when using chunk iteration partitioning for paral lel loops; (2) we exploit delayed updates in lazy-release-consistency DSMs to eliminate barriers guarding only anti-dependences; (3) when po ssible we replace barriers with customized nearest-neighbor synchroniz ation. Experiments on an IBM SP-2 indicate these techniques can improv e parallel performance by 20% on average and by up to 60% for some app lications.