Reconstructing sequential behavior from parallel behavior projections
type: Item
instance of: scholarly article
title: Reconstructing sequential behavior from parallel behavior projections
zbMATH Open document ID: 0577.68037
DOI: 10.1016/0020-0190(83)90052-2
author: Mark Weiser
published in: Information Processing Letters
publication date: 1983-01-01T00:00:00Z
review text: This paper investigates the problem of merging together the output of so- called data-flow slices. A sequential program may be transformed into slices - separately executable programs, results of which, taken together, are the same as results of the original sequential program. In an earlier paper the author suggested program slicing as another, different to vectorization, method of distribution of sequential computation onto parallel processors. A slice is a program created from the original program by removing certain statements. The removed statements are found in other slices of the same program. In the present paper the author discusses the question of slicing, i.e. sequencing the output of slices executed in parallel, to appear as produced by the original program. All the reasoning is given in terms of so-called Program Regular Expressions (PRE), representing all possible paths through a program. In their terms the author formulates restrictions on slices and, consequently, on the original program as well as on the slicing algorithm, to ensure reconstruction of the program result from its slice outputs. Finally, the author discusses briefly possible costs involved in slicing (more programs to compile, communication between slices, reconstruction of output) and speed-up gained. The latter is illustrated by examples of 3 different compilers which have been sliced and, then, their speed - measured against their sequential versions.
reviewed by: J.Olszewski
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 3924122
zbMATH Keywords: parallel processing
zbMATH Keywords: regular expressions
zbMATH Keywords: parallelization
zbMATH Keywords: data-flow slices
zbMATH Keywords: program slicing
zbMATH Keywords: Program Regular Expressions
zbMATH Keywords: slicing algorithm
MaRDI profile type: Publication
full work available at URL: 0020-0190(83)90052-2
OpenAlex ID: W1979611815
cites work: The ILLIAC IV Computer
cites work: Q4162449
cites work: A Unified Approach to Path Problems
cites work: Program Slicing
Recommended article: Sequential inference with reliable observations: Learning to construct force-dynamic models
Recommended article: Q4423620
Recommended article: Sequential learning using temporal context
Recommended article: Effective decomposability of sequential behaviours
Recommended article: Sequencing via explanation-based learning
Recommended article: Learning sequences of compatible actions among agents
description: scientific article; zbMATH DE number 3924122