Porting the sisal functional language to the EM-X distributed-memory multiprocessor

摘要

Distributed-memory multiprocessors have been regarded as a viable architecture of scalable and economical design for building large scale parallel machines. While these parallel machines can provide computational capabilities, programming such large-scale machines is often very difficult due to many practical issues including parallelization, data distribution, workload distribution, and remote memory latency. This report aims to solve the programmability and performance issues of distributed-memory machines using the Sisal functional language. The programs written in Sisal will be automatically parallelized, scheduled and run on the EM-X distributed-memory multiprocessor with no programmer intervention. Specifically, the proposed approach consists of the following steps. Given a program written in Sisal, the front end Sisal compiler generates a directed acyclic graph(DAG) to expose parallelism in the program. The DAG is partitioned and scheduled based on loop parallelism. The scheduled DAG is then translated to C programs with machine specific parallel constructs. The parallel C programs are finally compiled by the target machine specific compiler to generate an executable. Bitonic sorting and FFT problems are selected for experiments. Experimental results indicate that automatic parallelization of the Sisal programs based on loop parallelism is effective, giving 17 fold speedup for bitonic sorting and 60-fold speedup for FFT on 64 processors.