Complexity of the method of block paralleling structured programs
type: Item
instance of: scholarly article
title: Complexity of the method of block paralleling structured programs
zbMATH Open document ID: 0645.68035
author: A. P. Barban
published in: Programming and Computer Software
publication date: 1987-01-01T00:00:00Z
review text: The paper investigates certain well known paralleling algorithms oriented at preparing sequential programs for efficient (parallel) execution on multiprocessor computing systems (MCS) with multiple instruction and data flows such as, for example, the PS-3000 system. After application of the paralleling algorithm the original sequential program is partitioned into independent, as to control and data links, fragments which are grouped into branches (to minimize ``trigger functions'' [\textit{V. E. Kotov}, Kibernetika 1974, No.1, 1-16; No.2, 1-18 (1974; Zbl 0284.68018, Zbl 0288.68008)]) [(*)\ \textit{V. V. Ignatushchenko}, \textit{L. V. Karavanova}, Avtom. Telemekh. 1977, No.6, 176-191 (1977; Zbl 0419.68047)]. Isolation of program fragments suitable for parallel execution on asynchronous MCSs is a complicated and difficult procedure which is not always attainable. To facilitate analysis of program parallelism, the above procedure can be executed in two stages: decomposition of the program into fragments, and subsequent determination of dependencies between the isolated fragments in order to determine the possibility of their parallel execution (the proper paralleling procedure). The decomposition and paralleling stages are not clearly distinguished as, e.g., in (*). At the decomposition stage this leads to the need of constructing a rather complex preliminary general graph. A characteristic feature of the known decomposition methods oriented on nonstructured programs (NSP) is ``bottom-up'' program analysis which begins with individual operators (acting as elementary program components) that are combined into larger structures which, in turn, are combined into still larger structures, etc. Since the simplest programs to decompose are programs linked by the least number of dependencies, structured programs (SP) are of particular interest in this connection. In fact, in SPs control is organized in accordance with the ``one input-one output'' principle with minimum control…
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68N99
zbMATH DE Number: 4053000
zbMATH Keywords: paralleling algorithms
zbMATH Keywords: multiprocessor computing systems
zbMATH Keywords: Isolation of program fragments
zbMATH Keywords: analysis of program parallelism
zbMATH Keywords: fully structured programs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 4053000