Topham, Nigel

Franke, Bjorn

Murray, Alastair Colin

Engineering and Physical Sciences Research Council (EPSRC)

2013-10-24T12:23:16Z

2013-10-24T12:23:16Z

2012-11-29

The automatic generation of instruction set extensions to provide application-specific acceleration for embedded processors has been a productive area of research in recent years. There have been incremental improvements in the quality of the algorithms that discover and select which instructions to add to a processor. The use of automatic algorithms, however, result in instructions which are radically different from those found in conventional, human-designed, RISC or CISC ISAs. This has resulted in a gap between the hardware’s capabilities and the compiler’s ability to exploit them. This thesis proposes and investigates the use of a high-level compiler pass that uses graph-subgraph isomorphism checking to exploit these complex instructions. Operating in a separate pass permits techniques to be applied that are uniquely suited for mapping complex instructions, but unsuitable for conventional instruction selection. The existing, mature, compiler back-end can then handle the remainder of the compilation. With this method, the high-level pass was able to use 1965 different automatically produced instructions to obtain an initial average speed-up of 1.11x over 179 benchmarks evaluated on a hardware-verified cycle-accurate simulator. This result was improved following an investigation of how the produced instructions were being used by the compiler. It was established that the models the automatic tools were using to develop instructions did not take account of how well the compiler could realistically use them. Adding additional parameters to the search heuristic to account for compiler issues increased the speed-up from 1.11x to 1.24x. An alternative approach using a re-designed hardware interface was also investigated and this achieved a speed-up of 1.26x while reducing hardware and compiler complexity. A complementary, high-level, method of exploiting dual memory banks was created to increase memory bandwidth to accommodate the increased data-processing bandwidth provided by extension instructions. Finally, the compiler was considered for use in a non-conventional role where rather than generating code it is used to apply source-level transformations prior to the generation of extension instructions and thus affect the shape of the instructions that are generated.

http://hdl.handle.net/1842/8028

en

The University of Edinburgh

Richard V. Bennett, Alastair C. Murray, Björn Franke, and Nigel Topham. Combining source-to-source transformations and processor instruction set extensions for the automated design-space exploration of embedded systems. In Proceedings of the ACM SIGPLAN/ SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES ’07), pages 83–92, June 2007.

Alastair Murray and Björn Franke. Fast source-level data assignment to dual memory banks. In Proceedings of the 11th International Workshop on Software and Compilers for Embedded Systems (SCOPES ’08), pages 43–52, March 2008.

Alastair C. Murray, Richard V. Bennett, Björn Franke, and Nigel Topham. Code transformation and instruction set extension. ACM Transactions on Embedded Computing Systems (ACM TECS), 8(4):1–31, 2009.

Oscar Almer, Richard Bennett, Igor Böhm, Alastair Murray, Xinhao Qu, Marcela Zuluaga, Björn Franke, and Nigel Topham. An end-to-end design flow for automated instruction set extension and complex instruction selection based on GCC. In Proceedings of the First International Workshop on GCC Research Opportunities (GROW ’09), pages 49–60, January 2009.

Alastair Murray and Björn Franke. Using genetic programming for source-level data assignment to dual memory banks. In Proceedings of the 3rdWorkshop on Statistical and Machine Learning Approaches to Architectures and Compilation (SMART ’09), pages 75–89, January 2009.

Alastair Murray and Björn Franke. Using genetic programming for source-level data assignment to dual memory banks. In Proceedings of the 3rdWorkshop on Statistical and Machine Learning Approaches to Architectures and Compilation (SMART ’09), pages 75–89, January 2009.

Alastair Murray and Björn Franke. Adaptive source-level data assignment to dual memory banks. ACM Transactions on Embedded Computing Systems (ACM TECS), 11S(1), June 2012a.

compilers

automated instruction-set extension

design space exploration

Customising compilers for customisable processors

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy