Technical reports

Architecture-neutral parallelism via the Join Calculus

Peter R. Calvert

July 2015, 150 pages

This technical report is based on a dissertation submitted September 2014 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Trinity College.

DOI: 10.48456/tr-871

Abstract

Ever since the UNCOL efforts in the 1960s, compilers have sought to use both source-language-neutral and architecture-neutral intermediate representations. The advent of web applets led to the JVM where such a representation was also used for distribution. This trend has continued and now many mainstream applications are distributed using the JVM or .NET formats. These languages can be efficiently run on a target architecture (e.g. using JIT techniques). However, such intermediate languages have been predominantly sequential, supporting only rudimentary concurrency primitives such as threads. This thesis proposes a parallel intermediate representation with analogous goals. The specific contributions made in this work are based around a join calculus abstract machine (JCAM). These can be broadly categorised into three sections.

The first contribution is the definition of the abstract machine itself. The standard join calculus is modified to prevent implicit sharing of data as this is undesirable in non-shared memory architectures. It is then condensed into three primitive operations that can be targeted by optimisations and analyses. I claim that these three simple operations capture all the common styles of concurrency and parallelism used in current programming languages.

The work goes on to show how the JCAM intermediate representation can be implemented on shared-memory multi-core machines with acceptable overheads. This process illustrates some key program properties that can be exploited to give significant benefits in certain scenarios.

Finally, conventional control-flow analyses are adapted to the join calculus to allow the properties required for optimising compilation to be inferred. Along with the prototype compiler, this illustrates the JCAM’s capabilities as a universal representation for parallelism.

Full text

PDF (1.2 MB)

BibTeX record

@TechReport{UCAM-CL-TR-871,
  author =	 {Calvert, Peter R.},
  title = 	 {{Architecture-neutral parallelism via the Join Calculus}},
  year = 	 2015,
  month = 	 jul,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-871.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-871},
  number = 	 {UCAM-CL-TR-871}
}