Pipelining: A technique for implementing data restructurers

Abstract

In the past several years much attention has been given to the problem of data translation. The focus has been mainly on methodologies and specification languages for accomplishing this task. Recently, several prototype systems have emerged, and now the issues of implementation and performance must be addressed. In general, a data restructuring specification may contain multiple source and target files. This specification can be viewed as a “process graph” which is a network of restructuring operations subject to precedence constraints. One technique used to achieve good performance is that of pipelining data in the process graph. In this paper we address a number of issues pertinent to a pipelining architecture. Specifically, we give algorithms for resolving deadlock situations which can arise, and partitioning the process graph to achieve an optimal schedule for executing the restructuring steps. In addition, we discuss how pipelining has influenced the design of the restructuring operations and the file structures used in an actual system. © 1979, ACM. All rights reserved.