March 31, 1993

1 of 33

Refining and Defining the

Program Dependence Web

Philip L. Campbell
Ksheerabdhi Krishna
Robert A. Ballance

Department of Computer Science
The University of New Mexico
Albuquerque, NM 87131
Technical Report No. 93-6

February, 1993
Revised, March 1993

This work was supported in part by NSF under grant CCR-9110954 and by Sandia National Laboratories supported by the US Department of Energy under contract DE-AC04-76DP00789.

Abstract

The Program Dependence Web is a program intermediate representation which can be interpreted under control-driven, data-driven or demand-driven disciplines. An operational definition is given for the Program Dependence Web. This includes definitions for the nodes and arcs and a description of how webs are interpreted. The general structure for conditionals and loops is shown, accompanied by examples. The definition is a refinement of the original one in that a new node, the ?b node,? is introduced and two nodes, the m node and the hT node, are eliminated.

1.0 Introduction

To obtain peak performance it must be easy to match computations with machines. Today?s world of MIMD supercomputing makes this difficult because it is divided into separate camps. There is the control-driven von Neumann massively parallel camp. There is the data-driven dataflow machine camp. And there is the demand-driven graph reduction machine camp. Each camp confines users to one language style: imperative, dataflow or functional. Moving computations between camps is difficult. We believe this is a barrier to performance and to productivity. The Program Dependence Web (PDW) [1] helps to eliminate this barrier.

The PDW is a program intermediate representation which can be interpreted under control-driven, data-driven or demand-driven disciplines. The PDW presents the opportunity of interpreting different parts of the same program in different ways, depending on the part being executed, the input being used, or both. The PDW thus subsumes various hybrids as well. The PDW is not confined to a single language style, just as it is not confined to machines of a particular execution style, because it is an intermediate represen-