No label defined (Q4029595)

[For the entire collection see Zbl 0745.00057.] A generalization of serial instructions to parallel instructions of a given width (saying how many processors are needed) is presented. The concept of control graph with parallel instructions is introduced. Four elementary parallelizing construction are studied and used to transform a serial control graph into a control graph with parallel instructions when preserving serial (synchronous) mode of execution. Further several types (weak, strong, full) of parallelization of a serial control graph are defined and studied. The main source of parallelization is found in the fact that we are often using functions (and predicates) with arity \(>1\), i.e. with two or more arguments. Two measures of execution times of control graphs (without loops) with serial and parallel instructions are introduced and clarified on some examples.