We present an approach for automatic translation of sequential, imperative code into a parallel MapReduce framework. Automating such a translation is challenging: imperative updates must be translated into a functional MapReduce form in a manner that both preserves semantics and enables parallelism. Our approach works by first translating the input code into a functional representation, with loops succinctly represented by fold operations. Then, guided by rewrite rules, our system searches a space of equivalent programs for an effective MapReduce implementation. The rules include a novel technique for handling irregular loop-carried dependencies using group-by operations to enable greater parallelism.
We have implemented our technique in a tool called Mold. It translates sequential Java code into code targeting the Apache Spark runtime. We evaluated Mold on several real-world kernels and found that in most cases Mold generated the desired MapReduce program, even for codes with complex indirect updates.
Fri 24 Oct
|13:30 - 13:52|
ASPIRE: Exploiting Asynchronous Parallelism in Iterative Algorithms using a Relaxed Consistency based DSM
Keval VoraUniversity of California, Riverside, Sai Charan KoduruUniversity of California, Riverside, Rajiv GuptaUC RiversideLink to publication Media Attached File Attached
|13:52 - 14:15|
Brandon HoltUniversity of Washington, Preston BriggsUniversity of Washington, Luis CezeUniversity of Washington, Mark OskinUniversity of WashingtonLink to publication Media Attached File Attached
|14:15 - 14:37|
Tian XiaoTsinghua University / Microsoft Research, Zhenyu GuoMicrosoft Research, Hucheng ZhouMicrosoft Research, Jiaxing ZhangMicrosoft Research, Xu ZhaoUniversity of Toronto, Chencheng YeHuazhong University of Science and Technology, Xi WangMIT CSAIL, Wei LinMicrosoft Bing, Wenguang ChenTsinghua University, Lidong ZhouMicrosoft ResearchLink to publication Media Attached
|14:37 - 15:00|
Cosmin RadoiUniversity of Illinois, Stephen J FinkIBM, Rodric RabbahIBM Research, Manu SridharanSamsung Research AmericaLink to publication Media Attached