Browse Prior Art Database

Control Dependence Algorithm for Parallel Programming

IP.com Disclosure Number: IPCOM000036632D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29

Publishing Venue

IBM

Related People

Authors:
Cytron, R Ferrante, J [+details]

Abstract

A technique is described for efficiently constructing control dependences. It is an improvement over previous concepts which required quadratic space for intermediate computations and multiple passes over the post-dominator tree. The improved algorithm propagates dependences in a single pass through the post-dominator tree. The technique is provably linear for structured programs.