Skip navigation

Exploitation of symbolic information in interprocedural dependence analysis

Exploitation of symbolic information in interprocedural dependence analysis

Johnson, S.P., Cross, M. and Everett, M.G. (1996) Exploitation of symbolic information in interprocedural dependence analysis. Parallel Computing, 22 (2). pp. 197-226. ISSN 0167-8191 (doi:10.1016/0167-8191(96)00002-6)

Full text not available from this repository.

Abstract

The requirement for a very accurate dependence analysis to underpin software tools to aid the generation of efficient parallel implementations of scalar code is argued. The current status of dependence analysis is shown to be inadequate for the generation of efficient parallel code, causing too many conservative assumptions to be made. This paper summarises the limitations of conventional dependence analysis techniques, and then describes a series of extensions which enable the production of a much more accurate dependence graph. The extensions include analysis of symbolic variables, the development of a symbolic inequality disproof algorithm and its exploitation in a symbolic Banerjee inequality test; the use of inference engine proofs; the exploitation of exact dependence and dependence pre-domination attributes; interprocedural array analysis; conditional variable definition tracing; integer array tracing and division calculations. Analysis case studies on typical numerical code is shown to reduce the total dependencies estimated from conventional analysis by up to 50%. The techniques described in this paper have been embedded within a suite of tools, CAPTools, which combines analysis with user knowledge to produce efficient parallel implementations of numerical mesh based codes.

Item Type: Article
Uncontrolled Keywords: parallelisation tools, interprocedural dependence analysis
Subjects: Q Science > QA Mathematics
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis
School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis > Computational Science & Engineering Group
Related URLs:
Last Modified: 14 Oct 2016 08:58
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/14

Actions (login required)

View Item View Item