CaltechTHESIS
  A Caltech Library Service

GRAph Parallel Actor Language: A Programming Language for Parallel Graph Algorithms

Citation

DeLorimier, Michael John (2013) GRAph Parallel Actor Language: A Programming Language for Parallel Graph Algorithms. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/M3TW-7Y53. https://resolver.caltech.edu/CaltechTHESIS:08192012-145253489

Abstract

We introduce a domain-specific language, GRAph Parallel Actor Language, that enables parallel graph algorithms to be written in a natural, high-level form. GRAPAL is based on our GraphStep compute model, which enables a wide range of parallel graph algorithms that are high-level, deterministic, free from race conditions, and free from deadlock. Programs written in GRAPAL are easy for a compiler and runtime to map to efficient parallel field programmable gate array (FPGA) implementations. We show that the GRAPAL compiler can verify that the structure of operations conforms to the GraphStep model. We allocate many small processing elements in each FPGA that take advantage of the high on-chip memory bandwidth (5x the sequential processor) and process one graph edge per clock cycle per processing element. We show how to automatically choose parameters for the logic architecture so the high-level GRAPAL programming model is independent of the target FPGA architecture. We compare our GRAPAL applications mapped to a platform with four 65 nm Virtex-5 SX95T FPGAs to sequential programs run on a single 65 nm Xeon 5160. Our implementation achieves a total mean speedup of 8x with a maximum speedup of 28x. The speedup per chip is 2x with a maximum of 7x. The ratio of energy used by our GRAPAL implementation over the sequential implementation has a mean of 1/10 with a minimum of 1/80.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Compute Model; Parallel Programming; Programming Language; Graph Algorithm; Domain-Specific Language; GraphStep; Field-programmable gate array; Multiprocessor
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • DeHon, Andre (advisor)
  • Desbrun, Mathieu (co-advisor)
Thesis Committee:
  • DeHon, Andre (chair)
  • Martin, Alain J.
  • Chandy, K. Mani
  • Meiron, Daniel I.
  • Shrobe, Howard
Defense Date:12 June 2012
Non-Caltech Author Email:michael (AT) delorimier.org
Record Number:CaltechTHESIS:08192012-145253489
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:08192012-145253489
DOI:10.7907/M3TW-7Y53
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7188
Collection:CaltechTHESIS
Deposited By: Michael DeLorimier
Deposited On:14 Nov 2012 17:31
Last Modified:03 Oct 2019 23:56

Thesis Files

[img]
Preview
PDF (Complete Thesis) - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page